Yeah, may the next destination of tourist is 5000+ rating

jiangly will be the next tourist.

I second that.

are there any requirements for joining?

Sadly you can confirm what'll happen now

Did you sacrifice points to find the answer to your question? I am genuinely interested in the answer too, please give an update.

Ok so turns out I am not going to fall back to cm

CF Div1 >>>>>>>> Luogu

He did'nt participated

Are boarding schools common in your country? Are they strict?

this is always the case for combined contests.

well done

That's impressive.. But is this your alt account?

Lost rating sadly... But the process of my performance in this contest is so dramatic that I want to share it.

• Solved A~D.
• Tried to solve E. Got the idea and implemented it in thirty minutes, but the code got a wrong answer. There were thirty five minutes left.
• I didn't know why my code is wrong, so I wrote a stress test. Sadly, the code didn't failed when the n is less than 10, but it failed when n is less than 20. Due to the large scale, I couldn't analyze such a big tree.
• In the last few minutes of the contest, I just randomly modified my code. Surprisingly, when I did a change which was useless in my mind, my code worked! I submitted my code when it was only twenty seconds left. But it got a "wrong answer on test 1"! I checked it and found that I submitted to the problem F. It was only one second left, the contest ended.
• After contest, I submitted the code I had submitted to F to E. It passed.

How do you know this? Submissions aren't public and you haven't locked the one problem you solved.

i hope cheaters like udgm get banned sooon.

It was a simple greedy problem!

I spend the whole contest on it (after I solved c and came back to it) and then the problem was just I used int instead of long long :)

No: I have only KMP.

FFT in 1C?

EDIT: probably wrong, ignore

I don't think so, given that you only really need to solve the problem for $$$k=2$$$ and $$$k=4$$$ (for all "normal" cases, $$$k=1$$$ works and other values of $$$k$$$ fail).

The solution comes down to the following observation:

In an SCC component $$$G$$$ for a directed graph, denote by $$$h[v]$$$ the distance from the (arbitrary) root of the vertext $$$v$$$ in the DFS tree of $$$G$$$. Then $$$k$$$ divides ALL cycle lengths iff: for each edge of the graph $$$u$$$ to $$$v$$$, we must have that $$$h[v] \equiv (h[u]+1)$$$ $$$mod k$$$

We need the digraph to be an SCC for this lemma to hold because of edges across SCCs don't have to be part of cycles.

With this observation, the problem is simple: we need to perform DFS over the 2 SCCs we are given. Now, if the 2 given SCCs dont form a cycle (all edges from one SCC are outgoing), then the answer is always YES, of course.

Otherwise, we need to find the "shift" of the second DFS tree wrt the first mod k. This is just finding if two arrays are cyclically equivalent, which can be done by hashing easily.

Very strong examples. I'm amazed. Got -9 on 1C.

Yes.

nah it is like a difference array except for minimums

how did u do d?

just sort the arrays ascendingly based on the summation of their two elements

I have another approach. Simply Sort the vector<pair<int, int> pr(n) based on,

1. whichever pair has minimum value of x = max(pr[i].first, pr[i].second) comes first.

2. if some pairs have equal values of x, then whichever pair between them has a minimum value of y = min(pr[i].first, pr[i].second) comes first.

3. if some pairs also have equal y value, then whichever pair has pr[i].first < pr[i].second comes first.

   sort(pr.begin(), pr.end(), [](pair<int, int> &a, pair<int, int> &b) {
      int maxA = max(a.first, a.second);
      int maxB = max(b.first, b.second);
      if (maxA != maxB) {
         return maxA < maxB; 
      }
      int minA = min(a.first, a.second);
      int minB = min(b.first, b.second);
      if (minA != minB) {
         return minA < minB; 
      }
      return a.first < b.first;
   });

you may not believe me, but its neither :O

you can also connect the 2nd graph back to the first graph (and it's not simply just (x+C)%k)

You need one extra step: checking if the new cycles formed by the edges you added alsohave lengths divisible by $$$k$$$. For all edges $$$(a_\mathrm{in}, a_\mathrm{out})$$$ from graph 1 to graph 2 and $$$(b_\mathrm{in}, b_\mathrm{out})$$$ from graph 2 to graph 1, you need to check if $$$(a_\mathrm{out} - a_\mathrm{in}) + (b_\mathrm{out} - b_\mathrm{in}) + 2 \equiv 0 \pmod k$$$.

In your solution, this corresponds to checking whether there are a pair of $$$C$$$'s for both "directions" of edges which have a difference of $$$- 2$$$ under modulo $$$k$$$.

Wait what do you mean, i tried this in contest and it didn't work for me.

Suppose you put the array with the bigger maximum in front of the one with the smaller maximum, now you will create more inversions.

I got WA when I did it like that, then I sorted them based on the summations of the two elements no the maximum

I sorted based on minimum first and then maximum only to get WA on pretest 4. Then, I reversed the order and got AC. Still not able to understand how the order of checking min/max is affecting the algorithm.

You can look at it as a directed graph. Every back edge is free, and every edge going forwards costs you the points that the starting point is worth, then its a simple dijkstra

Actually 1B/2D can be solved without Dijkstra, but rather with DP optimized with BIT.

Consider pairs $$$(a,b)$$$ and $$$(x,y)$$$. If conditions $$$\min(a,b)\le \min(x,y)$$$ and $$$\max(a,b)\le \max(x,y)$$$ are both true, it's obvious that we should put the first pair before the second pair.

If such condition doesn't meet then their relative position doesn't matter.

let inv(A, B) be the number of inversions if position of pair A < position of pair B

if A.first + A.second = B.first + B.second then inv(A, B) = inv(B, A).

if A.first + A.second < B.first + B.second then inv(A, B) <= inv(B, A), because max(B) > max(A) or min(B) > min(A) holds

exactly. it looked like graphs but i wasn't sure on then how to use that knowledge