Kick start round C 2020 solution

general
, , , ,
1

solution of Google Kick start Round C 2020
problem A
with explanation and code
solution

2

I need help with other problems

1 Like
3

i solved c …perfect subarray…
https://youtu.be/OdxUf9zaSrw

solution is correct passed small data case but got TLE in big test case.

4

Which one

5 
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <cstdio>
#include <numeric>
#include <vector>
#include <iterator> 
#include <map>
#include <set>
#include <climits>
#include <queue>
#include <iomanip>
#include <cmath>
#include <stack>
#include <cctype>
#include <bitset>
// #include <bits/stdc++.h>
#define int long long int
#define ibs ios_base::sync_with_stdio(false)
#define cti cin.tie(0)
#define bp __builtin_popcount
#define pb push_back
using namespace std;//coded by abhijay mitra
const int N=2e5+1;
const int inf = /*0x3f3f3f3f*/1e15;
// const ll M = 998244353 ; // Mulo
const int M = 1e9+7 ; // Mulo
#define F first
#define S second
int n;
//building the tree
void build(int a[],int t[], int v=1, int tl=1, int tr=n) {
    if (tl == tr) {
        t[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(a,t, v*2, tl, tm);
        build(a,t, v*2+1, tm+1, tr);
        t[v] = t[v*2] + t[v*2+1];
    }
}
//queries
int sum(int l, int r,int t[],int v=1, int tl=1, int tr=n ) {
    if (l > r) 
        return 0;
    if (l == tl && r == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    return sum( l, min(r, tm),t,v*2, tl, tm)
           + sum(max(l, tm+1), r,t,v*2+1, tm+1, tr );
}
//
void update(int pos, int new_val,int t[],int v=1, int tl=1, int tr=n ) {
    if (tl == tr) {
        t[v] = new_val;
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(pos,new_val,t,v*2, tl, tm);
        else
            update(pos,new_val,t,v*2+1, tm+1, tr);
        t[v] = t[v*2] + t[v*2+1];
    }
}
int arr[5][N],a[N];char c;
int q,t[5][4*N];
void solve(){
  cin>>n>>q;
  memset(arr,0,sizeof arr);memset(a,0,sizeof a);memset(t,0,sizeof t);
  for(int i=1;i<=n;i++)cin>>a[i];
  for(int i=1;i<=n;i++){
    if(i&1)arr[1][i]=a[i];
    else arr[1][i]=-a[i];
    arr[2][i]=i*arr[1][i];
    arr[3][i]=-arr[1][i];
    arr[4][i]=-arr[2][i];
  }
  int ans=0;
  build(arr[1],t[1]);
  build(arr[2],t[2]);
  build(arr[3],t[3]);
  build(arr[4],t[4]);
  for(int i=1;i<=q;i++){
    cin>>c;
    if(c=='U'){
      int pos,val;
      cin>>pos>>val;
      if(pos&1){
        update(pos,val,t[1]);
        update(pos,val*pos,t[2]);
        update(pos,-val,t[3]);
        update(pos,-val*pos,t[4]);
      }
      else{
        update(pos,-val,t[1]);
        update(pos,-val*pos,t[2]);
        update(pos,val,t[3]);
        update(pos,val*pos,t[4]);
      }
    }
    else{
      int l,r;
      cin>>l>>r;
      if(l&1){
        // cout<<sum(l,r,t[2])-(l-1)*sum(l,r,t[1])<<"\n";
        ans+=sum(l,r,t[2])-(l-1)*sum(l,r,t[1]);
      }
      else{ 
        // cout<<sum(l,r,t[4])-(l-1)*sum(l,r,t[3])<<"\n";
      /*else */ans+=sum(l,r,t[4])-(l-1)*sum(l,r,t[3]);}
    }
  }
  cout<<ans;
}
int32_t main()
{
  ibs;cti;
  // solve(),cout<<"\n";
  int x=0;
  int t;cin>>t;while(t--){x++;cout<<"Case #"<<x<<": ";solve();cout<<"\n";}
  return 0;
}

solution to D

1 Like
6

thanks…

1 Like
8 
#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int T ; cin >> T;
    int i_ = 1;
    while (T--) {
        int N, K; cin >> N >> K;
        int x, j, i = 0, res = 0;
        while ( i < N ) {
            cin >> x; 
            j = K; i ++;
            while (x == j && i < N) {
                cin >> x;
                j --; i ++;
                if (x == 1 && j == 1) {res ++; break;}
            }
        }
        cout << "Case #" << i_++ << ": " <<  res << '\n';
    }
    return 0;
}

what is problem with this code?

9

Understand why it is wrong with this example:

1
3 2
2 2 1

Your code will output 0 as ans whereas ans is 1.
When you’re breaking, you’re starting afresh again which is wrong.
Simulate the process with this example and you’ll understand.

1 Like
10

This works:

Code 
#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int T ; cin >> T;
    int i_ = 1;
    while (T--) {
        int N, K; cin >> N >> K;
        int x, j, i = 0, res = 0;
        while ( i < N ) {
            cin >> x; 
            j = K; i ++;
            while (i < N) {
            	if(x!=j){
            		if(x==K){j=K;}
            		else{break;}
            	}
                cin >> x;
                j --; i ++;
                // cout<<x<<" "<<j<<endl;
                if (x == 1 && j == 1) {res ++; break;}
            }
        }
        cout << "Case #" << i_++ << ": " <<  res << '\n';
    }
    return 0;
}
1 Like
11

Thankyou buddy, i understand why that failed now. :ok_hand: :ok_hand:

you have been the most helpful mate here to me.

1 Like