Google APAC 2017 Round A Editorial

Revision en3, by loser21, 2016-07-11 14:01:20

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

Tags apac, google, editorial, meet in the middle


  Rev. Lang. By When Δ Comment
en5 English loser21 2016-07-11 14:31:54 1979 (published)
en4 English loser21 2016-07-11 14:03:08 105
en3 English loser21 2016-07-11 14:01:20 544
en2 English loser21 2016-07-11 13:52:08 32 Tiny change: 'paces too.[](\n[Code](h' -> 'paces too.\n[Code](h'
en1 English loser21 2016-07-11 13:51:37 737 Initial revision (saved to drafts)