LeJoepher's blog

By LeJoepher, history, 2 months ago, In English

Recently, I came across one of my old codes for CSES Grid Paths. In a moment of frustration, I seem to have hardcoded some of the cases that got TLE. Today, I tried to uphack it, but to my dismay, I was unable to come up with a hack case, even with casegen. Can someone come up with a hack case?

The hack link and the code are here

Thanks in advance!

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

U can prove that there are only 5 cases where that code gets tle

»
2 months ago, # |
  Vote: I like it +16 Vote: I do not like it

When you try to uphack your own code... and fail... and make a cf blog instead... Just how bored are you?

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

I believe that those test cases are the ones that consider the most amounts of paths, so if testing those yield no results then your solution might just be fast enough? Placing less ?s in the string limits the amount of cases to be considered, and moving any LRUD closer to the front limits cases as well since a larger branch of cases will be skipped over.

EDIT: Actually I am not sure why your code would TLE in the first place since a case like "???????????????????????????????????????????????U" runs within the time limit, and this should be very close in runtime to "???????????????????????????????????????????????D" (differing only at the last step).