Amedeo
SYMBIOSYS OF
PURPOSE & STYLE
Follow us

Search

ekusiadadus
  -  Programming   -  Competitive Programming   -  Google Kickstart 2021 Round A Solutions
kickstart2021A

Google Kickstart 2021 Round A Solutions

K-Goodness String

Problem

Charles defines the goodness score of a string as the number of indices ii such that Si≠SN−i+1Si≠SN−i+1 where 1≤i≤N/21≤i≤N/2 (11-indexed). For example, the string CABABC has a goodness score of 22 since S2≠S5S2≠S5 and S3≠S4S3≠S4.

Charles gave Ada a string SS of length NN, consisting of uppercase letters and asked her to convert it into a string with a goodness score of KK. In one operation, Ada can change any character in the string to any uppercase letter. Could you help Ada find the minimum number of operations required to transform the given string into a string with goodness score equal to KK?

Input

The first line of the input gives the number of test cases, TT. TT test cases follow.

The first line of each test case contains two integers NN and KK. The second line of each test case contains a string SS of length NN, consisting of uppercase letters.

Output

For each test case, output one line containing Case #xx: yy, where xx is the test case number (starting from 1) and yy is the minimum number of operations required to transform the given string SS into a string with goodness score equal to KK.

Limits

Memory limit: 1 GB.
1≤T≤1001≤T≤100.
0≤K≤N/20≤K≤N/2.

Test Set 1

Time limit: 20 seconds.
1≤N≤1001≤N≤100.

Test Set 2

Time limit: 40 seconds.
1≤N≤2×1051≤N≤2×105 for at most 1010 test cases.
For the remaining cases, 1≤N≤1001≤N≤100.

Sample

Sample Inputsave_altcontent_copy

2
5 1
ABCAA
4 2
ABAA

Sample Outputsave_altcontent_copy

Case #1: 0
Case #2: 1

In Sample Case #1, the given string already has a goodness score of 11. Therefore the minimum number of operations required is 00.

In Sample Case #2, one option is to change the character at index 11 to B in order to have a goodness score of 22. Therefore, the minimum number of operations required is 11.

Solution

#include<bits/stdc++.h>
using namespace std;

int main(){
    int t;
    cin >> t;
    for(int tt = 1; tt <= t; ++tt){
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        int ans = 0;
        for(int i = 0; i < s.size()/2; ++i){
            if(s[i] != s[s.size() - i - 1]) ans++;
        }
        cout << "Case #" << tt << ": " << abs(k-ans) << endl;
    }
    return 0;
}

L Shaped Plots

Problem

Given a grid of RR rows and CC columns each cell in the grid is either 00 or 11.

A segment is a nonempty sequence of consecutive cells such that all cells are in the same row or the same column. We define the length of a segment as number of cells in the sequence.

A segment is called “good” if all the cells in the segment contain only 11s.

An “L-shape” is defined as an unordered pair of segments, which has all the following properties:

  • Each of the segments must be a “good” segment.
  • The two segments must be perpendicular to each other.
  • The segments must share one cell that is an endpoint of both segments.
  • Segments must have length at least 22.
  • The length of the longer segment is twice the length of the shorter segment.

We need to count the number of L-shapes in the grid.

Below you can find two examples of correct L-shapes,

Examples of valid L-shapes.

and three examples of invalid L-shapes.

Examples of invalid L-shapes.

Note that in the shape on the left, two segments do not share a common endpoint. The next two shapes do not meet the last requirement, as in the middle shape both segments have the same length, and in the last shape the longer segment is longer than twice the length of the shorter one.

Input

The first line of the input contains the number of test cases, TT. TT test cases follow.

The first line of each testcase contains two integers RR and CC.

Then, RR lines follow, each line with CC integers representing the cells of the grid.

Output

For each test case, output one line containing Case #xx: yy, where xx is the test case number (starting from 1) and yy is the number of L-shapes.

Limits

Time limit: 60 seconds.
Memory limit: 1 GB.
1≤T≤1001≤T≤100.
Grid consists of 00s and 11s only.

Test Set 1

1≤R≤401≤R≤40.
1≤C≤401≤C≤40.

Test Set 2

1≤R≤10001≤R≤1000 and 1≤C≤10001≤C≤1000 for at most 55 test cases.
For the remaining cases, 1≤R≤401≤R≤40 and 1≤C≤401≤C≤40.

Sample

Sample Inputsave_altcontent_copy

2
4 3
1 0 0
1 0 1
1 0 0
1 1 0
6 4
1 0 0 0
1 0 0 1
1 1 1 1
1 0 1 0
1 0 1 0
1 1 1 0

Sample Outputsave_altcontent_copy

Case #1: 1
Case #2: 9

In Sample Case #1, there is one L-shape.

  • The first one is formed by using cells: (1,1)(1,1), (2,1)(2,1), (3,1)(3,1), (4,1)(4,1), (4,2)(4,2)
Visualization for the first sample case, showing one L-shape.

In Sample Case #2, there are nine L-shapes.

  • The first one is formed by using cells: (1,1)(1,1), (2,1)(2,1), (3,1)(3,1), (4,1)(4,1), (5,1)(5,1), (6,1)(6,1), (6,2)(6,2), (6,3)(6,3)
  • The second one is formed by using cells: (3,1)(3,1), (4,1)(4,1), (5,1)(5,1), (6,1)(6,1), (6,2)(6,2)
  • The third one is formed by using cells: (6,1)(6,1), (5,1)(5,1), (4,1)(4,1), (3,1)(3,1), (3,2)(3,2)
  • The fourth one is formed by using cells: (3,3)(3,3), (4,3)(4,3), (5,3)(5,3), (6,3)(6,3), (6,2)(6,2)
  • The fifth one is formed by using cells: (6,3)(6,3), (5,3)(5,3), (4,3)(4,3), (3,3)(3,3), (3,2)(3,2)
  • The sixth one is formed by using cells: (3,1)(3,1), (3,2)(3,2), (3,3)(3,3), (3,4)(3,4), (2,4)(2,4)
  • The seventh one is formed by using cells: (3,4)(3,4), (3,3)(3,3), (3,2)(3,2), (3,1)(3,1), (2,1)(2,1)
  • The eighth one is formed by using cells: (3,4)(3,4), (3,3)(3,3), (3,2)(3,2), (3,1)(3,1), (4,1)(4,1)
  • The ninth one is formed by using cells: (6,3)(6,3), (5,3)(5,3), (4,3)(4,3), (3,3)(3,3), (3,4)(3,4)

The first three L-shapes are shown on the picture below. 

Visualization for the second sample case, showing first three L-shapes.

Solution

#include<bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int t;
  cin >> t;
  for(int tt = 1; tt <= t; ++tt){
    int r,c;
    cin >> r >> c;
    vector<vector<int>> g(r, vector<int> (c,0));
    vector<vector<int>> gr(r, vector<int> (c,0));
    vector<vector<int>> grr(r, vector<int> (c,0));
    vector<vector<int>> gc(r, vector<int> (c,0));
    vector<vector<int>> gcc(r, vector<int> (c,0));

    for(int i = 0; i < r; ++i){
      for(int j = 0; j < c; ++j) {
        cin >> g[i][j];
      }
    }

    for(int i = 0; i < r; ++i){
      for(int j = 0; j < c; ++j){
        if(g[i][j] == 0) {
          gr[i][j] = 0;
          gc[i][j] = 0;
        }else{
          if(i == 0) gr[i][j] = 1;
          if(i != 0) gr[i][j] = gr[i-1][j] + 1;
          if(j == 0) gc[i][j] = 1;
          if(j != 0) gc[i][j] = gc[i][j-1] + 1;
        }
      }
    }

    for(int i = r-1; i >= 0; --i){
      for(int j = c-1; j >= 0; --j){
        if(g[i][j] == 0) {
          gr[i][j] = 0;
          gc[i][j] = 0;
        }else{
          if(i == r-1) grr[i][j] = 1;
          if(i != r-1) grr[i][j] = grr[i+1][j] + 1;
          if(j == c-1) gcc[i][j] = 1;
          if(j != c-1) gcc[i][j] = gcc[i][j+1] + 1;
        }
      }
    }
    long long ans = 0;

    for(int i = 0; i < r; ++i){
      for(int j = 0; j < c; ++j){
        if(gcc[i][j] >= 2) ans += max(0, min(gr[i][j]/2,gcc[i][j])-1);
        if(gc[i][j] >= 2) ans += max(0, min(gr[i][j]/2,gc[i][j])-1);
        if(gc[i][j] >= 2) ans += max(0, min(grr[i][j]/2,gc[i][j])-1);
        if(gcc[i][j] >= 2) ans += max(0, min(grr[i][j]/2,gcc[i][j])-1);
        if(gr[i][j] >= 2) ans += max(0, min(gc[i][j]/2,gr[i][j])-1);
        if(grr[i][j] >= 2) ans += max(0, min(gc[i][j]/2,grr[i][j])-1);
        if(grr[i][j] >= 2) ans += max(0, min(gcc[i][j]/2,grr[i][j])-1);
        if(gr[i][j] >= 2) ans += max(0, min(gcc[i][j]/2,gr[i][j])-1);
      }
    }
    cout << "Case #" << tt << ": " << ans << endl;
  }

  return 0;
}

Rabbit House

Problem

Barbara got really good grades in school last year, so her parents decided to gift her with a pet rabbit. She was so excited that she built a house for the rabbit, which can be seen as a 2D grid with RR rows and CC columns.

Rabbits love to jump, so Barbara stacked several boxes on several cells of the grid. Each box is a cube with equal dimensions, which match exactly the dimensions of a cell of the grid.

However, Barbara soon realizes that it may be dangerous for the rabbit to make jumps of height greater than 11 box, so she decides to avoid that by making some adjustments to the house. For every pair of adjacent cells, Barbara would like that their absolute difference in height be at most 11 box. Two cells are considered adjacent if they share a common side.

As all the boxes are superglued, Barbara cannot remove any boxes that are there initially, however she can add boxes on top of them. She can add as many boxes as she wants, to as many cells as she wants (which may be zero). Help her determine what is the minimum total number of boxes to be added so that the rabbit’s house is safe.

Input

The first line of the input gives the number of test cases, TT. TT test cases follow.

Each test case begins with a line containing two integers RR and CC.

Then, RR lines follow, each with CC integers. The jj-th integer on ii-th line, Gi,jGi,j, represents how many boxes are there initially on the cell located at the ii-th row and jj-th column of the grid.

Output

For each test case, output one line containing Case #xx: yy, where xx is the test case number (starting from 1) and yy is the minimum number of boxes to be added so that the rabbit’s house is safe.

Limits

Memory limit: 1 GB.
1≤T≤1001≤T≤100.
0≤Gi,j≤2⋅1060≤Gi,j≤2⋅106, for all ii, jj.

Test Set 1

Time limit: 20 seconds.
1≤R,C≤501≤R,C≤50.

Test Set 2

Time limit: 40 seconds.
1≤R,C≤3001≤R,C≤300.

Sample

Sample Inputsave_altcontent_copy

3
1 3
3 4 3
1 3
3 0 0
3 3
0 0 0
0 2 0
0 0 0

Sample Outputsave_altcontent_copy

Case #1: 0
Case #2: 3
Case #3: 4

In Sample Case #1, the absolute difference in height for every pair of adjacent cells is already at most 11 box, so there is no need to add any extra boxes.

In Sample Case #2, the absolute difference in height of the left-most cell and the middle cell is 33 boxes. To fix that, we can add 22 boxes to the middle cell. But then, the absolute difference of the middle cell and the right-most cell will be 22 boxes, so Barbara can fix that by adding 11 box to the right-most cell. After adding these 33 boxes, the safety condition is satisfied.

In Sample Case #3, the cell in the middle of the grid has an absolute difference in height of 22 boxes with all of its four adjacent cells. One solution is to add exactly 11 box to all of the middle’s adjacent cells, so that the absolute difference between any pair of adjacent cells will be at most 11 box. That requires 44 boxes in total.

Solution

#include<bits/stdc++.h>
using namespace std;

int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int t;
  cin >> t;
  for(int tt = 1; tt <= t; ++tt){
    int r, c;
    cin >> r >> c;
    vector<vector<int>> g(r, vector<int>(c,0));
    priority_queue<pair<int,pair<int,int>>> q;
    for(int i = 0; i < r; ++i){
      for(int j = 0; j < c; ++j) {
        cin >> g[i][j];
        q.push(make_pair(g[i][j],make_pair(i,j)));
      }
    }
    long long ans = 0;
    while(!q.empty()){
      int x,y;
      x = q.top().second.first;
      y = q.top().second.second;
      q.pop();
      int v = g[x][y];
      int m = 0;
      for(int i = 0; i < 4; ++i){
        if(x+dx[i] >= r || y+dy[i] >= c || x+dx[i] < 0 || y+dy[i] < 0) continue;
        if(g[x+dx[i]][y+dy[i]] > v-1){
          m = max(m,g[x+dx[i]][y+dy[i]]);
      }
      }
      if(m > v+1){
        ans += m-v;
        g[x][y] = m;
      }
      v = g[x][y];
      for(int i = 0; i < 4; ++i){
        if(x+dx[i] >= r || y+dy[i] >= c || x+dx[i] < 0 || y+dy[i] < 0) continue;
        if(g[x+dx[i]][y+dy[i]] < v-1){
          ans += v-1-g[x+dx[i]][y+dy[i]];
          g[x+dx[i]][y+dy[i]] = v-1;
          q.push(make_pair(g[x+dx[i]][y+dy[i]],make_pair(x+dx[i], y+dy[i])));
        }
      }
    }
    cout << "Case #" << tt << ": " << ans << endl;
  }
  return 0;
}

Checksum

Problem

Grace and Edsger are constructing a N×NN×N boolean matrix AA. The element in ii-th row and jj-th column is represented by Ai,jAi,j. They decide to note down the checksum (defined as bitwise XOR of given list of elements) along each row and column. Checksum of ii-th row is represented as RiRi. Checksum of jj-th column is represented as CjCj.

For example, if N=2N=2, A=[1101]A=[1011], then R=[10]R=[10] and C=[01]C=[01].

Once they finished the matrix, Edsger stores the matrix in his computer. However, due to a virus, some of the elements in matrix AA are replaced with −1−1 in Edsger’s computer. Luckily, Edsger still remembers the checksum values. He would like to restore the matrix, and reaches out to Grace for help. After some investigation, it will take Bi,jBi,j hours for Grace to recover the original value of Ai,jAi,j from the disk. Given the final matrix AA, cost matrix BB, and checksums along each row (RR) and column (CC), can you help Grace decide on the minimum total number of hours needed in order to restore the original matrix AA?

Input

The first line of the input gives the number of test cases, TT. TT test cases follow.

The first line of each test case contains a single integer NN.

The next NN lines each contain NN integers representing the matrix AA. jj-th element on the ii-th line represents Ai,jAi,j.

The next NN lines each contain NN integers representing the matrix BB. jj-th element on the ii-th line represents Bi,jBi,j.

The next line contains NN integers representing the checksum of the rows. ii-th element represents RiRi.

The next line contains NN integers representing the checksum of the columns. jj-th element represents CjCj.

Output

For each test case, output one line containing Case #xx: yy, where xx is the test case number (starting from 1) and yy is the minimum number of hours to restore matrix AA.

Limits

Memory limit: 1 GB.
1≤T≤1001≤T≤100.
−1≤Ai,j≤1−1≤Ai,j≤1, for all i,ji,j.
1≤Bi,j≤10001≤Bi,j≤1000, for i,ji,j where Ai,j=−1Ai,j=−1, otherwise Bi,j=0Bi,j=0.
0≤Ri≤10≤Ri≤1, for all ii.
0≤Cj≤10≤Cj≤1, for all jj.
It is guaranteed that there exist at least one way to replace −1−1 in AA with 00 or 11 such that RR and CC as satisfied.

Test Set 1

Time limit: 20 seconds.
1≤N≤41≤N≤4.

Test Set 2

Time limit: 35 seconds.
1≤N≤401≤N≤40.

Test Set 3

Time limit: 35 seconds.
1≤N≤5001≤N≤500.

Sample

Sample Inputsave_altcontent_copy

3
3
1 -1 0
0 1 0
1 1 1
0 1 0
0 0 0
0 0 0
1 1 1
0 0 1
2
-1 -1
-1 -1
1 10
100 1000
1 0
0 1
3
-1 -1 -1
-1 -1 -1
0 0 0
1 1 3
5 1 4
0 0 0
0 0 0
0 0 0

Sample Outputsave_altcontent_copy

Case #1: 0
Case #2: 1
Case #3: 2

In Sample Case #1, A1,2A1,2 can be restored using the checksum of either 1-st row or 2-nd column. Hence, Grace can restore the matrix without spending any time to recover the data.

In Sample Case #2, Grace spends one hour to recover A1,1A1,1. After that, she can use checksums of 1-st row and 1-st column to restore A1,2A1,2 and A2,1A2,1 respectively. And then she can use checksum of 2-nd row to restore A2,2A2,2. Hence, Grace can restore the matrix by spending one hour.

In Sample Case #3, Grace can spend one hour to recover A1,1A1,1 and another hour to recover A2,2A2,2. After that, she can use checksum to restore the rest of the matrix. Hence, Grace can restore the matrix by spending two hours in total.

Solution

#include<bits/stdc++.h>
using namespace std;

class UnionFind {
  public:
  vector<int> par;
  vector<int> rank;
  vector<int> Size;

  UnionFind(int n) {
    for(int i = 0; i < n; ++i) {
      par.push_back(i);
      rank.push_back(0);
      Size.push_back(1);
    }
  }

  int root(int x) {
    if(par[x] == x) return x;
    else return par[x] = root(par[x]);
  }

  bool same(int x, int y) {
    return root(x) == root(y);
  }

  void unite(int x, int y) {
    x = root(x), y = root(y);
    if(x == y) return;
    if(rank[x] < rank[y]) {
      par[x] = y;
      rank[y]++;
      Size[y] += Size[x];
    }
    else {
      par[y] = x;
      if(rank[x] != rank[y]) rank[x]++;
      Size[x] += Size[y];
    }
  }

  long long size(int x) {
    return Size[root(x)];
  }
};

#include<bits/stdc++.h>
using namespace std;

int main(){
    int t;
    cin >> t;
    for(int tt = 1; tt <= t; ++tt){
        long long ans = 0;
        int n;
        cin >> n;
        vector<vector<int>> a(n, vector<int> (n,0));
        vector<vector<int>> b(n, vector<int> (n,0));
        vector<int> r(n);
        vector<int> c(n);

        vector<tuple<int, int, int>> g;

        UnionFind uf(2*n);

        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                cin >> a[i][j];
            }
        }
        ll s = 0;
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                cin >> b[i][j];
                s += b[i][j];
                g.emplace_back(b[i][j], i, n+j);
            }
        }

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

        sort(g.rbegin(), g.rend());

        ll remove = 0;
        
        for(auto [w, u, v] : g){
          if(uf.same(u,v)) continue;
          remove += w;
          uf.unite(u,v);
        }
        ans = s-remove;
        cout << "Case #" << tt << ": " << ans << endl;
        
    }
    return 0;
}
Leave a Comment