I was upsolving Balkan OI 2019 problems and got stuck on “Clear the Memory” and “Roadtrip” (both from day 2). Could anyone give me hints for how to solve those problems fully?
For “Clear the Memory”, I have a 69-point solution:
69 points
We binary search for the answer.
Let the current candidate be pref. We basically BFS and process the programs we use backwards.
Initially, push program i into the queue only if i has no 1s in [1, pref]. When we process a program, we mark the positions of each 0 in [1, pref] as visited. We push an unprocessed program into the queue only if the positions of each 1 have been marked as visited.
pref is good if and only if each position in [1, pref] has been marked as visited at the end.
This should work in \mathcal O((\text{No. of bits}) \log M) time if implemented correctly.
For “Roadtrip”, I think I have a 53-point solution, but I’m not sure whether it works:
53 points
Just BFS from each node to get the nodes reachable using exactly 5 edges. We can then do another BFS to get the answer.
You can submit code for “Clear the Memory” here, but there’s currently nowhere to submit code for “Roadtrip”.