It already started!

In the Contest Page itself , after the contest AtCoder provides Tutorials for each problem in well descriptive way.

you have to get length of cycle in component containing 1

find the beginning of the cycle in the created graph (or linked list), as well as the length of the cycle. Then, roughly speaking, take K % (cycle of length) and just traverse the list one more to find the final index.

Do it for 2 different cases k<=n and k>n. Check manually for k<=n and use the idea of cycle for k> n!

Here is the code

Hint : After a point towns start to repeat themselves periodically and king starts travelling in a cycle. https://atcoder.jp/contests/abc167/submissions/13059179

Simulate the teleportation until you find repetition. Then go and find the first occurrence of the repeated value. The answer will be to travel to the first occurrence and then going in a loop from the first occurrence to last occurrence, for which the answer can be calculated using modulo.

Let $$$f_k(i)$$$ be the town we end up at if we start at town $$$i$$$ and teleport $$$k$$$ times. Then note that for positive $$$p$$$,

The input corresponds to $f_1$. So compute $$$f_2, f_4, f_8, \dots$$$ using this DP. Then divide $$$k$$$ into powers of 2 and apply the $$$f_i$$$ that correspond to those powers.

Here's a short implemenation.

I did it using binary lifting...as it was what i got in my mind first but finding cycle length is a great idea(and easier i guess).

Here is my submission: Code

I have observed most people used std::set and messy implementations to find the starting point of the cycle but you can use a very easy floyd warshall cycle detection algorithm to find it. you can learn about it on the internet it very easy to understand

Here is my implementation I have heavily commented it at so that you can understand easily

Because there are n towns, accoriding to pigen hole theroy, after n moves, there must be repeated visited towns. So the solutions is: (1) if k <= n, just simulate k moves; (2) if k > n, simulate n moves. If the n-th visited town is x, then the cycle length is n-last[x]. last[x] is the last time x is visited before the n-th move. Decompose k moves into three parts. First n moves, then (k-n)/(n-last[x]) cycles, then (k-n)%(n-last[x]) moves. After the cycles part the king returns to x. So the answer is move from x for (k-n)%(n-last[x]) moves.

first find the length of cycle then using bisection you can get the solution one think you have to consider when cycle length is 2e5 overflow can occure because 2e5*1e18 cross long long range ..

loop k1=0 to k:
   ans+=c(n-1,k1)*m*(m-1)^(n-1-k1)

Here is my approach: Consider we divide the n blocks into p sets of partitions and label them as n1,n2,n3,...,np. We could do it in (n-1)c(p-1) ways.

Another constraint is the total pairs of contiguous blocks with same color <=k. It means that (n1-1)+(n2-1)+....+(np-1)<=k which implies n1+n2+...+np-p<=k which implies n-p<=k thus we get p>=n-k

Now for coloring part of p sets can be done in m*((m-1)^(p-1)) ways.

So simply iterate p from n-k to n and add ((n-1)c(p-1)) * (m*((m-1)^(p-1))) to the answer.

Exact same problem: https://mirror.codeforces.com/gym/101341/problem/A

EDIT: link to the editorial for this problem: https://mirror.codeforces.com/blog/entry/51445?#comment-393777

difference of opening and closing brackets in non-decreasing order

(A.openCount-A.closeCount) - (B.openCount-B.closeCount)

A,B,C < 1000

D : 1200/1300

E : 1500/1600

F : 2000/2100

My best estimate:

A — 600 B — 900 C — 1100 D — 1400 E — 1700 F — 2000

Roughly, the gap in difficulty between the problems was the same.

At most K adjacent pairs can be same. So at least n-1-k pairs have to be different. Let we need to make p pairs different. So it can be done in C(n-1,p)*M*(M-1)^p. Do this for all p from n-1-k to n-1.

You can bruteforce for all 2^n possibilies since n<=12.