DishonoredRighteous's blog

Codeforces Round #866 (Div.1, Div.2, based on Lipetsk Team Olympiad) Editorial
By DishonoredRighteous, history, 12 months ago, In English

1820A - Yura's New Name

Author: FairyWinx

Preparation: FairyWinx

Editorial
Solution

1820B - JoJo's Incredible Adventures

Author: golikovnik

Preparation: teraqqq

Editorial
Solution

1819A - Constructive Problem

Author: TeaTime

Preparation: golikovnik

Editorial
Solution

1819B - The Butcher

Author: Tikhon228

Preparation: Kon567889

Editorial
Solution

1819C - The Fox and the Complete Tree Traversal

Author: golikovnik

Preparation: DishonoredRighteous

Editorial
Solution

1819D - Misha and Apples

Author: Um_nik

Preparation: dshindov

Editorial
Solution

1819E - Roads in E City

Author: Tikhon228

Preparation: grphil

Editorial
Solution

1819F - Willy-nilly, Crack, Into Release!

Author: teraqqq

Preparation: teraqqq

Editorial
Solution
  • Vote: I like it
  • +88
  • Vote: I do not like it

Comments Comments (32)
| Write comment?
»
12 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks for the editorial.

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

The idea in 1819C is so clever. How come I am so stupid in it, sticking in a implementation on it.

My stupid idea is that every subtree (apart from original) will expose exactly two routes to the rest of the tree, hence it could be implemented in a way of discussing the case of exposing exactly one current subtree root (if this subtree has no other nodes), the case of exposing one subtree root together with one its direct son, and the case of exposing two of its direct sons.

Removed it from my ugly implementation problem collection.

→ Reply
»
12 months ago, # |
  Vote: I like it +32 Vote: I do not like it

A different solution for D1D, runs in O(NlogN) and is slightly more horrible in implementation, but (imho) easier to understand. First, if there are two shops that both sell nothing and are located next to each other, we can delete the prefix before those two shops — it won't matter anyway. If there is a shop at the end — the answer is simply M, we can always choose the remaining apples.

Now let's divide the remaining shops into contiguous blocks which are separated by a shop which we can choose. Let's calculate for each shop the next shop at which it will intersect and delete all apples, if there is no such shop, we put it equal to N — we call it go. Then, the claim is such — if i and go[i] lie in the same block, we add an edge from i to go[i] + 1. Otherwise, find the first position of a shop that sells nothing — call it pos. We need to add an edge to all positions from pos + 1 to go[i] + 1. We can do it with a segment tree-like construction. Then, we simply run a DFS from vertex 0 and look at the optimal position we can reach.

Working code: https://mirror.codeforces.com/contest/1819/submission/202346479

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

    The segment tree on nodes is a neat technique, but you don't actually need to build the graph in this problem. Since you're just interested in which nodes you can reach, and not the path you take to get there, and since all edges go from left to right, you can just iterate through the nodes from left to right. For each node $$$i$$$, if you can reach $$$i$$$, then add $$$1$$$ to the values of all nodes in the range it can reach. Then you can check if a node is reachable by checking if it's value is positive.

    And you do not need data structures to add $$$1$$$ over a range. You can add $$$1$$$ to the first node in the range, subtract $$$1$$$ from the one after the last one and build prefix sums as you go.

    Code

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

The Python solution of 1819B gets TL in the system tests (or maybe you have to be extra careful with the constant). Is that what it was supposed to be?

Code: https://mirror.codeforces.com/contest/1820/submission/202227398

→ Reply
»
12 months ago, # |
  Vote: I like it -62 Vote: I do not like it

→ Reply
»
12 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

In 1819A/1820C

It's easy to see that in the resulting array, there should exist some element equal to {m+1}.

I believe, that is should be {$$$m$$$}, and not {$$$m+1$$$}, since existence of {$$$m+1$$$} would not allow for $$$MEX$$$ = {$$$m+1$$$}.

Also, with regard to the time complexity, I believe, that $$$O(n)$$$ should work. I used a bitset to achieve the same (an array works as well).

Submission: 202202551

Here, I map all large/inconsequential elements to {$$$a.length+9$$$} (just for convenience)

Snippet

Edit 1: Corrected typo

Edit 2: Added problem ID

→ Reply
»
12 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

CHEESY $$$O(N.(\log{N})^{2})$$$ implementation for div-1 D using segment tree: Link. (It can be optimized to $$$O(N.\log{N})$$$ using fractional cascading but im too lazy lol)

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

As for the solution to problem D, "Then we check that there will be no disappearances on the segment [s+1,j−1]". There might be a typo, we should check [s+1,i-1] instead because the disappearances on [j,i-1] can also affect the presence of apples.

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

The idea for D1C is clever, however, it requires some observation. I have come up with a solution with dp, I think it's harder to implement, but we don't need to say "If there is no subgraph then we win". Let's say there are two boolean arrays $$$from$$$ and $$$to$$$.

$$$from[v] = 1$$$ if we can travel all vertices in subtree of $$$v$$$ starting at $$$v$$$ and end in its child $$$u$$$, else $$$from[v] = 0$$$.

$$$to[v] = 1$$$ if we can travel all vertices in subtree of $$$v$$$ starting in some child $$$u$$$ of $$$v$$$ and end in $$$v$$$.

If $$$v$$$ is a leaf, we say that $$$from[v] = to[v] = 1$$$, however is isn't very important.

This might seem a little strange, but if you try to draw a path, these arrays will come naturally (at least I was able to think of this during the contest).

Both of these can be counted using dp. For example, for $$$to[v] = 1$$$ we need to travel through all children and their subtrees. If at least two children are not leafs, then we can already say that $$$to[v] = 0$$$, because if you go down from $$$u$$$, you can only go back in $$$v$$$, but then it will be final move in subtree, meaning there can only be at most non-leaf child. If all children are leafs, $$$to[v] = 1$$$. Else, let's say the remaining child is $$$u$$$. We need to travel through all vertices in subtree and then go back to $$$v$$$, meaning we need to end in a child, which is the exact definition of $$$from[u]$$$. So $$$to[v] = 1$$$ if all children are leafs, or there is one non-leaf child $$$u$$$ and $$$to[u] = 1$$$. $$$from[v]$$$ is counted using similar ideas.

Let's say we root the tree to a non-leaf vertex $$$root$$$ (if $$$n > 2$$$ then there is at least one). Let's remember all children of $$$root$$$ and erase them. If there are at least 3 vertices left, the answer is No. Else if there are 0, the answer is obviosly Yes, if there is 1 $$$u$$$, either $$$from[u]$$$ or $$$to[u]$$$ must be true, if there are 2 $$$s$$$ and $$$t$$$, $$$to[s] = 1$$$ and $$$from[t] = 1$$$, so that we can create the path.

The path will look like $$$root\space ->\space ...\space ->\space s\space ->\space all \space leafs\space -> f \space-> ... ->\space root$$$. First $$$...$$$ is a path that starts in a child of $$$s$$$ and ends in $$$s$$$. Second $$$...$$$ is a path that starts in $$$f$$$ and ends in its child. These sound familiar. We can recover those using recursive functions that call each other.

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

    Actually I figured out, that we don't need to count dp, but instead do a little bruteforce. Since there can be at most 2 non-leaf children of $$$root$$$, we can just try every combination of $$$s$$$ and $$$f$$$, since finding the answer doesn't need $$$from$$$ and $$$to$$$!

    → Reply
»
12 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Правда что задача D1B Мясник была названа так, чтобы отдать дань уважения nn русскому репу, а именно в честь трека Мясник который вышел за день до раунда(https://music.yandex.ru/album/25431536)

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

    Конечно, весь состав жюри олимпиады уважает российскую аграрную промышленность и считает русские репы самыми лучшими.

    → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by DishonoredRighteous (previous revision, new revision, compare).

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

Div1C is a weaker version of this problem.

→ Reply
»
12 months ago, # |
  Vote: I like it +9 Vote: I do not like it

div1 ABCD video solution for Chinese ：

BiliBili

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

My solution of question The Butcher is giving Run time error on tc 4. I have debugged it for hours and couldnt able to spot any potential error.

Any help is apppreciated. Thank you

→ Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Div 1 B:

it's easy to notice that this is a rectangle with the maximum width.

But why?

UPDATE:

It's now obvious to me after re-reading the statement. We cut and then put one of the part in a box and don't cut it again.

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it 
const int n = s.size() / 2;

if (k > n) {
   cout << (ll)n*n << '\n';

Can someone explain me this part of the solution to Jojo's adventures?

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

    If the longest chain of $$$1$$$'s in the double string (considered for including cycles) turns out to be greater than the length the string. The only case where it happens is if there are NO ZEROES. i.e. the entire square is filled with $$$1$$$'s (then the value of k == s.size()). The answer is the area of the entire square!

    → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

please simplify this statement.. I couldn't understand it.

Problem B-: We will proof this fact in such way. If there exists some rectangle of size a×b . Considering its first row, we can see that it has a+b−1 consecutive ones. But it means that a+b≤k+1 . Without loss of generality, if a≤b , we can do the following replacements: a=⌊(k+1)/2⌋−λ , b=⌊(k+1)/2⌋+λ . It means that ab=⌊(k+1)/2⌋⋅⌊(k+1)/2⌋−λ2≤⌊(k+1)/2⌋⋅⌊(k+1)/2⌋

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

    I am also having trouble understanding the solution. Specifically, whhy is it a+b-1 (like how do we know it is a+b-1) and then why do we do the replacements for a and b (the floor and ceil part)

    EDIT: Ok I have figured out why the a+b-1 part is true, but am still confused on the replacements part.

    EDIT: Ok it kind of makes sense now, but barely.

    → Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I've just realized that my solution to 1819D - Misha and Apples is somewhat different from the official solution.

Let $$$s_i$$$ be the set of all $$$k$$$ such that it's possible to visit $$$[1, i]$$$ with last reset (= the apples disappear) in $$$k$$$.

$$$s_i$$$ is a subset of $$$s_{i-1} \cup \{i\}$$$. How to find $$$s_i$$$? Let's define $$$j < i$$$ like in the editorial.

  • The elements $$$> j$$$ in $$$s_{i-1}$$$ are not affected by $$$i$$$, so they stay in $$$s_i$$$. The other resets become impossible (because there is a new reset in $$$i$$$). So, we have to remove elements $$$\leq j$$$ from $$$s$$$.
  • A new reset in $$$i$$$ is possible only in two cases:
    • the above case (i.e., if there exists an element $$$\leq j$$$ in $$$s_{i-1}$$$);
    • if you can use zeros to force a reset in $$$i$$$ (in particular, if there is a zero in $$$[p+1, i]$$$, where $$$p$$$ is the smallest element in $$$s_i$$$).

So, in the set $$$s$$$ you have to support "insert $$$i$$$" (which will become the largest element of $$$s$$$) and "remove elements from the beginning". So, you can just maintain $$$s$$$ using a queue. Then, you can calculate the final answer like in the editorial.

AC submission: 202229089 (it's $$$O(n (\log n + \log m))$$$, can be optimized to $$$O(n)$$$ like above, supposing $$$\sum k_i = O(n)$$$)

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A simple doubt concerning problem B: How the answer be 4 for s = 11 according to the editorial's explanation?

For s = 11, k = 2, answer should be : floor(3/2) * ceil(3/2) = 2

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

    If the string only consists of 1, then answer will be n^2.

    → Reply
»
12 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I don't undestand why in the problem A, in this part:

for (int i = 0; i < n; ++i) {
  assert(a[i] != mex);
  if (a[i] > mex || (leftOcc[a[i]] != rightOcc[a[i]])) {
    return true;
  }
}

Why the condition (leftOcc[a[i]] != rightOcc[a[i]])? For the case 0 1 4 0 with mex = 2, the code tell me that should remplace each value by 2 between the two zeros, obtain 2 2 2 2, that it has mex = 0, not 3? Can someone explain to me?

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Alternate easy dp solution for D1-C which also runs in $$$O(n)$$$:

Let us root the tree at some node $$$r$$$.

The only observation required: If some valid cyclic path exists, then there will exist atleast one valid cyclic path which obeys the following rule: Whenever we enter subtree of some node $$$u$$$ while going along the path, then we exit it only after visiting all the nodes in subtree of $$$u$$$.

proof

Ok, so now that we can divide the paths into subpaths which are disjoint and completely contained within different subtrees, it's natural to think of subtree dp.

The states only need to hold boolean values, and they will be:

  1. $$$dp[u][1][2]$$$: This is true if it's possible for us to go to $$$u$$$, visit entire subtree of $$$u$$$ and then move $$$2$$$ edges away from $$$u$$$ (obviously only true when $$$u$$$ is a leaf node).
  2. $$$dp[u][1][1]$$$: This is true if it's possible for us to go to $$$u$$$, visit entire subtree of $$$u$$$ and return to parent of $$$u$$$ from some child of $$$u$$$.
  3. $$$dp[u][2][2]$$$: This is true if it's possible for to first go to some child of $$$u$$$, visit entire subtree of $$$u$$$, and then move $$$2$$$ edges away from $$$u$$$. (obviously only possible when $$$u$$$ is the last node visited in it's subtree)

Now technically speaking there could have existed another slightly tricker to handle dp state, but we can completely neglect it by simply rooting the tree at a node with $$$> 1$$$ degree, so do it.

Ok, so what will the transitions be like? They're pretty trivial but here goes:

  1. $$$dp[u][1][2]$$$ is true only when $$$u$$$ is a leaf node.
  2. $$$dp[u][1][1]$$$ can be true in two cases:
    1. $$$dp[v][1][2]$$$ is true for all $$$v \in \text{children of u}$$$. (In this case we can simply visit $$$u$$$ first, then visit all it's children's subtrees in any order we wish, then come back outside from the last one visited)
    2. $$$dp[v][1][2]$$$ is true for all $$$v \in \text{children of u}$$$ except for only child $$$x$$$, for which $$$dp[x][2][2]$$$ is true (Here we visit $$$u$$$ first, then go to $$$x$$$, then visit all remaining children's subtree in any order we wish, and come out from the last child we visit).
  3. $$$dp[u][2][2]$$$ can also be true in two cases:
    1. $$$dp[v][1][2]$$$ is true for all $$$v \in \text{children of u}$$$. (In this case we can visit children of $$$u$$$ in any order we wish, then go to $$$u$$$ and exit from it)
    2. $$$dp[v][1][2]$$$ is true for all $$$v \in \text{children of u}$$$ except for only child $$$x$$$, for which $$$dp[x][1][1]$$$ is true (Here we first visit all the children of $$$u$$$ except for $$$x$$$, go to $$$x$$$, then go to $$$u$$$ and finally exit from there).

Finally, we have to handle transitions for the root node, $$$r$$$ seperately. The final answer will exist only if the children of $$$r$$$ can be rearranged such that:

  1. For the first child $$$v$$$, $$$dp[v][1][2]$$$ or $$$dp[v][2][2]$$$ must be true.
  2. For the second to second last child, $$$dp[v][1][2]$$$ must hold true.
  3. For the last child $$$v$$$, $$$dp[v][1][2]$$$ or $$$dp[v][1][1]$$$ must be true.

And that's it, you can rebuild the required path from this dp with some simple implementation.

Implementation: link (my implementation is $$$O(n \log{n})$$$ which can be easily optimized to $$$O(n)$$$)

→ Reply