SUPERPLN - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

At each step Dunno is in some city at some time. If Roly-Poly lives in this city and the start time of the birthday party is not less than the time when Dunno get this city then the answer is “Yes”. Otherwise you need to find the closest flight from this city for the given time. If there is no flights in that city after this moment of time then the answer is “No” because Dunno will be stuck in that city forever. If he have already use the closest flight then the answer is also “No” because he will flight forever using the same sequence of flights and never gets the party. Otherwise you should use this flight, mark it as used, change your city and time to the corresponding ones and continue this procedure. Obviously we will use each flight at most once so we will have in total no more than N steps. The closest flight can be found using binary search. For example you can sort all flights by the city of arrival and then by the time of arrival and use binary search for such array. So the overall time complexity is O(N log N).

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

2

I created a test case after understanding the problem [1] [5] [1 3 4 3] [1 4 6 3] [4 4 3 5] [6 4 3 2] [3 3 2 0] [1 2 2 1] but this fails for the solution given by the Tester & the Setter, I don’t understand

3

The answer is NO. And that is exactly what the setter’s problem show as well.

Flights are taken in order

[1 3 4 3]
[4 4 3 5]
Stuck !

As the inly flight at 3 had left at 3.

4

@perseus
But what if he had taken the flight in the following order…

[1 4 6 3]
[6 4 3 2]
[3 3 2 0]

Then he would reach the party before time(which is at 1) and at the correct place too (which is 2)…??