antontrygubO_o's blog

Editorial of Codeforces Round 794
By antontrygubO_o, 3 years ago, In English

I hope you enjoyed the round.

While problem D1B was good for balance in Div1, it was too hard for balance in Div2. I apologize for this.

Problem D1B = D2D is by dario2994. Other problems are mine.

D2A
D2B
D2C/D1A
D2D/D1B
D2E/D1C
D2F/D1D1
D1D2
D1E
  • Vote: I like it
  • +250
  • Vote: I do not like it

Comments Comments (88)
| Write comment?
»
3 years ago, # |
  Vote: I like it -7 Vote: I do not like it

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

Divison 1

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).

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    I can't find the test case.I got wa on 177th token of 2nd test.Please tell me the test case,this is my submission id:158470917

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      Consider this testcase in Ticket 7727.

      What's special about this testcase? All numbers are in $$$[0, 3]$$$, and $$$sum(array) = Length(arr)$$$. Hence, if you partition the array at $$$1$$$, the AM would be $$$49/49$$$, which would convert all numbers to 1. Hence, the answer is YES, but your code prints NO.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thankyou so much,can you please tell me what's wrong with my code,as far as i see the logic seems to correct as well.But somehow the value stored in my 'ms' variable doesn't end up in it,and it doesn't get checked at all ,not until i try to print it externally.

        → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    It says "Python supported has been temporarily disabled..." for Div2 A

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I cannot find the test case responsible for my WA.https://mirror.codeforces.com/contest/1685/submission/158616772 is the link to my submission.

    → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Very good problems! I like this types problems!

→ Reply
»
3 years ago, # |
  Vote: I like it +97 Vote: I do not like it

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?)

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I made the same mistake as well. I wrote and submitted a solution using stack that solves the flip problem (158461024). Not sure about correctness though.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Silly in retrospect, but I also made the same mistake.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the same as me

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -51 Vote: I do not like it

.

→ Reply
»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +27 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

How many constructives?

"Yes"

→ Reply
»
3 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +70 Vote: I do not like it

    If exactly one of jury and participant found such k after some update, check if that k works, and return with WA or fail.

    Otherwise, look at the instances where ks found by jury and participant were different. Briefly, check random ~1000 of them.

    This approach doesn't guarantee that submission will give WA even if its output is incorrect, so we disabled hacks.

    → Reply
»
3 years ago, # |
  Vote: I like it +37 Vote: I do not like it

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

$$$\dfrac{\sum_{i \neq r} a[i]}{n-1} = a[r]$$$
$$$\implies \sum_{i \neq r} a[i] = a[r] \cdot (n-1) $$$
$$$\implies \sum_{i} a[i] = a[r] \cdot n $$$

Therefore, the required condition becomes:

$$$\dfrac{\sum_{i} a[i]}{n} = a[r]$$$

Which is the same as asking the question

$$$\text{Is the average of the list present in it?}$$$

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

Code

Complete code: 158477863

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    This is how I solved it and I think this approach is much more elegant!

    → Reply
»
3 years ago, # |
  Vote: I like it +102 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Good job!

    I also remembered this problem, but decided not to open the editorial (which was a mistake). I think this reasoning is much easier to understand than the one from this blog.

    To clarify, we have directed edges $$$(b_i, a_i)$$$ and want to construct edges $$$(a_i, b_{i+1})$$$ for some permutation to minimize length of euler tour. Turns out, for me it was hard to understand how to fulfill the condition that each node must have one ingoing and one outgoing edge (which is kind of necessary to construct a solution). The proof is: construct an euler tour (it is necessary to have balances zero and graph connected, and it is also sufficient — even with big edges $$$(b_i, a_i)$$$ that are actually not many small ones, because indegree is still equals to outdegree for nodes in between segment $$$(b_i, a_i)$$$), write down all edges $$$(b_i, a_i)$$$ in order of euler tour, now part of euler tour between $$$a_i$$$ and $$$b_{i+1}$$$ is some path in line graph, but since we minimize the length (which is key) this path must be straight segment, so its actually $$$|a_i - b_{i+1}|$$$ which is exactly what we need.

    Its a bit different from the IOI problem because we were allowed to travel back and forth, so the length might not be $$$|a_i - b_{i+1}|$$$, but again, because of minimization its always the case.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please explain a reduction from original problem to "we want to add the minimum number of directed edges so that we can form a valid Eulerian tour through all edges." in more details? The most unclear part is how to calculate the weight of the $$$q$$$ from the original problem using our Eulerian tour.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +10 Vote: I do not like it

      We can think of $$$\lvert b_{q_i} - a_{q_{i+1}} \rvert$$$ as the number of new $$$x \leftrightarrow x+1$$$ edges we need to move from the tail of edge $$$q_i$$$ to the head of edge $$$q_{i+1}$$$. Thus, a particular set of extra edges and an Euler tour corresponds to the permutation $$$q$$$ of the original edges in the order visited, and the weight is the number of extra edges.

      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -26 Vote: I do not like it

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

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

→ Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

I hate linguistics now.

→ Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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...

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    It is pretty well-known problem, so we can easily get how to make it under 3 reverses. Then we just have to think if we are able to make it in less reverses. D1C is actually a good problem, unfortunately I didn't manage to solve it during contest because of D1B...

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      What well-known problem?

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Perhaps I find it. Is it the cyclic shift in editorial of E?

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

"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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I got the following test case using CF Stress.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Thanks!

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how to check this?? because i want to check test case 21950

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        You probably cannot check this large numbered test case on Codeforces. If you want to find out some other test case where your solution is failing, you can visit CF Stress and stress test your solution there.

        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Implementation ?

→ Reply
»
3 years ago, # |
  Vote: I like it +47 Vote: I do not like it

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?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Personally I didn't come up with this during the contest (I solved this problem in a different way). But I think this is how you could come up with it: You see the opening brackets as +1 en closing as -1 and look at the prefix sum. This is the first thing you should always think about with these kind of bracket problems. Draw a few graphs of these prefix sums and see what happens if you reverse a sub string. The first thing you can notice is that it rotates a part of the prefix sum graph by 180 degrees. The second thing you can notice is that if the part of the sub string you reverse starts with a prefix of 0 and ends with a prefix of X, then if there is no prefix greater then X this part of the sub string will have a prefix where every value is greater then 0. (Because of the rotating by 180 degrees) Because of this you can always find an answer of 2, by reversing everything before the greatest prefix sum, and everything after that.

    For my solution I made all of these insights, except the last one that the answer is at most 2.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    The easiest (but boring) way is to write a brute force.

    → Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Two points I would like to highlight:

    1. You could use data type int instead of double. First check if the remainder of the division is NOT 0. In that case, the answer is NO. If the remainder is 0, compute the integral quotient and search for it in the array.

    2. The binary search approach would be more expensive than a linear scan as it would require an O(nLogn) sort prior to the search.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually D is easier than it looks.

    If you are confused on proof part, here is an intuition. If you want to take BA from Type 2, it'll be better to take it from larger sizes as 1 will be wasted everytime you take from any. So while taking AB from type 2, take from smallest everytime. That's exactly what he is proving.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    If the count of A is correct then count of B will always be correct because $$$a+b+2*c+2*d = len(s).$$$
    In the example you mentioned, the above condition is not satisfied, so it's not a valid test case.

    → Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

Approach
My Submission

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The number of values from type I will always be zero right as there are no A's

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No, there will be such chains, these are the indexes which are already disjoint that is they have no neighbouring A.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

**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 **

→ Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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$$$.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

$$$\sum_{u\in U}f(u) + \sum_{v\in V}f_{AB}(v) + \sum_{w\in W}f_{BA}(w)$$$

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I think, it means following:
    Suppose we have two multisets of pairs of numbers A and B. For exapmle, A = {(0, 1), (0, 1)} and B = {(5, 2), (0, 7), (3, 11)}. A ∪ B = {(0, 1), (0, 1), (5, 2), (0, 7), (3, 11)} (size of this multiset is size(A) + size(B)). But A + B is a multiset consisting of all such pairs (x, y) that there exist a pair (x_a, y_a) ∈ A, pair (x_b, y_b) ∈ B and x_a + x_b = x, y_a + y_b = y (i.e. (x_a, y_a) + (x_b, y_b) = (x, y)). In my example A + B = {(5, 3), (0, 8), (3, 12), (5, 3), (0, 8), (3, 12)} (size of this multiset is size(A) * size(B)).

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Thanks for reply.You are right,it means that (c,d) must be in the multiset of all possible combinations of valid pairs from three types of strings.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Div2, Problem A

https://mirror.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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You mixed up mean and median. In this problem mean is the average of some values, not the middle element.

    → Reply
»
3 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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!

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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]

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    your approach is wrong ,the correct array construction is like that:
    if sorted a=[1,2,3,4,5,6] then split a into two halves like that a1=[1,2,3] and a2=[4,5,6] .
    then fill the circle alternatively between a1 and a2 starting from a1 ,so answer = [1,4,2,5,3,6].

    → Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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$$$?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I'm also a bit confused on the function $$$f$$$ used in that proof. In the three subcases, you define the input to $$$f(k)$$$ as $$$\lfloor \frac{|t|}{2} \rfloor$$$. (ex. $$$|t|=2k+1$$$ for case 1) However, in the equation $$$(c, d) \in \sum_{u\in U} f(u) + \sum_{v\in V} f_{AB}(v) + \sum_{w\in W} f_{BA}(w)$$$ and subsequent lines, the entire length of each string is plugged into $$$f$$$. As defined, $$$U$$$, $$$V$$$, and $$$W$$$ are "the multisets of lengths of strings of the first, second and third type respectively."

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      @dario2994 I guess

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Fixed the typo "$$$k$$$ instead of $$$u$$$" in two places. Thank you for pointing it out.

        You have misunderstood the definition of the function $$$f$$$. $$$f(k)$$$ is not a number, it is a set of pairs (as defined in the editorial).

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          Thanks for replying! Just to clarify, I wasn't asking about $$$f(k)$$$, but rather about $$$k$$$ itself. Based on your initial definitions of $$$f$$$, shouldn't $$$(c, d) \in \sum_{u\in U} f(u) + \sum_{v\in V} f_{AB}(v) + \sum_{w\in W} f_{BA}(w)$$$ be turned into $$$(c, d) \in \sum_{u\in U} f(\frac{u-1}{2}) + \sum_{v\in V} f_{AB}(\frac{v}{2}) + \sum_{w\in W} f_{BA}(\frac{w}{2})$$$?

          Sorry if I wasn't clear the first time.

          Also, your fixes aren't showing up in the above editorial for some reason...

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            You are totally right, my mistake. Now it should be fixed (changed the definition of the sets $$$U, V, W$$$).

            Sooner or later my fixes should be propagated to this post. If it does not happen in a couple of days, I will try to fix it.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thanks! I don't seem to see your changes though, and it's been a week...

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                2 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                We are trying to propagate the changes without much success.

                → Reply