TOYOTA SYSTEMS Programming Contest 2024（AtCoder Beginner Contest 377) Announcement

2 месяца назад, # ^ |

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.

→ Ответить

2 месяца назад, # ^ |

← Rev. 4 →

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

→ Ответить

_trie_again

2 месяца назад, # ^ |

then how its different from this problem: link

→ Ответить

2 месяца назад, # ^ |

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.

→ Ответить

2 месяца назад, # ^ |

← Rev. 2 →

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.

→ Ответить

2 месяца назад, # ^ |

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

→ Ответить

2 месяца назад, # ^ |

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

→ Ответить

2 месяца назад, # ^ |

← Rev. 3 →

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.

→ Ответить

2 месяца назад, # ^ |

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

→ Ответить

L1C1T

4 недели назад, # ^ |

Wow, this is what I was missing; I was scratching my head trying to solve this over the past hour

→ Ответить

_trie_again

2 месяца назад, # ^ |

yes , i also tried binary exponentiation but didnt worked

→ Ответить

alyoks1

2 месяца назад, # ^ |

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

→ Ответить

2 месяца назад, # ^ |

Think about the cycles of the permutation.

→ Ответить

2 месяца назад, # |

← 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

→ Ответить

retard.

2 месяца назад, # ^ |

← Rev. 2 →

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?

→ Ответить

2 месяца назад, # ^ |

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.

→ Ответить

retard.

2 месяца назад, # ^ |

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.

→ Ответить

brave-kid

2 месяца назад, # ^ |

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

→ Ответить

2 месяца назад, # ^ |

← Rev. 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.

→ Ответить

gameface_123

2 месяца назад, # ^ |

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

→ Ответить