My Editorial for Google Kick Start 2020 Round D

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

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Problem A — Record Breaker

Implementation. Keep a record of the current maximum. Compare the current value to it, and also to the next number.

Time complexity is $$$O(N)$$$.

Code

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

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) {
    int n;
    read(n);
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
      read(a[i]);
    int ans = 0, hi = -1;
    for (int i = 0; i < n; ++i) {
      if (a[i] > hi && (i == n - 1 || a[i] > a[i + 1]))
        ans++;
      hi = max(hi, a[i]);
    }
    printf("Case #%d: %d\n", case_num, 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 B — Alien Piano

Simple DP. Enumerate all choices of the last step and the current step.

Time complexity is $$$O(P^2K)$$$, where $$$P=4$$$ in this problem.

Code

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

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) {
    int n;
    read(n);
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
      read(a[i]);
    vector<vector<int>> dp(n, vector<int>(4, n));
    for (int k = 0; k < 4; ++k)
      dp[0][k] = 0;
    for (int i = 1; i < n; ++i) {
      for (int last = 0; last < 4; ++last)
        for (int now = 0; now < 4; ++now) {
          if (now == last) {
            if (a[i] == a[i - 1])
              dp[i][now] = min(dp[i][now], dp[i - 1][last]);
            else
              dp[i][now] = min(dp[i][now], dp[i - 1][last] + 1);
          } else if (now > last) {
            if (a[i] > a[i - 1])
              dp[i][now] = min(dp[i][now], dp[i - 1][last]);
            else
              dp[i][now] = min(dp[i][now], dp[i - 1][last] + 1);
          } else {
            if (a[i] < a[i - 1])
              dp[i][now] = min(dp[i][now], dp[i - 1][last]);
            else
              dp[i][now] = min(dp[i][now], dp[i - 1][last] + 1);
          }
        }
    }
    int ans = n;
    for (int k = 0; k < 4; ++k)
      ans = min(ans, dp[n - 1][k]);
    printf("Case #%d: %d\n", case_num, 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 — Beauty of Tree

Inclusion-exclusion, DFS.

We need to find, for every node, the number of descendants has a distance that can be divided by $$$A$$$, and similar for $$$B$$$. This can be done during DFS if we keep a record of the current path.

After having $$$ca[i]$$$ and $$$cb[i]$$$, we can simply calculate how many times the current node will be counted, via inclusion-exclusion:

$$$t[i]=(ca[i]+cb[i])\cdot N-ca[i]\cdot cb[i]$$$

Then we add up all the results and divide it by $$$N^2$$$.

The total time complexity is $$$O(N)$$$.

Code

#include <cstdio>
#include <iostream>
#include <vector>
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 {
  int n, a, b;
  vector<vector<int>> adj;
  vector<int> pa, pb, ac, bc;
  void dfs(int u, vector<int> &path) {
    int l = path.size();
    if (l >= a)
      pa[u] = path[l - a];
    if (l >= b)
      pb[u] = path[l - b];
    path.emplace_back(u);
    ac[u] = 1, bc[u] = 1;
    for (int v : adj[u])
      dfs(v, path);
    path.pop_back();
    if (pa[u] > 0)
      ac[pa[u]] += ac[u];
    if (pb[u] > 0)
      bc[pb[u]] += bc[u];
  }

public:
  void solve(int case_num) {
    read(n), read(a), read(b);
    adj = vector<vector<int>>(n + 1);
    for (int i = 2; i <= n; ++i) {
      int v;
      read(v);
      adj[v].emplace_back(i);
    }
    pa = vector<int>(n + 1);
    pb = vector<int>(n + 1);
    ac = vector<int>(n + 1);
    bc = vector<int>(n + 1);
    vector<int> path;
    dfs(1, path);
    double ans = 0;
    for (int i = 1; i <= n; ++i) {
      ans += (double)(ac[i] + bc[i]) * n;
      ans -= (double)ac[i] * bc[i];
    }
    printf("Case #%d: %.12f\n", case_num, ans / n / n);
  }
};

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 — Locked Doors

I used a rather complicated algorithm leveraging monotonic stack, sparse table and binary search.

For each door, calculate the first door to its left having higher difficulty, and the first door to its right having higher difficulty. For simplicity, a door with infinite difficulty is added at either end. This part is done by monotonic stack in $$$O(N)$$$.

Then construct a sparse table for range maximum query in $$$O(N\log N)$$$.

In each query, on the $$$K_i$$$-th day, there will be $$$K_i-1$$$ opened doors. Some are to the left of the $$$S_i$$$-th room, while some are to the right. If there are $$$l$$$ opened doors to the left on the $$$K_i$$$-th day, there needs to be at least $$$f(l)$$$ opened doors to the right, so that the highest difficulty among the $$$f(l)$$$ doors to the right is higher than the highest difficulty among the $$$l$$$ doors to the left. An observation is that $$$l+f(l)$$$ is monotonic. So the suitable $$$l$$$ can be found via binary search.

The last step is to determine whether we should use the leftmost room or the rightmost room. This can be done by comparing the highest difficulty of the doors to the left and those to the right. If the highest difficulty is to the left, then on the $$$K_i$$$-th day we must be in the leftmost room, otherwise rightmost.

The total time complexity is $$$O((N+Q)\log N)$$$.

Code

#include <cmath>
#include <cstdio>
#include <iostream>
#include <stack>
#include <vector>
#define INF 0x3f3f3f3f;
#define K 18

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) {
    int n, q;
    read(n), read(q);
    vector<int> a(n + 1);
    for (int i = 1; i <= n - 1; ++i)
      read(a[i]);
    a[0] = INF;
    a[n] = INF;
    printf("Case #%d: ", case_num);
    vector<int> lf(n + 1, -1), rf(n + 1, n + 1);
    vector<vector<int>> sparse(n + 1, vector<int>(K));
    for (int i = 0; i <= n; ++i)
      sparse[i][0] = i;
    for (int k = 1; k < K; ++k) {
      for (int i = 0; i <= n; ++i) {
        sparse[i][k] = sparse[i][k - 1];
        int right = i + (1 << (k - 1));
        if (right <= n && a[sparse[right][k - 1]] > a[sparse[i][k]])
          sparse[i][k] = sparse[right][k - 1];
      }
    }
    auto query_sparse = [&](int l, int r) {
      if (l == r)
        return l;
      int len = r - l + 1;
      int half = trunc(log2(len - 1));
      int ans = sparse[l][half];
      if (a[sparse[r - (1 << half) + 1][half]] > a[ans])
        ans = sparse[r - (1 << half) + 1][half];
      return ans;
    };
    stack<int> st;
    for (int i = 0; i <= n; ++i) {
      while (!st.empty() && a[st.top()] < a[i]) {
        rf[st.top()] = i;
        st.pop();
      }
      st.push(i);
    }
    st = stack<int>();
    for (int i = n; i >= 0; --i) {
      while (!st.empty() && a[st.top()] < a[i]) {
        lf[st.top()] = i;
        st.pop();
      }
      st.push(i);
    }
    while (q--) {
      int s, k;
      read(s), read(k);

      auto output = [&](int ans) {
        printf("%d ", ans);
      };

      if (rf[s - 1] - (s - 1) > k - 1) {
        int ans = s + k - 1;
        if (ans > n)
          ans = n - k + 1;
        output(ans);
        continue;
      }
      if (s - lf[s] > k - 1) {
        int ans = s - k + 1;
        if (ans < 1)
          ans = k;
        output(ans);
        continue;
      }
      int l = 1, r = min(k - 2, s);
      while (l <= r) {
        int mid = (l + r) >> 1;
        int ma = query_sparse(s - mid, s - 1);
        int right = rf[ma];
        int tot = right - (s - mid);
        if (tot > k - 1)
          r = mid - 1;
        else
          l = mid + 1;
      }
      int lmost = s - r;
      int rmost = s - r + k - 2;
      int ans;
      if (rmost > n)
        ans = n - k + 1;
      else {
        int hi = query_sparse(lmost, rmost);
        if (hi >= s)
          ans = rmost + 1;
        else
          ans = lmost;
      }
      output(ans);
    }
    printf("\n");
  }
};

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);
  }
}

Heltion's Cartesian tree solution.

Code

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
constexpr int maxn = 240000;
int D[maxn], S[maxn], L[maxn], R[maxn], H[maxn];
int RL[maxn], RR[maxn];
int SZ[maxn], F[maxn][20];
void DFS(int u){
    SZ[u] = u & 1;
	if(u & 1) RL[u] = RR[u] = (u + 1) / 2;
    for(int i = 1; i < 20; i += 1) F[u][i] = F[F[u][i - 1]][i - 1];
    if(~L[u]){
        F[L[u]][0] = u;
        DFS(L[u]);
        SZ[u] += SZ[L[u]];
		RL[u] = RL[L[u]];
    }
    if(~R[u]){
        F[R[u]][0] = u;
        DFS(R[u]);
        SZ[u] += SZ[R[u]];
		RR[u] = RR[R[u]];
    }
}
void work(){
    int N, Q;
    cin >> N >> Q;
    for(int i = 1; i < N; i += 1) cin >> D[i];
    for(int i = 1; i < 2 * N; i += 1){
        L[i] = R[i] = -1;
        if(i & 1) H[i] = 0;
        else H[i] = D[i / 2];
    }
    for(int i = 1, top = 0; i < 2 * N; i += 1){
        int k = top;
        while(k and H[S[k]] < H[i]) k -= 1;
        if(k) R[S[k]] = i;
        if(k < top) L[i] = S[k + 1];
        S[k += 1] = i;
        top = k;
    }
    int root = max_element(H + 1, H + 2 * N) - H;
    F[root][0] = 0;
    DFS(root);
    SZ[0] = INT_MAX;
	//for(int i = 1; i < 2 * N; i += 1) cout << i << " " << L[i] << " " << R[i] << "\n";
    for(int i = 0, S, K, X; i < Q; i += 1){
        cin >> S >> K;
        if(K == 1) cout << S << " ";
        else{
            X = S * 2 - 1;
            for(int j = 19; ~j; j -= 1) if(SZ[F[X][j]] < K) X = F[X][j];
			int L = RL[X], R = RR[X];
			//cout << "\nX = " << X << " " << L << " " << R << "\n";
			if(L == 1) cout << K;
			else if(R == N) cout << N - K + 1;
			else if(D[L - 1] > D[R]) cout << L + K - 1;
			else cout << R - K + 1;
			cout << " ";
        }
    }
    cout << "\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;
    cin >> T;
    for(int t = 1; t <= T; t += 1){
        cout << "Case #" << t << ": ";
        work();
    }
    return 0;
}

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

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

kartik8800

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

← Rev. 4 →

+12

For those who might be interested, here is my O(N) solution to beauty of tree: code

dp[i][0]: number of nodes in the subtree of node i such that they are at a distance of 0, a, 2a, 3a.... from node i.
dp[i][1]: number of nodes in the subtree of node i such that they are at a distance of 0, b, 2b, 3b.... from node i.

I will be adding a detailed video explanation on my YT channel by tonight and will add link in this comment :)

Video Explanation: Well detailed Explanation
Have added timestamps in a comment to save you some time.

→ Ответить

darkworld1

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

I used LCA for doing this question, but this question has a much simpler solution.;)

Shashank_Chugh

Were you able to do the complete task using LCA ?

Yes, I use dp[nod] which tell me how many child is at ath distance from the current node. so the transition is dp[node] += d[child at ath distance] , so for finding ath node i use LCA .

Can you please share your kickstart handle, so that I can refer to your submission ?

← Rev. 2 →

Link is redirecting to Indian ranklist , just tell your username I will find by myself

try again

blank_manash

In Problem Beauty,

Can You explain why are we adding the probabilities ? From what I know about expectations is that the answer should be,

$$$\sum_{i=0}^{n} i*P(i)$$$

Where $$$P(i)$$$ is the probability of $$$i$$$ number of nodes being selected,

How is the sum of all the probabilities of number of times each node occurs is equivalent to the above expression ?

I have explained this part quite in detail in my video from 08:00 to 12:00.

anubhavp

← Rev. 3 →

You should look for "Linearity of Expectation". The number of nodes selected ($$$X$$$) can be written as summation of all $$$X_i$$$ where $$$X_i$$$ is an indicator variable (1 if node $$$i$$$ is selected otherwise 0). Therefore, E($$$X$$$) = Summation of all E($$$X_i$$$)

Harshil_

You can solve B easily without DP.

Just keep track of how long the increasing or decreasing subarray you got and if it's length is more than 4 then increment your answer.

Here is my code. Here cnt1 is for increasing and cnt2 is for decreasing subarray'slength.

Spoiler

    int ans = 0,cnt1 = 1,cnt2 = 1;
    for(int i = 1; i < k; i++){
        if( a[i - 1] < a[i] ){
            cnt1++;
            cnt2 = 1;
        }
        else if(a[i - 1] > a[i]){
            cnt2++;
            cnt1 = 1;
        }
        if(cnt1 > 4 || cnt2 > 4){
            cnt1 = cnt2 = 1;
            ans++;
        }
    }
    cout << ans << '\n' ;

iharshit009

← Rev. 5 →

Please look over my code, I could not find out which cases I am missing, Is my logic correct?

I think your code will give 0 on the below test case while the answer should be 1.

Test Case

Jake1617

Hi i am still unable understand prob 2 correctly. If we have to find when the aliens piano goes out of sequence we do ans++,but in the first test case it is 1,5,100,500,1. Why doesn't we add ans++ when at last element i.e. 1 since it decreases from the current increasing sequence....

Suppose Alien piano has four notes A,B,C and D.

These notes pitches are in increasing order. A < B < C < D.

Now we can assign this four notes in the below order.

1,5,100,500,1

A, B, C, D, C

other possible orders

A, B, C, D, B

A, B, C, D, A

In above all orders answer will be 0.

Oo....so if there were 600 at last position, that would give us a break of sequence....and thus ans = 1....

Yes. You are right.

Lelouch.Lamperouge

A neater solution to problem C(Beauty of tree) :

AC-SOLUTION

// credits William Lin 
#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define int long long 
#define ar array 
#define pb push_back 
#define vi vector
#define FOR(i,n) for(int i=0;i<n;i++)
const long mxN =5e5+2 ;
vi<int> adj[mxN] ;ld ans=0 ;
int n,ca[mxN],cb[mxN],a,b;
void dfs(int v=0,int p=-1,int d=0){
  int la = ca[d%a],lb=cb[d%b];
  ca[d%a]++;cb[d%b]++ ;
  for(int x:adj[v])
    if(x^p)
      dfs(x,v,d+1);
  int na = n-(ca[d%a]-la),nb = n-(cb[d%b]-lb);
  ans+=1.0-na*nb/(ld)n/n ;
}
void solve(){
  ans=0 ;cin >> n >> a >> b ;
  FOR(i,n-1){
    int p;cin >>p;--p;
    adj[i+1].pb(p);adj[p].pb(i+1);
  }
  memset(ca,0,sizeof(ca));
  memset(cb,0,sizeof(cb));
  dfs();cout << ans << "\n";
  FOR(i,n)
    adj[i].clear();
}
signed main() {
  cout << setprecision(20) << fixed ;
  int t;cin >> t;
  FOR(_,t){
  	cout << "Case #" <<  _+1 <<  ": ";
  	solve();
  }
}

Newton

I think you should give credit of code to William Lin because your code is exactly match with his solution code

unstoppable_1000

It's William Lin himself on his alt account

Hey, could anyone explain this part more clearly? I am unable to get it.

"If there are l opened doors on the Ki-th day, there needs to be at least f(l) opened doors to the right, so that the highest difficulty among the f(l) doors to the right is higher than the highest difficulty among the l doors to the right. An observation is that l+f(l) is monotonic. So the suitable l can be found via binary search."

My solution to 4th problem is similar to that of the editorial presented in this blog.

Let start be the starting room and k > 1.

Key takeaways:
1. Either Kth Room lies in [1,start-1] or [start+1,N]
2. Assume it lies in [1,start-1], pick any room X in the range [1,start-1]. Check if X is the Kth Room to be explored.
3. How do I check that? If X is the Kth room to be explored then 1 thing is that before we reach Room X we should have already explored Room X + K but No room to the right of room X+K must be explored before exploring room X.
This would suggest that atleast 1 door in range X to start — 1 must be harder to open than all doors in range start to X+K-1(the door you need to open to reach room X+K)
4."but No room to the right of room X+K must be explored before exploring room X" this would suggest that there should be no door harder to open in the range X to start-1 when compared to door X+K.

If both conditions are true we found our door, otherwise depending upon which of the two conditions (3),(4) fail re-adjust the search range and do a binary search.

If door isn't in left range, then use same idea for right range.

Poorly Implemented AC code: Will only see solve function

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

Problem A — Record Breaker

Problem B — Alien Piano

Problem C — Beauty of Tree

Problem D — Locked Doors