mango_lassi's blog

By mango_lassi, history, 5 months ago, In English,

This problem

I have a solution I think is correct but can't get it to pass, and apparently even my n^2 code (standard game theory iterating through all states solution) that should obviously work gets WA. They both give the same answers for random small inputs.

I can't find editorials or test data for the contest, so seeing so many teams have +1 or more in this problem, is there some tricky corner case I might have missed?

My code if it is of any interest:

code
n^2 code

Submissions: 54559534 54559186

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

»
5 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Do recheck — it seems to me that testdata is visible in coach mode. In particular, your code seems to fail on following case:

Testcase
  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    Okay, it looks like it matters that A cannot move into nodes that B has visited, I thought it was enough to check that A doesn't move into the node B is currently in. The brute-force code had the same assumption, so no wonder they gave the same answers.

    Thank you, I found the issue now. A small change and the code gets accepted :) 54563432