We will hold AtCoder Regular Contest 140.

- Contest URL: https://atcoder.jp/contests/arc140
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220515T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: PCTprobability, nok0
- Tester: Nyaan
- Rated range: — 2799

The point values will be 300-400-500-700-800-900.

We are looking forward to your participation!

Wish me luck.

Good luck

Good luck.

good luck

randomization can't solve problem E >3

sure? this problem with c=3, n<=10 was in russian regional olympiad several years ago and proper solution is randomization

Anyone else got WA on 1 test case in C?

Took almost an hour to realize it was |P[i]-P[i+1]| instead of P[i]-P[i+1] in C lmao

Bonus: the solution to problem E can be slightly modified to obtain a $$$625\times 625$$$ board. Can we construct a greater square board?

I can't do better with a square board, but I think $$$625\times 650$$$ is possible. Identify the labels with elements of the finite field $$$\mathbb{F}_{25}$$$, the rows with ordered pairs $$$(u, v)\in \mathbb{F}_{25}^2$$$, and the columns with tuples $$$(a, b, c)\in \mathbb{F}_{25}^3$$$ where $$$(a, b)$$$ is restricted to the set $$$\{(1, x) \mid x\in \mathbb{F}_{25}\}\cup \{(0, 1)\}$$$. Then the label at the intersection of $$$(u, v)$$$ and $$$(a, b, c)$$$ is $$$au+bv+c$$$.

Let's choose distinct rows and columns $$$(u_1, v_1), (u_2, v_2), (a_1, b_1, c_1), (a_2, b_2, c_2)$$$ and suppose that the corners all have the same label. If $$$(a_1, b_1) = (a_2, b_2)$$$ then $$$c_1\neq c_2$$$, so $$$a_1u_1+b_1v_1+c_1 \neq a_2u_1+b_2u_1+c_2$$$, i.e. the corners don't have the same label. Otherwise, $$$(a_1, b_1)\neq (a_2, b_2)$$$ so then $$$(u_1, v_1)$$$ is uniquely determined by $$$a_1u_1+b_1v_1+c_1$$$ and $$$a_2u_1+b_2v_1+c_2$$$. However, $$$(u_2, v_2)$$$ is determined by the same constraints so we would get $$$(u_1, v_1) = (u_2, v_2)$$$ contradiction.

Also, by a counting argument, $$$625\times k$$$ is not possible for $$$k > 650$$$.

If you can get $$$625 \times 650$$$, you can also get $$$625 \times 625$$$ by cutting the board (?)

The board $$$625\times625$$$ can be achieved just by placing $$$x_1x_2+y_1+y_2$$$ almost like in the editorial, but picking $$$x_{1,2}$$$ and $$$y_{1,2}$$$ from $$$\mathbb{F}_{25}$$$ instead of $$$\mathbb{Z}_{23}$$$. The question is, can you do at least $$$626\times 626$$$?

Could anyone share the reasoning behind the particular construction in E (mentioned in editorial)? Thanks in advance!

Source: I spent almost the whole contest on problem E, and I got AC $$$37$$$ seconds before the end.

My notes: PDF

I can't understand the editorial of D. What is "number of cycles that contain vertices in the connected components numbered x1...xk" mean?

If we consider directed edge (i->xi), then each vertex will have out degree of exactly 1. Because of that, if we consider one graph such that all xi != -1, then each component will have at most one cycle if there are any.

No. of connected components = No. of vertices — No. of edges + No. of cycles

Initially we will have n components in which no edge is added. We will start adding edges one by one. Adding each edge will reduce the component by one unless we are already in a same CC in which it won't reduce. All such edges will have one to one mapping with cycles. So we can count cycles instead.

Now if we consider the graph with X array given in the question. We will get some components. Each component will have at most one xi = -1. We only consider the component with xi =-1 as we are interested only in cycles.

Let the size of components be A1,A2...AM where M are the number of component which have xi = -1

Consider the cycle formed from component set {A1,A2,A3...AK}. We can permute them in (k-1)! ways. And then we connect the edges. There are A2 edges we can direct of comp1 to comp2, A3 edges we can direct from comp2 to comp3 ... and A1 edges we can direct from compK to comp1. Then we can choose remaining edges arbitrarily. So we multiply N^(M-k).

Thus for component set {A1,A2...AK} we have (k-1)! * A1 *A2...*Ak * N^(M-k)ways to form a cycle. So we can use NTT to find Summation of product of (A1*A2*A3..AK) for each k.

Thanks a lot.

Coming to ask for some help. Would anyone like to talk about problem D in more details? The editorial of problem D is somehow not so clear, at least for me :(

I think this is about combinatorial mathmatics, but still not able to find out how to deal with it.

Hello there, I'll try my best to give a clear explanation about the solution.

first of all, let's assume that the given array contains no -1 (in other words, all edges are given). By looking at a single component of the graph, you can see the number of edges in it are equal to the number of nodes, since as given in the input there is a single edge having a starting point at each particular vertex.

Therefore, for every graph built in the same manner as the problem asks, it is enough to count the number of it's cycles and add these numbers up to form the answer. So from now on, we forget about the main problem and solve the new one, which is counting the number of cycles of all the graphs that can be built.

Array A may contain values equal to -1, let's see how the graph will look if we forget about these edges. There will be a bunch of components, each one having at most one cycle since there is at most one vertex in each with no edge starting at it.

Now instead of counting for each graph the number of cycles it contains, we can count for each cycle the number of graphs which contain it and sum these values up. Think of a cycle which there are T other values equal to -1 in A other than those used to make the cycle. Then there are n^T graphs containing the cycle. So if there already exists a cycle in a component of the given graph, just add n^(the number of -1s) and forget about these components.

What is left, is a group of components, each looking like a tree, with exactly one node in them that you can add an edge from it to any other node to make your cycles. Consider a cycle using components with size B_1, B_2, ..., B_x. Then there are exactly

`(x - 1)!(B_1 * B_2 * ... * B_x)`

cycles that can be formed since you can put these components around a circle and then connect each component to the next one. So now you just have to calculate sum of the given expression for all components, which can be done using dynamic programming.

Here's also my code for better understanding of the solution

CodeI hope this helps :)

Thank you so much for your detailed reply and paticient help, and I have learned a lot from your words.

I think I have missed at least two important observations that prevent me from solving this problem.

The first one is, if we ignore all -1, the left nodes will form several connected components, and each of them either contains a cycle or looks like a tree. If it already has a cycle, then we don't need change it, while if it is a tree, then we should add one more edge to it, and this is what we should compute.

The second one is, as you said, "Now instead of counting for each graph the number of cycles it contains, we can count for each cycle the number of graphs which contain it and sum these values up. ". This is an important "transformation" of the original problem which makes the calculation available, and this is very tricky!

Thank you so much again for your help, and hope that one day I could handle such problem on my own.

Since functional graphs (N nodes, N edges) are not necessarily simple cycles, why must the component be a simple cycle?

I'm afraid I don't understand your question. Actually, the point that I am making in my explanation, is that since each functional graph has exactly one cycle, counting the number of cycles will be enough to solve the problem.

Also when building a new component by merging some of the given components, the new component will not always be a cycle.

Oh I see. I thought you meant that each component is only one cycle. Thank you for your explanation and follow-up!

Thanks for the

muchbetter explanation than the original editorial. I understand the subproblems and equations from your explanation but I can't figure out the DP recurrence, nor the DP state.What is your DP state, and your DP recurrence?

Hi, I wrote problems B, C, E. Thank you all for your participation!!

Thank you so much for creating such great problems.

Problem B is a nice practice for greedy algorithm, and I think there are several corner cases which one should take care of.

As for Problem C, I missed the simple solution in editorial and used a more complicated one, but anyway, I have learned a lot of exciting ideas from your problems, thanks a lot!

I'm glad to hear that! Thank you!

B and C maybe a bit simple for me. Thanks for Problem E. I took really much time in it in the contest (sadly didn't solve D or E), and was happy when I could explain and proof the solution clearly.

Really a nice construction round, thank you again. ;)

Thank you for solving my problem E!

I'm not good at construction problems, but I like them :)

Could anyone explain how so solve case $$$M=1$$$ in problem F. I don't understand clearly of the last part of the editorial.

Thanks!