AMR14I - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Editorialist: Karan Aggarwal

DIFFICULTY:

EASY

PREREQUISITES:

Simulation, Ad-hoc

PROBLEM:

The problem requires you to simulate the running of 2 players with different speed P and Q around a stadium for S seconds each, and tell the number of time they will meet.

EXPLANATION:

The stadium is in form of a line with M-1 pillars and then a loop with N-M+1 pillars, thus a total of N pillars. The limits of S are such that a O(S) solution will pass the time limits. Also, given a current position and speed, the next position of the player can be found in O(1) by simple mathematics.
new_pillarPosition = M + (current_pillarPosition + speed - M) % (N-M+1)
To reach to this formula, we have to observe that there is a cycle of length (N-M+1), but a extra M is present in the pillar position, which we can remove, then add the speed and find the new position in the cycle by taking a MOD with cycle length, then add M again, to get the actual pillar number.

AUTHOR’S AND TESTER’S SOLUTIONS:

Editorialist’s solution.

2

What is the problem in this formula I have come up with?

pos = (cur_pos + speed)

if pos is greater than n, then

pos = pos%n + m-1

I have been regularly getting WA. Please explain.

1 Like
3

use while loop in place of if,
while(pos>n)pos=pos%n+m-1;

4

i didn’t got how this formula works: new_pillarPosition = M + (current_pillarPosition + speed - M) % (N-M+1)

5

can any body explain this problem more clearly?

1 Like