Hello everyone, I'm trying to understand the linear-time solution proposed in the analysis of the "Mysterious Road Signs" problem from Round 1B 2018.
Could anybody help me with that please? While I believe it should work, I'm still not convinced. I understand that we maintain two candidates. I also understand meanings behind the (M,N,start,xstart) properties of both candidates. What I do not understand is how the proposed procedure (for creating a new candidate) guarantees to maintain the invariants. It also is not clear why two candidates are enough? Could someone elaborate on that parts? A proof would be great of course, but I would be happy to hear any hints, explanation of logic behind the solution, etc. Thanks in advance! Best regards, Michael. -- Michael V. Antosha -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CABUXKX68BJx7O5dokj2h5Pw9Z_TrosMtv2YgPQPYXrtubSSUJQ%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
