Artyom123's blog

By Artyom123, 13 days ago, translation, In English

We hope that you enjoyed the contest. Let's get right into the editorial:

A: Median Maximization
B: MIN-MEX Cut
C: MAX-MEX Cut
D: Seating Arrangements
E: Buds Re-hanging
F: Points Movement
G: Four Vertices
H: Xor-quiz
Who did what?
 
 
 
 
  • Vote: I like it
  • +372
  • Vote: I do not like it

»
13 days ago, # |
  Vote: I like it +28 Vote: I do not like it

Thx for fast editorial

»
13 days ago, # |
  Vote: I like it +50 Vote: I do not like it

Thanks for the round and fast editorial.

»
13 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Lightning Fast Editorial!!

»
13 days ago, # |
  Vote: I like it +7 Vote: I do not like it

Fastest Editorial I've ever seen

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Faster than flash!

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

good round!! thx for the fast tutorial

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any livestreamming of solutions on youtube/twitch?

»
13 days ago, # |
Rev. 2   Vote: I like it -14 Vote: I do not like it

I can't read the condition!!! For task D2 , I thought that there are columns and rows that do not affect anything. Because of this, I did not solve the problem. OMG

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    that is why reading question is imp before solving it. :)

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Lets work together as a team if you are interested. I am a 13 year old middle school student, so far working on C++, I solved 3 problems on this contest(I suck as well) hope we might have something in common.

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Forget it, I suck a lot more then you do.At least you are a specialist. But if you are still interested please tell me.Thanks♪(・ω・)ノ

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Got the logic for D2 but wasn't able to convert it to code :(

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

    solving lot of implementation questions helps! and generally it comes with time and consistency.

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

      Did i tell wrongly? Downvoters should comment the appropriate answer before degrading my answer.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

The Editorial section of the 2nd solution of problem A is misplaced. Please edit this.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

thank you for being fast this time.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Fast As Flash editorial ! LETS GOOOOOO

»
13 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Feels bad to solve B and C but not A ):

»
13 days ago, # |
  Vote: I like it +6 Vote: I do not like it

Thanks for the editorial. I noticed that the second solution for Problem A has the editorial for Problem B. It will be great if it can be rectified.

»
13 days ago, # |
  Vote: I like it +90 Vote: I do not like it

I think you over-killed F with seg-trees. it could be done with just one sort and the rest was O(n) dp.

first remove all covered segments that have either a point or another segment inside them. then sort all segments and points.(compare segments by right ends with points). now let dp_i be answer for the first i things(segments and points together) and let pd_i be answer if we force that after our operations, we have a point in the position X_i.(if the i'th thing is a point X_i is its position otherwise its the segment's leftpoint) you can see details of updating the table in my submission.128662794(its very messy cause I finnished debugging in last minute of the contest)

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    I have something similar with just a sort and O(n) dp.

    First keep only useful segments and assign them to the point on their right. Then for each point, we want to calculate dp[i][c], which is the minimal cost to cover all segments on the left of point i if the point i travels to the left c times (c = 1 or 2). Either point i goes to the left, then comes back and goes to the right, or vice versa.

    Then to go from point i to i + 1, there are (k + 1) ways to split the k intervals between them, and for each of them there are 4 transitions. Finally, the answer is just dp[n] (we add a point with position +inf at the start).

    You can see my submission here 128653517

  • »
    »
    13 days ago, # ^ |
    Rev. 3   Vote: I like it +21 Vote: I do not like it

    Code is good, but logic description would be better.

    I have also O(n) dp without trees. I did check point coverage by binary search, then removed overlapping segments using simple sort and stack. Additional observation is that you don't need to move point over any previous point initial position. So dp[i][j] was where dp[i+1][j] would tell how much we need to move points [0,i] to cover everything up to point i would be visited and j segments in between point i and i+1 exactly visited by point i. So dp[2][1] would tell how much should we move points 0 and 1 such that every segment up to point 1 would be visited and exactly single segment between points 1 and 2 would be visited by point 1. For each j I did brute force how far we should go left and then rearranged it a bit and noticed fact that we actually pick one of two choices for each j. 128674186 (commented part is brute force version).

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Pretty fast. Thanks

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Even Superman is amazed

»
13 days ago, # |
  Vote: I like it +1 Vote: I do not like it

This was a nice round. For the first time I solved more than 2 problems of a global round. Could have solve D2 also, but the implementation was beyond me....

»
13 days ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

For E, Can anyone explain why Sum of Leaves + Sum of Buds = n — 1? Precisely, why this holds true?

Initially, there are n - k - 1 leaves (total amount of nodes — the amount of buds — root)
  • »
    »
    13 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Because if initially a node is neither a bud nor a leaf, when you remove all the buds under this node, it becomes either a bud or a leaf (doesn't apply to the root).

»
13 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Constraints in D should've been stricter IMHO

  • »
    »
    13 days ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    I instinctively went straight to ordered multiset (happy that I would finally use this thing in a contest) to achieve $$$O(nmlog(m))$$$ but yeah, I didn't notice that $$$O(nm^2)$$$ fits.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I completely agree. I myself used the Fenwick tree, not noticing that the constraints allow us to solve for a square.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +54 Vote: I do not like it

    I strongly disagree — the problem is nice in its current state, increasing constraints just unnecessarily adds some data structure work on top of that.

    In my opinion adding data structures is usually justifiable if its easier than the actual ad-hoc part of the problem. Even a fenwick tree (or any other easy method of inversions) is way tougher than the observations needed in D1, maybe even D2.

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it +35 Vote: I do not like it

      In my opinion, counting inversion is actually easier (or more straightforward) than the construction part. Still, I agree with you that it adds no value to the problem.

      • »
        »
        »
        »
        13 days ago, # ^ |
        Rev. 3   Vote: I like it +4 Vote: I do not like it

        I see your point, but I'd argue its more standard, not easier. It still requires someone to know Fenwick / pbds / merge sort trick.

        This is most likely trivial for anyone 17-1800 or higher as they've likely encountered the idea before.

        However I suspect there are a lot of participants in the 14-1600 range who could make the observations for D1/D2 but don't know any of the standard methods for inversions. I certainly didn't till I was 16-1700.

        • »
          »
          »
          »
          »
          13 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Some knows, some don't. With this logic "there are some people who don't know these alg/ds" you could cut them out from any problem.

          Your argument makes sense, but I think you underestimate what people know. Pretty sure half the cyans know about Fenwick/Segtree nowadays and would be happy to practice them

      • »
        »
        »
        »
        12 days ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        How can we solve this variation of problem D2?

        So instead of seat indexes being

        1 , 2 , 3 , 4 .. m

        m + 1, m + 2, ... 2m
        .
        .
        n rows

        what if they had been,

        1 , 2 , 3 , 4 .. m
        1 , 2 , 3 , 4, .. m
        .
        .
        .
        n rows

        I misread the question and was solving this variation for problem D2 during the entire contest ;_; I couldn't come up with any solution though.

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

      Ya your point is fine increasing constraints force the participants to use data structures like fenwik tree/segment-tree but in my opinion this has a positive outcome,If the participant couldn't solve the problem during the contest due to lack of data structure knowledge but it enables them to learn these data structures after the contest and then try to solve it again that's what upsolving all about. Having knowledge of more data structures always helps :)).

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

    Ya I did it in O(nmlogm) by counting inversion with divide and conquer whereas my friend got also got passes with naive O(nm^2) algo.T_T

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I dunno about constraints as much as test coverage. My AC would've been nuked by an all-repeats max case, and it registers as weird that it tied for 'fastest-running-pypy3-turtle' from the contest... because it's horrid: simulating the seating with linear probing and everything.

    Intent did seem foggy from a few things: 1e9 default constraint when the number of seats maxes out well below that... and the editorial text speaking of simulation vs. the code being... shinier. I can presume dupes were explicitly allowed because that's a more interesting problem, but then the omission of the all-dupes case points to a more default "dupes are fine if rng makes them happen"...?

    tl;dr FREE UPHACK...! (probably a few more besides mine among the py solves because 1sec TL vs. maxcases with more IO than custom invocation input limit...?)

»
13 days ago, # |
Rev. 2   Vote: I like it -52 Vote: I do not like it

I recently encountered a problem during the contest. I don't know if it's a bug or a Codeforces thing. The problem is, if I give two correct submissions for the same problem, my last correct submission is taken into account for my points distribution. I think that logically, the first correct submission for the problem should be taken into account. I solved D1 first, and then, D2. After which, I submitted the solution for D2 in D1 also, due to which I lost half of the points of that question. So, it didn't matter if I got AC for D1 long ago, I got considerably low points .

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    Not a bug, part of the rules. You might want to resubmit a problem if you think it won't pass sys tests or it will get hacked.

»
13 days ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Thanks for the great round!

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

unexpected answer of a :(

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

According to the question, for less seat index, less clear person should be preferred. Now in the figure drawn [row i col 0] has has a higher seat index than [row i — 1, col m]. So shouldnt it be that the person with lower a[i] should prefer [row i — 1, col m] and NOT [row i col 0] ???

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Really liked the question. This contest was really competitive, with people solving questions at high speed. And liked the editorial(the idea of giving hints first).ThankYou

»
13 days ago, # |
  Vote: I like it +14 Vote: I do not like it

I like this kind of editorial with spoiler hints

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

thx for good and fast editorial!

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I loved the bugaboos today

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Didn't notice O(nm^2) fits into the solution.Was thinking of something else. Thanks for the round and a pretty fast editorial!

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

This editorial came out really quick and easy to understand.

»
13 days ago, # |
  Vote: I like it +51 Vote: I do not like it

Thanks for the great contest!

Unfortunately, I think I saw problem G somewhere.

»
13 days ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

Is there meant to be special-casing for $$$C \in \{3,6,7,15,23,43\}$$$ in problem H? For these values, the number of square-free integers in $$$[1..C]$$$ is strictly greater than $$$\lceil 0.65 \cdot C \rceil$$$, which Hint 2 suggests is impossible.

EDIT: Whoops! I just noticed the unusual constraint $$$C \geq 100$$$, which is important for this reason.

EDIT2: But in light of this, I don't understand the problem-setting reasoning behind making the problem interactive at all. Was it originally intended to be an easier problem?

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Contest was good for both beginner as well as experienced programmer Ig

»
13 days ago, # |
Rev. 2   Vote: I like it +33 Vote: I do not like it

Why there are 700+ test cases for G... XD

»
13 days ago, # |
  Vote: I like it -9 Vote: I do not like it

Weak pretests on problem D2

»
13 days ago, # |
  Vote: I like it +82 Vote: I do not like it

My G (the case with two edges without common endpoints):

Paint each vertices in one of $$$c$$$ colors (I've chosen $$$c=5$$$). Now for each edge we know a pair $$$(a, b)$$$ ($$$1 \leq a \leq b \leq c$$$) which denotes the colors of it's endpoints. If for two edges and their pairs $$$(a, b)$$$ and $$$(x, y)$$$ each of $$$a \neq x$$$, $$$a \neq y$$$, $$$b \neq x$$$ and $$$b \neq y$$$ holds, then we know for sure that these edges have no common endpoints.

For each pair maintain a multiset of edge values (and the largest one of them) and iterate over a pair of pairs. Then, we can with probability around $$$0.416$$$ (for $$$c=5$$$) find a correct answer. Do as many iterations as you can fit in the time limit.

My H:

Also gaussian eliminations for each group to find any solution. To find a solution with correct $$$n$$$, use hill climbing.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Chinese universe students with a morning lesson cryyyyy.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody please tell me what's wrong in my code for problem C https://codeforces.com/contest/1566/submission/128644148

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone please find, what's wrong with my submission for D2? My Submission

My approach: first of all, i found the correct seating arrangement. then for each person, i'm finding the maximum possible column over all rows, and also maintaining already occupied seats in that row, and then adding inconvenience to the answer.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Please Help! I don't know why is this code is giving WA for Problem A.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for such a good round and fast editorial

»
13 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

So in reality the $$$\lceil 0.65 n \rceil$$$ can be replaced with the number of squarefree numbers smaller than $$$n$$$? (in H)

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

After looking at the constraints again, Order Statistic Tree seems like an overkill for D1 and D2.
My Submission

»
13 days ago, # |
  Vote: I like it +1 Vote: I do not like it
»
12 days ago, # |
  Vote: I like it +1 Vote: I do not like it

I think that the input in D2 is not easy to understand &_&

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

why not every contest tutorials are like this .. very well written tutorial and solution code thanks !

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank You for the amazing round and excellent editorial.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Help() Please

https://codeforces.com/contest/1566/submission/128700326

Here is my submission i'm trying to solve D1 with help of PBDA where the heck i'm wrong : ( Could'nt find any counter test case why I'm getting WA on Test Case 2

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

the problems are interesting and helpful,thanks a lot.

»
12 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it
»
12 days ago, # |
  Vote: I like it +62 Vote: I do not like it

The first hint in problem E is incorrect, and here's a counter-example:

  1
 / \
2   3
     \
      4
     / \
    5   6

Re-hanging 4 (bud) to 2 (leaf) won't decrease the number of leaves.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain how answer is 2 in the third test case. I think it should be 3

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

B problem of this contest is of tag dp, would someone tell me how it is?

»
12 days ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

 shouldn't it be min instead of max? as we need here the ending index (j) of the second last segment? Or I am getting it wrong? Here is my accepted solution using the given idea but using min : 128769652

»
12 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

128624993 why I am getting tle on Question c although my solution is of O(1e5) and editorial of d2 which is of O(1e8) is still running.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I am unable to get how having a leaf connected with root will always reduce the size. Can anyone explain in detail for the third test case given in the question.

»
11 days ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D can actually be solved in O(n*m*log(m)) by using an ordered set to calculate the inconvenience of a person in log(m). Here is my solution using Policy Based DS in cpp.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

So Fast!

»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

I think the difference in difficulty between E and F is too large.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem E, why we are subtracting 2*k, it is not clear to me. Can someone expalin?

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

this is my code for problem D1 , i am curious to know can it be optimized further or any other better solution , please share it to me

Code
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a problem about PROBLEM B, 0002000 ,i think it ouput 1,but std output 2. Maybe I misunderstand the problem?

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am sorry to make a stupid question, i have solve the problem:)

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks for having a pictorial explanation of test cases...