Google APAC 2017 Round A Editorial

Правка en3, от 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

Теги apac, google, editorial, meet in the middle

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский loser21 2016-07-11 14:31:54 1979 (published)
en4 Английский loser21 2016-07-11 14:03:08 105
en3 Английский loser21 2016-07-11 14:01:20 544
en2 Английский loser21 2016-07-11 13:52:08 32 Tiny change: 'paces too.[](http://pastebin.com/7iV1uEEg)\n[Code](h' -> 'paces too.\n[Code](h'
en1 Английский loser21 2016-07-11 13:51:37 737 Initial revision (saved to drafts)