manishbisht's blog

Google APAC 2017 — Round D
By manishbisht, history, 7 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 I am only able to solve Problem A. What are your views about the problems ?

Here are the problem statements.

Final Round on Sunday, November 6, 2016 13:00 CST

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

Comments Comments (38)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how did u solve A ?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I didnt solve it through the contest because I had some troubles, but I submited now and got AC to both, small and large. Large run in 6sec, so I think is a good solution. Complexity is O((N+M)*N) I keep a dp[i][j] with size [4000][2000] where i is the position and j is how much 'A' voters I have until that position. Dp itself keeps the ways we can achieve that with the rules that statements says. So dp[i][j] = dp[i-1][j] * max(0, M — (k-1)), for the case that we want to add in ith position an 'B', and dp[i][j] += dp_solve[i-1][j-1] in case we want to add an 'A'. Finally you will print dp_solve[N+M][N] / factorial(N+M). In large that will overflow, so we can keep a clever division in each for loop, something like that-> dp[i][j] /= i, because we want dp[i][N] to be divided by i!, so dp[i-1][N] will be divided by (i-1)! so new dp[i][N] can be equal to (i-1)!*i, so you see that you can just divide by i in each loop.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      What is the variable k and dp_solve?

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

        dp_solve is the dp. I write it differently by accident. k is the variable that keeps the 'B' voters we can have at current state. It is caclulated as i-j.

        → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    sanket407 Read the problem statement carefully and Just see the sample inputs. The ans will be (n-m)/(n+m). You can get this by writing all the permutations as explained in problem. Check this for more details : Bertrand's ballot theorem

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

A: Simple DP with state as (N, M) denoting number of people of first kind and second kind left. Transitions are easy, just check if second kind person votes now, then first person should be still winning.

B: I'm not sure, but I think I got AC on large by fluke, just submitted some random greedy solution. Any ideas on proof or your solution? Solution for small: DP with state (current Index, mask of row[currentIndex-1], mask of row[currentIndex-2]). Transitions are easy, check all possible masks for the current row which satisfy all conditions.

C: Again DP in O(N2 logN) per test case. State is (Current Index). From the current index, start iterating forward keeping an array of frequencies. At each position, check if we have the same frequency of characters as in any one of the strings using a map(which is computed previously).

D: Small: Brute force, try out all 210 combinations. No idea how to solve large. Anyone?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    D: DP[x][i] stores the minimum cost required for formation of length exactly x using some rubber bands upto i. Transitions are pretty straight forward. One can use segment tree or sparse table to speed up the same.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Thanks a lot! :)

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Can you explain a bit more on how segment table or sparse table can be used to speed up transitions

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

    please state the recurrences for A

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it 
      find(noOfPeopleVoted, noOfVotesforA) = P(A)*find(noOfPeopleVoted+1, noOfVotesforA+1) + P(B)*find(noOfPeopleVoted+1, noOfVotesforA)

      P(A) = Probability to select a person that votes for A from remaining voters

      Similarly for P(B). These could be find out from initial, n, m, noOfPeopleVoted, noOfVotesforA

      Answer is in find(0, 0)

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

    How did u bitmask on large dataset ? R,c<100

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

      Only for the small dataset. For large I used a greedy approach that I don't have a proof of.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        can you explain how to use greedy approach to solve the problem? I think the method is like this:

        xox xox xox ...
xxo xxo xxo ...
oxx oxx oxx ...
xox xox xox ...
xxo xxo xxo ...

        so I get the answer: 

        1 2 2 3 4 4 5 6 6 7 8 8 9 10 10
2 4 4 6 8 8 10 12 12 14 16 16 18 20 20
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30
3 6 8 11 14 16 19 22 24 27 30 32 35 38 40
4 8 10 14 17 20 23 27 30 33 37 40 43 47 50
4 8 12 16 20 24 28 32 36 40 44 48 52 56 60
5 10 14 19 23 28 33 38 42 47 52 56 61 66 70
6 12 16 22 27 32 38 43 48 53 59 64 69 75 80
6 12 18 24 30 36 42 48 54 60 66 72 78 84 90
7 14 20 27 33 40 47 53 60 67 74 80 87 94 100
8 16 22 30 37 44 52 59 66 74 81 88 95 103 110
8 16 24 32 40 48 56 64 72 80 88 96 104 112 120
9 18 26 35 43 52 61 69 78 87 95 104 113 122 130
10 20 28 38 47 56 66 75 84 94 103 112 122 131 140
10 20 30 40 50 60 70 80 90 100 110 120 130 140 150

        N = 15,M = 15

        the code like this :
int getAns(int N,int M)
{
    int ans;
    if(N < M) swap(N,M);
    if(M == 2 || N == 2)
    {
        swap(N,M);
        if(M % 3 == 1)
            ans = ((M / 3) * 2 + 1) * N;
        else
            ans = ((M + 1) / 3) * 2 * N;
    }
    else
    {
        ans = (N / 3) * 2  * M ;
        if(N % 3 != 0) ans += (N % 3) * ((M + 2) / 3) + (N % 3 &mdash; 1) * ((M + 1) / 3) +   (M / 3);
    }

    return ans;
}

        but it's wrong!!! I don't know how to solve it. thanks a lot

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

          I had a shitty greedy, this is what I did:

          Every time if the previous column in the same row is blank, and the same column in above 2 rows both are not filled, I fill this current cell.

          If the previous column is filled:

          1) If the above top 2 rows of current column is filled, do nothing.

          2) Else if the above row is not filled, fill this cell.

          3) Now if the above cell is filled, we check the previous column. If the row above in previous column is also filled, we don't fill the current cell(if it is the last row, we fill it), else we fill it.

          When I did this, it didn't pass the small dataset.

          Then I did the same thing for both, the given matrix, and transpose of the matrix because answer won't change since we have started filling in another way.

          Now I took max of both, and it passed the large data set too.

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

            thank you for you reply, but I have some doubts. I default the cells above the first row are all blank.

            Every time if the previous column in the same row is blank, and the same column in above 2 rows both are not filled, I fill this current cell.

            and

            2) Else if the above row is not filled, fill this cell.

            so the first row will be filled like this:

            xxxxxxxxxx

            Maybe I have some misunderstanding, very thanks

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

              I'm sorry for the confusion, you also have to check at each time that there isn't any consecutive 3 cells. So first row is filled like this -xxoxxoxxoxxo...

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

    How did you create a map of character frequencies for the dictionary words in C?

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

      Used C++ and a map that maps vector to int.

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

A: well-known problem, answer is (n-m)/(n+m).

B: I don't know the right way but I made a few observations and with a little help from oeis, I guessed the answer. Answer for (r,c) is same as (c,r). Assume r<=c. If r=1 or r=2, answer is r*(c-floor(c/3)). If r is a multiple of 3, answer is (2*r/3)*c, else the answer is r*c-floor((r*c)/3).

C: DP. Dp[i] is the number of ways to form the string till i. To find this, select some j<i and consider the string between these two indices. Check for how many words in the vocabulary, this string is an anagram of. Call that number X, then dp[i]=dp[i]+x*dp[j-1].

D: Did the small dataset only by checking all the subsets.

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

    How to prove answer for A is (n-m)/(n+m) ?

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

    Could u please tell me how did u get this formula about r and c in problem B. Thanks a lot!

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

      When r = 1:

      xxo xxo xxo ...

      When r = 2:

      xxo xxo xxo ...

      xxo xxo xxo ...

      When r > 3 and r % 3 == 0 or 1:

      Consider the following method:

      xxo xxo xxo ...

      oxx oxx oxx ...

      xox xox xox ...

      xxo xxo xxo ...

      When r > 3 and r % 3 == 2:

      xox xox xox ...

      xxo xxo xxo ...

      oxx oxx oxx ...

      xox xox xox ...

      xxo xxo xxo ...

      Here we permute the lines to assure that the leading columns filled with 'x' as many as possible.

      Then you can get the above formula.To prove the correctness,

      For every continous 3 grids we need to fill at least 1 'o',

      while the method we suggested can do exactly 1 'o' every 3 grids.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 4   Vote: I like it 0 Vote: I do not like it

        Thank u very much! I have got your idea,but one question here is.

        If i keep every 3 seats must have one 'o' in a line,and permute the 'o's position in different lines, why when r > 3 and r % 3 == 2 is:

        xox xox xox ...

        xxo xxo xxo ...

        oxx oxx oxx ...

        xox xox xox ...

        xxo xxo xxo ...

        Is it the same with?:

        xxo xxo xxo ...

        oxx oxx oxx ...

        xox xox xox ...

        xxo xxo xxo ...

        oxx oxx oxx ...

        which means does the first line can be xxo xxo ... form? they all have 15 'o'

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

          Take your same examples and take C = 10 (instead of 9 above) Then couunt the no. of X in both cases U will get the difference

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

          "Here we permute the lines to ensure that the leading columns filled with as many 'x' as possible."

          When r % 3 == 2, we only consider the last 2 lines. When the column number increase, we want to keep as many 'x's as possible.

          (i)

          xxo

          oxx

          when c = 1, number of 'x' is 1. when c = 2, 'x' is 3, c = 3, 'x' is 4.

          (ii)

          xox

          xxo

          when c = 1, number of 'x' is 2. when c = 2, 'x' is 3, c = 3, 'x' is 4.

          You can see when c = 1, the second one is better.

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

Can somebody tell me of how much order pass in Apac or Codejam. In Codeforces solution of 10^8 pass. However, I am not sure about how much complexity Apac allows. Please guide me in this as I thought my A would not pass large test cases but however it did.

So please tell me is it 10^8 computations in Apac too.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    There's nothing like that in code jam or apac as you have to post the output file rather than code. Your code will not be run by server like in CF. So basically it comes down to generating the output file on your pc using your code within the time limit ( 4 minutes from time of downloading input file to time of submitting i guess )

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      No, they take the source code so obviously they check the code on their cases too. Else 4 minutes is too much I guess. It may happen that many TLE solution may pass.

      Plz someone help over here.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        They check any similar codes to avoid copying. TL is dependent on your computer and 4min is very lenient but still enough to kill most suboptimal solutions.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Thanks a lot. And so Facebook Hacker Cup follows same procedure( of just checking output files ) or do they have limit on computation. Can you please tell this too?

          → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        source code is just for plaigarism check i or some other reason They dont run it themselves https://code.google.com/codejam/apactest/terms.html check rules 3-4-5-6 under 4.PROBLEMS section

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

Is there any other way to solve B-large , apart from formula ?

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

Problem D. large test case in detail anybody please

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    Let's dp[n][L] = the least money to create a rope of exactly size L

    then dp[n][L] = min(dp[n — 1][L — b[n]] -> dp[n — 1][L — a[n]] you can find the answer by using dequeue,

    Code

    → Reply