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

Автор atcoder_official, история, 3 недели назад, По-английски

We will hold TOYOTA SYSTEMS Programming Contest 2024(AtCoder Beginner Contest 377).

We are looking forward to your participation!

  • Проголосовать: нравится
  • +69
  • Проголосовать: не нравится

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится -29 Проголосовать: не нравится

Good luck & Have fun!

»
3 недели назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится
»
3 недели назад, # |
  Проголосовать: нравится -25 Проголосовать: не нравится

These point values are just right for the beginners.

»
3 недели назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

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

My Solution
  • »
    »
    3 недели назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    The 2^k part is clear from the start, but how did you find the actual number of steps since 2^k is too big? I split p into cycles and solved for each of those independently, but it looks too complex, is there more elegant solution?

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How is it clear ? Can you elaborate a bit more on that. Also my solution was same but I dont think it is that complex. I found the idea in the last 5 mins of the contest and it took me 3 mins to implement it.

      • »
        »
        »
        »
        3 недели назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        How is it clear?

        I've just generated several examples with straightforward op implementation ASAP and saw the pattern from there. I have no idea or strict proof why it's like that though.

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      well you just do $$$2^k - 1$$$ $$$mod$$$ $$$m$$$ ,$$$m$$$ is the number of nodes in the cycle it is in

  • »
    »
    3 недели назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    Basically the problem asks you to square the permutation $$$p$$$ $$$k$$$ times, so you are actually computing $$$p^{2^k}$$$. A cycle of size $$$s$$$ shifts by one each time you apply $$$p$$$ and after applying $$$p$$$ $$$s$$$ times you get back to the start, so applying $$$p$$$ $$$2^k$$$ times you have effectively to shift by $$$2^k \mod s$$$.

    Clarification about the notation: Permutations form a group under composition, so it is often convenient to use product notation for compostion of permutations. So with $$$p^n$$$ I mean $$$p \circ p \circ \ldots \circ p$$$, composing $$$n - 1$$$ times.

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you please share some sources with a more detailed explanation on how applying a permutation works how you have described?

      • »
        »
        »
        »
        3 недели назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        The notation is introduced for example here. There is a lot of theory about permutations, the group of all permutations of a fixed size $$$n$$$ for example is often denoted by $$$S_n$$$ and called a symmetric group. It should not be too hard to find more information if you are interested.

        • »
          »
          »
          »
          »
          3 недели назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Thanks for your response electron. I think I intuitively understand how we get the shift factor of 2 ^ k — 1 now when you mentioned it.

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How E? I used binary lifting but got wrong

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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;
}
»
3 недели назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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?

»
3 недели назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
3 недели назад, # |
Rev. 3   Проголосовать: нравится -24 Проголосовать: не нравится

hard problems qwq

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

hint: someone seems angery so here's why I think that:
»
3 недели назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is problem G well known, or classical?

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I liked task C