Good luck & Have fun!

lzn_tops

These point values are just right for the beginners.

我AC了第三题！可是我第四题不会 qwq

any Hint on how to solve $$$E$$$? Only hint

What was the intuition for E so that to move k steps we do 2^k-1 i = p[i] ?

I solved it but I kinda guessed it from the sample case and it took me a long time. The idea of 2^k-1 came to my mind from this :

When we do 1 move p[i] = p[p[i]] and p[p[i]] = p[p[p[i]]] , it seemed like number of moves would double each move. However this was a very vague idea and the problem kinda teased my brain , thats why it took me so long to solve the problem.

Here is my submission : https://atcoder.jp/contests/abc377/submissions/59187007

How E? I used binary lifting but got wrong

Can someone please help with the mistake in following solution for problem D? Note: My idea was just inverse of what is done in editorial.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
    ll N, M, L, R;
    cin >> N >> M;
    ll answer = (M * (M + 1)) / 2;
    
    unordered_map<ll, ll> RtoL;
    for (ll i = 0; i < M; i += 1) {
        cin >> L >> R;
        if (RtoL.find(R) == RtoL.end()) RtoL[R] = L;
        else RtoL[R] = max(RtoL[R], L);
    }
    
    map<ll, ll> LtoR;
    for (auto& [R, L] : RtoL) {
        if (LtoR.find(L) == LtoR.end()) LtoR[L] = R;
        else LtoR[L] = min(LtoR[L], R);
    }
    
    deque<pair<ll, ll>> Q;
    for (auto& [L, R] : LtoR) {
        if (Q.empty()) {
            Q.push_back({L, R});
            continue;
        }
        
        if (Q.back().second > R) Q.pop_back();
        Q.push_back({L, R});
    }
    
    while (!Q.empty()) {
        L = Q.front().first;
        R = Q.front().second;
        Q.pop_front();
        
        ll Rnext = Q.empty() ? (M + 1) : Q.front().second;
        answer -= (L * (Rnext - R));
    }
    
    cout << answer;
}

Someone look at the first place person's F submission: https://atcoder.jp/contests/abc377/submissions/59171780

They import sys like 8 times, comments in code, wrote 140 lines in 5 minutes.

Surely they will get banned right?

I enjoyed the problems, and I'm amazed at how surprising they turned out to be!

hard problems qwq

seems to be A < B <= C < F <= G < D < E

Problem E is great! At first, I thought it is just binary-lift, but later find that in fact we need find p[p[p[.....p[i]]]], where there are 2^k p[ ] operations. Thus, we can use dfs to find the period T of each i, and calculate R = 2^k mod T. Meanwhile, we also compute the "binary-lift" during the above dfs. Finally, the answer is p[p[p....p[i]]], where there are R p[ ] operations, which can be solved based on the above "binary-lift".

solved A-C

Tried to solve F using N-Queens logic, but ultimately got TLE

E was some disjoint graph cycle i think, will try to upsolve.

Is problem G well known, or classical?

Can someone explain how E [https://atcoder.jp/contests/abc377/tasks/abc377_e] can be solved.

I am not able to visualise it. I understood that if we apply permutation p on a sequence k times then how its changing. But if the permutation itself is changing then how the sequence is gonna change. Can someone help me understand it or point me to some relevant resource.

Does anybody have the derivation of that $$$P^{2^{k}}$$$ in problem $$$E$$$?

(I'm asking about derivation, not the proof by induction)