1

Codeforces Global Round 24 Editorial

 1 year ago
source link: https://codeforces.com/blog/entry/109468?f0a28=1
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

By Imakf, history, 31 hour(s) ago,

30 hours ago, # |

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?

  • 30 hours ago, # ^ |

    The comment is hidden because of too negative feedback, click here to view it

    • 30 hours ago, # ^ |

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

      • 29 hours ago, # ^ |

        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.

      • 2 hours ago, # ^ |

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

  • 30 hours ago, # ^ |

    Yeah. I also spent hours watching the GIF.

  • 30 hours ago, # ^ |

    Yeah it was really good for understanding the problem

  • 29 hours ago, # ^ |

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

  • 29 hours ago, # ^ |

    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.

30 hours ago, # |

Fast Editorial

29 hours ago, # |

Sad life. I could not solve any problem.

  • 29 hours ago, # ^ |

    Same. We actually don't belong here. I won't be surprised if they kick us out of the platform.

29 hours ago, # |

Excuse me. How to prove the property in F?

29 hours ago, # |

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

29 hours ago, # |

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

  • 29 hours ago, # ^ |

    have you tried reading the blog you are commenting on?

    • 29 hours ago, # ^ |

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

      • 28 hours ago, # ^ |

        ← Rev. 2 →  

        0

        the best range is always .

  • 17 hours ago, # ^ |

    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

    • 12 hours ago, # ^ |

      Thanks @iusecookies64

29 hours ago, # |

Really good another math forces round. Thanks a lot for the fast tutorial and problems.

29 hours ago, # |

The last move makes the rubber band to stretch and touch the blue peg. So there is 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?

  • 83 minutes ago, # ^ |

    ← Rev. 2 →  

    0

    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

29 hours ago, # |

← Rev. 2 →  

0

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 :(

  • 29 hours ago, # ^ |

    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.

29 hours ago, # |

← Rev. 2 →  

+147

D can be solved in .

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 be the number of bad arrays of length . Adding any number not yet in the array to the end of them creates bad arrays of length that have bad proper prefixes, and all bad arrays with bad proper prefixes can be generated in this way. Thus, there are exactly "ending states" of length . Thus the answer is , which can be computed in once we know all 's.

Note that for , and for . Otherwise, let be the length of the longest continuous segment of removed pegs. There can only be one such segment, whose location has choices. The remaining removed pegs have choices, and all removed pegs' permutation have choices. Thus . Using https://en.wikipedia.org/wiki/Hockey-stick_identity, the last summation simplifies to . Thus can be computed in each after precomputing factorials in .

Edit: Accepted code: https://codeforces.com/contest/1764/submission/182702973

29 hours ago, # |

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.

29 hours ago, # |

← Rev. 2 →  

+24

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

29 hours ago, # |

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!

29 hours ago, # |

← Rev. 3 →  

+63

Here is another way to solve problem E.

Let be the number we have to reach to paint with color .

There are three cases:

  1. If there exist unused and such that and (assume ), then we can first paint position as color , then paint position as color .

  2. The is impossible to reach if there is no such .

  3. If there is only one such , then could only be painted with color . Therefore is now set to "used" and .

So, we can first sort the pairs by descending and then update the value of using a for-loop.

Code: 182685578

  • 29 hours ago, # ^ |

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

29 hours ago, # |

Nice round, but I need more training, thank you

29 hours ago, # |

Can someone explain where does the \binom{i+j-1}{j} term comes from in problem D? From what I understand, j! and (i-1)! are from the different orderings we can choose for the consecutive and extra sets, but I didn't get that first one.

28 hours ago, # |

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

  • 16 hours ago, # ^ |

    this is my soltuion too.

28 hours ago, # |

Here is another way to think about problem D.

The pegs are numbered from to below.

First, we can assume that the rubber band is stretched around peg , the blue peg, and maybe some peg . By symmetry, we can calculate the answer for and then multiply it by .

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

  1. Must be removed (): the pegs in must be removed to make the rubber touch the blue peg.

  2. Last to remove (): one of the pegs in should be the last to remove. Otherwise, the rubber will touch the blue peg too early.

  3. Optional (): pegs in are optional.

If we choose pegs in optional type, then there will be ways to remove them. Therefore, the total number of ways is

Code: 182682907

  • 28 hours ago, # ^ |

    Wow. Great solution

  • 15 hours ago, # ^ |

    Why we need divide for (M+s)?

    • 9 hours ago, # ^ |

      ← Rev. 2 →  

      0

      From my understanding, it's the same as doing (M + s — 1)!. The chosen L (last to remove) element is included in the M set, so there's one less option there that is instead represented by the L term and we need to subtract it.

  • 88 minutes ago, # ^ |

    Really nice solution.

    Video Solution for Problem D explaining the same.

28 hours ago, # |

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

27 hours ago, # |

i was just having a thought is it a good practice to read from editorial verses watching video tutoraials

24 hours ago, # |

← Rev. 2 →  

0

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

  • 118 minutes ago, # ^ |

    and d broke my laptop in a bad way :).

22 hours ago, # |

Problem A:Select all makes perfect

21 hour(s) ago, # |

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?

17 hours ago, # |

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

13 hours ago, # |

← Rev. 2 →  

+37

(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 , it's weight is just . So no DFS needed!

  • 9 hours ago, # ^ |

    ← Rev. 2 →  

    +8

    I had a similar approach for F, no DFS and no need to first find the edges of the tree — for vertices the formula above gives the distance 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 that doesn’t correspond to an edge this only occurs after we’ve seen all the edges on the tree between and .

    182848636

4 hours ago, # |

maybe i saw the exact same problem B somewhere in recent contest!! but i can't remember exactly

  • 4 hours ago, # ^ |

    ← Rev. 2 →  

    0

    previous div2 B contest might help you getting recognizing we are doing the gcd process by taking 2 numbers only but still we need to observe either gcd is linear combination or know the fact and this fact should strike in your head that ax+by=g

6 minutes ago, # |

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)

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK