ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1519. Formula 1

how to solve this problem
Posted by nttjuvwamsncc 14 Feb 2007 14:29
I think this is very interesting and hard problem
so who can tell me the solution of this problem
what is the author's solution
Re: how to solve this problem
Posted by Denis Koshman 20 Jul 2008 13:26
I will tell you the solution because this problem should have time limit of around 3-5 seconds. I struggled for almost two days making that algo suffice all tests, and still I had to precompute an empty 12x12 grid, and my AC solution ran for exactly 1 second :))

Go row-by-row with state representing connected components above. These will be something like 11022, 12021, 10220133, etc... Where 0 stands for no exit from above and 1..n stand for connected component number. Actually, every connected component will have exactly two exits downwards, and they will be placed in stack order. Cases like 1212 are impossible because it would mean that paths 1..1 and 2..2 intersect somewhere above. So, this gives us a way to effectively enumerate all of components using at most 2^2 * 3^10 states. Digit 0 means skip. Digit 1 means start new component. Digit 2 means close last open component (remeber their stack order). First digit can't be 2 and last digit can't be 1.

This is enough to keep values about previous and next row with cache of next_x[12] - a matching of exits for each column. Also, don't forget to keep array of indices with non-zero values for previous and the next row, this optimizes things a little as you will run only through reachable states.

Once you complete current row, paint everything to find resulting components matching with exits from the row just painted. It can be done via BFS, but I couldn't meet TL with that, so I had to optimize it - all paths are chains, so just walk straight. For the last row a path should be a chain loop covering of all upper exits.

Internal transfers should keep all components alive, that is - there must be no loops. This also allows to optimize recursive steps for building current row by remembering last connected upper component connected by "rhhhh..." - so just don't allow closing it towards itself, unless it is the last row.

Also, do not forget to skip first and last rows full of **********.
Re: how to solve this problem
Is tracing row-by-row quicker than element-by-element???
Re: how to solve this problem
Posted by die_young 21 Jul 2018 12:03
Can be solved in less than 0.1s using broken profile dynamic programming.