sanket407's blog

Google APAC 2017 Round C
By sanket407, history, 8 years ago, In English

Hey How to solve problem B and D ? https://code.google.com/codejam/contest/6274486/dashboard#s=p1 https://code.google.com/codejam/contest/6274486/dashboard#s=p3

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sanket407 (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

For B, calculate dp[i][j], which denotes the size of maximum square ending at i,j. Then simply sum dp[i][[j] from i=0 to R-1 and j=0 to C-1. Calculating the above dp is explained here: http://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem A test case 2 , how is the probability of transition from (8,3)->(8,2) = 0.23743359 . Can anyone please explain this.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

D:
O(n**3) solution is to compress the given values in both column so none of them goes over n.
Then if you are at state (i, j) (i is the maximum attack value and j is the maximum defence value in the already choosen set), you could try out all possible pair (soldier) you could add in O(n) and then memoize the results. This only passes small test though.

→ Reply
»
8 years ago, # |
  Vote: I like it +17 Vote: I do not like it

The solution to problem D is actually deceptively simple. Let's say whoever picks last wins.

If there are no soldiers, then Alice loses, because she has no moves. Otherwise, let the highest attack of the soldiers be maxA and the highest defense be maxD. We have two cases:

  • If there is a soldier with (Ai, Di) = (maxA, maxD), then Alice picks this soldier and wins immediately.
  • Otherwise, the players will never pick any soldier with attack maxA or defense maxD. The reason for this is that, if one player picks a soldier with attack maxA, the other immediately picks any soldier with defense maxD and wins. Therefore, as no soldiers with attack maxA or defense maxD will ever be picked, we can simply delete these soldiers and start again.

The straightforward O(n2) implementation is good enough, but it should be possible to implement this in by sorting the soldiers first.

→ Reply