Блог пользователя kostka

Автор kostka, 5 лет назад, По-английски

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.

 .

  • Проголосовать: нравится
  • +51
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

The contest starts in just 10 hours!

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

How to solve 3rd problem-elevanagram?

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

    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

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +2 Проголосовать: не нравится

      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).

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        "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.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

          Please elaborate.

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

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

          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.

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

        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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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?

»
5 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

How to solve the 2nd Problem fully?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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)$$$

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +16 Проголосовать: не нравится

When will they enable submit button for practice?

Edit : It's working now.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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)?

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

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.