He Who Must Not Be Late

Discussions Toph Problems
1

He Who Must Not Be Named, Lord Voldemort, is chasing Harry and Hermione. They have been able to reac…

Click here to read the complete problem statement.

If you need help solving this problem, mention your approach and ask specific questions. Please avoid sharing your code and asking the Community to figure out “what’s wrong”.

1 Like
2

This post is regarding the concerns raised about the problem He Who Must Not Be Late.

Hello fellow programmers,

As pointed out by a contestant, we have had a look into the issue of my problem (He Who Must Not Be Late). At first, it was thought to be a dataset error issue (which it was, in a small scale); but in the end, after a “long long” discussion with half a dozen programming enthusiast, I thought of writing down the discussion here.

Just for your kind information, we tried to consider all the possible cases, from platform precision issues to OS problems to library functions. At the end, it was a new learning for me in many ways, how precision in a programming problem can behave if implemented differently.

  1. The main issue with the problem was (for which most of them were getting WA, and for a valid reason) that many were working on two precision dependent calculations.

    • Angles: Many of the contestant tried to solve the problems using angles. Though correct arithmetically, the reason for Wrong Answer is a simple one – precision. In theory, you one can consider the angle and keep on going, but in fact, the result of the intervals or calculations had decimals of repeating sequence, or irrational, in a few cases. Adding them constantly, proved a significant outcome (example provided later).

    • Intervals between two overlaps of Hour and Minute hands: If someone tries to add up the time of intervals consecutively, the program will provide you a WA. It is because, adding up decimals for multiple times (if the number is higher, the chances of getting WA gets higher) may end up with a different value after rounding up.

      Example:

      The following two codes for finding the train times had decisive outcomes (first one yielded WA)

      // First one
double interval_time = (double) H*M/ (double)(H-1);
TrainTimes.push_back(0.0);
int i=0;
while(i<2*(H-1)-1)
{
     TrainTimes.push_back(TrainTimes[i]+interval_time);
     ++i;
}

// Second one
double interval_time = (double) H*M/ (double)(H-1.0);
TrainTimes.push_back(0.0);
TrainTimes.push_back((double) H*M);
int i=1;
while(i<H-1)
{
    interval_time = (double) (i*M)/(double) (H-1);
    TrainTimes.push_back((double) i*M + interval_time);
    TrainTimes.push_back((double) i*M + interval_time + (double) H*M);
    i++;
}
sort(TrainTimes.begin(), TrainTimes.end());

      The reason for this is that in the first one, decimal numbers are being added multiple times, one on another. If the error for the any of the variable is 0.01, after 10 additions, that becomes 0.1 making it a significant amount for rounding.

  2. The second most decisive issue for the solution was to use EPS(1e-6) and fabs()/abs() function incorrectly. Though ultimately, one will get a Wrong Answer anyway, using EPS made a few solvers code correct for a few cases. For example, A>B provided 20+ errors, whereas A-B>EPS scaled it down to around 15 for a few participants. Using fabs()/abs() incorrectly also gave the verdict WA. In this particular problem A-B>EPS is totally different from fabs(A-B)>EPS.

Thanks a lot for your patience. We thank Nirjhor for pointing out a case, which led to this. We have updated the judge solution and dataset after this. Hope we all enjoy problem solving. After all, learning is an infinite loop.

If you have any thoughts regarding this, feel free to address it here. :blush:

3 Likes