Rhodoks's blog

By Rhodoks, history, 2 months ago, In English

Sorry for the late editorial. May this editorial help you. If you have questions, feel free to ask.

1711A - Perfect Permutation

hint1.
solution
code

1711B - Party

hint1.
hint2.
solution
code

1710A - Color the Picture

hint1.
hint2.
solution
code

1710B - Rain

hint1.
hint2.
hint3.
solution
code

1710C - XOR Triangle

hint1.
hint2.
solution
code

1710D - Recover the Tree

Thank dario2994, the key part of the proof is from him.

hint1
hint2
hint3
solution
code

1710E - Two Arrays

hint1.
hint2.
hint3.
solution
code
 
 
 
 
  • Vote: I like it
  • +3132
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +536 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it +529 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Thanks !

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Thank you for the editorial!

»
2 months ago, # |
  Vote: I like it +133 Vote: I do not like it

You don't deserve the downvotes man :(

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

    Upvoting this Blog can decrease his negative contribution.

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

      Let me be a snob and point out that this mathematically means it will become worse

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

    The editorial is very well done, with hints/proofs of statements etc.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why do we need to sort array in 1710 A? It works fine without it

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

    it is just a way to give a valid answer. There may be better ways and in this problem you in fact do not need to implement it.

»
2 months ago, # |
Rev. 2   Vote: I like it +154 Vote: I do not like it

Great Div.1 D. If there had been a normal E, it would have been the best contest this month (so far).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Really liked the idea behind Div. 2 D, and the editorial explains it very well. Thanks!

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

    Really? For me it reads like explaining nothing, just stating some formulars. I am lost in the second line.

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Div2 B,I spent a full hour and a half thinking about the y=0 case and did it wrong!The torial is like a drop of holy water on my rusty brain feel so good~

»
2 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Can someone explain in a little more detail Div 1 C?

»
2 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Is there an error in Div2 D's solution? I think it should be pi−|xi−xj|>=aj−m

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

    you are right. Thank you very much.

    I have fixed it.

»
2 months ago, # |
  Vote: I like it +475 Vote: I do not like it

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

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

in Div2B,I think "if (degree[x[i]]%2==0 && degree[y[i]]%2==0)" need to replaced by "if((degree[x[i]]+ degree[y[i]])%2==0)"

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

    They both work well.Exactly,"if (degree[x[i]] % 2==0 && degree[y[i]]%2==0)" is better.Because there are two cases if "degree[x[i]]+degree[y[i]] )%2==0",both x and y are even or odd.and when x and y are odd,we only need to remove one of them not two,So this should not be repeated.

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I don't understand the idea of difference array for Div2D. Can anyone explain in an easier way?

  • »
    »
    2 months ago, # ^ |
    Rev. 4   Vote: I like it +28 Vote: I do not like it

    a[i] can also be calculated in this way.
    Firstly,we make the contributions two arithmetic sequences.
    for example x=6,p=5
    that's 1,2,3,4,5 for [2,6] and 4,3,2,1 for [6,10].

    then we divided the contribution of an arithmetic sequence into two parts: b+k*i
    for the above examples
    we add -1 for each position i [2,6],then increase each position i [2,6] by i.
    we add 11 for each position i [7,10],the decrease each position i [7,10] by i.

    now let's find two arrays for both the b and i.
    it's easy to calculate a 1D difference array.

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

      Thank you so much for your reply. However, if you loop through each position i in [2,6] or [7,10], will that not make your runtime O(n^2)?

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

        well,for a arithmetic sequence,we divided its contribution into two parts.
        the first part is add a number b to an interval [l,r], you can use difference array to maintain it.
        the second part is add i for position i within interval [l,r] ,You can calculate how many times a position i is added,then it becomes add 1 to an interval [l,r]

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

          Oh, I think I see what you're saying now. Thank you!

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

      But isn't the constraint on range of x and p too high. How are u supposed to calculated difference array like this without iterating over the complete range atleast once?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

my solution to problem B without using graphs--165604121

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

Greedy proof for B:

Assume we need to remove k people from the party in an optimum solution.

Case 1 :

Atleast one of these k people has odd number of friends. In this case, invite everyone except the person with an odd number of friends. If there is more than one such person, invite all except the one with the least unhappiness count.

Case 2:

All of these k people have even number of friends. In this case, there is at least one pair (i,j) among the k people such that i and j are friends. But then invite everyone except i and j. Since there are only m pairs of friends, we can iterate over all the pairs and find the minimum happiness count (a[i]+a[j]) where i and j have an even number of friends.

Time complexity: O(m)

Edit: Didn't care to look at the graph approach cause I hadn't learned it. Just found out that the editorial describes the same approach.

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

    I have one doubt in case 1. If we consider this situation n = 4, m = 3 a[4] = [1,1,5,7] pairs[3] = [(1,2),(1,4),(2,3)]

    Here we have two people with odd number of friends. This is case 1 according to you and we need to remove 3 to yield unhappiness count of 5. But we get minimum unhappiness count when we remove 1 and 2 to yield unhappiness count of 2. This means if we have odd number of friends, we need to check for both cases and the answer will be one with least unhappiness count. Correct me if I went wrong somewhere.

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

      You're right. What I meant is that we need to check for 2 cases in each iteration and update the answer in each iteration. In your example, since 1 and 2 have an even number of friends, we need to consider the case where we remove both 1 and 2. If the result is smaller than the previous answer, update it.

      Here is my code: 165598905 Ignore the comments in the code

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

        The proof implies that the final answer will be either 1 guy with odd friends or 2 friends (both with even friends). It cannot be anything else.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had a doubt in case 2, why not uninvite the person with even pair contribution and the lowest ai, then re-calculate the pair contribution per person considering the previous un-invitation, and then again uninvite the person with odd pair contribution and lowest ai?

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That's essentially what happens. A person among the k people will be left with an odd number of friends (after not inviting the previous person) only when he is a friend of the previous person. Remember, we started with all having even friends.

»
2 months ago, # |
  Vote: I like it -41 Vote: I do not like it
»
2 months ago, # |
Rev. 4   Vote: I like it +33 Vote: I do not like it

In Div 1C, there's an equivalent condition for the inequalities,

$$$(a \oplus b) + (a \oplus c) = ((a \oplus b) \oplus (a \oplus c)) + 2 ((a \oplus b) \land (a \oplus c)) = (b \oplus c) + 2 ((a \oplus b) \land (a \oplus c)),$$$

from the identity $$$x + y = (x \oplus y) + 2(x \land y)$$$.

So, the three satisfy the triangle inequality iff $$$a \oplus b$$$, $$$b \oplus c$$$ and $$$c \oplus a$$$ are all pairwise non-disjoint.

A digit DP solution from here is rather straightforward, 165666080.

Here's $$$\land$$$ and $$$\oplus$$$ refer to bitwise AND and XOR respectively.

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

    Yeah I did this. The editorial soln has $$$2^9$$$ constant factor but this soln took only $$$2^6$$$.

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

      Not really, you have atmost $$$8$$$ transitions from each state so it's more or less the same constant factor.

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

    Can you please explain your dp states and transitions in brief?

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 6   Vote: I like it +9 Vote: I do not like it

      Rather than calling the numbers $$$a, b, c$$$ let's call them $$$x_0, x_1, x_2$$$.

      We iterate from the highest bit to the lowest, so call the highest bit $$$0$$$.

      We have the states $$$(\text{idx}, \text{tight}, \text{cond})$$$ where $$$\text{idx}$$$ is the current bit we are on, $$$\text{tight}$$$, and $$$\text{cond}$$$ are bitmasks of size $$$3$$$.

      • $$$\text{tight}_i$$$ is set if $$$x_i$$$ currently matches the input on the prefix $$$[0, \text{idx})$$$.

      • $$$\text{cond}_i$$$ is set if $$$(x_i \oplus x_{i + 1}) \land (x_i \oplus x_{i - 1})$$$ (the indices are modulo $$$3$$$) has a bit set among the $$$[0, \text{idx})$$$ bits.

      I believe the transitions should be clear if you have experience with digit DP.

      We finally require that $$$\text{cond}_0, \text{cond}_1, \text{cond}_2$$$ are set so the final answer is $$$\sum_i \text{dp}(\lvert n\rvert, i, 7)$$$.

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

    what does "all pairwise non disjoint" mean?

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

      By disjoint I mean that $$$x \land y = 0$$$, because if you view $$$x$$$ and $$$y$$$, as bitmasks/sets, $$$x \land y$$$ is the intersection of $$$x$$$ and $$$y$$$, and we say that sets $$$S$$$ and $$$T$$$ are disjoint if $$$S \cap T = \varnothing$$$.

      So $$$x, y, z$$$ being pairwise non-disjoint means that $$$x \land y$$$, $$$y \land z$$$ and $$$z \land x$$$ are all non-zero.

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

As a member of botswana community, i upvoted this post !!!!!!!!!!!!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does this solution give the wrong answer? http://pastebin.ubuntu.com/p/TrRV4gSKG5/

»
2 months ago, # |
  Vote: I like it +11 Vote: I do not like it

For 1710B-Rain, why will the maximum position always be one of the centers? Can anybody help me to prove that?

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

    A point $$$p$$$ which is between two center points, $$$L$$$ is all the points locates left to it and $$$R$$$ is all the points locates right to it. When we move $$$p$$$ from left to right, the rainfall from $$$L$$$ decrease(getting far away from it) or stay the same(some points is too far to give rainfall), the rainfall from $$$R$$$ increase or stay the same. In detail, the rainfall from $$$L$$$ decrease quickly first, then slowly(some points becomes too far) and the rainfall from $$$R$$$ increase slowly first, then fast(some points becomes close enough). That is the second derivative is always non-negative. So one of the center point must be the maximum point.

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

      This makes so much sense. Thanks a lot :)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me understand the solution of div1B? I do not understand the implementation of the logic given in the editorial. What exactly is getIntersection() calculating?

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

I struggled a lot with understanding how we found the intersections in 1710B — Rain without doing exhausting casework, so I decided to explain the math in the code for anyone else who also had a hard time.

The post is a bit long, so I'll keep it in spoilers.

There might be an easier way but it is the most intuitive way I could find to understand the solution.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +14 Vote: I do not like it

    i think we can calculate intersection directly. suppose we have two region specified by $$$(a,b)$$$ and $$$(c,d)$$$ , and the intersection is $$$(x,y)$$$. then because the boundaries of regions are just line with slope 1 or -1, we can get

    $$$ \begin{align*} x + y = c + d \\ y - x = b - a \end{align*} $$$

    which gives

    $$$ \begin{align*} x = (a-b+c+d)/2 \\ y = (b-a+c+d)/2 \end{align*} $$$

    through my test, it seems the same as the one in tutorial code

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 7   Vote: I like it +8 Vote: I do not like it

      That may be the case for some situations but the formulas are not correct every time. That is why my goal in the post was to skip "exhausting casework".

      Consider two points which sit on the same horizontal line, specifically $$$(a, b)$$$ and $$$(c,d) = (a, d)$$$. Then the formulas give the intersection as $$$(x,y) = \left(\frac{2c+d-b}{2}, \frac{b+d}{2}\right)$$$. We can see how this is not correct since the we can easily see that the center point should be $$$(x,y) = (a,b)$$$. (suppose $$$b>d$$$)

      Note: you might argue that we never intersect points with the same $$$x$$$ value, so with some constraint the problem may be solved the way you described but it is not whole picture I wanted to give.

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

        oh, well, you are right. the main reason is that when one region totally contain another region, the intersection assumed in my equation is actually not exist.

        so it can not achieve "check whether point (xi,pi) belongs to such region", but just calculate some "ideal" intersection ... QAQ

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          hello, after calculating the prefix and suffix sums and getting the total rainfall in all xi's, why can't we do an O(n^2) approach, where we go through each day and get the maximum after removing that day's rain and checking if it is <= m ? , i tried it but gave me WA in TC2 , can you tell me why my approach would be wrong?

          • »
            »
            »
            »
            »
            »
            7 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            if we put time complexity aside, your method is absolutely right.

            however this problem has no guarantee about input xi and pi, so there may be some cases that many pairs of same xi and pi, and your 'originalPos' only record one position. if there are more than one feasible solutions among them, you just change one position in answer string.

            one possible work around is use map<pair, queue> , you can refer to this

            meanwhile, i don't understand very well how you calculate 'left' and 'right' arrays , could you explain a little

            • »
              »
              »
              »
              »
              »
              »
              7 weeks ago, # ^ |
              Rev. 7   Vote: I like it 0 Vote: I do not like it

              okay i assumed xi's are always unique my bad, so i think there's an easier way to pre calculate the sums but for me the motivation was, for each xi (consider sorted pair<xi,ai> and the rainfall can extend only to the right of xi), it will be

              left[i]=a[i]+max(0,left[i-1]-valReduce[i]- cnt*abs(x[i]-x[i-1])),

              now what is cnt? cnt should ideally be the number of rains that have happened before x[i] (in terms of the number-line) but that does not happen as some rainfall might not extend till the current x[i] hence at every iteration for left prefix i check the max index to which i can extend my current rainfall to, and to the next index of that (redxnIndex) i increase cntReduce array so that when i arrive at that index i know i will need to reduce my cnt by this and also add some correction value to the above equation to valReduce array , similarly i do the same for right and then get the tot[i]=left[i]+right[i]-rainfall[i]

              so it will take O(N*log(N) + N) to calculate the total rainfall after N days

              also according to the constraints shouldn't O(N^2) run in 4 seconds? just curious

              • »
                »
                »
                »
                »
                »
                »
                »
                7 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                thanks for explanation.

                for time issues, firstly based on system test result we know it can't pass. then from my experience, if a problem is tend to be solved by a n^2 solution, the N is at most around 1e4.

»
2 months ago, # |
  Vote: I like it +40 Vote: I do not like it

Let's upvote this editorial to show some support to Rhodoks.

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

Just to add to Div2 C, it's called toroidal coloring because the parallel edges are connected by the modular relation. If you imagine, that will make a toroid.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Lets appreciate them for making this contest possible, humans make mistakes, thanks for the contest and editorial ❤️

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me figure out what's wrong with my submission for C 165672596

long explanation follows

As you can probably tell, this problem frustrated me a lot in contest. I'm wondering if anyone has a testcase or logic flaw that breaks my solution.

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

    Take a look at Ticket 15920 from CF Stress for a counter example.

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

    Here is a test-case:

    5 5 4
    15 10 10 10
    

    First color fills 3 rows, while the rest each fill 2 rows. The YES solution is simple: use 3 + 2 = 5. However, your approach calculates a sum of 3 + 2 + 2 + 2 = 9. Then the first iteration of the leftover loop checks if 3 can be dropped, concluding that yes, 3 can be dropped to reduce the sum to 6, and it also changes the 3 to 0. However, without the 3, it is impossible to reach a target value of 5, since all that's left are 2s.

    Even aside from this, I don't feel like your approach of calculating leftovers and adjusting the sums accordingly is guaranteed to reach a correct solution, especially since the loop doesn't revisit a color (just a plain for loop). Have you actually proved anything about this approach?

    Instead, consider this alternative observation: if we overshoot the target, then for each color that covered more than 2 rows, we can decrease how many rows it covers (don't implement this, just think). If you keep reducing the problem in this manner, what are the possible outcomes? Is there some state that can't be reduced in this manner, but still overshoots? Once you characterize this state, you should be able to figure out when such a state can lead to a YES and when it will lead to a NO.

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

      You beat me to it.

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

      yeah, thanks. It's obvious to me now that a constructive solution like mine would be harder to make work.

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

    Say your list is [3,2,2,2] and you are trying to make 5. You algorithm will take 1 out of the 1st element, and report 'No'?

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

      I like how we both thought of literally the exact same counterexample

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a proof of Hint 2 from XOR Triangle Editorial ? a XOR b <= a + b

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

    For each bit, XOR is the plus modulo $$$2$$$ which is less or equal to plus.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In div 2 problem c my logic is same as given in this editorial but still it shows wrong answer on test 8 . Here's my solution https://codeforces.com/contest/1711/submission/165574557 Please help!!!

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

    Oh, your ll is just long but not long long.

    So it will overflow.

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

wow, the relation between div2D and region intersections is beyond my thought, interesting.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

To be honest, apart from Div. 1 E, this is a really great round. The questions are really well-thought.

Thank you for this round.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Question not that related to this round: Was problem difficulty rating system different in the past? I found lot of problems that have very high difficulty rating for it's difficulty. Some of them are from like 10 years ago, but some of them like this one is from 3 years ago.

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

    Well I dont know if the rating system was different or not but my guess is that codeforces had fewer number of participants back then so many questions had less number of accepted submissions so their rating seems to be inflated, also a lot of time due to weak pretests a lot of successful submissions during the contest fail the system test, when this happens the rating of that particular question gets inflated as successful submissions during the contest really goes down.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i like the problems a lot ty <3

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

The editorial of Div2B (1711B) is a little misleading:

If $$$y \geq 1$$$, then only deleting one vertex with odd degree would have been enough.

If $$$y = 0$$$, then the parity of the edges at the end is determined only by the number of edges whose both endpoints are deleted. In particular, there must be at least two adjacent vertices deleted with even degree.

In particular, specifying the conditions of $$$y \geq 1$$$ and $$$y = 0$$$ (which are mutually exclusive conditions) suggests that these are two mutually exclusive cases to consider, i.e., if $$$y \geq 1$$$, we should only consider the odd degrees for removal, while the removal of adjacent vertices with even degree should only be considered when $$$y = 0$$$. But this is false, since even when $$$y \geq 1$$$, it is not enough to consider only the odd vertices, and the optimal solution may require the removal of two adjacent even vertices instead.

My suggestion would be to remove all mention of $$$x$$$ and $$$y$$$ (since their values are irrelevant for the algorithm design), and instead phrase these "cases" as options to consider (the I/O explanation in the problem also refers to them as options), with a brief note of why it's sufficient to only consider these two options: the other options not considered are the removal of a single even person only (which doesn't fix the total degree parity) or the removal of some superset of one of these two options (odd + some set, or even + even + some set).

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

    well said

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +83 Vote: I do not like it

    Well, what I want to express is that, if you have an answer:

    1. If $$$y \geq 1$$$, you can get a not worse (but may not be the best) answer by only deleting one odd degree vertex of the $$$y$$$ vertices. So you do not need to consider it except when $$$(x,y)=(0,1)$$$.

    2. If $$$y = 0$$$, you can get a not worse (but may not be the best) answer by only deleting two adjacent even-degree vertices. So you do not need to consider it except when $$$(x,y)=(2,0)$$$ and they are neighbours.

    So, If we want to find the best answer, we only need to consider such two cases as I said.

    And if you think what I express here is easier to understand, I will modify it.

»
2 months ago, # |
  Vote: I like it -8 Vote: I do not like it

cough it's totally not because I suck at graphs that I ruined my ratings this round cough it shouldn't be violent cough

»
2 months ago, # |
  Vote: I like it -8 Vote: I do not like it

if m is even why the answer is zero ? cannot there be present a friend who is not connected to a friend ?

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

    Because there is already even number of cakes so it's optimal to invite everyone

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

c is a brilliant problem...

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

A different solution to Div1 D:

$$$Construct(L,R)$$$ is a function that finds the edges in the component of [L,R] ([L,R] is connected).

You can construct as follows:

Let $$$z$$$ be the largest number satisfies $$$z<R$$$ and $$$[L,z]$$$ is connected.

Let $$$x$$$ be the largest number satisfies $$$x\leq z$$$ and $$$[x,R]$$$ is connected.

There is a useful property :

  • There is no segment $$$[l',r'],(l'\in [L,z],r'\in (z,R))$$$ that is connected.

Then if you construct $$$[L,z]$$$ first , the only influence to $$$[L,R]$$$ are the segments $$$[y,R],(L\leq y\leq z)$$$

If $$$[z+1,R]$$$ is connected then the rest of construction is easy:

  1. $$$Construct[z+1,R]$$$
  2. Connect $$$R$$$ and $$$x$$$

If $$$[z+1,R]$$$ is not connected . Then $$$[z+1,R]$$$ can be split into some connected components $$$[l_1,r_1],[l_2,r_2]...[l_k,r_k],[l_{k+1},r_{k+1}]$$$.

The solution is also not hard:

  1. $$$Construct[l_i,r_i]$$$ for every $$$i$$$.

  2. Connect $$$r_1,r_2,r_3...r_{k-1}$$$ and $$$R$$$.

  3. Connect $$$r_k$$$ and $$$x$$$.

  4. Connect $$$R$$$ and $$$x$$$.

In fact the last two part can be implemented together.Submission: 165734051

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

I get stuck proving only stripe pattern make all cell to have at least 3 neighbors. (Div.2 C)

Is there a easy way to prove it?

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

    It must be stripe pattern.

    In a row or a column.

    like this:

    1 1 1 1
    2 2 2 2
    2 2 2 2
    1 1 1 1
    

    or

    1 1 2 2
    1 1 2 2
    1 1 2 2
    1 1 2 2
    

    Prove:

    We can proof by contradiction. If there is someting like this:

    1 1 1 1
    1 1 2 2
    2 2 2 2
    

    It is not beautiful picture, because the "1" in row $$$2$$$ column $$$2$$$ only has $$$1$$$ neighbor.

    similarly, this sort of picture is not beautiful:

    1 1 2 2
    1 1 2 2
    1 2 2 2
    1 2 2 2
    
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In other words, if the picture is not a stripe, there must be a place which has $$$2$$$ neighbors with different colors.

    neighbors with different colors are blacken.

    1 1 1 1

    1 1 2 2

    2 2 2 2

    Node that the lenth / width of the stripes mush be bigger than $$$2$$$.

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

      thank's for your reply.

      i proved this by different way!

      we can generalize "non stripe pattern" as a "(stripe pattern) — (hole)" when hole is not stripe.

      and there is a two case.

      1. holes appear in first column.

      2. no hole appears in first column.

      1st case ex)

      xxxxxx

      001000 <- 1 in this column is bad

      010000

      110011

      010001

      (x is color which is not 1 (possibly 0))

      then

      -> there exists always bad color 1 in column which color 1 is appear for the first time.

      2nd case ex)

      xxxxxx

      111111

      111111

      010000 <- some 0 in this column is bad

      110011

      010001

      then

      -> there exists always bad color 0 in column which color 0 is appear for the first time.

      and this model include all possible region -> proved!

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

oH mine gods, Sparky_Master_WCH1226 are the goodest in contributon rateing agan. thakns for you suppot sar.

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

D2D

Damn. This getIntersection magic is the one I wouldn've thought about.

You can do it simpler. Just maintain the minimum height current point should have to "cover" all the things on the left of it. It is a very simple dp.
Then calculate the same for right and check for each point whether it satisfies both left and right.

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

In the problem B,we always can delete a edge to get a legal state. I think that "if(degree[x[i]]%2==0&&degree[y[i]]%2==0)" can be annotated. This is my test Your text to link here...

for(int i=1;i<=m;i++)

/*if(degree[x[i]]%2==0&&degree[y[i]]%2==0)*/
    ans = min(ans,unhappy[x[i]]+unhappy[y[i]]);
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We can't delete an edge. We have to remove a vertex.

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

      If m%2==0 ,the status is legal. We can delete two vertices of an edge.

      "Let's consider the case where m is odd only, since if m is even the answer is 0."

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi everyone. I request you to check my submission: https://codeforces.com/contest/1711/submission/165852284 It is giving correct answer in my console but wrong answer on codeforces.

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

    It was a segmentation error. Thanks to anyone who checked.

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

      for(int i = 1; i<=n; i++) cin >> arr[i]; for(int i = 0; i<n; i++){ if(cnt[i]%2 ==1){ ans = min(ans, arr[i]);} }

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

Hello. Can someone tell me please, why this solution for C is WA?

https://codeforces.com/contest/1711/submission/165895290

Thank you!

UPD: Got it: https://codeforces.com/contest/1711/submission/165896780

»
2 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Getting MLE in Problem B (Party). My solution

How to resolve?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For 1710A-Color the Picture, shouldn't $$$\sum_{i=1}^{n} \lfloor \frac{a_{i}}{m} \rfloor$$$ instead be $$$\sum_{i=1}^{k} \lfloor \frac{a_{i}}{m} \rfloor$$$? Also, I don't understand why if, when $$$n$$$ is even, $$$\sum_{i=1}^{k} \lfloor \frac{a_{i}}{m} \rfloor \geq n$$$ is sufficient. What if every $$$a_{i}$$$ was a single row? Don't you still check if you can make the sum using at least $$$2$$$ from each? It should be the sum of every $$$\lfloor \frac{a_{i}}{m} \rfloor$$$ that is at least $$$2$$$.

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

    You are right, It is $$$k$$$ and I forget to mention skipping those $$$a_i < 2*m$$$.

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

I solved Div1B in incredibly ugly way using segment tree. It was good exercise though.

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

    I also tried an approach with a seg tree but couldn't figure it out. If you have time, could you please explain how you did it?

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it +9 Vote: I do not like it

      Let $$$T(x)$$$ be the total accumulation at position $$$x$$$. We can compute a bunch of intervals $$$[l_{i},r_{i})$$$ and pairs of integers $$$(a_{i},b_{i})$$$ such that for all $$$x\in[l_{i},r_{i})$$$, $$$T(x)=a_{i}x+b_{i}$$$ using prefix sum technique. If we let $$$f_{i}=\max_{x\in [l_{i},r_{i})} a_{i}x+b_{i}$$$ then it is obvious that we will get $$$f_{i}$$$ either at $$$x=l_{i}$$$ or $$$x=r_{i} - 1$$$. Now we want to consider the case when we can erase the $$$j$$$ th rain. After we erase the rain, if we let $$$W_{j}(v)$$$ be the total accumulation of the position $$$v$$$ if we erase $$$j$$$ th rains, then:

      $$$ W_{j}(v) = \begin{cases} T(v) & \text{if } v \lt x_{j} - p_{j} \\ T(v) - v - p_{j} + x_{j} & \text{if } x_{j} - p_{j} \le v \lt x_{j} \\ T(v) + v - p_{j} - x_{j} & \text{if } x_{j} \le v \lt x_{j} + p_{j} \\ T(v) & \text {if } x_{j} + p_{j} \le v \\ \end{cases} $$$

      Notice, that for every $$$i$$$, $$$\max_{v\in [l_{i},r_{i})} W_{j}(v)$$$ will also be achieved at either $$$v=l_{i}$$$ or $$$v=r_{i}-1$$$. Thus, all we have to do is compute the maximum of $$$W_{j}(v)$$$ for all $$$v\in [l_{i},r_{i})$$$ for each $$$i$$$ using segment tree and compare the maximum with $$$m$$$. (Forgive me for terrible explanation because it is quite difficult to explain in plain English which is not my mother tongue)

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

        That was a really good explanation, thanks a lot!

»
2 months ago, # |
  Vote: I like it -17 Vote: I do not like it
»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

»
2 months ago, # |
  Vote: I like it +24 Vote: I do not like it

I was having hard time figuring out the editorial soln for Div2D/Div1B. So this is what I came up with.

First we figure out all the $$$a_i$$$ values as stated in the editorial. We will only consider all the $$$x$$$ values for which $$$a_{x} > m$$$. Call them critical points.
Take a look at the $$$i$$$-th flood. We will check it's left and right side separately. For it to fix any point $$$j$$$ to it's left (that is $$$j < x_i$$$), this must be true: $$$a_j - (p_i - |x_i - j|) \leq m$$$ $$$\Rightarrow a_j - j - m \leq p_i - x_i$$$. Deletion of $$$i$$$-th flood must satisfy this for all critical points to it's left. Here we can keep prefix maximum for $$$a_j - j - m$$$ for all critical points and compare that with the R.H.S.

We can get similar equation for the right half. It's $$$a_j + j - m \leq p_i + x_i$$$. This can be checked by keeping suffix maximums for all critical points.

Overall the solution will be $$$\mathcal{O}(n\log{}n)$$$. One note for implementation, it's easier to check the two equations for all relevant points (even ones with $$$a_x <= m$$$) instead of just the critical ones. For points with $$$a_x <= m$$$ define their L.H.S of the two above equations to be $$$-\infty$$$ and it will be fine. Here is my submission.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In div1C, can anyone explain how the transitions are taking place? What is m and how does it decide tmpmask1 and tmpmask2?

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

    $$$m$$$ is the $$$i$$$-th bit of $$$a,b,c$$$. For example, when $$$m=(101)_2$$$ then $$$a_i=1,b_i=0,c_i=1$$$.

    First, you should check if $$$m$$$ is valid for the current state. If $$$cnt$$$ will let $$$a,b,c$$$ exceed the upper bound you should "continue".

    Then $$$tmpmask2$$$ is whether it will reach the upper bound ($$$0$$$ is yes while $$$1$$$ is no). $$$tmpmask1$$$ is whether it satisfies the conditions we mention in the editorial ($$$1$$$ is yes while $$$0$$$ is no).

»
2 months ago, # |
  Vote: I like it +26 Vote: I do not like it

The editorial of 1E says:

If we consider the initial bipartite graph, it's easy to see that we only need to check whether $$$(1,1)$$$ is in all maximum matchings of the initial graph, becuase the maximum matching remains unchanged in the other $$$999$$$ parts.

(And it mistakes "because" for "becuase".)

I think it's not obvious (probably because I'm too foolish), so I try to prove it. We need to prove

  • If we want to get a maximum matching of the new graph, we can just copy a maximum matching of the initial graph $$$1000$$$ times.
  • If $$$(1,1)$$$ belongs to all the maximum matchings of the initial graph, and we want to get a maximum matching of the new graph with a copy of $$$(1,1)$$$ removed, we can just remove a copy of $$$(1,1)$$$ from the maximum matching of the new graph we get above.

The main idea of my proof is to prove that there exists no augmenting path in the two matchings we get above. To prove this, we assume that there exist an augmenting path, and we try to make it contains no more than one copy of any vertices. Then we show that this path is an augmenting path of the maximum matching of the initial graph or the initial graph without $$$(1,1)$$$.

Sorry for not writing the whole proof down here, but my poor English doesn't allow me to do that.

However, since the editorial said "it's easy to see", I believe there is a much cleverer and shorter proof. But I'm not able to come up with it. If anyone knows the proof, please teach me. Thanks.

»
2 months ago, # |
  Vote: I like it +23 Vote: I do not like it

And the editorial says

For the maximum independent set without the initial cell, you just need to remove it when it is in $$$I$$$.

Note that if $$$da_{va}=da_{va-1}$$$ or $$$db_{vb}=db_{vb-1}$$$ ($$$(va,vb)$$$ is the starting cell), this strategy may not give the correct result for a certain $$$(i,j)$$$. I don't know whether it can always give the correct maximum independent set.

I'm too lazy to write the proof for why it's correct if $$$(va,vb)$$$ doesn't meet this condition, but it's not hard to prove.

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

    Actually, I think you can get WA depending on how you implement it.

    Let $$$s(i,j), i \in [0,n], j \in [0,m],$$$ denote the size of the independent set if we pick the first $$$i$$$ rows and $$$j$$$ first columns white. Let $$$db[j]$$$ be the number of white cells in each column. Note that $$$db[j]$$$ decreases with $$$j$$$. Then, (when the initial position is considered black)

    $$$\delta(i,j) = s(i,j+1) - s(i,j) = \min(db[j], i) + \max(db[j], i) - n = db[j] + i - n.$$$

    That means that it is useful to increase $$$j$$$ if $$$\delta(i, j) > 0 \iff db[j] > n - i$$$. On the other hand, if $$$db[j] = n-i$$$, then we get the same size of independent set whether or not we increase $$$j$$$. Thus, you could implement it such that you increment $$$j$$$ whenever $$$db[j] >= n-i$$$ or whenever $$$db[j] > n-i$$$ and both would be correct when the initial position is considered black. However, when the initial position is not considered black, for some $$$j$$$ the condition becomes $$$db[j] > \text{or} >= n - i - 1$$$. Let us see that if you pick the strict option, $$$db[j] > n - i$$$, your code gives WA.

    Suppose $$$n = 4, m = 2$$$ and that the matrix is as follows, where X marks the initial position.

    WW
    WW
    BX
    BB
    

    Then, $$$db[] = {2,2}$$$. For $$$i = 0$$$, $$$db[0] = 2$$$ is smaller than $$$n - 0 = 4$$$, so the optimal $$$j$$$ is $$$0$$$ and $$$s(0,0) = 3$$$ because the starting point is not considered black. The same happens when $$$i = 1$$$. When $$$i = 2$$$, though, $$$n - i = 2$$$ and $$$db[0] = 2$$$. Hence, if we increase $$$j$$$ we still have the same maximum independent set size. But, once we do so, the condition becomes $$$db[j] >= n - i -1$$$, meaning that it is strictly better to increase $$$j$$$. The optimal $$$j$$$ for $$$i = 2$$$ is $$$j = 2$$$. This corresponds to choosing all white cells as independent set, giving answer $$$4$$$. They key fact is that if we don't increase $$$j$$$ when the answer would not improve, we don't get to this position.

    It is true that in this example the same position would be obtained when $$$i = 3$$$, but I think that we can craft examples where this does not happen.

    To remember this easily, the mental heuristic would be to prefer maximum independent sets with more white vertices, since afterwards there is a black vertex that we are going to remove if it is in our independent set.

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Can anyone explain me Question B — Rain. I'm unable to understand the editorial.

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

    Which part do you need to explain? Difference and prefix sum? Or the calculation of region?

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

      Please explain calculation of region part?

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

        First, the maximum of $$$a$$$ can always be achieved at the center of a certain rain. So if for the center position of any rain $$$j$$$, $$$a_j \leq m$$$ then we know it is valid.

        If $$$a_j > m$$$ then if erasing rain $$$i$$$ can make position $$$j$$$ valid, $$$p_i−|x_i−j| \geq a_j−m$$$ must hold. Let's see what such a region is like.

        $$$p_i−|x_i−j| \geq a_j−m \iff |x_i-j| \leq p_i+m-a_j$$$ where $$$m-a_j$$$ is known constant for a certain $$$j$$$.

        So point $$$(x_i,p_i)$$$ should be in such a region:

        $$$-p_i-C_1 \leq x_i-C_2 \leq p_i + C_1$$$

        Which is the translation of region $$$-p_i \leq x_i \leq p_i$$$, like:

        ..*********...
        ...*******....
        ....*****.....
        .....***......
        ......*.......
        

        Multiple such regions' intersection still holds such structure, and it can be easily calculated. I think UUUnmei's picture shows it clearly.

        You can refer to my getIntersection function which uses a way of rotation (rotate 45° clockwise and take the maximum of $$$x,y$$$ then rotate them back) to calculate it.

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

          So much thanks for this wonderful explanation.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What topic should know first to understand the solving approach/ solution of problem D:Rain?

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

    I think you need to understand difference and prefix sum. You can refer to this link.

    In this problem, you need a "second difference" and calculate it after discretization.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me understand 165556433 for Div1 B?

Specifically, What do a and b in the struct event represent?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Well, so finally Rhodoks' contribution turns positive again. That is a fair result at last anyway. Congratulations again, and also %%% CCOrz.

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

explanation for Q2.... party

//basically we have two ways and the ans will be min from both of those cases..... //one way could be finding the point having odd connections and remove that..... //another way could be deleting 1 member in such a way that deleting it causes min unhappiness value.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can any one help me with last test case in B problem I think the answer must be 1

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

anybody can explain last test case in problem B

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

Alternate solution to problem 1710B Rain which does not requires you to find intersection: The idea is similar to this problem. First calculate value of a at all points then calculate the equivalent points. Then take their range. For any valid point it must cover the entire range.

Solve function

AC Submission