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.

recursion approch. check all posibilities, cauz constraint is very less(2^12)*12.

M and N were very small, so you were able to brute force and test every possible combination of books bought vs cost.

Use bitmask to consider all possibilities and update the minimum cost if it's valid.

Submission

With only $$$N = 12$$$ books, you can brute force all possible sets of them ($$$2^N = 4096$$$) and find the minimal cost. An easy way to work with it is to have an integer where $$$i$$$-th bit is set if you take $$$i$$$-th book.

Just a brute force for all 2^N combinations. My solution

I just used brute force. Try all possible subset of rows using bitmasks. The constraints imply this will fit within time.

Thanks for your solution but can I solve E with dp ?

Hey, for choosing x components from n elements, there should be (n-1)C(x-1) ways, right? Then why did you multiply each m*(m-1)^(x-1) element by (n-1)C(x)? UPD: I understood my mistake.

The Japanese tutorials are usually posted quite early after the contest ends. You might have to wait a day maybe for the english editorial sometimes. But you can always use Google Translate :).

(

)((

()))

If a string looks like '))(((((...' you cannot use it everywhere. Each string has a balance and a min value of needed balance before that string.

same :-( still around half of all test cases passed.

To check if a bit is set or not, you don't need to convert it to string.

For example to check if jth bit in X is set or not, you can simple check the value of (x & (1<<j))

This might help

My ideas was also exactly this. It doesn't work for me too :( Can someone give a counter example for this idea?

Try the following test case :

["(((", ")", ")))("]

The correct answer is yes

EDIT : Formatting

This approach will fail for the following case:

3
(((
())
)))(

After taking first string, you should take the third one, but according to your algo, you will take the second one.

Why "equal to prev"?

We can use a string at a position if the current balance of open/close is bigger than the needed open brackets before that string.

To greedyly find a seq we can use all strings with above property, and would use the one with the biggest balance. Since that one gives most oportunities for the next step.

On each step we need to check if balance is smaller/bigger than needed open brackets.

But I do not get how to implement this in O(n logn)

Edit: Ok, did not see that: Every string has a third property, the number of closing brackets which must occour after it. We need to consider this, too.

you missed the case when k<a. In that case answer is just 'k' but your code prints 'a'

Very nicely written pls make of codeforces as well.

Read about Binary Lifting.

Using min-cost max-flow, take n nodes to the left side ( represents books), m nodes to the right side ( represents algorithms), connect a source to all the n nodes in the left with capacity = total understanding it provides for all algorithms, and cost = cost of the ith book. connect sink with all the m nodes to the right with capacity x and cost 0, also for all the n nodes in the left, connect to each of the m nodes with a capacity equal to a[i][j] and cost 0. Now perform min cost maxflow algorithm and for the maximum flow calculate the minimum cost, if the maximum flow is not equal to m*x, then the answer is -1.(maximum flow cannot be greater than m*x since the capacity of all the edges to sink is x).

https://www.dropbox.com/sh/nx3tnilzqz7df8a/AAAYlTq2tiEHl5hsESw6-yfLa?dl=0 ,but the testcases of this round have not been added. Check again after few hours.

https://mirror.codeforces.com/blog/entry/77148?#comment-619315

Testcases are available at this link after some days https://www.dropbox.com/sh/arnpe0ef5wds8cv/AAAk_SECQ2Nc6SVGii3rHX6Fa?dl=0

Use brute force over all 2^n possibilities. I use bitmask to do so. https://atcoder.jp/contests/abc167/submissions/13070747

0/1 knapsake also works