lucifer1004's blog

My Editorial for Google Kick Start 2021 Round A
By lucifer1004, 4 years ago, In English

Google Kick Start 2021 Round A Tutorial

中文版 | Chinese version

Problem A — K-Goodness String

First, we need to calculate the current score $$$K_c$$$. Since in one operation we can increase or decrease the score by $$$1$$$, the answer is $$$|K_c-K|$$$.

  • Time complexity is $$$\mathcal{O}(|S|)$$$.
  • Space complexity is $$$\mathcal{O}(1)$$$.
Code (C++)

Problem B — L Shaped Plots

First, we calculate the length of longest continuous $$$1$$$ starting from each cell via simple dynamic programming, namely, $$$W[i][j]$$$, $$$E[i][j]$$$, $$$N[i][j]$$$ and $$$S[i][j]$$$.

Then we enumerate each cell and count the L-shaped plots centering at the cell. There are four types of L-shaped plots considering the orientation:

  • WN
  • WS
  • EN
  • ES

And for each type, we need to consider which side to be the longer side.

  • Time complexity is $$$\mathcal{O}(RC)$$$.
  • Space complexity is $$$\mathcal{O}(RC)$$$.
Code (C++)

Problem C — Rabbit House

Obviously, the highest cell should not be increased. With this insight, we can solve this problem in a Dijkstra-like manner.

We use a max-heap to store the cells to be processed. When we process a cell with height $$$h$$$, we need to ensure that all its neighbors are at least as high as $$$h-1$$$. If the height of any of its neighbors is increased, then we should enqueue that cell with the new height.

In the end, we accumulate the difference between each cell's final height and original height to get the answer.

  • Time complexity is $$$\mathcal{O}(RC\log(RC))$$$.
  • Space complexity is $$$\mathcal{O}(RC\log(RC))$$$.
Code (C++)

Problem D — Checksum

The hardest part of this problem is to recognize that it is actually a Minimum Spanning Tree (actually Maximum Spanning Tree, but they are equivalent) problem.

The first observation is that we can consider the known numbers to be unknown with a cost of $$$0$$$, and solve an equivalent problem in which all numbers are unknown.

The second observation is that we need to check exactly $$$(N-1)^2$$$ cells for a $$$N\times N$$$ matrix:

  • If we check fewer than $$$(N-1)^2$$$, then at least $$$2N$$$ cells are unknown, while we can induce at most $$$2N-1$$$ cells.
  • If we check more than $$$(N-1)^2$$$, then there is at least a row/column whose cells are all checked, which is unnecessary.

Now, instead of determining the $$$(N-1)^2$$$ cells to be checked, we try to determine the $$$2N-1$$$ cells which are induced. We want the sum of their costs to be maximized so that the sum of the checked cells can be minimized.

An insight is that, if we consider the $$$N$$$ rows and $$$N$$$ columns to be nodes, and the cells to be undirected edges (cell $$$(i,j)$$$ is considered to be an edge $$$r_i\leftrightarrow c_j$$$), then there will be exactly $$$2N$$$ nodes, while we need to choose $$$2N-1$$$ edges from all edges such that the sum of their weights is maximized. Very close to MST!

To confirm that it is exactly MST, we need to check whether loops are allowed. Since there are no edges that connect two rows or two columns, a loop must be in the form $$$r_0\leftrightarrow c_0\leftrightarrow r_1\leftrightarrow c_1\cdots\leftrightarrow r_0$$$. If a loop occurs, then all the rows and columns in this loop would have at least two unknown cells, which is unsolvable.

So we need to choose $$$2N-1$$$ edges in a graph with $$$2N$$$ nodes and loops are not allowed. Now we are confirmed that this is an MST.

The MST part is quite trivial, both Kruskal and Prim can work fluently.

  • Time complexity is $$$\mathcal{O}(N^2\log N)$$$ for Kruskal, and $$$\mathcal{O}(N^2)$$$ for Prim (since it is a dense graph).
  • Space complexity is $$$\mathcal{O}(N^2)$$$.
Code (C++)
  • Vote: I like it
  • +99
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
»
4 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

In Problem D Suppose we have $$$5*5$$$ matrix with values :

matrix

Suppose last three columns have known values and suppose in first two column we know only the value of x12 . Thus total $$$3*5+1 = 16 = (5-1)^2$$$ values are known . Now except $$$x11$$$ how other values are induced ?

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

    There are loops in your example, so it is invalid.

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

      I have taken arbitrary matrix , value xij can be 0 or 1 . Just we know some of those value (last three columns and x12) . How it's invalid ? I don't see any "loop" word in problem. If you mean two x41 , i corrected it , xij are just notation to denote a cell .

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

        All known numbers can be seen as unknown with a cost of $$$0$$$, as I said in my editorial.

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

          Ok, so after finding the edges in the maximum spanning tree of the graph, will we be adding the weights of edges not included in max. spanning tree to give the answer?

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

            Yes, the answer is the total cost minus the cost of the maximum spanning tree.

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

having done this problem really helped :P

though I fkd up it in a hurry and used queue instead of PQ only to realize it at the very end of the contest.

Thanks for the solution, I have learned a lot from your blogs/post!!

hey lucifer1004 , one doubt

why using
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
gives error

error: 'std::tuple<int, int, int> <structured bindings>' has incomplete type
    auto [h, i, j] = pq.top();

but 
#include<bits/stdc++.h>
works??
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There might be some OS differences. During the contest, I used a lot of includes and I cleaned them up after the contest. But the sanitized version has only been tested on my Mac, so there might be some issues on other OS.

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

      These are results from the contest judge, I tested these in the practice round, I guess some additional header is needed for structural binding.

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

Can somebody tell, the intuition of making graph with row and col(i was thinking to make with each cell in same row and col but edges were becoming too high) in question 4(checksum). How to think that intuitively. or tell the question which are related to this idea.

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

    My take, from what I can make of it so far :

    1. To recap, the goal is to break cycles of -1's at a minimal cost. This is done by finding the maximum spanning tree in a given array where A[i][j] = -1 and by restoring all other -1's at their given cost B[i][j]
    2. Maximum/Minimum spanning trees are implemented using Data Set Unions (DSU's)
    3. DSU's are implemented via 1D arrays. Here we have a 2D array so how do we bridge this gap?
    4. Each cell can be seen as the intersection of a (unique) combination of a row and column
    5. In this problem, each unknown value (i.e. A[i][j] == -1) uniquely corresponds to row (i) and column (j)
    6. Instead of thinking about this in 2D, consider flattening out the 2D array to a 1D (since DSU operates on 1D)
    7. Then, each cell, A[i][j], would become A[i*N + j] where N is the number of columns, and there would now only be one row (by definition since its 1D)
    8. A[i*N + j] is the equivalent of a DSU union of (i + N, j)
    9. So the overall mapping is: A[i][j] -> A[i*N + j] -> DSU union (i + N, j)
    10. (i + N, j) is the equivalent of connecting row (i + N) to column j
    11. So we are effectively drawing out two separate sets of Rows and Columns (given that they are all uniquely numbered now), and connecting across them during the merge. Note that the merge never connects one row to another row, or a column to another column, always a row to a column.
    → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In problem C, can't we use multisource bfs?

We start with all the cell having height = max.

We check all its neighbours should have max — 1 height, if not increase their height and add diff in ans.

Once we reach a level end, we decrease max by 1. and keep going.

Can anyone suggest what is flow in this? https://pastebin.com/ECG6iBZX

→ Reply