RRACE - Editorial

Editorial - Rabbit Race

PROBLEM LINK:

Problem Link

Contest Link

Author: Naman Shah

Tester: Raj Tiwari

Editorialist: Naman Shah

DIFFICULTY:

EASY

PROBLEM:

The problem consists of 2 rabbits(A and B), taking leaps of specific length in a straight path, labelled with tiles of 0’s and 1’s.

Considering n as the number of tiles, and a 0 based index. The race will start at tile 0(ie both rabbits will initially be at tile 0) and end at tile n-1

Both rabbits A and B are assigned stride values as s1 and s2 respectively.

Each rabbit have health points hp1 and hp2 assigned to it.

The rabbits will make moves alternatively, starting from A. That is, A will increase its positon by s1, followed by B moving ahead by s2, then A again, followed by B and so on…

But there are conditions to the movement of the rabbits. If a rabbit lands on a 0 labelled tile

  • His hp will be decremented by 5
  • He will be unable to go ahead in his following move. That is in the rabbit’s very next move, he would not be changing his position

    (his hp will not be reduced this time though)

The only time when a rabbit will make a stride/hop for a length different than the assigned length is when, its distance from the final tile is less than the stride length. In this case, its stride length will equal the rabbits distance from the final tile.

In a situation where the leading rabbit is on the last tile and reaches 0hp simultaneously, he wins.


Output requires the winning rabbit’s name(A/B) and absolute difference of distance between 2 rabbits at the end of the race, seperated by a space.

EXPLANATION:

Explanating with an example initially:

Input:

1

12 3 2 10 10

1 0 0 1 1 0 1 1 0 0 1 1

Output:

A 5

Explanation:

A and B both initially at position 0 (indexing is from 0, hence range of positions: 0 - 11)

A moves by 3 --> position 3 --> lands on tile 1

B moves by 2 --> position 2 --> lands on tile 0 (therefore hp2 -= 5)

A moves by 3 --> position 6 --> lands on tile 1

B does not move --> position 2 (skipping 1 move as penalty)

A moves by 3 --> position 9 --> lands on tile 0 (therefore hp1 -= 5)

B moves by 2 --> position 4 --> lands on tile 1

A does not move --> position 9 (skipping 1 move as penalty)

B moves by 2 --> position 6 --> lands on tile 1

A moves by ((12 - 1) - 9) --> position 11 --> END (when stride length > distance of A from last tile, stride length = distance of A from last tile)

Winner: A

Distance: 11 - 6 = 5

Special case

Input:

1

1 3 5 2 6

0

Output:

A 0

Explanation:

A and B both initially at tile 0

The race will start with A

A will move ahead by it’s distance from the last tile ie 0

Now hp1 = 3 and should be reduced to 0, but since this is the last tile, hp will not matter as A has won the race

Winner: A

Distance: 0

Getting started with the logic

We will consider 1 hop as one move. There are 2 conditions, that will result in the end to the race that need to be checked at every move.

  • If position of rabbit from the start >= number of tiles
  • If the rabbit’s hp <= 0

We will have a while loop where we increment the position of the rabbits A and B by s1 and s2, checking the above 2 conditions for both of them in each loop.

Another condition we have to take care of is, if the rabit lands on a 0 labelled tile for any step, not to increment it’s stride value and also skip checking the above conditions.


Getting down to code. Below are pseudo codes to handle the main condtions, all of these combined with some additons will result in the final solution.

  • First to handle the condtion on landing on the 0 labelled tile. We’ll declare a boolean variable for both rabbits,
    whose state will decide whether the rabbits are skipping the move due to the penalty, or they are moving ahead with the conditions being checked.
while(True):
	# for rabbit A
	if flag1 == False:
		# increment position by s1
		# check both finishing conditions
	else:
		flag1 = False
		# rabbit did not go ahead
		# flag's value adjusted to make sure it moves ahead on the next loop
	
	# similarly for rabbit B
	if flag2 == False:
		# increment position by s2
		# check both finishing conditions
	else:
		flag2 = False
		# rabbit did not go ahead
		# flag's value adjusted to make sure it moves ahead on the next loop
  
  • Code under if flag == False --> Incrementing position and checking the finishing conditions to break from the loop
# pos --> position, arr --> input arrray, len --> input length
# other variables, self explanatory. 0 based indexing used
pos += stride_val
if arr[pos_A] >= (len - 1):
	win = 'A'
	dist = (len - 1 - arr[pos_B]) # handling the distance condition in the case stride_val > (len - pos)
	break
if arr[pos_A] == 0:
	hp1 -= 5
	flag1 = True
if hp1 <= 0:
	win = 'B'
	dist = abs(arr[pos_A] - arr[pos_B])
	break

# similar code for rabbit B
  • This was the main logic, other parts of the code include checking if the starting tile was 0, and printing out the solution

SOLUTIONS:


Find the setter’s solution here

Find the tester’s solution here