Alpaca Racing, aka Using the First Five Chapters!

What’s up, Python people,

I don’t usually get multiple requests to cover the same thing, but I’ve gotten a few requests to cover a problem called Alpaca Racing. (Why? Alpacas learning Python? Hi, buddies. Please don’t spit on me.)

I’m going to assume here that you’ve studied the first five chapters of the book. If you have, you know all about variables, built-in Python functions, if statements, for loops, while loops, and lists. We’re going to use all of that here!

Sometimes problem descriptions can be scarier than solving the problems themselves! This is no fault of the problem writer: there’s a lot of information to convey in a small amount of text. A bunch of variables, a bunch of restrictions… and they generally don’t have pages and pages like I did in Learn to Code by Solving Problems to slow down and go through everything.

So, the first thing I’d like to say here is: don’t let a problem description scare you away. Sometimes the spit is worse than the bite.

Please keep that in mind as you read the problem description. Go for it… read the original problem description and then keep reading here for more information.

What is the problem asking?

It’s an alpaca race! There are a bunch of other alpacas that are racing your Alpaca, and you want your alpaca to win the race. By winning the race, the problem means that your alpaca finishes the race in the fastest time. You cannot have a tie… you have to win outright.

Each alpaca runs at a certain speed. Your alpaca will win the race if it has a speed faster than every other alpaca, and it will lose otherwise.

Now, some of the other alpacas might be faster than yours. So your alpaca will lose the race in those cases… but wait, not necessarily! Because we have a cheating machine that we can use. If we use the cheating machine on an alpaca, it reduces that alpacas speed by what I’ll call a cheating factor.

Say that some alpaca currently has speed s. Here’s what the cheating machine does to that alpaca’s speed:

s = int(s * (100-cheat_factor)/100)

The reason for the int there is because the original formula used the floor operator, which rounds numbers down to the nearest integer. For positive numbers, we can accomplish this using Python’s int function.

The greater the cheating factor, the more dramatically we cheat; that is, the more dramatically we reduce an alpaca’s speed. Let’s play around with this.

>>> cheat_factor = 30
>>> s = 100  # Some alpaca's original speed
>>> s = int(s * (100-cheat_factor)/100)
>>> s  # Now their speed, after we cheated
70
>>> cheat_factor = 55  # More cheating than before
>>> s = 100
>>> s = int(s * (100-cheat_factor)/100)
>>> s
45

So that’s how the machine works: it comes preset to a cheating factor, and we use the machine to cheat and slow down other alpacas’ speeds. The cheating factor determines the percentage of speed that’s taken away from an alpaca.

We can’t keep using the cheating machine forever, though. If we could, the problem wouldn’t be very interesting, because we could win the race by just cheating every other alpaca until their speed is less than your alpaca’s. That’s why there’s a maximum number of times we can use the cheating machine.

Given all this, the question is: can your alpaca win the race?

Simplifying the Problem a Little

The problem talks about racing around a track of length $D$. But wait: why do we care what the length of the track is? If your alpaca is slower than some other alpaca, then your alpaca will lose. If it’s faster than all other alpacas, then your alpaca will win. The track could be two feet or two miles, it wouldn’t matter. The length of the track therefore doesn’t matter. Sure, without the length of the track we don’t know how long it takes each alpaca to finish the race. But for this problem, we don’t care about that. All we want to know is whether your alpaca can win. For that, speed matters, nothing else.

All Those Variables

When a problem talks about one or two variables, calling them $M$ or $N$ or whatever can be OK. It can still be confusing, but not as confusing as single-letter variable names when there are three or four or more variables. Again, this is just the nature of problem descriptions: they are written to be concise.

The problem’s Input Specification tells us that the first line of input contains four variables. As I mentioned above, we’re going to ignore the length of the track, so that leaves three. I’m going to give them nicer names in our Python code than $N$, $K$, and $X$. Here’s how we can read that first line of input into meaningful Python variable names:

lst = input().split()
num_competitors = int(lst[0])
num_cheats = int(lst[2])
cheat_factor = int(lst[3])

Reading the Rest of the Input

To read the rest of the input, we have to read the other alpaca’s speeds and then your alpaca’s speed. We’re going to use a list (Chapter 5) to hold the other alpaca’s speeds. And we’ll use a for loop (Chapter 3) to read each speed from the input. Here we go:

competitor_speeds = []

for i in range(num_competitors):
    competitor_speeds.append(int(input()))

my_speed = int(input())

Can Your Alpaca Win?

The heart of the problem is to determine whether your alpaca can win or not. The strategy is to look at each other alpaca’s speed and cheat their speed down until it’s lower than your alpaca’s. Maybe some alpaca is already slower than your alpaca. In that case, we don’t waste any of our cheating on that one. But maybe some alpaca is the same speed or faster than your alpaca. In that case, we have to cheat them down, otherwise your alpaca won’t win the race. As we go through the alpacas, we have to keep track of the number of times that we cheat their speed down.

This is actually a pretty tricky while loop (Chapter 4) coming up. We want to loop as long as we have more alpacas to process… that’s true. Your first instinct may be to try something like this:

while i < num_competitors:

That’s a good start, and actually you can solve the problem correctly this way… but not fast enough to pass all test cases. The reason is that this loop would continue processing alpacas even when the number of times we can cheat goes negative. We may already have cheated way more than allowed, but this while loop would continue frivolously processing alpacas all day long, even though the answer to the problem instance is already guaranteed to be NO.

Right… so we should only continue processing alpacas as long as the number of remaining allowed cheats isn’t negative. Like this:

while i < num_competitors and num_cheats >= 0:

What do we do inside that while loop? Well, we have to keep cheating the current alpaca’s speed down until they’re slow enough. How do we know when to stop? By using another, nested, while loop! Here goes:

    while competitor_speeds[i] >= my_speed and num_cheats >= 0:
        competitor_speeds[i] = int(competitor_speeds[i] * (100-cheat_factor)/100)
        num_cheats = num_cheats - 1  # We used one cheat

Again I’ve included num_cheats >= 0 in the while condition. If there’s some super fast alpaca that wastes all of our cheats, there’s no point going way negative with our num_cheats because of that alpaca… we’re already guaranteed to lose the race.

Once these nested while loops are done, we have to check the value of num_cheats. If num_cheats is greater than or equal to 0, it means that your alpaca could win the race without you cheating beyond your allowed number of cheats. Otherwise, you cheated too much! So, we need an if statement following the loops:

if num_cheats >= 0:
    print('YES')
else:
    print('NO')

Full Solution

Here’s the full solution that we developed throughout this post.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
lst = input().split()
num_competitors = int(lst[0])
num_cheats = int(lst[2])
cheat_factor = int(lst[3])

competitor_speeds = []

for i in range(num_competitors):
    competitor_speeds.append(int(input()))

my_speed = int(input())

i = 0

while i < num_competitors and num_cheats >= 0:
    while competitor_speeds[i] >= my_speed and num_cheats >= 0:
        competitor_speeds[i] = int(competitor_speeds[i] * (100-cheat_factor)/100)
        num_cheats = num_cheats - 1
    i = i + 1

if num_cheats >= 0:
    print('YES')
else:
    print('NO')

I think those two nested while loops (15-16) are the trickiest part of the solution. If you find them confusing, try re-coding this part using your own style.

More Practice

What did you think of this problem? Want to see more like this?

Don’t forget to check the growing list of exercises for more practice with the material from the book.

Happy Pythoning!