April 11, 2017 2017 TCO Algorithm Round 1B Editorials

TCO17 Algorithm Round 1B Editorials are now here! A big thanks to Egor (TCO’12 Algorithm Champion) for writing the editorials and also sharing some interesting insights from the different phases of the match. You may discuss the problems in the match discussion forum.
 
Summary
Topcoder Open Round 1B happened last Saturday and once again standings were dominated by semi-retired coders who had not fulfilled criteria to get bye despite having high enough rating. xudyh get the first place with impressive scores on all 3 problems (he solved all of them in under 15 minutes!) and 4 successful challenges, sdya and VArtem about 150 points behind. 76 coders got all 3 problems right, quite impressive. Let’s look at problems in more detail.
 
2017 TCO Algorithm Round 1B – Division I, Level One WaterAndOxygen
In this problem there are two different approaches. One is to do binary search on answer. First we need to check if we’ve got enough water to survive this many days. If we do then we electrolyze balance to oxygen and check if we’ve got enough oxygen as well. For implementation of this approach refer to RRx’s solution.
Second approach is to notice that answer is actually minimum of two values: remainH2O/costH2O and (remainH20 + 2 * remainO2) / (costH2O + 2 * costO2) – we need to have enough water and then also enough of water plus twice oxygen because we can transform water into oxygen. For implementation of this approach refer to Sfiction’s solution.
One thing you should keep in mind is that costH2O + 2 * costO2 can overflow 32-bit integer. That’s exactly what happened with author’s solution.
 
2017 TCO Algorithm Round 1B – Division I, Level Two CoinConstruction
This problem’s solution is based on one insight – suppose we have bag of coins with S consisting of exactly num elements and maximal value in S is max. Then if we add coin with value max (1) to the bag set S would consist of exactly 2 * num elements, while if we add coin with value max + 1 (2) to the bag S would consist of exactly 2 * num + 1 elements. Now if we would start with bag with 1-value coin in it and go through binary representation of k from left to right ignoring first one and adding coins to bag according to (1) if we encounter zero and according to (2) if we encounter one we will get bag of coins with exactly k different elements in set S with no more than log k + 1 coins in it with values up to 2 * k, which will fit in problem constraints. You can look at Kankuro’s solution for implementation details.
2017 TCO Algorithm Round 1B – Division I, Level Three SubtreeSumHash
Let’s assign vertex 0 to level 0, all its adjacent vertices to level 1, all vertices adjacent to level 1 vertices that are not level 0 vertices to level 2 and so on. For vertex v at level L let’s define H(v) as sum of hashes of all subtrees that contain vertex v but no vertex of level L-1. This way answer for problem is just sum of H for all vertices. Suppose vertex v has k adjacent vertices on level L+1 – u1, u2, …, uk. Then H(v) = x^weight(v) * (H(u1) + 1) * (H(u2) + 1) * … * (H(uk) + 1) (proof is left as an exercise to the reader.
Go to OlerRobbin’s solution if you want to check out how exactly it could be done.