Since Google APAC is one of the few contests where there is no official editorial/analysis available, I decided to write a short editorial for Round A of Google APAC 2017. You can read the problem statements from this link.

Problem A

You need to find the number of distinct uppercase English alphabets in each of the given strings. Out of all those strings who have the maximum number of distinct alphabets, simply output the smallest one in the lexicographic order. Be careful while taking input for the large test data as the strings might contain spaces too. Code

Problem B

To solve this problem, iterate from the smallest height to the largest height. For a given height h, find all connected component of cells where all cells have height h using BFS/DFS. Now for a particular connected component of height h, look at all neighbours of cell in this connected component (not of height h) and find the neighbour with minimum height say x. If x > h, update all cells in the component to height x. Time Complexity: O(R*C*max(H[i][j]) per test case. Code

Problem C

Divide the entire expression by (1 + r)^M. The expression becomes C₀ = C₁ / (1 + r) + C₂ / (1 + r)² + .... Note that the RHS of the expression is a decreasing function in r. Use binary search to find out the value of r such that the expression on RHS = LHS. Make sure you run your binary search for enough iterations so that the error is small enough. Time Complexity: O(M*(Number of Iterations of Binary search)) per test case. Code

Problem D

To solve the small dataset, a DP approach can work where the state is dp[i][p] which stores the minimum number of coins to achieve power p using updates on first i cards only . However this approach will time out for the large data set as it is O(N*(Max Possible Total Power)). Code Code To solve the large dataset, a meet in the middle approach works. (Use the search engine of your choice to find out more about meet in the middle approach in case you want to read about it). The idea is to consider all N choose 8 combination of cards and then divide the 8 cards into two groups of 4 cards each. Now for each of the two groups use brute force to find out all possible combination of power and the minimum number of coins to achieve that power using a map/dictionary. Eliminate all entries in a map where there is a smaller number of coins to achieve a larger power. Now iterate through all entries in a map, suppose for a particular entry you can achieve power p using k coins. Use binary search on the second map to find the max power you can get using atmost m-k coins. This approach works is O((12choose8) * (10⁴) * log(10⁴) per test case. This took a couple of minutes on my machine to run. Code

In case if something is incorrect or unclear, please feel free to point it out either through a PM or a comment on this post. It would be great to read alternate approaches for any of the problems. Apologies in advance for any error that I might have made while writing this post.

I have been trying the question , Just Some Permutations , for quite some time and I am unable to make real progress. I guess we need to apply Principle of Inclusion Exclusion somehow but I am unable to understand exactly how. The question appeared in the 2014 ACM ICPC Dhaka Regionals. Any help on how to solve it will be great.