Thanks for the great contest and fast editorial!

Thanks for the fun contest!

The bonus of D !

Asking $$$A=[1,1,\dots,k]$$$​​​​ in which $$$k=2,3,\dots $$$​​​​, when the first time get answer $$$0$$$​​​, there is $$$p_n=n-k+1$$$​​​ if this is the $$$k$$$​​​-th query. What's more, if the answer to $$$u$$$​​​-th query is $$$b_u$$$​​​, then $$$p_{b_u}=p_n+u$$$​​. Now we get the position of $$$b_n,b_{n}+1,\dots n$$$ and only make $$$n-p_n$$$ queries.

Then asking $$$a_i=n$$$ if $$$p_i$$$ is determined, $$$a_i=k$$$ if else, from $$$k=1$$$ to $$$k=p_n-1$$$. If the answer to $$$u$$$-th query is $$$c_u$$$, then $$$p_{c_u}=p_n-u$$$.

Now we get the position of all numbers and only make $$$n$$$ queries.

And here is my solution

By the way, the girl is that "Hu Tao" in problem E.

Really a tough contest.. waiting for rating to go down....

Nice problems! E and F should've been swapped imo. E was so tedious to formulate and code. Think F would have far more solves if it were in place of E. Took an hour on E and missed F by a whisker cause of one dumb typo ~>_<~

The editorial for problem D does not respect the requirement $$$1 \leq a_j \leq n$$$ on the queries. (But it is trivial to fix this.)

I am sorry but in problem E the editorial does proves only the fact that if every vertex appears even number of times, then answer is 0.

How to prove that ANY spanning tree works if we wanna find out the minimum number of queries to be added? This is the hard part.

can anyone help me with solution C 132264422

My approach to F was different, and allows for a trivial lower bound proof.

Fix the number of colours $$$c$$$ you will be using. For every node $$$i$$$, define the array $$$LEN[i]$$$ such that $$$LEN[i][t]$$$ is the length of the longest monocoloured path of colour $$$t$$$ from node $$$i$$$. In a valid solution, we have $$$0 \leq LEN[i][t] < k$$$.

Take any optimal solution and consider these arrays. Let $$$t$$$ be the colour of the edge from $$$i$$$ to $$$j$$$. Then $$$LEN[i][t] \geq LEN[j][t] + 1$$$. This immediately shows that we must have $$$LEN[i] \neq LEN[j]$$$ for all $$$i \neq j$$$. Since there are $$$k^c$$$ different arrays, any valid solution must thus have $$$n \leq k^c$$$.

Also, given that $$$n \leq k^c$$$, we can construct a solution by assigning the possible arrays in lexicographically decreasing order.

Although I failed this contest, I really liked the originality of problem B !

Great contest! For those who prefer video explanations, I explain solutions to all problems except I and G at the end of my screencast here.

My first time to solve an interactive problem! Stuck at E and tried G but withdrew...

my solution to D is working in my device properly but when i submitted it showed TLE on permutation {1,2} anyone kindly help 132260554

Here are the video solutions to the first 4 problems. solutions

My feedback on A-G:

• A: The idea is fine but I don't like that we have to print out the subset (I can understand the reason behind this though).
• B: This feels like a hit or miss problem for me. I almost thought that we could ignore the tree condition and construct a line instead. Fortunately, I took my time and tried to use the special condition.
• C: This seems a bit difficult for its position. I would rate this somewhere between A and B in a Div 1 round. Consider that we have 6 problems after this and only 135 min, I would prefer an easier one.
• D: Nice problem that allows many approaches. Mine was also to find $$$p_n$$$ but in a different way from the one above.
• E: This one feels oddly crafted for me. You have to think why it's okay to just keep a tree (I tried to prove it but I doubt everyone would do, because printing out the paths would be too difficult if it's not true). I would rather be given a tree and asked to print out the paths in the "NO" case.
• F: I love how simple yet elegant the solution for this is. Props to the author for such a great problem.
• G: Harder version of 1552F - Telepanting but the overall idea is quite similar. The strong sample tests definitely help, too. I wish I went for this instead of F in the contest. 27 ACs seem to be a problem position effect instead.

UPD: added G

Another way to construct a coloring for F is to think about the indices $$$0$$$ to $$$n-1$$$ in base $$$k$$$. Color the edge from $$$a$$$ to $$$b$$$ by the position of the most significant digit that changes. There is no path of length $$$k$$$ with only one color as the most significant digit that changes can only increase $$$k-1$$$ times.

Wow, how beautiful the solution to F is!

Thanks for the interesting problems and +114 rating!

Can I asked for a solution in problem B if (m >= n)?

I'm curious about the special judge for problem B.How to check an output is valid or not quickly(I can only thought about a data structure which is O(n log^2 n))?

Thank you , Hutao , for this fantastic contest . The division degree is good.

In problem H,I have a different way on maintaining the information.

After off-line the queries,it requires us to find out the maximal toll on the road to the reachable cities with the maximum enjoyment value.And the maximum enjoyment could be saved on Link-Cut-tree with set maintaining the maximum value of each node subtree,while the maximal toll could be found at the same time.

Unfortunately,I would have thought that 3 seconds were enough for n log^2 n.It took me more an hour to get the program faster and faster.In the end,I control the size of each set no more than 3,because there is no edge cutting operation,with the time complexity O(n log n).

I have only solved A and H,and I have known I'm doing wrong.Now,I'm learning how to use binary search.

A stupid $$$O((n+q) \log^2 (n+q))$$$ solution for H:

First find out the answer to the first question using dsu. Then do centroid decomposition to find out the second answer. Let $$$mx_u$$$ and $$$mi_u$$$ respectively be the maximum toll and minimum capacity from $$$u$$$ to centroid, and $$$bel_u$$$ be the subtree within which $$$u$$$ lies. Then, we just have to find out the following:

• $$$bel_v\ne bel_u$$$.
• $$$\min(mi_u,mi_v)\ge V$$$. ($$$V$$$ is the number of vehicles in the query)
• $$$a_v=ans1$$$. ($$$ans1$$$ is the answer to the first question)
• among those $$$v$$$, the maximum value of $$$\max(mx_u,mx_v)$$$.

By maintaining a segtree independently for each $$$a_v$$$, the whole task can be solved in $$$O((n+q) \log^2 (n+q))$$$. (without any observation)

Why is this giving TLE on 2nd test case whereas it runs just fine on other IDE

my solution

How to solve B? if m may not be less than n

I really like the way D was made. It was easy but little trick at the same time. Thanks for this

In problem C, I can not understand the meaning of "This includes the cell itself, so all filled in cells are not exitable".

The thicken words for B is really useful! :)

I think the proof of F doesn't seem so right....How can the necessity be proved like that?

[solved]

The editorial of G is very long and I had to be patient enough to read it carefully. However, I didn't understand the sequence "Specifically, we can represent a valid set v as the set u of intervals that aren't implied to be in v by any other element of v" after reading it again, again, again, again, again and again. Though I asked many other people, I still found it hard to realize what it exactly mean... So is there any people who is good at English explain about it? Thanks. Sorry for my poor English:(

How to solve B if number of restrictions is not necessarily less than n?

We can also solve the problem D using the binary search. We can first try to find the value of pn i.e. the last element of the permutation. We can query the maximum diff such that p[n] + diff would exist twice in the array. For example lets say p[n] is 5 and n is 7 then diff would come out to be 3 because 5 + 3 will occur twice in the array (5 + 3 and 7 + 1) if we chose our array a to be [1, 1, 1, 1, 1, 1, diff] and 3 is greatest amongst all such diff values. Then pn can be easily computed as n - diff + 1 i.e. 5. It would require aroung log n queries to find the value of diff.

Then we can do the classic n - 1 queries to find the remaining n - 1 elements. 

Total queries: log n + n - 1.

Another way to think about the tree reduction for E. Thanks to SecondThread for the helpful explanation.

Suppose we have a cycle $$$C = c_1 c_2 \ldots c_m c_1$$$ and we remove an edge $$$e = (c_k,c_{k+1})$$$ from the graph. Now for each path that originally contained $$$e,$$$ say $$$P = v_1 v_2 \ldots v_i (c_k c_{k+1}) v_{i+3} \ldots v_j,$$$ we now remove $$$c_k c_{k+1}$$$ and reroute to the rest of the cycle, ie. the new path is $$$v_1 v_2 \ldots v_i (c_{k} c_{k-1} \ldots c_1 c_m \ldots c_{k+1}) v_{i+3}\ldots v_j.$$$ If we do this for every original path that contained $$$e,$$$ which is an even number of them* (see the note at the bottom), we see that the edge weight of $$$e$$$ goes to $$$0$$$ (even), and we add $$$e$$$'s original weight (an even number) to each of the other edges in $$$C \setminus e.$$$ Since all weights were originally even, the weights after rerouting all paths that originally contained $$$e$$$ are also all even. We can keep removing edges this way until we are left with a spanning tree.

However, the new path may no longer be simple (ie. it will repeat edges if $$$P$$$ contained any edges in $$$C \setminus e.$$$) But it turns out that having non-simple paths is fine at the end when we are left with a tree. Why is this true? Intuitively if we have a non-simple path in a tree, if we go down and visit a child and then come back up, we could just delete this because it cancels and the parity isn't changed, and we can turn it into a simple path.

Thus we have shown: If there is a valid solution with simple paths on $$$G,$$$ there is a valid solution using (possibly non-simple) paths on any spanning tree $$$T$$$ of $$$G,$$$ and further, any solution on a tree with non-simple paths is equivalent to a solution using the unique simple paths of $$$T,$$$ and the proof is complete.

F is amazing! Spent a whole day convinced that the answer was $$$\lceil \frac{n}{k} \rceil$$$ and stumbled upon the correct solution after repeatedly failing to prove it.

Simpler solution for problem G:

Firstly, like in editorial, we consider each task $$$p$$$ to be an interval $$$[a_p, b_p]$$$ on the number line. Now, passage of time and time travels can be visualized as okabe moving forward by 1 step and teleporting backwards on this number line.

Observation 1: Whenever okabe reaches some point $$$x$$$ on this number line, such that $$$b_p = x$$$ for some $$$p$$$, then at that moment of time, any task $$$q$$$ with $$$b_q < b_p$$$ will be completed. (easy to prove by contradiction, as existence of incomplete task $$$q$$$ with $$$b_q < b_p$$$ would imply we teleported forward at some point of time).

Now, let us consider some incomplete task $$$p$$$. When okabe reaches point $$$b_p$$$, he will teleport backwards, then travel for some time (with some intermediate teleports), and then finally reach $$$b_p$$$ again.

Let us define $$$dp_p$$$ to be the number of teleports which okabe needs to perform before first reaching $$$b_p$$$ again, after teleporting back from $$$b_p$$$ when $$$p$$$ was incomplete.

Observation 2: $$$dp_p$$$ (ie. the number of teleports to reach $$$b_p$$$ again), does not depend on the completion status of any other task. This is true because only some task $$$q$$$ with $$$b_q < b_p$$$ can affect $$$dp_p$$$ and any such task is always completed at any instance of us teleporting back from $$$b_p$$$ by observation 1. It does not matter whether any task $$$q$$$ with $$$b_q > b_p$$$ is completed or not, because we will reach $$$b_p$$$ before reaching $$$b_q$$$.

Now how do we calculate $$$dp_p$$$ for some $$$p$$$? Firstly, notice that we never go behind $$$a_p$$$ before reaching $$$b_p$$$ first. This is easy to show , because going behind $$$a_p$$$ would imply that there exists some incomplete task $$$q$$$ for which $$$a_q < a_p$$$ and $$$b_q > b_p$$$. But this is a contradiction to the fact that all such tasks were complete before teleporting back from $$$b_p$$$, and teleporting behind from $$$b_p$$$ only ever resets completion status of tasks $$$r$$$ with $$$a_p < a_r$$$ and $$$b_r < b_p$$$.

So this means that only tasks $$$q$$$ with $$$a_q > a_p$$$ and $$$b_q < b_q$$$ contributes to $$$dp_p$$$. As it turns out, $$$dp_p$$$ is simply $$$\sum{dp_q} \quad \forall q | (a_q > a_p, b_q < b_p)$$$.

Why is this valid? It's because this corresponds to only considering each task $$$q$$$'s contribution to be the number of intermediate teleports we make to reach $$$b_q$$$ after first teleporting back from $$$b_q$$$ (which is nothing but $$$dp_q$$$), and this is clearly a valid and complete formulation. $$$dp$$$ value for all tasks can be computed easily in $$$O(n\log{n})$$$ by using any point update range sum query structure.

Now, for the final part of the problem, we need to figure out the least time by which all the tasks in the given set of tasks $$$S$$$ are completed.

Let us define $$$opt_p$$$ to be the task $$$q$$$ with the maximum $$$b_q | (a_p < a_q, b_q < b_p)$$$.

Let $$$x$$$ be the task with the maximum value of $$$b_x \quad \forall x \in S$$$.
Now, consider why the answer is not simply $$$\sum{dp_q} \quad \forall q | (b_q \leq b_x)$$$

Notice that for task $$$x$$$, after we teleport back from $$$b_x$$$, do some intermediate teleports, and reach a state wherein $$$opt_x$$$ is completed, we do not need to travel forward anymore (ie. we do not need to reach $$$b_p$$$ again). So basically, if we consider the answer to be $$$\sum{dp_q} \quad \forall q | (b_q \leq b_x)$$$, then we need to subtract $$$dp_r$$$ from the answer for all $$$r$$$ such that $$$a_r > a_p, b_r > b_{opt_p}$$$. Now, similarly for $$$opt_p$$$, we do not need to reach $$$b_{opt_p}$$$ again, so we do not need to travel anymore after teleporting back once from $$$b_{opt_p}$$$, and $$$opt_{opt_p}$$$ getting completed. This is to be done recursively till we reach a task which has no task's interval lying within its own.

As $$${opt_p}^{x + 1} < {opt_p}^{x}$$$, we can simply use two pointers to do this final recursive procedure in $$$O(n)$$$ at the end.

Implementation: link