We will hold TOYOTA SYSTEMS Programming Contest 2024(AtCoder Beginner Contest 377).
- Contest URL: https://atcoder.jp/contests/abc377
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20241026T2100&p1=248
- Duration: 100 minutes
- Writer: MMNMM, sounansya
- Tester: physics0523, kyopro_friends
- Rated range: ~ 1999
- The point values: 100-200-300-400-475-550-575
We are looking forward to your participation!
Good luck & Have fun!
lzn_tops
These point values are just right for the beginners.
any Hint on how to solve $$$E$$$? Only hint
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.
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).
then how its different from this problem: link
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.
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.
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".
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:
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.
Thank you! Now it's clear that I indeed interpreted the statement incorrectly.
yes , i also tried binary exponentiation but didnt worked
I guess because in binary exponentiation we don't change the permutation while in the task permutation changes after every operation
Think about the cycles of the permutation.
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
I created a directed graph where there is a edge between i -> p[i].
I guessed that after k moves , We need to do 2^k-1 i = p[i] , so for each i I found its 2^k-1th child in the graph.
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?
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.
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.
well you just do $$$2^k - 1$$$ $$$mod$$$ $$$m$$$ ,$$$m$$$ is the number of nodes in the cycle it is in
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.
Can you please share some sources with a more detailed explanation on how applying a permutation works how you have described?
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.
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.
How E? I used binary lifting but got wrong
I was able to do it with binary lifting — here
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.
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?
It says they are using AI in profile as well.
still not banned :/
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
A: know that sort exists
B-C-F: implement whatever is given in the statement
G: know that trie exists
D: first problem where you actually need to think
E: second thinking problem where you also might need to know that binary lifting exists
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?
It's just based on a data structure named Trie, which is one of the "more known" advanced data structure.
When trie become advanced data structure?
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.
Look up — Permutation Graphs & Binary Lifting
Does anybody have the derivation of that $$$P^{2^{k}}$$$ in problem $$$E$$$?
(I'm asking about derivation, not the proof by induction)
I liked task C