8VC Venture Cup 2016 Final Round

8VC Venture Cup 2016 Final round div1 on CF screen cast by eddy1021

Finished A at exactly 5 minutes!

B is a interesting problem. Given s and x up to 10^12, you should find the number of ordered pair (a,b) such that a+b=s and a xor b = x. Take both s and x into binary notation. Then, the answer is easy to check. Answer will be 2^(number of bit being 1 of x). If s = x, subtract 2 for the pair (0,s) and (s,0). However, one should check whether s is possible. An easy way is to check whether ((s-t)>>1)&t being non-zero. If it's non-zero, the answer should be 0.

C isn't a difficult problem. But I didn't get the important statement (actually I don't understand that very statement). Thus, I solved C within about 10 minutes after finishing D. C can be handled by two segment trees. For each query, it is as the prefix of first segment tree add suffix of second one.

D is a good greedy problem. Given a distance and capacity of fuel tank and the information about m gas station with position and price, you should find the minimum cost to get to the destination. Easy to show that for each position, one had better go to the cheapest gas station within its reach. Thus, for each gas station, if the next one is cheaper than its, we just buy enough fuel to get there. If the next one is more expensive, we fuel the whole tank. For the last one gas station which can get destination, we just buy enough fuel to get there.

E is a beautiful problem. I don't think I was able to solve it during the contest thus I turn to hack others' solution. The problem is that given a tree with values on node, you should root it and rearrange its arrangement. Thus, the minimum value among first k node on the dfs list is maximum. The idea is that if we can find a solution suitable for value a, then we must be able to find a solution suitalbe(all values chosen is equal or bigger) for value a-1. Thus, we binary search the answer. Then, we know whether each node can be taken. Therefore,  use tree dp with state dp[i][2] as each subtree rooted at i and all the node taken or some nodes taken as a valid dfs list. Then, run another tree dp again, we can find the maximum possible number of node chosen for each root.

Rank 27 on final standing. Reach red again with exactly 2400 rating! Thanks to the hack on 1:58!