749D: Leaving Auction(!!!)

707D: Persistent Bookcase (!!!)

If only operation 1,2, and 3, we can keep track of the inverse, and twist the operation as we go. This also means we need to maintain the whole state.

I was having problem handling the 4th operation, because I wasn’t sure how to handle the memory and run time requirement when it comes to revert. Turns out because we have all entries there already, we can do a full pre-computation and store the result, to avoid the case of re-computing a single node many times => i.e., we cache it as part of computation progress!

Idea 1 (Offline)

Instead of calculate the result online, collect all queries and but a dependency graph, DFS it once and fill the cache, and then print out the result

Note that because we try to apply changes at each step, the revert may be a noop because the application didn’t go through in the first place!

Idea 2 (O(nq) space and time)

Becasue we have only 10^5 queries, max of 10^5 lines are modfies, therefore, we store those 10^5 lines explicits, along with the which version they represent. To make op 4 calculate quickly, we have a cache of state[version][i] to keep track of the version of a single row i of at the overall version.

On operation 4, we just interation through all n and sum up (with the help of count cache)

711D: Directed Roads(!!!)

In a sunny graph, find the edges in the center circle. The final answer will be (2^|size of cycle| - 2) * (2^|edges outside the cycle|)

Note that by the given input, each node has exactly 1 outgoing edge, failed to realize this makes my solution and reasoning much harder

Also, we can use dfs’s depth to calculate the cycle, but we have to watch out for the case where other edge from the branch hitting the cycle and thus will mess up the cycle size based on depth!

To defend against that, we have to mark which visit the discover is from, and allow only the visit from the same discovers. Note that this secondary discovery will not affect our count of ways, because of our forumla - only each individual cycle length matters

735D: Taxes

If n is prime, we pay only 1.

Otherwise, if n is even, by goldbach’s conjecture, we can find 2 primes

If n is odd, then it can be the sum of a prime and an even number. Note the speical case of that even number = 2 (!!!), otherwise, the answer will be 3.