№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	166
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

Google Kick Start 2021 Round A Tutorial

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

#include <cstdio>
#include <iostream>

using namespace std;

template <typename T> void read(T &x) {
  x = 0;
  char c = getchar();
  T sig = 1;
  for (; !isdigit(c); c = getchar())
    if (c == '-')
      sig = -1;
  for (; isdigit(c); c = getchar())
    x = (x << 3) + (x << 1) + c - '0';
  x *= sig;
}

class Solution {
public:
  void solve(int case_num) {
    printf("Case #%d: ", case_num);
    int n, k;
    read(n), read(k);
    string s;
    cin >> s;
    int cnt = 0;
    for (int i = 0; i < n / 2; ++i) {
      if (s[i] != s[n - 1 - i])
        cnt++;
    }
    printf("%d\n", abs(cnt - k));
  }
};

int main() {
  int t;
  read(t);
  for (int i = 1; i <= t; ++i) {
    Solution solution = Solution();
    solution.solve(i);
  }
}

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:

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

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

template <typename T> void read(T &x) {
  x = 0;
  char c = getchar();
  T sig = 1;
  for (; !isdigit(c); c = getchar())
    if (c == '-')
      sig = -1;
  for (; isdigit(c); c = getchar())
    x = (x << 3) + (x << 1) + c - '0';
  x *= sig;
}

class Solution {
public:
  void solve(int case_num) {
    printf("Case #%d: ", case_num);
    int r, c;
    read(r), read(c);
    vector<vector<int>> m(r, vector<int>(c));
    for (int i = 0; i < r; ++i)
      for (int j = 0; j < c; ++j)
        read(m[i][j]);
    vector<vector<int>> W(r, vector<int>(c));
    vector<vector<int>> E(r, vector<int>(c));
    vector<vector<int>> N(r, vector<int>(c));
    vector<vector<int>> S(r, vector<int>(c));
    for (int i = 0; i < r; ++i) {
      for (int j = 0; j < c; ++j) {
        if (m[i][j]) {
          W[i][j] = 1;
          if (j >= 1)
            W[i][j] += W[i][j - 1];
        }
      }
      for (int j = c - 1; j >= 0; --j) {
        if (m[i][j]) {
          E[i][j] = 1;
          if (j + 1 < c)
            E[i][j] += E[i][j + 1];
        }
      }
    }
    for (int j = 0; j < c; ++j) {
      for (int i = 0; i < r; ++i) {
        if (m[i][j]) {
          N[i][j] = 1;
          if (i >= 1)
            N[i][j] += N[i - 1][j];
        }
      }
      for (int i = r - 1; i >= 0; --i) {
        if (m[i][j]) {
          S[i][j] = 1;
          if (i + 1 < r)
            S[i][j] += S[i + 1][j];
        }
      }
    }

    ll ans = 0;
    for (int i = 0; i < r; ++i)
      for (int j = 0; j < c; ++j) {
        ans += max(0, min(W[i][j], N[i][j] / 2) - 1);
        ans += max(0, min(W[i][j] / 2, N[i][j]) - 1);
        ans += max(0, min(W[i][j], S[i][j] / 2) - 1);
        ans += max(0, min(W[i][j] / 2, S[i][j]) - 1);
        ans += max(0, min(E[i][j], N[i][j] / 2) - 1);
        ans += max(0, min(E[i][j] / 2, N[i][j]) - 1);
        ans += max(0, min(E[i][j], S[i][j] / 2) - 1);
        ans += max(0, min(E[i][j] / 2, S[i][j]) - 1);
      }

    printf("%lld\n", ans);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  read(t);
  for (int i = 1; i <= t; ++i) {
    Solution solution = Solution();
    solution.solve(i);
  }
}

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

#include <cstdio>
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>

using namespace std;
using ll = long long;

template <typename T> void read(T &x) {
  x = 0;
  char c = getchar();
  T sig = 1;
  for (; !isdigit(c); c = getchar())
    if (c == '-')
      sig = -1;
  for (; isdigit(c); c = getchar())
    x = (x << 3) + (x << 1) + c - '0';
  x *= sig;
}

const int d[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

class Solution {
public:
  void solve(int case_num) {
    printf("Case #%d: ", case_num);
    int r, c;
    read(r), read(c);
    vector<vector<int>> g(r, vector<int>(c));
    priority_queue<tuple<int, int, int>> pq;
    for (int i = 0; i < r; ++i)
      for (int j = 0; j < c; ++j) {
        read(g[i][j]);
        pq.emplace(g[i][j], i, j);
      }
    vector<vector<int>> g0(g);
    while (!pq.empty()) {
      auto [h, i, j] = pq.top();
      pq.pop();
      if (h < g[i][j])
        continue;
      for (int k = 0; k < 4; ++k) {
        int ni = i + d[k][0], nj = j + d[k][1];
        if (ni < 0 || ni >= r || nj < 0 || nj >= c)
          continue;
        if (h - 1 > g[ni][nj]) {
          pq.emplace(h - 1, ni, nj);
          g[ni][nj] = h - 1;
        }
      }
    }

    ll ans = 0;
    for (int i = 0; i < r; ++i)
      for (int j = 0; j < c; ++j)
        ans += g[i][j] - g0[i][j];

    printf("%lld\n", ans);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  read(t);
  for (int i = 1; i <= t; ++i) {
    Solution solution = Solution();
    solution.solve(i);
  }
}

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

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

template <typename T> void read(T &x) {
  x = 0;
  char c = getchar();
  T sig = 1;
  for (; !isdigit(c); c = getchar())
    if (c == '-')
      sig = -1;
  for (; isdigit(c); c = getchar())
    x = (x << 3) + (x << 1) + c - '0';
  x *= sig;
}

class UnionFind {
  int n;
  vector<int> parent, size;

public:
  UnionFind(int n) {
    this->n = n;
    parent = vector<int>(n);
    size = vector<int>(n, 1);
    for (int i = 0; i < n; ++i)
      parent[i] = i;
  }

  int find(int idx) {
    if (parent[idx] == idx)
      return idx;
    return parent[idx] = find(parent[idx]);
  }

  void connect(int a, int b) {
    int fa = find(a), fb = find(b);
    if (fa != fb) {
      if (size[fa] > size[fb]) {
        parent[fb] = fa;
        size[fa] += size[fb];
      } else {
        parent[fa] = fb;
        size[fb] += size[fa];
      }
    }
  }
};

class Solution {
public:
  void solve(int case_num) {
    printf("Case #%d: ", case_num);
    int n;
    read(n);
    vector<vector<int>> a(n, vector<int>(n));
    vector<vector<int>> b(n, vector<int>(n));
    vector<int> r(n);
    vector<int> c(n);
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        read(a[i][j]);

    vector<tuple<int, int, int>> edges;
    ll tot = 0;
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j) {
        read(b[i][j]);
        tot += b[i][j];
        edges.emplace_back(b[i][j], i, n + j);
      }
    sort(edges.rbegin(), edges.rend());
    UnionFind uf(n * 2);

    for (int i = 0; i < n; ++i)
      read(r[i]);
    for (int i = 0; i < n; ++i)
      read(c[i]);

    ll remove = 0;
    for (auto [weight, u, v] : edges) {
      if (uf.find(u) == uf.find(v))
        continue;
      remove += weight;
      uf.connect(u, v);
    }

    printf("%lld\n", tot - remove);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  read(t);
  for (int i = 1; i <= t; ++i) {
    Solution solution = Solution();
    solution.solve(i);
  }
}

Комментарии (13)

Показать архивные | Написать комментарий?

rananjay23

4 года назад, # |

← Rev. 4 →

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

matrix

x11 x12 x13 x14 x15
x21 x22 x23 x24 x25
x31 x32 x33 x34 x35
x41 x42 x43 x44 x45
x51 x52 x53 x54 x55

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

→ Ответить

lucifer1004

4 года назад, # ^ |

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

← Rev. 2 →

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 .

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

aknov711

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?

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

forcdc

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

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.

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

Fixed. Should include tuple instead of algorithm.

_manvirag

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.

sh_maestro

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

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]
Maximum/Minimum spanning trees are implemented using Data Set Unions (DSU's)
DSU's are implemented via 1D arrays. Here we have a 2D array so how do we bridge this gap?
Each cell can be seen as the intersection of a (unique) combination of a row and column
In this problem, each unknown value (i.e. A[i][j] == -1) uniquely corresponds to row (i) and column (j)
Instead of thinking about this in 2D, consider flattening out the 2D array to a 1D (since DSU operates on 1D)
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)
A[i*N + j] is the equivalent of a DSU union of (i + N, j)
So the overall mapping is: A[i][j] -> A[i*N + j] -> DSU union (i + N, j)
(i + N, j) is the equivalent of connecting row (i + N) to column j
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.

pribic

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

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

Google Kick Start 2021 Round A Tutorial

Problem A — K-Goodness String

Problem B — L Shaped Plots

Problem C — Rabbit House

Problem D — Checksum