manishbisht's blog

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

Let's discuss the solutions of all the problems. I would like to know other peoples approaches for the problems. This time problems seems hard for me. What are your views about the problems ?

Here are the problem statements.

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

Comments Comments (6)
| Write comment?
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Code for Qn. A : Peoblem A I used simple recursion here :)

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

    For Problem 1 Taking the first example test case Initial Point is (0,0) and we have to take 5 steps. The path given is (0,0)->(0,1)->(0,2)->(1,2)->(2,2)->(2,3) For making the first step how to select the next point from (0,1), (1,1) and (1,0)

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

code for Question B Problem B A simple DP approach :)

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

PROBLEM A:

DO DFS from start cell to all possible cells until no. of steps is less than battery. Note that you can come back to same cell to catch pokemons but probability of catching pokemons will change. If you come first time to a cell to catch a pokemon the prob. = P or Q (depending on A or .). When u come to same cell second time the probability will be (prob. of failure on 1st visit)*(prob of catching now) = (1-P(or Q)) * P(or Q). So if you come to a cell nth time then prob. = (1-P)^(n-1) * P. So while doing dfs keep a track of how many times you visited a cell in past by a 2-D array. Also to restrict some unwanted dfs keep a visited array[r][c][s] which stores max prob. now at cell[r][c] after steps 's' So u can avoid unwanted dfs with less prob .

Code: http://ideone.com/xvbBpd

PROBLEM 2: create dp[r][c] At every dp[i][j] store the max. size of square submatrix whose right bottom corner is [i][j]. Refer http://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/ (note that here we need to count with all 0s) . Then ans = sum of all dp[i][j] for i=1 to r and j = 1 to c

PROBLEM C:

Here create an directed graph with edges from function arguments to the assignment variables. if a=f(m,n) add edges m->a and n->a since a depends on m and n . Observe that if there are cycles in the graph then we cannot evaluate all variables due to cyclic dependency. One more thing to be checked is that all variables should be once used as assignment variable previously. To do this create a dummy node and for all exp. of type a=f() add edge from dummy node to a. So now all nodes in graph should be reachable from the dummy node as each variable is basically derived from dummy node. So check two things: 1. all nodes reachable from dummy node 2. no cycle in graph

Both of these can be done together by starting dfs at dummy node. Keep a counter of visited nodes and use dfs to update counter as well as to check for cycles. At the end if count != no. of nodes +1(dummy node) OR cycle found then BAD.

note that the string preprocessing has to be done using hashmaps (or some equivalent )

Code: http://ideone.com/8IXHzQ

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

There is another approach for problem C:

We need to maintain a set found of all variables which have already been evaualted, and a map to keep variable -> function parameters.

Now, first we add all the variables that have no required function parameters to the found set. Then, we iterate through the map and check if any variable has all it's function parameters already calculated, and if so, we remove that variable's mapping and add it to the found set.

We do this until the size of the map is 0.

To break from this loop in case an answer does not exist, we just have to check if in an iteration we remove at least 1 variable from the map.

My code : here

→ Reply