atcoder_official's blog

TOYOTA SYSTEMS Programming Contest 2024（AtCoder Beginner Contest 377) Announcement
By atcoder_official, history, 4 weeks ago, In English

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

We are looking forward to your participation!

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

»
4 weeks ago, # |
← Rev. 2   Vote: I like it -29 Vote: I do not like it

Good luck & Have fun!

→ Reply
»
4 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

lzn_tops

→ Reply
»
4 weeks ago, # |
  Vote: I like it -25 Vote: I do not like it

These point values are just right for the beginners.

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

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

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

    Also why binary exponentiation of the permutation https://cp-algorithms.com/algebra/binary-exp.html#applying-a-permutation-k-times doesn't work? Still couldn't figure it out.

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

      You misunderstood the statement. You don't have to apply the given $$$p$$$ $$$k$$$ times (i.e. compute $$$p^{k + 1}$$$), you have to square $$$p$$$ $$$k$$$ times (i.e. compute $$$((p^2)^2)^{...}$$$ and so on $$$k$$$ times).

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

        then how its different from this problem: link

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

          The difference is that we need to compute not p^(k+1) but p^(2^k) which seems to be a harder task.

          But at the first glance I also thought that the problem from the current round and https://atcoder.jp/contests/abc367/tasks/abc367_e are almost identical.

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

          I think because in this problem we are applying p to itself each time. But in that problem applying X to A , where X doesnt change at all.

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

        What does squaring a permutation mean ? Can you give some understanding on that , I get confused when I try to think these kinds of stuff in my head. I guess I lack some understanding on "applying a permutation".

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

          You can look at the code from here https://cp-algorithms.com/algebra/binary-exp.html#applying-a-permutation-k-times to understand what applying a permutation means:

          vector<int> applyPermutation(vector<int> sequence, vector<int> permutation) {
    vector<int> newSequence(sequence.size());
    for(int i = 0; i < sequence.size(); i++) {
        newSequence[i] = sequence[permutation[i]];
    }
    return newSequence;
}
          → Reply
        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          Since permutations form a group under composition it is sometimes convenient to use the multiplication notation for composition. So with $$$p^2$$$ I mean $$$p \circ p$$$ and in general with $$$p^n$$$ I mean $$$p \circ p \circ \ldots \circ p$$$, composing $$$n - 1$$$ times.

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

        Thank you! Now it's clear that I indeed interpreted the statement incorrectly.

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

      yes , i also tried binary exponentiation but didnt worked

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

      I guess because in binary exponentiation we don't change the permutation while in the task permutation changes after every operation

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

    Think about the cycles of the permutation.

    → Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

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
→ Reply
  • »
    »
    4 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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?

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

      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.

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

        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.

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

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

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

    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.

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

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

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

        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.

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

          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.

          → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How E? I used binary lifting but got wrong

→ Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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;
}
→ Reply
»
4 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

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?

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

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

→ Reply
»
4 weeks ago, # |
← Rev. 3   Vote: I like it -24 Vote: I do not like it

hard problems qwq

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

hint: someone seems angery so here's why I think that:
→ Reply
»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is problem G well known, or classical?

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

    It's just based on a data structure named Trie, which is one of the "more known" advanced data structure.

    → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I liked task C

→ Reply