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."

This might answer your question: https://blog.google/inside-google/life-at-google/advice-google-engineer-join-coding-competition/

Maybe this can help. link

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!

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.

How to solve for second and third case

need help!!! it gives me WA in C. my code thanks:)

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

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.

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.

Same for me

Me too :(

Frustrating Indeed . I thought maybe I was messing up somewhere

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

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

Exactly what happened to me :(

Same man :(

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

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.

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

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

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

I used segment tree and lifting the exponent lemma.

Essentially, you store the following information in the node, and disregard elements $$$ \lt 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.

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 \lt 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.

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

Learn to read statement sir :

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

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

`

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