We will hold NIKKEI Programming Contest 2019-2.

- Contest URL: https://atcoder.jp/contests/nikkei2019-2-qual
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20191109T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: yutaka1999
- Rated range: ~ 2799

The point values will be announced later.

We are looking forward to your participation!

Is it for only Japanese or all participants?

For all participants. All rated contests in AtCoder will have English statements.

Nice and interesting contest, thanks.

How to solve C?

My solution is as follows:

First check, after sorting $$$a$$$ and $$$b$$$, is $$$a_{i}\leq b_{i}$$$ for every $$$i$$$. If not, the answer is impossible.

Note that, after sorting $$$a$$$ and $$$b$$$, if there exists some $$$i> j$$$, such that $$$a_{i}\leq b_{j}$$$, then the answer is Yes by simply putting the $$$N-1$$$ indices except $$$i$$$ and $$$j$$$ in place.

So after checking the above cases, we need to arrange $$$a$$$ in a certain permutation, and to sort a permutation, for each cycle of length $$$l$$$ in the permutation, we need at least $$$l-1$$$ swaps. So it suffices to check if the permutation consists a single cycle of length $$$N$$$.

How comes this cycle thing with l-1 swaps?

For each swap you can decrease the length of the cycle by at most one.

More generally you can break a cycle of length $$$L$$$ into two cycles of lengths $$$L'$$$ and $$$L - L'$$$ with one swap.

Pardon me, but i am a bit confused about the 'cycle' thing, can you share your code?

For cycles, search 'permutation' on Wikipedia.

My code: Code

Thank you!

$$$i > j$$$ instead of $$$i \ge j$$$ rihgt ?

Ah, yes, fixed.

Do this operation at most $$$n-2$$$ times :

for every $$$A[i]$$$, try to swap it with the maximum number $$$<=$$$ $$$B[i]$$$ in the range from $$$i$$$ to $$$n$$$ and lets denote it as $$$x$$$, so if $$$x$$$ equals $$$A[i]$$$ then don't swap the two numbers, else then swap them.

Now, check for every index $$$i$$$ that $$$A[i]$$$ <= $$$B[i]$$$.

my submission

What is the proof of this method?

i think for A =1,3,7 and B=4,8,5 it should be yes but yrs is giving no...

can you still hack it after sorting both A,B

according to B in non-descending orderso that

`A = 1, 3, 7`

and`B = 4, 5, 8`

and it will produce a`Yes`

For A=5,8,6 and B=7,7,10. It should be Yes

Edit: Distinct numbers: A=1,5,2 and B=3,4,6

By searching for this example I even found small bug in my submission which also passed systests XD

actually I don't see how this would fail, we only need to swap at the 2nd pair, and the only number on its right to swap with is 2 which make a valid sequence of

`A = 1, 2, 5`

and`B = 3, 4, 6`

so?But his algo starts at first element of A, which is 1, and swaps it with 2 because 2 <= 3 and 2 != 1

Edit: If you have some other solution in mind you can post the code and I'll try to find counterexample for it

And for (A=1,7,3 B=4,5,8) his solution gives No, and you said it gives yes

Yeah! Sorry that was a typo! [Fixed]

The solution I'm trying to hack sorts pairs of A, B according to B in ascending order and only considers such indices where

`A[i] > B[i]`

and tries to find the maximal value of A[j] where`A[j] <= B[i]`

and swaps! In case there are many such`j`

s choose the furthest maybe?I'm trying to hack it with no luck! So any help is appreciated!

A=5,2,1 B=2,3,5

Your algo tries to make 2 swaps while (5-1) swap is enough

I see, so the only way to make this fail is to target the numbers of swaps! Thanks!

Sort $$$A$$$ and $$$B$$$. If $$$A_i > B_i$$$ for some $$$i$$$, the answer is No. Otherwise, if you can swap some two adjacent elements of $$$A$$$ such that the above inequality still holds for all $$$i$$$, the answer is yes [1]. Otherwise, look at the permutation needed to bring $$$A$$$ from its original order to the order where $$$A_i \leq B_i$$$, assuming we didn't change the order of elements in $$$B$$$. The answer is Yes if this permutation has more than one cycle and No otherwise.

Note — the smallest number of swaps needed to sort a permutation is $$$n - c$$$, where $$$c$$$ is the number of cycles in the permutation. In [1], you can choose between some two permutations which differ by exactly one swap, and so they cannot both consist of only one cycle.

Suppose that $$$B_i \leq B_{i+1}$$$ and that we can achieve the required $$$n-1$$$ operations.

If there is $$$x$$$ and $$$y$$$ such that $$$x \neq y$$$, $$$A_x \leq B_1$$$ and $$$A_y \leq B_1$$$ then any pairing between $$$A_x$$$, $$$A_y$$$, $$$B_1$$$ and $$$B_2$$$ is good. Therefore, we can ignore these and pair all the rest of numbers in at most $$$n-2$$$ operations.

If there isn't any $$$x$$$ such that $$$A_x \leq B_1$$$ then obviously answer doesn't exist.

Otherwise there is exactly one such $$$x$$$. If $$$x=1$$$ then we saved one operation and can can pair the rest of numbers in $$$n-1$$$ operations. Otherwise swap $$$A_1$$$ with $$$A_x$$$ and try to solve the smaller problem with $$$n-1$$$ pairs and $$$n-2$$$ operations.

Will the editorial be translated to English?

How to solve E?

The construction is impossible if

. The above inequality is equivalent to $2K-2>N-1$.

Otherwise, the construction is always possible. For example, if $$$K=4$$$ and $$$N=7$$$, $$$(4, 14), (5, 15), (6, 16), (7, 17), (8, 11), (9, 12), (10, 13)$$$ can be made into construction. That is, divide the numbers between $$$K$$$ and $$$K+2N-1$$$ into "middle half" and "non-middle half" and pair the numbers in ascending order.

Can you elaborate the splitting, it looks to me like you are pairing middle and first element increasingly then the rest of them and please do tell what is the main idea behind such splitting. "middle half" and "non middle" didn't quite get to me.

The idea is trial and error, and in my AC solution, I first chose $$$\lceil\frac{n}{2}\rceil$$$ smallest and largest numbers and paired them, then paired remaining numbers similarly. I thought I would get AC by trying the method for various small value of $$$K$$$ and $$$N$$$.

My AC code

I have another solution.

First if k+k>n+1 ,there isn't a construction.

Then just make the construction like this:

(k,2n,k+2n),(k+2,2n-1,k+2n+1),(k+4,2n-2,k+2n+2)....

the rest, just choose the first number in the construction from the left ,the second number in the construction from k+2n-1 to the left (of course they aren't used).

Sort and match them with the rest numbers(bigger than k+2n and aren't used) from small to large.

Can anyone explain B?

Think of the tree being constructed from root to the nodes on deeper levels.

You can place any node in the numer of places parent nodes on that level exist.

So, the first node is the root node. All nodes on level 1 must be childs of the root node (on level 0), so there is only one possibiliy to place them.

Every nodes on level 2 can be placed as a child of every node of level 1. So the posibilities are numNodes(level1) * numNodes(level2)

The same is true for all other levels, too, so we need to multiply them.

Can anyone tell me how to solve F?

Really nice problem! I'll give the outline.of the solution.

Firstly, note that by flipping each interior square, we alter the points that lie on two diagonally oriented rectangles (possibly degenerate, i.e. diagonals). There are $$$n+1$$$ such rectangles, and each interior point can be encoded with a pair $$$(a, b)$$$ denoting the rectangles they "flip" (we number the rectangles by their distance of the top vertex from the top left corner of the grid). Notice that $$$a, b$$$ have the same parity and are distinct.

By flipping a point with code $$$(a,b)$$$, we flip the lights where at least one coordinate of their code is $$$a$$$ or $$$b$$$. Consider a graph on the numbers from $$$0$$$ to $$$n$$$ of the same parity. Our operation of flipping a light can be described as choosing two vertices $$$u,v$$$ and flip the edges with at least one endpoint $$$u,v$$$. A configuration of lights is nice iff the lights with the same code are consistent and there exist a sequence if operations to reduce our graph to the empty graph, where we start by drawing an edge between the numbers in the code of on lights.

We claim that if our graph has $$$N$$$ vertices, then the task is always possible if $$$N$$$ is even, and the task is possible for $$$N$$$ is odd iff the degree of each vertex is even. The necessity can be proven simply by considering the parity of the degree of each vertex after each operation.

To prove the sufficiency, firstly note that by performing operations on $$$(a,b),(b,c),(c,a)$$$ where $$$a,b,c$$$ are distinct, then we can flip only these 3 edges. For $$$N$$$ even, flip $$$(u,v)$$$ and then flip $$$(u,v),(v,w),(w,u)$$$ for all other $$$w$$$. This flips exactly one edge $$$(u,v)$$$. For $$$N$$$ odd, we claim that we can always flip an Eulerian cycle. Indeed, we can simply extend the cycle repeatedly by flipping a triangle.

Finally, it remains to count such graphs. The $$$N$$$ even case is obvious. To count the $$$N$$$ odd case consider the graph of unfixed edges. For each connected component, we can choose the existence of all edges except a spanning tree (we need to be careful about the case where the sum of "degree" of all vertices in the component is odd if we consider only fixed edges, in which case the answer is $$$0$$$ since our unfixed edges can only alter the sum of degree by an even number). This gives an $$$O(n^2)$$$ solution.

Thank you.I think very long time about "the sum of "degree" of all vertices in the component is odd if we consider only fixed edges, in which case the answer is 0".See your explanation I finally understand.Thank for you much.

Question B D1 = 0 is required for a tree to satisfy the condition, otherwise the answer is 0. In the following, D1 = 0. Consider one tree where the distance between vertex 1 and vertex i is Di, and for each vertex i other than vertex 1, let pi be the closest vertex to vertex 1 among the adjacent vertices. You can see that it is 1. On the other hand, if (p2, ..., pN) is defined such that Dpi = Di−1 (i ≥ 2), the tree consisting of the edges connecting vertex i and vertex pi is uniquely determined. Therefore, the number to be obtained is the number of (p2, ..., pN) where Dpi = Di-1 (i ≥ 2). When the number of i where Di = k is ck, the number is obtained by multiplying each integer i of 2 or more by cDi−1, so it can be obtained in linear time.

Question C B1 ≦ B2 ≦ .... ≦ BN may be set by first arranging the elements appropriately. Suppose you want to rearrange (A1, ..., AN) with (Ap1, ..., ApN). In other words, the condition that Ai ≦ Bi in the end and the condition that the number of swaps is up to N−2 times, respectively, the condition that should be (p1, ..., pN) is as follows. Api ≦ Bi • When cyclic permutation (p1, ..., pN) is decomposed into cycles, it is decomposed into two or more cycles. First, take (p1, ..., pN) so that Ap1≤Ap2≤ ... ≤ApN. If Api ≤ Bi (i = 1, ..., N) does not hold at this time, there is no (p1, ..., pN) that satisfies the first condition, so the answer is No. Consider the case where Api ≤ Bi (i = 1, ..., N). If (p1, ..., pN) satisfies the second condition, the answer is Yes is. Therefore, it is sufficient to consider the case where (p1, ..., pN) consists of one cycle when it is decomposed into cycles. Here, if Bi <Api + 1 (i = 1, ..., N−1), there is only (p1, ..., pN) cyclic permutations that satisfy the first condition. The answer is no. On the other hand, if there is i such that Bi ≧ Api + 1, the cyclic permutation of (p1, ..., pi−1, pi + 1, pi, pi + 2, ..., pN) The answer is yes. All of this is done, so you can ask for an answer. The time complexity is O (NlogN) because it sorts.

D: Shortest Path on a Line You can see that d1 ≦ d2 ≦ .... ≦ dN, where di is the length of the shortest path from vertex 1 to vertex i. Therefore, even if a zero-length edge is added from vertex i + 1 to vertex i for each i, the length of the shortest path from vertex 1 to each vertex does not change. In the following, it is assumed that all these edges are included in the graph. Considering the edge added at the i-th time, if you add an edge of length Ci from vertex Li to vertex Ri, the other edges do not affect the shortest path. This is for a vertex s, t with Li ≦ s <t ≦ Ri, there is a zero-length path from s to Li, there is a side of length Ci from Li to Ri, and length 0 from Ri to t Since there is a path, we can see that there is a path of length Ci from s to t. From the above, it can be seen that the shortest path from vertex 1 to each vertex can be found by considering only N + M−1 edges. Therefore, the Dijkstra method can be used to solve with a time complexity of O ((N + M) logN).

## Solution to D using segment tree:

Observation: If you can move to point $$$i$$$ using cost $$$c$$$, you can also move to any point $$$j < i$$$ using cost $$$\le c$$$.

Therefore, we can sort the intervals by left-coordinate and apply each interval one at a time. Here, "applying" an interval $$$(L,R,C)$$$ means compute/store the optimum cost $$$c(L)$$$ to reach $$$L$$$, then set $$$c(R) = \min(c(R), c(L) + C)$$$. We know that by the time we reach $$$L$$$, we've already found its optimum cost, because we've already processed all intervals that could be used to reach $$$L$$$ (because we sorted them). Because of the observation above, we can compute $$$c(L)$$$ once we reach $$$L$$$ by taking $$$min(c(L), c(L+1), \ldots, c(n))$$$, and it's sufficient to store $$$c(L) + C$$$ to $$$c(R)$$$ specifically, instead of all indices between $$$L$$$ and $$$R$$$.

Runtime: $$$\mathcal{O}(N + M \log N)$$$

Code (L and R are 0-indexed here)D is a well known problem,and one can search for countless solutions posted online.Many,sorry to say but it included myself,just copied the solution,modified the edge weight,and got AC.Perhaps problem setters should check for similar,or the same problems more carefully.

Excuse me, but I am having problems with proof of the observation "If you can move to point $$$i$$$ using cost $$$c$$$, you can also move to any point $$$j < i$$$ using cost $$$\le c$$$."

Can anyone give some mathematical proof?

Consider the path that goes to $$$i$$$, then it "passes through" all points $$$\le i$$$, and our definition of the graph allows us to stop at any time during our trip to $$$i$$$.

Get it. Thanks!

Can someone please help me to find why my solution does not work for problem C? I'm sorting by B and building a segment tree on A, and then for every Ai > Bi i search for some Bk >= Ai and Ak <= Bi and swap them, if there is no such Bk i try to find the Bj with the smallest Aj such that j > i and Bj >= Ai and Aj <= Bi.

Will test cases be posted?

Similar problems:

D and BZOJ 3073(pay to access)

both segment tree optimizing vertexes connecting