kostka's blog

Google Kick Start 2019 — round H
By kostka, 5 years ago, In English

You've got only one more chance to participate in Google Kick Start 2019, so don't miss it!

Round H will start this Sunday (November 17) at 05:00 UTC and will last 3 hours.

Get ready and register now at g.co/kickstart.

.

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

Comments Comments (30)
| Write comment?
»
5 years ago, # |
  Vote: I like it +21 Vote: I do not like it

The contest starts in just 10 hours!

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

    Editorials are available (click on the problem statement and click on the analysis tab).

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

Maybe this was already asked, but where can I see test cases? No idea where my solutions go wrong

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

How to solve 3rd problem-elevanagram?

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

    i just made the constraints smaller i.e. if ai>20 make ai=20 or 21 depending on ai-20 is even or odd respectively. rest is just digit dp

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

      I too solved it the same way. Now the question boils down to finding if the array elements can be divided into two subsets whose size is either equal(if total elements are even) or differ by 1(if total elements are odd) and their difference is divisble by 11.(Here array is formed by appending a digit as many times as it's frequency in input).

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

      why we need to reduce a[i] and how it is always correct.

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

        "Why" is clear. We can't do a dp on 10^9. I am not very sure but the proof of correctness relates to this case:

        11..111 21 times leads to divisibility by 11.

        Other occurrences of 1 can simply be reduced as two 1s can be put at places of different parity.

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

          Please elaborate.

          Not able to figure out the logic of writing down 22!

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

          The_Kings_Gambit actually 111..11 22 times is divisible by 11.

          so what you mean is, suppose we have 30 one's. so we can make it 20 and use 10 ones of + and — parity each which will cancel out.

          and suppose we have 31 one's, we replace it by 21 and use 10 ones of + and — parity each to cancel out each other. this way we reduced larger test data to smaller one, and do the same just what we did for test set 1.

          Am i right.

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

        Let's say we put digits which will be added on the left side, and the ones which will be subtracted on the right side. Now, for any i in [1, 9], given a[i] is greater than or equal to 20, we generate a list sums using i only.

        By placing some i's on the (+)left side and others on the (-)right side. For example i = 2, and a[i] = 3. Sums list will be as follows:

        1. | 2 2 2 -> -2 -2 -2 = -6
        2. 2 | 2 2 -> +2 -2 -2 = -2
        3. 2 2 | 2 -> +2 +2 -2 = +2
        4. 2 2 2 | 0 -> +2 +2 +2 = +6

        Now, if a[i] >= 20, then for each j in [0, 10] there will exist a value in sums such that value%11 == j. And, [0, 10] is nothing but range of (any number)%11.

        Let's take an example where i = 1, and a[i] = 20.

        Sums will be: [0, 2, 4, 8, 10, 12, 14, 16, 18, 20]

        Sums%11: [0, 2, 4, 8, 10, 1, 3, 5, 7, 9], which basically covers all numbers in range [0, 10].

        And, since we only care about sums modulo 11, we therefore have covered all the possible sums. Hence we can reduce a[i] to 20 or 21 on the basis of their parity

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

          Thanks a lot, very well explained. :)

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

          What if i equals 11 and assume ai as 20? then sum % 11 will be always 0.

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

            i ranges from [1, 9], and 11 is not a digit

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

      How will this always be correct, it there any property or some observation I missed out on?

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

    The intended solution should be DP, but I get it passed by randomly generating numbers and check whether it is divisible... (The order doesn't matter so I only generate the frequency of each number in odd/even positions)

    Anyone wants to hack?

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

      How you generated them randomly?

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

How to solve the 2nd Problem fully?

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

    Create a graph where each node is a diagonal. See the problem as coloring the nodes with black and white (Black means we are using the diagonal. White means not using.) Then we want the graph to have a minimum number of black nodes.

    Suppose we have a grid that is black, and it can be changed by two diagonals $$$A$$$ and $$$B$$$. Then in the final coloring $$$A$$$ and $$$B$$$ should be in the same color. If the grid is white, then $$$A$$$ and $$$B$$$ should be in different color. Then we can do something similar to bipartite graph checking to color the graph, and take the minimum of two colors in each connected component.

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

      Can you please explain the bipartite check part a little more?

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

        I guess my code can explain it better than myself: code

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

    although I didn't solve it, I think below solution is right. since till the end I found the bug that doesn't separate odd/even two part.

    first separate graph into odd/even diag-part, i.e. (i+j)&1?

    note for one graph, there are exactly two ways to flip, since once some diag decided, can deduce others. so you can use dfs or two_sat to get the cnt(=how many diags choosen to flip), then result = min(cnt, N-cnt). where N=#diags of that part graph.

    final result is sum of two part.

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

    I just brute forced for diagonals of the same length (starting with the longest) with bitmasks and then recursed. There is always some field that is not touched by smaller length diagonals, so one can prune some states early.

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

    I did it like this:

    1. brute-force whether to "flip" values at 2 upper-left "/-diagonals": 1st diagonal is (0,0), 2nd diagonal is (1,0) and (0,1) (there will be 2*2==4 choices).

    2. Depending on cell (0,0), flip "\-diagonal" (0,0), (1,1), ... , (N-1, N-1) (main diagonal)

    3. Depending on cell (1,0), flip "\-diagonal" (1,0), (2,1), ... , (N-1, N-2) (1-below main diagonal).

    4. Depending on other cells (not (0,0) or (1,0)) cells, flip "/-diagonal" that contains (i, i) or (i+1, i).

    5. Depending on values in (2, 0), (3, 0), ... (N-1, 0), flip "\-diagonals" that contain (i+2, 0) (below 1-below main diagonals)

    6. Depending on values in (0, 1), (0, 2), ..., flip "\-diagonals" that contain (0, i+1) (above main diagonals)

    7. Check that you have all '#'s, update result

    Overall complexity: $$$O(4\times N^2) = O(N^2)$$$

    However, I've seen other simpler solution:

    1. brute-force whether to flip "\-diagonal" (0,0), (1,1), ... , (N-1, N-1) (main diagonal) and "\-diagonal" (1,0), (2,1), ... , (N-1, N-2) (1-below main diagonal) (still 2*2 == 4 choices)

    2. Depending on value in cell (i, i) or (i+1, i), flip "/-diagonal" that contains this cell

    3. Either flip or don't flip all other "\-diagonals" (just like steps 4., 5. in previous solution).

    4. Check that you have all '#'s, update result.

    Complexity: still $$$O(N^2)$$$

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

why 3rd was easier than 2nd. 2nd was quite hard. it should be 3rd. wated a lot of time. tried with queue but it gave MLE.

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

    i used masking for one direction diagonal and after applying operations in one direction,check for other direction diagonal whether it is possible to do operations to make grid complete black.

    As for one diagonal we can do operations either 0 or 1 time that's why masking

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

When will they enable submit button for practice?

Edit : It's working now.

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

In the second problem by reducing the frequency of digit how we are making sure that the number of terms going to even side and the odd side are the same or (odd — 1 == even)?

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

The Analysis of Problem 2 (Diagonal Puzzle) says the following:

One interesting observation is that if we decide whether we would flip the two largest diagonals or not, we can pick all other diagonals to flip deterministically. There are four choices for flipping/not flipping the largest two diagonals. And for each of these choices, we can go through all other diagonals in the grid. For each of these other diagonals, we can check if the cell where it intersected with one of the largest diagonals is white. If it's white, we need to flip this diagonal, otherwise not. For each of those four combinations of the largest diagonal flips, if after all the flips(both largest two diagonals and others), the final state has all black cells, then we have a possible answer, otherwise not. We take the minimum flips of the four possible choices.

I am assuming that the two longest diagonals are Major and Minor. So, there will be diagonals which won't intersect with both major and minor diagonals at a particular cell. For example take the following grid:

3
.*.
*.. 
...

Here, the diagonal in *[(0, 1), (1, 0)], neither intersects with the major diagonal or the minor diagonal, at a particular cell. Although, it does intersect with the major diagonal but not at a particular cell.

And, the analysis clearly mentions, the following: For each of these other diagonals, we can check if the cell where it intersected with one of the largest diagonals is white But, it is clear from the above example, that there will be some diagonals which won't have a common cell of intersection.

Therefore, I am not sure as to how will the above approach work.

→ Reply