Artyom123's blog

By Artyom123, 3 years 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

| Write comment?
»
3 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Thx for fast editorial

»
3 years ago, # |
  Vote: I like it +50 Vote: I do not like it

Thanks for the round and fast editorial.

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Fastest Editorial I've ever seen

»
3 years 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

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

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

»
3 years 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 :(

  • »
    »
    3 years 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.

    • »
      »
      »
      3 years 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.

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

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

»
3 years 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.

»
3 years 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)

  • »
    »
    3 years 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

  • »
    »
    3 years 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).

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

    the author's approach to finding segments that don't contain other segments might also be overkill. If we consider all segments in decreasing order of L then we can just maintain the min r[j] we've met so far. When considering {l[i], r[i]}-> this segment contains another segments if (min r[j]) <=r[i];

    I'm not really sure why the author decided to use Fenwick trees here

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

    Nice Approach

»
3 years 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....

»
3 years 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)
  • »
    »
    3 years 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).

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

Constraints in D should've been stricter IMHO

  • »
    »
    3 years 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.

  • »
    »
    3 years 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.

  • »
    »
    3 years 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.

    • »
      »
      »
      3 years 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.

      • »
        »
        »
        »
        3 years 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.

        • »
          »
          »
          »
          »
          3 years 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

    • »
      »
      »
      3 years 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 :)).

  • »
    »
    3 years 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

»
3 years 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 .

  • »
    »
    3 years 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.

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

Thanks for the great round!

»
3 years 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

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

I like this kind of editorial with spoiler hints

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

thx for good and fast editorial!

»
3 years 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!

»
3 years 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.

»
3 years 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?

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

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

»
3 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Weak pretests on problem D2

»
3 years 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.

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

Chinese universe students with a morning lesson cryyyyy.

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

Thanks for such a good round and fast editorial

»
3 years 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)

»
3 years 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

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

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

»
3 years 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 !

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

Help() Please

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

»
3 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it
»
3 years 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.

  • »
    »
    3 years 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

»
3 years 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

»
3 years 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.

»
3 years 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.

»
3 years 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.

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

So Fast!

»
3 years 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.

»
3 years 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?

»
3 years 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?

  • »
    »
    3 years 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:)

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

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