Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

Problem 1351C

Revision en5, by Sven867, 2020-05-09 04:55:04

I believe the solution to input #2 for problem 1351C is incorrect.

In input #2, line #58 is "SNWNSENSNNSWNNW". The problem states that each letter "S", "N", "E", "W" should correspond to a direction (south, north, east, west). You move 1m every time, and any time you are at a unique location, it takes five seconds to reach it. It takes only one second to reach a location you have already reached.

For this test case, if you consider the problem using coordinates, starting at (0, 0), you should find:

  • (0, -1) + 5

  • (0, 0). + 1 // you started there

  • (-1, 0) + 5

  • (-1, 1) + 5

  • (-1, 0) + 1 // already been there

  • (0, 0) + 1

  • (0, 1) + 5

  • (0, 0) + 1

  • (0, 1) + 1

  • (0, 2) + 5

  • (0, 1) + 1

  • (-1, 1) + 1

  • (-1, 2) + 5

  • (-1, 3) + 5

  • (-2, 3) + 5

Summing, the total time, t, should be 47. This is the output my program gives. Yet the expected answer is 51.

I tried to "brute force" that one line of that test by forcing my program to print 51 in this specific case. But there were several more instances where I was supposedly off by 4. There have been a couple of accepted solutions, so there is obviously a pattern to these issues. The vast majority, however, have failed this exact test case. Looking at accepted submissions, I have no idea why they work any differently than some of my submissions or other rejected submissions I have looked at. Regardless, by doing this calculation manually, it appears that it is wrong. I am not sure if there's a way to report wrong test cases, but I wanted to share in case someone else has any insights about whether or not the test case is correct.

Edit: I'm wrong. It doesn't matter if you end up in the same point as you were before, what matters is if you take the same path as you already did. So going from (0, 0) to (0, 1) to (1, 1) to (1, 0) to (0, 0) would be a series of five second movements. It doesn't matter that you started at (0, 0), because you would never intersect your path unless you went between, say, (0, 0) and (0, 1) again. Hopefully that helps clarify things for future reference.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English Sven867 2020-05-09 04:55:04 464
en4 English Sven867 2020-05-08 21:14:08 2 Tiny change: 'ld find:\n- (0, -1' -> 'ld find:\n\n- (0, -1'
en3 English Sven867 2020-05-08 21:13:24 28
en2 English Sven867 2020-05-08 21:12:49 30
en1 English Sven867 2020-05-08 21:11:39 1625 Initial revision (published)