sumantopal07's blog

By sumantopal07, 3 months ago, In English

https://cses.fi/problemset/task/1625 I am applying staright forward DFS to the problem but it's getting Time Limit Exceeded. How to optimise the code. I checked out William Lin's Livestream but did'nt get his approach to the problem

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

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

https://cses.fi/book/book.pdf page 52 (the printed page number) or 62 (the pdf page number)

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

    thanks

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i understood the optimisations, but can you explain the runtime mathematically? the explanations there looks more experimental.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone with a sharp eye help me please? I basically tried “to go by the the book”, and do the pruning of the T-shaped wall hits, — just as @tmwilliamlin168 does for this problem in his epic 11-hour stream.

Still, however, I'm getting 30+ seconds on the all-question-marks 88418 paths case. What am I missing? I tried to code it up in a clean way, so you probably won't have any trouble following the logic.

Thanks!

The code
  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I've shaved off about 50% of time by removing all that pairs instantiations. Still not good enough. 16 seconds on the 88418 paths case. Help!

    Version 2
  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    So, seems like, the constraints are really tight, and the constant factor caused by all the nice code factorizations was simply killing it. After I unrolled all the DRY-ness, and uglified the code to the point listed below, it got accepted.

    UPD: Ah, btw, the absolute numbers in seconds I quoted above are not quite representative, as I ran the code with memory sanitization, and all the optimizations disabled. So, it should be, like, 7 times faster, when run by the OJ.

    Version 3