Imakf's blog

Codeforces Global Round 24 Editorial
By Imakf, history, 2 years ago, In English

1764A - Doremy's Paint

idea: Cocoly1990

Solution
Code

1764B - Doremy's Perfect Math Class

idea: waaitg

Solution
Code

1764C - Doremy's City Construction

idea: waaitg

Solution
Code

1764D - Doremy's Pegging Game

idea: Imakf

Solution
Code

1764E - Doremy's Number Line

idea: Imakf

Solution
Code

1764F - Doremy's Experimental Tree

idea: Cocoly1990

Solution
Code

1764G3 - Doremy's Perfect DS Class (Hard Version)

idea: waaitg

Solution
G1 Code
G3 Code

1764H - Doremy's Paint 2

idea: Imakf, waaitg and errorgorn

Solution
Code
  • Vote: I like it
  • +121
  • Vote: I do not like it

Comments Comments (67)
| Write comment?
»
2 years ago, # |
  Vote: I like it +580 Vote: I do not like it

I hope you liked the GIF on problem D. I spent hours making it on manim.

code

Since the file size was very large even after making resolution and framerate very small, I was considering to only put images in the statement and host the GIF on an external website. Would this method of hosting the GIF be preferred, and if so, what site can be used that everyone can access?

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

    I prefer using imgur for such purposes. As an alternative, Discord (yes, Discord) works as a good alternative as well, but using Discord as a CDN just sounds awkward, doesn't it?

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

      I believe imgur is blocked in Indonesia and discord is blocked in China

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

        Oh, that's too bad. I can't think of any good CDNs (excluding widely known paid ones such as Cloudflare) anymore. I hope MikeMirzayanov could help host the contest materials.

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

        I believe imgur is blocked in Indonesia and discord is blocked in China

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

    Yeah. I also spent hours watching the GIF.

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

    Yeah it was really good for understanding the problem

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

    As I enjoyed watching the GIF, I believe you must had fun of making the GIF

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

    The GIF was pretty. I wish, at some time I would learn how to create such GIFs, they are very cute.

    However, once I watched it, I understood the problem, so it became needless. If I solved the problem relatively fast, it would be ok; however, I stuck at it, and at some point the GIF on the second monitor (I kept the statement on one monitor, while coding on the other) became too distracting, that I even blocked it with AdBlock ;P

    Probably it would be better to put it somewhere deep below, in the notes section.

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

    ok

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

    It was good. But I wish it was 2 separate gifs for n=8 and n=9, so I don't spend twice as much time waiting for the case I'm currently working on :)

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

Excuse me. How to prove the property in F?

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

    Take the spanning tree made out of some edge that isnt in the original tree. Because of the property that "If path (x,y)⊂(X,Y), then f(x,y)>f(X,Y)", you can remove that edge and insert an edge from the original tree to connect the graph, making the weight bigger. Therefore, it cannot be a maximum spanning tree.

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

Can someone hack my 182692536, I think it might be cubic.

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

Guys, I tried solving the first problem in O(n^2). Can anyone share the Efficient approach ? Thanks in advance.

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

    have you tried reading the blog you are commenting on?

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

      Yes, @biggy_cheese. That's why I have asked for some approach after going through the pithy solution, and the incomprehensible code discussed above.

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

    The answer is always the range 1 to n because if we consider a range say l to r, then increasing the range to left or right in the worst case give us a distinct element that is not already present which will decrease the score, but since size also increase by one, the effect is cancelled and score remains same, hence increasing subarray size will mean score might increase or remain the same, hence we should take the entire array for maximum score

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

The last move makes the rubber band to stretch and touch the blue peg. So there is $$$2t−i$$$ ways to choose the last move.

I cannot see any correlation between these two sentences... Can anyone tell me how to conclude the second one?

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

    Took me some time to parse this sentence as well

    Only those pegs that make rubber band touch the blue peg can be the last move. And that is the number of such pegs

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

    Imagine a long consecutive stretch of removed red pegs (i.e. $$$i>t$$$). There is a number of pegs in the beginning and in the end of this stretch that cannot be removed in the last move (e.g. consider the very first peg in the stretch, it cannot be removed in the last move because, in that case, there was already a consecutive stretch of $$$i-1\ge t$$$ removed pegs). Let's count the number of pegs that cannot be removed in the last move: there are $$$i-t$$$ pegs at the beginning and $$$i-t$$$ pegs at the end. So, the number of pegs that can be removed in the last move is $$$i-(i-t)-(i-t)=2t-i$$$.

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

is there's a way to solve Problem D by OEIS ?

i generated the first 4 elements (3,16,50,612) but got no results :(

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

    no

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

    You already answered your own question.

    But you can always contribute a new sequence to OEIS, if you can rephrase this problem into something concise and general enough.

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

D can be solved in $$$O(n)$$$.

Let's call an array bad, if removing all pegs in the array results in the blue peg being touched. Bad arrays differ from "ending states" in that the blue peg may have been touched before removing the last peg in the array. "Ending states" are exactly those bad arrays whose proper prefixes are not bad.

Obviously, a bad array is still bad after adding any number to its end. Let $$$f(k)$$$ be the number of bad arrays of length $$$k$$$. Adding any number not yet in the array to the end of them creates $$$(n-k)f(k)$$$ bad arrays of length $$$k+1$$$ that have bad proper prefixes, and all bad arrays with bad proper prefixes can be generated in this way. Thus, there are exactly $$$f(k+1)-(n-k)f(k)$$$ "ending states" of length $$$k+1$$$. Thus the answer is $$$\sum_{k=0}^{n-1}(f(k+1)-(n-k)f(k))$$$, which can be computed in $$$O(n)$$$ once we know all $$$f(k)$$$'s.

Note that $$$f(k)=0$$$ for $$$k<t=\lfloor\frac{n}{2}\rfloor$$$, and $$$f(k)=n!$$$ for $$$k\geq n-1$$$. Otherwise, let $$$l\in[t,k]$$$ be the length of the longest continuous segment of removed pegs. There can only be one such segment, whose location has $$$n$$$ choices. The remaining removed pegs have $$$\binom{n-l-2}{k-l}$$$ choices, and all removed pegs' permutation have $$$k!$$$ choices. Thus $$$f(k)=nk!\sum_{l=t}^{k}\binom{n-l-2}{k-l}$$$. Using https://en.wikipedia.org/wiki/Hockey-stick_identity, the last summation simplifies to $$$\binom{n-t-1}{k-t}$$$. Thus $$$f(k)=nk!\binom{n-t-1}{k-t}$$$ can be computed in $$$O(1)$$$ each after precomputing factorials in $$$O(n)$$$.

Edit: Accepted $$$O(n)$$$ code: https://codeforces.net/contest/1764/submission/182702973

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

Does anyone know what the counting technique used on D is called? I don’t have a math background so I don’t really understand how the “choose” this many moves part works.

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

I have a totally different solution for E. My approach is this: if x1 + y1 is less than k then the answer is no. If x1 >= k then the answer is yes. Otherwise, let's notice that we have to determine if we can color any number between k — y1 and x1. Let's call it solving the problem for the segment [k — y1, x1] and the set of xi and yi where i > 1. We can notice that if any xi is greater than the left point of the segment, the answer is yes. Otherwise, if for all i xi + yi is less than the left point of the segment, the answer is no. If there is more than one i with xi + yi >= left point of the segment, then the answer is yes, because if there are at least two, say, j and k (let's say xj >= xk), then we can use the j-th position to color the point xk and then color the left side of the segment using the k-th position. If there is exactly one such i, we can consider the same problem for the segment [left position of current segment — yi, xi]. Also we have to remove the i-th position from consideration for the next checks. Thus we iterate through segments, and at every iteration we either prove that the answer is yes or no, or we need to solve the problem for a new segment with less positions in consideration. We need to keep a set for xi and xi + yi for all i that are still in consideration. Actually, now that I look at my solution, we never use the right points of the segments, so we can only consider the left points. Here is my submission: 182681261

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

Great contest. I really enjoyed the problems a lot especially D tho being hard and the most exciting is that I returned BLUE again! Wohhoo!

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

Here is another way to solve problem E.

Let $$$\text{goal} = K - b_1$$$ be the number we have to reach to paint $$$K$$$ with color $$$1$$$.

There are three cases:

  1. If there exist unused $$$x$$$ and $$$y$$$ such that $$$a_x + b_x \ge \text{goal}$$$ and $$$a_y + b_y \ge \text{goal}$$$ (assume $$$a_x \le a_y$$$), then we can first paint position $$$a_x$$$ as color $$$y$$$, then paint position $$$\text{goal} \le a_x + b_x$$$ as color $$$x$$$.

  2. The $$$\text{goal}$$$ is impossible to reach if there is no such $$$x$$$.

  3. If there is only one such $$$x$$$, then $$$\text{goal}$$$ could only be painted with color $$$x$$$. Therefore $$$x$$$ is now set to "used" and $$$\text{goal} \leftarrow \text{goal} - b_x$$$.

So, we can first sort the pairs by $$$a_x + b_x$$$ descending and then update the value of $$$\text{goal}$$$ using a for-loop.

Code: 182685578

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

    I think our solutions are similar, but your comment is much better :)

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

    imagine wrt to a node.way to count .

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

Nice round, but I need more training, thank you

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

I had a very simple solution to F. We notice that "f" only decreases on extending the cycle. So if we look at $$$f(1, x)$$$ with least reduction from $$$f(1, 1)$$$, $$$x$$$ must be adjacent to 1, otherwise shortening the cycle could make the solution better. So we iterate over $$$x$$$ in increasing order of reduction. To check if $$$x$$$ isn't actually in some previous subtree, we can use the fact that $$$f(s,x)$$$ would be larger if $$$s$$$ is adjacent to $$$1$$$ and $$$x$$$ is in it's subtree. If it's smaller for all current found edges, it must be a new adjacent edge.

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

    this is my soluion too.

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

    Your approach is pretty intuitive and very intresting But it just only finds the structure of the tree. How did you actually come up with weights of each edge. I think it is also going to be pretty much intuitive.

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

      I used the formula in this comment. You can deduce it by noticing that the contribution of each node $$$x$$$ in the $$$f(u, u) + f(v, v) - 2f(u, v)$$$ is $$$d(x, u) + d(x, v) - 2\min(d(x, u), d(x, v))$$$. Since $$$d(x, u) + w = d(x, v)$$$ or vice versa, its easy to see the value will be $$$w$$$, or the weight of the $$$(u, v)$$$ edge.

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

        thanks for your valuable time and efforts to explain. I realized this comment some time after i wrote the comment.

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

Here is another way to think about problem D.

The pegs are numbered from $$$0$$$ to $$$n-1$$$ below.

First, we can assume that the rubber band is stretched around peg $$$0$$$, the blue peg, and maybe some peg $$$x$$$. By symmetry, we can calculate the answer for $$$x \in \left[0, \left\lceil \frac{n}{2} \right\rceil - 1 \right]$$$ and then multiply it by $$$n$$$.

If we fix peg $$$0$$$ and peg $$$x$$$, the other pegs can be classified into three types:

  1. Must be removed ($$$M$$$): the pegs in $$$[x+1, n-1]$$$ must be removed to make the rubber touch the blue peg.

  2. Last to remove ($$$L$$$): one of the pegs in $$$\left[\left\lceil \frac{n}{2} \right\rceil, \left\lfloor \frac{n}{2} + x \right\rfloor \right]$$$ should be the last to remove. Otherwise, the rubber will touch the blue peg too early.

  3. Optional ($$$S$$$): pegs in $$$[1, x-1]$$$ are optional.

If we choose $$$s$$$ pegs in optional type, then there will be $$$(M+s)! \cdot \frac{L}{M+s}$$$ ways to remove them. Therefore, the total number of ways is

$$$ \displaystyle n \cdot \sum_{x=0}^{\left\lceil \frac{n}{2} \right\rceil - 1} \sum_{s=0}^{S} \binom{S}{s} \cdot (M+s)! \cdot \frac{L}{M+s} $$$

Code: 182682907

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

There is a significant difficulty gap betw C and D (like ..1200-1800) . Nice round btw :)

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

Cool round, E and G broke my brain (in a good way), thanks!

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

In Problem D, having a real hard time trying to understand why there are 2t — i ways of choosing the last move, can anyone enlighten me?

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

Video Solution for Problem C.
Will probably create one for Problem D as well.

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

(for problem F) Actually, after finding the edges of the tree, their weights can be found even simpler than in editorial: If we have an edge between vertices $$$(x, y)$$$, it's weight is just $$$\frac{f(x, x) + f(y, y) - f(x, y) \cdot 2} {n}$$$. So no DFS needed!

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

    I had a similar approach for F, no DFS and no need to first find the edges of the tree — for vertices $$$(x, y)$$$ the formula above gives the distance $$$D(x, y)$$$ between x and y on the tree. Then we simply sort all the distances and iterate through them in increasing order, using DSU — if our two vertices are in different components we merge them and print this edge, otherwise if they’re in the same component we ignore this distance and keep going. This works because every time we encounter a distance $$$D(i, j)$$$ that doesn’t correspond to an edge this only occurs after we’ve seen all the edges on the tree between $$$i$$$ and $$$j$$$.

    182848636

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

F time limit is 2.5s, and the official editoral solution cost 2464ms(??????) in C++20 submission/182954105 (same code in c++17 982ms submission/182954544)

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

[[user:waaitg] g3 code in the editorial seems to be having bug. But it is giving accepted verdict on submitting.please correct me if iam unable to understand the below lines correctly. else{ if(){ if(rt)divide(l,mid,L,l2,r1,R); else divide(mid+1,r,l1,L,R,r2); } if(query(1,mid,n)==2)rt=0,divide(mid+1,r,l1,L,R,r2); else rt=1,divide(l,mid,L,l2,r1,R); } I suspect that multiple branches get created in the recursion and also the excess usage of queries when n is even.

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

For problem C, the following binary search gets TLE.

for v in [min_value_in_a, max_value_in_a]:
    pos = lower_bound(a.begin(), a.end(), v)

But the following one gets Accepted.

for i in [0, n - 1]:
    pos = lower_bound(a.begin(), a.end(), a[i])

The difference is only 10^6 vs 2*10^5. Not sure whether this time limit is intended.

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

    The second one does $$$O(n)$$$ binary searches per test case while the first does up to $$$10^6$$$ binary searches per test case. If you add over $$$10^4$$$ test cases, this leads to $$$10^{10}$$$ operations which is too slow.

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

      Wow, I didn’t realize that even when n=2 the first one can still do 10^6 binary searches. Thank you!

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

    Hey, in the c problem, we are coloring them based on their neighborhood, right (or is it just given as an example?)Cause I have colored them based on their neighborhood, I cannot find the correct answer. also why are we dividing the whole set into two parts? How will it ensure we get the answer without violating the condition mentioned in the question?

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

      Problem C is essentially forming a bipartite graph. If you look at the 3-vertex-paths you will realize that it's going back and forth between the two vertex sets and thus the condition is satisfied.

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

I have a different solution to problem F:

consider building the tree from an connect component $$$CC$$$ which initially have only vertex $$$1$$$, then consider $$$f(u, v)$$$ where $$$u \in CC, v \notin CC$$$, if $$$u$$$ and $$$v$$$ are not adjacent, we can let one of the vertex approach another by one edge without breaking the rule $$$u \in CC, v \notin CC$$$, let say we move vertex $$$u$$$ to have a new vertex $$$u'$$$, then it is easy to see that $$$f(u', v) > f(u, v)$$$, thus if $$$f(x, y)$$$ is the $$$max(f(u, v))$$$ among all possible $$$(u, v)$$$, $$$x$$$ and $$$y$$$ must be adjacent, and we can span an edge between them.

And by doing this process $$$n - 1$$$ times, we can know the whole structure of the tree.

Regard to the implementation, just use a priority queue to maintain $$$f(u, v), u \in CC, v \notin CC$$$ in $$$O(n^2\lg n)$$$.

edit: I found out this is actually just what Prim's algorithm does, so it is actually the same as the editorial but with a prove.

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

The weights of edges in problem F look precisely like the result of keyboard mashing

→ Reply