If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.

Divison 2

• A: Everything Everywhere All But One
• B: Odd Subarrays)
• C: Circular Local MiniMax
• D: Linguistics
• E: Bring Balance
• F: Permutation Weight (Easy Version)

Divison 1

• A: Circular Local MiniMax
• B: Linguistics
• C: Bring Balance
• D1: Permutation Weight (Easy Version)
• D2: Permutation Weight (Hard Version)

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

Very good problems! I like this types problems!

I just realized on reading this that reversing a substring in D1C means actually reversing order of the substring, not flipping every bracket in the substring :(

Would have been nice to have a sample/statement exactly capturing that, though (I think none of the samples differentiate between these two interpretations?)

.

I personally like adhoc problems, and do best when the problems require less topic-specific knowledge, less coding, and more thinking.

Not everyone agrees, but I loved Div 2D.

I didn't like the problem names. They were boring.

How many constructives?

"Yes"

How did you write the checker in 1685E - The Ultimate LIS Problem?

For 1686A - Everything Everywhere All But One, suppose the number to be excluded is at index $$$r$$$, we require:

Therefore, the required condition becomes:

Which is the same as asking the question

Nothing new here i suppose, but I found this easier to code than what's in the editorial.

int sum = std::accumulate (arr.begin( ) , arr.end( ) , 0 );
if(sum % n == 0 && find(arr.begin(), arr.end(), sum/n) != arr.end()) {
  cout << "YES" << endl;
}
else{
  cout << "NO" << endl;
}

Complete code: 158477863

Problem D can be generalized further: given $$$n$$$ pairs of (arbitrary) integers $$$(a_i, b_i)$$$, find the (lexicographically minimal) permutation $$$q_i$$$ which minimizes $$$\sum_{cyc} \lvert a_{q_i} - b_{q_{i+1}}\rvert$$$. In this phrasing, this problem is quite similar to IOI 2016 railroad.

Consider the graph with 1 vertex per integer. Let's view the pair $$$(a_i, b_i)$$$ as a directed edge from $$$a_i$$$ to $$$b_i$$$. Now, we want to add the minimum number of directed edges $$$i \to i+1$$$ or $$$i+1 \to i$$$ so that we can form a valid Eulerian tour through all edges. To do this, we should first make sure that the number of edges crossing between each integer in each direction is balanced (in problem D, this is always the case, since all given vertices have indegree and outdegree equal to $$$1$$$). Then, we need to add the minimum number of pairs of edges $$$i \to i+1$$$ and $$$i+1 \to i$$$ to make the graph connected, which reduces to minimum spanning tree.

We can still find the lexicographically minimal permutation in $$$O(n^3)$$$ time by trying to add each possible next edge, and checking if it's still possible to finish the Euler tour, which turns out to only require checking some connectivity conditions.

Why I couldn't see editorial in div2's Contest materials? plz fix it :)

upd：now I can see it, thanks for fixing it!

Best contest I've ever wrote. Really nice problems!

I hate linguistics now.

For some reason, understanding the explanations in this editorial itself seems difficult, for me :(

Really wondering how the top 100 come up with

Key observation: It's always possible to get a balanced sequence in at most 2 operations.

in contests in a couple of minutes...

"wrong answer Jury found the answer but participant didn't (test case 1435)" this verdict on 3rd problem test case 2.

Where did I go wrong? Submission--> 158448669

Implementation ?

How can one notice that the answer is at most 2 in D2E/D1C? I wouldn't have ever guessed that if I didn't look at the solution. How to come up with this myself?

Problem (1686A — Everything Everywhere All But One) can be solved simply by computing the average of that array as avg (type: double), then searching for avg in the array (normal search: O(n/2), binary search: (O(log2(n)), although the normal search is enough to accept. Isn't it simpler than the tutorial?

P/S: sorry for my bad English, I translated it myself.

Can anyone please help me on how to solve problem D, in Div2?

Thanks for the contest, I enjoyed it a lot! Why in the "Linguistics" task we don't check the same initial condition for the letter "B"? Moreover, in the editorial it is said we are sure that the number of characters A and B is correct because of the initial check. I imagine a=1, b=0, c=1, d=1, and a string AABBABBBB. a + c + d = 3, it passes the initial check. But we see we don't have enough B's.

My solution for problem D(Linguistics) and an attempt to explain it.

This is my first time explaining a solution in writing on Codeforces. Suggestions are welcome and please point out the mistakes.

**I can't find the test case. I got WA on the 1435th token of the 2nd test. Please tell me the test case,this is my submission id:158613119 **

For anyone trying to upsolve D1D2: In the editorial for problem D1D2 it gives a list of criteria that is sufficient, but when I tried implementing it I got wrong answer. I think they forgot one constraint: "There is no $$$x$$$ such that there is a left segment $$$i$$$ with $$$l_i < x < r_i$$$ and a right segment $$$i$$$ with $$$l_i < x < r_i$$$.

Can anyone tell me that in the proof part of div2D,what's the meaning of "+" and "$$$\sum$$$" in

,are they equivalent to $$$\cup$$$ here?

Div2, Problem A

https://codeforces.com/contest/1686/submission/158501965

I got WA in the 2nd test. Can someone kindly tell/give an array where my code won't work?

My logic was, for a sorted array the mean value will be at the center. So I considered the middle value and checked if the (sum-mid value)/(n-1) = mid value. If not, then answer is No, else Yes.

Sounds crazy, problem F in div.2 we can solve it in $$$\mathcal{O}(n\log n)$$$ just like the editorial. But the limit of $$$n$$$ is $$$\sum n\leq400$$$. It's really crazy!

159346667 I am getting an error in the 1435 test case. I'm not able to figure out whats wrongs. would appreciate if someone could help. [problem:D1A]

In d1D2 I think a condition is left out by the editorial: for $$$1\le i\le n$$$, if $$$i$$$ is covered by two segments (we know they are a left segment and a right segment), it's an endpoint of one of the two segments. This guarantees $$$i$$$ is in the correct cycle in graph $$$G$$$.

For example let's consider $$$p=[1,4,3,6,5,2]$$$, and $$$[1,3,5]$$$ as a prefix of $$$q$$$. We have a left segment $$$[1,3]$$$ and a right segment $$$[1,3]$$$. $$$[1,3,5]$$$ is a possible prefix for an optimal $$$q$$$ according to the five conditions in the editorial, but in fact we see $$$1$$$ and $$$3$$$ make up a cycle without $$$2$$$. By the way, the answer of $$$p=[1,4,3,6,5,2]$$$ is $$$q=[1,3,6,4,5,2]$$$.

The proof that the six conditions are enough is left to the reader as an exercise. x

For the D1B proof, shouldn't the $$$k$$$ in $$$(c, d) \in f\Bigg(\sum_{u\in U} k + \sum_{v' '\in V\setminus V'} (v' ' - 1) + \sum_{w' '\in W\setminus W'} (w' ' -1)\Bigg) + \bigg(\sum_{v'\in V'} v', 0\bigg) + \bigg(0, \sum_{w'\in W'} w'\bigg)$$$ be $$$u$$$?