kostka's blog

Google Kick Start 2021
By kostka, 3 years ago, In English

Looking for a way to stay connected, try something new, and have a little fun? The Kick Start 2021 season has begun!

Kick Start offers programmers of all skill levels the opportunity to boost your skills through a series of intriguing algorithmic and mathematical problems designed by Google engineers. Each round starts fresh, so give any one of our 2021 online rounds a try — or join them all!

Join

Prepare

  • View our tutorial video to learn more about the competition platform and some useful tips and tricks.
  • Practice makes progress! Try your hand at past problems and read through our FAQ if you have a question.

Connect

Be part of the #KickStart community by joining our Facebook Group to meet other participants, chat about past problems, and hear about the latest updates!

Questions? Reach out to [email protected].

We hope you’ll join us for some fun practice. What are you waiting for?

  • Vote: I like it
  • +239
  • Vote: I do not like it

Comments Comments (77)
| Write comment?
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

This may be a dumb question, but why are all participants less than 16 years of age not allowed to participate?

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

    I think you misread

    " You understand and acknowledge that you must be at least $$$(18)$$$ years old or the age of majority in your country of residence (whichever is greater) at the time you register for the KS Contest to be contacted by a Google recruiter."

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      No, I tried registering and it said I must be at least 16 years of age.

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

Can you please answer one thing? Does Google really hire people from Kickstart?

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

Just curious, why cannot residents of Quebec participate in the contest?

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

Nice round how to do C?

i did it with BFS but it gave me Memory limit exceeded

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

    It's a multisource BFS problem.

    The idea is once you get the original matrix, there is only one optimal matrix that can be obtained. So, you find that matrix using BFS => First, store the indices of all matrix elements that have the maximum possible number in the matrix(note that it is always less than 2e6), and then move to it's neighbours and keep doing the same thing!

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

      I just did this : traverse from maximum to minimum values

      Lets talk about a value v, then set its neighbours to max(value_neighbour, v — 1) I tried to do multinode bfs, I got WA

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

      I did multisource bfs but I got WA :( Can you spot an error here?

      My Code
      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it +13 Vote: I do not like it 
        1
4 4
10 1 1 1
1 1 1 1
1 1 1 1
1 1 1 9

        Correct answer: 93

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

    No need for BFS.

    You can just find for each cell lower bounds in each of 4 directions and set new value to maximum of those (and initial value). For example, going bottom and right you need to find maximum of value[i][j] — i — j. The solution code is actually very similar to problem B.

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

Cool problem D

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    How to solve for second and third case

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

      how to solve for even first case ....Did recursion for all possible cases works??

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

        yes recursion works, find a subset of -1s which you will find by using their cost, and then find that if the remaining -1s can be found without using any cost, i.e. just using checksums.

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

Problem set was quite nice. Was able to solve till C only :(

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

Can anyone explain how to do Checksum problem?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    The analysis given when you go back to the question now that it's in practice mode is very well written.

    → Reply
»
3 years ago, # |
  Vote: I like it -17 Vote: I do not like it

can someone pls help me with problem C,

my code gave the wrong ans

include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int main(){ int t; cin>>t; int nn = 1; while(t--){ int r,c; cin>>r>>c; vector<vector> g(r,vector(c));

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

        }
    }

    priority_queue<vector<int>> pq;
    vector<vector<int>> visited(r,vector<int>(c,0));
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            pq.push({g[i][j],i,j});
        }
    }

    int ans = 0;
    //cout<<q.size()<<endl;
    vector<vector<int>> update(r,vector<int>(c,0));
    while(pq.empty()==false){
        int x = pq.top()[1];
        int y = pq.top()[2];
        //cout<<pq.top()[0]<<endl;
        pq.pop();
        if(visited[x][y]==1){
            continue;
        }
        visited[x][y] = 1;

        int dx[] = {0,0,1,-1};
        int dy[] = {1,-1,0,0};
        for(int k=0;k<4;k++){
            int x1 = x + dx[k];
            int y1 = y + dy[k];
            if(x1<0 || x1>=r || y1<0 || y1>=c || visited[x1][y1] == 1 || (abs(g[x1][y1] - g[x][y])<=1)){
                continue;
            }
            pq.push({g[x][y]-1,x1,y1});
            if(update[x1][y1]==0){
                update[x1][y1] = 1;
                ans += g[x][y] - g[x1][y1] - 1;
            }    
            g[x1][y1] = g[x][y] - 1;

        }
    }

    cout<<"Case #"<<nn<<": "<<ans<<endl;


    nn++;
}



return 0;

}

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

    One thing to be careful of in this problem is that the final result can be larger than the limits of a 32-bit integer. Using 64-bit integers avoids WAs due to overflow.

    the ans does not fit in 32-bit integer you have to use long long.

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

Will Google be backfilling test data for old problems (GCJ and Kickstart), or will Google only be uploading test data for problems starting this season?

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

Guys, do you have any test cases for the "Checksum" task? I'm trying to find a bug in my solution, but without having a failing test case it's not easy. It's obviously passing Sample Input/Sample Output, but failing with WA on the Test Set 1.

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

    running it side by side on random inputs with the solution of ecnerwala (the winner) — mine always prints the same outputs as his, so a random generator is not what helps with revealing the issue, there should be some special edge cases I'm missing.

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

Is it just me that my kickstart problem page is still showing "In Review" and not showing my final rank and I received a mail from Google to accept your participation certification but on that page also it is showing "No competition History".

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

Screenshot-2021-03-24-163857
Just in case someone isn't aware of it.

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

This problem from the Philippines' national olympiad is similar to Round A problem C; I do recommend anyone who's solved it to give it a try.

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

Thank you sir for the plagiarism check. My rank increased by 1000. Thank you so much.

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

Good luck to everyone in round D. If anyone somehow missed the reminders, the round is about to start in less than half an hour.

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

is it happening with just me ? my submission is still being judged for 15 minutes

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

There is a tremendous queue, Do something about it @google. Or the entire experience will be ruined.

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

    yes,It is taking so much Time. submitted 20 minutes ago, still pending.

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

Queue :(.

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

    Its been 30 mins since my solution has been running now :(

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

Its been 30 mins I've submitted B , didn't get verdict till now

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

Cancel the round if you can't fix the issue, it's irritating!

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

I want a penalty refund after the solution runs for more than 25 mins and returns WA. :')

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

Google giving Codechef vibes :(

→ Reply
»
3 years ago, # |
  Vote: I like it -35 Vote: I do not like it

Why wait for the queue? Just solve the next problem.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    What to do if you are not able to solve next problem ?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -14 Vote: I do not like it

      Then pretend your current submission will fail, and try to find the error. If it afterwareds turns out your submission was ok you did not loose anything. And otherwise you can submit the corrected solution.

      However, this does not work good if you submit by trial and error, but that strategy does not work good anyways.

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +42 Vote: I do not like it

    Speaking from experience, it's very frustrating when you put a solution in queue for 20 minutes that you think will pass only to get WA, at which point you'd probably have to stop what you were working on and then go to debug it now.

    I agree a lot of it can be solved by a good mindset towards it (i.e. not caring about it too much and moving on to other problems), but at least for me it's harder to focus when I know one of my previous solutions might WA and I wouldn't know for a while, not to mention the frustration if it eventually does.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -23 Vote: I do not like it

      Of course it is better to have a quick queue instead of a slow one. But that was not my question.

      A lot of comments in this thread read like "I had to wait for X minutes before beeing able to proceed...". That is not true.

      → Reply
»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Hey Guys, Actually I have a question on how if we dont have return statement if the function is declared as int fun(), it is giving runtime error. That too only on google's ide ? but not anywhere else ? You can see here

https://ide.geeksforgeeks.org/U707PgW7Co

This solution runs on all the ide's I have tried (gfg, codechef, codeforces, and local cmd etc...),it runs perfectly fine but not on google's where It gives RE. I wasted about 1 hour trying to find what the hell is wrong, but after 1 hour i was able to finally figure out that this is the issue. (i.e if we change the function int calc to void calc, it runs fine in google) But I dont understand why. Could someone pls help.

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

Intervals, Intervals, everywhere...

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

For the 2nd part of last problem if $$$P$$$ divides $$$A_i$$$ then no problem but when $$$P$$$ does not divide $$$A_i$$$ we know that $$$A_i-(A_i\, mod\, P)$$$ has some power of $$$P$$$ but how to find power of $$$P$$$ from another factor — $$$(A_i^S-(A_i\, mod\, P)^S)/(A_i-(A_i\, mod\, P))$$$ or may be can we prove it doesn't contain?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    The editorial says we should use https://en.wikipedia.org/wiki/Lifting-the-exponent_lemma to do that.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    What you are looking for is a theorem called LTE lifting the exponent be careful to p=2 who is different

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    I thought it was about binomial coefficients. You can imagine Ai = x*P^z + y, where x, y are not divided by p and y = Ai mod p. Then this expression turns into (x * P^z + y)^ s — y ^ S. We can open parentheses and y ^ S cancels out leaving you with (x*P^z)^S + ... + S * y^(S-1) * x * P^z. This last member seams to answer the question: ans(Ai) = z + h (where S = g * p^h and g%p > 0).

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      yes it's the proof of LTE but again be careful to p=2 which is a little bit different

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 3   Vote: I like it -8 Vote: I do not like it

        Nope, seams I missed something... Even for [p = 2 and even n] from analysis binomials work for small numbers. Problem must be elsewhere.

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

How to do Testcase 2 for problem D ?

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

    I used segment tree and lifting the exponent lemma.

    Essentially, you store the following information in the node, and disregard elements $$$< p$$$:

    1. Sum of highest powers of $$$p$$$ dividing $$$a[i] - a[i] \% p$$$ for all $$$i$$$ in the range handled by the node.

    2. Sum of highest powers of $$$p$$$ dividing $$$a[i] + a[i] \% p$$$ for all $$$i$$$ in the range handled by the node.

    3. Sum of highest powers of $$$p$$$ dividing $$$a[i]$$$ for all $$$i$$$ in the range handled by the node.

    4. Number of elements for which the third point is 0.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      tbh, I have never even heard of lifting the exponent lemma, idk what to reply on this.

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    My solution is completely based on some patterns, that are found using brute force solutions.

    Our goal is to calculate $$$V(a^n - (a \bmod p)^n)$$$.

    • Case 1: if $$$a < p$$$, then answer is $$$0$$$.
    • Case 2: if $$$a \bmod p = 0$$$, then answer is $$$V(a) \cdot n$$$.
    • Case 3: if $$$a \bmod p \neq 0$$$, then answer is $$$V(n) + \max\limits_{a - p + 1 \leq j \leq a}V(j)$$$ .

    Above method will fail if $$$p = 2$$$, $$$a \bmod 4 = 3$$$ and $$$n \bmod 2 = 0$$$. So i handle that case manually.

    Overall I used 4 Fenwick trees to implement the complete solution.

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

      I also tried brute forces in contest and saw some patterns, for a mod p == 0 and if a mod p != 0 and s mod p != 0. I didnt get any thing for case where a mod p != 0 and s mod p == 0.

      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

Can anyone help me why this logic gives WA on problem C. I store all pairs {Ai,Bi} in a set. Then as we get the query X, i lower_bound X in the set and try to find the closest difficulty according to the conditions in the problem. After this i edit the pairs in the set accordingly.

Code
→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it -36 Vote: I do not like it

Weak test cases of problem C:

Spoiler

Edit: Test cases are correct

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

    The case is wrong, the given intervals supposed to be disjoint.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      Ohh, I solved this problem for the overlapping intervals

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

        How to solve for overlapping intervals, its so hard when the intervals overlap

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

          For each S[i], if there is any interval A[i]<S[i]<B[i] then split that interval into 3 parts. [A[i],S[i]-1], [S[i],S[i]] and [S[i]+1,B[i]].

          After that it is normal problem which can be solved using lower and upper bound. My solution https://ide.geeksforgeeks.org/0XydTTD6pG

          → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -25 Vote: I do not like it

    Learn to read statement sir :

    Among all problems from all sets, it is guaranteed that no two problems have the same difficulty.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -44 Vote: I do not like it

    CAN SOMEBODY HELP ME WHAT'S WRONG WITH MY CODE, I AM FIGURING IT OUT FROM 2 HOURS

    KICK START ROUND D 2021

    `

    include<bits/stdc++.h>

    using namespace std;

    define ll long long

    const ll MAX = 1000000000000000000; ll mod = 1000000000; long double pi = 3.141592653589793238; void pls() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);

    endif

    } /* DON'T STUCK ON SINGLE APPROACH OR QUESTION*/ const ll N = 3e5 + 2; ll n, m; void solve() { int tc = 1; int t; cin >> t; while(t--) { cout << "Case #" << tc++ << ": ";

    cin >> n >> m;
    vector<ll> a;
    vector<ll> b;
    vector<ll> s(m);
    set<pair<ll, pair<ll, ll>>> st;
    for(int i = 0; i < n; i++)
    {
        ll aa, bb;
        cin >> aa >> bb;
        a.push_back(aa);
        b.push_back(bb);
        st.insert({a[i], {0, i}});
        st.insert({b[i], {1, i}});

    }

    for(int i = 0; i < m; i++)
    {
        cin >> s[i];
    }
     ll cnt = n;
    for(int i = 0; i < m; i++)
    {
        auto it = st.upper_bound({s[i], {-1, 0}});




        if(it == st.end())
        {
            it--;
            ll y = it->first;
            ll ix = it->second.second;
            ll dir = it->second.first;

            ll sk = s[i] ;

            s[i] = y;

            ll x = a[ix];

            if(x == y)
            {
                st.erase({y, {1, ix}});
                st.erase({x, {0, ix}});
            }
            else
            {
                st.erase({y, {1, ix}});
                st.insert({y - 1, {1, ix}});
            }
        }
        else if(it == st.begin())
        {
            ll x = it->first;
            ll ix = it->second.second;
            ll dir = it->second.first;

            ll sk = s[i] ;

            s[i] = x;

            ll y = b[ix];

            if(x == y)
            {
                st.erase({y, {1, ix}});
                st.erase({x, {0, ix}});
            }
            else
            {
                st.erase({x, {0, ix}});
                st.insert({x + 1, {0, ix}});
            }
        }
        else
        {

            ll x = it->first;
            ll ix = it->second.second;
            ll dir = it->second.first;

            // inside
            if(x == s[i])
            {
                if(dir == 0)
                {
                    ll y = b[ix];
                    if(x == y)
                    {
                        st.erase({y, {1, ix}});
                        st.erase({x, {0, ix}});
                    }
                    else
                    {
                        st.erase({x, {0, ix}});
                        st.insert({x + 1, {0, ix}});
                    }
                }
                else
                {
                    ll xx = a[ix];
                    if(xx == x)
                    {
                        st.erase({x, {1, ix}});
                        st.erase({xx, {0, ix}});
                    }
                    else
                    {
                        st.erase({x, {1, ix}});
                        st.insert({x - 1, {1, ix}});
                    }
                }
            }
            else if(dir == 1)
            {
                ll xx = a[ix];
                st.erase({x, {1, ix}});
                st.erase({xx, {0, ix}});
                    a.push_back(xx);
                    b.push_back(s[i] - 1);
                    st.insert({xx, {0, cnt}});
                    st.insert({s[i] - 1, {1, cnt}});
                    cnt++;
                    a.push_back(s[i] + 1);
                    b.push_back(x);
                    st.insert({s[i] + 1, {0, cnt}});
                    st.insert({x, {1, cnt}});
                    cnt++;

            }
            else
            {
                it--;
                ll lx,lix,ldir;
                lx=it->first;
                lix=it->second.second;
                ldir=it->second.first;

                if(abs(lx - s[i]) <= abs(x - s[i]))
                {
                    ll sk = s[i] ;

                    s[i] = lx;

                    ll xy = a[lix];

                        st.erase({lx, {1, lix}});
                        st.insert({lx - 1, {1, lix}});

                }
                else
                {
                    ll sk = s[i] ;

                    s[i] = x;

                    ll y = b[ix];


                        st.erase({x, {0, ix}});
                        st.insert({x + 1, {0, ix}});

                }
            }

        }


    //  for(auto x: st){
    //  cout<<x.first<<" "<<x.second.first<<" "<<x.second.second<<endl;
    // }
    // cout<<endl;
    }
    // for(auto x: st){
    //  cout<<x.first<<" "<<x.second.first<<" "<<x.second.second<<endl;
    // }
    // cout<<endl;

     // cout<<a[i]<<" "<<b[i]<<endl;
    // for(int i=0;i<a.size();i++)
    for(int i = 0; i < m; i++)
    {
        cout << s[i] << " ";
    }
    cout << endl;

}

    } int main() { pls(); solve(); return 0; }

    `

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

kostka Seems like someone forgot to change the generic analysis header -- it still says "Thank you for participating in Kick Start 202X Round X!" :)

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Shhhh, no one saw that. Should be fixed now.

    → Reply