Блог пользователя MikeMirzayanov

Автор MikeMirzayanov, 5 лет назад, По-английски

Hello,

Initially, the problem 1255B - Fridge Lockers was with no constraint $$$m \le n$$$ (just $$$m \le 2000$$$). Almost all participants (and me) invented wrong solution like: "make a cycle plus take the cheapest edge $$$m-n$$$ times". The counter-example is $$$n=5$$$, $$$m=6$$$ and prices are $$$3, 4, 1, 4, 5$$$. Look into the picture:

It was really unexpected for my intuition (and, of course, failed a proof).

Do you know the solution for this case?

  • Проголосовать: нравится
  • +184
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +79 Проголосовать: не нравится

After seeing this, now the change in constraints make sense

»
5 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

I had thought about a case like this during the contest and all the time during the contest I was trying to come up with a full-proof solution (that could solve this case as well). I was confused as how could a problem like this is receiving so many accepted solutions.

Much (or almost all?) of the accepted solutions would fail this test case.

My question is : How is it fair to change the problem into something that is much much simpler by changing the constraints AND letting people get away with wrong submissions AMIDST THE CONTEST. Not to mention after almost 1 hour had passed. I did not even go for the third problem for a long time thinking B is receiving so many submissions.

MikeMirzayanov Your thoughts?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    If it affected you heavily, you can ask to be unrated for you. There is a link where the contest was published.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    My approach was wrong.that's why i've got WA. But you don't know how many contestants struggled whole time without submission in such case and not going to next problem. Which form will they fill? :(

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how 1500 people solved this before changes?)

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The pre-tests were also incorrect. (Or at least didn't test the edge cases)

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится -11 Проголосовать: не нравится

      i recieved wrong answer at test 2, but did all as written above. moreover, now it's full solving)

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится

        I am assuming you are talking about this submission. This submission is incorrect because your calculation of min2 is incorrect. Consider the following test case:

        1
        3 4
        1 2 1
        

        Here, you will find the two smallest elements to be 1 and 1, so you say min1 is 0 (correct) and that min2 is 1+min1 = 1. However, as you can see, min2 should actually be 2, so your output is wrong.

        Your Output:

        10
        1 2
        2 3
        3 1
        1 2
        

        Correct Output:

        10
        1 2
        2 3
        3 1
        1 3
        
»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

Graph formed in optimal answer must have m edges .So optimal solution is to connect as much edges to the vertex (fridge) having least weight as well as keeping the degree of other vertices atleast 2 . making cycles of 3 with least weighted fridge and finally connecting the remaining edges between vertices having least weight . As i have written below in comment , it is possible that few vertices will be left , we need to put them in between some cycle of length 3.

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    How about when n % 2 = 0 ?
    In that case, after making cycles of 3 with the least weighted vertex, you'll have one last vertex not connected to anything.
    I think then we just link it to any of the cycles because it should have a degree 2 anyway and anywhere we add it it's gonna add its weight * 2 to the answer.

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

      procedure is : 1.if m<n output -1.

      2.if m=n , output 2*(sum of weights of all fridges)

      3.If m>n .Sort the vertices . Make cycle of length 3 (with v1,v2,v3). m = m-3 and n = n-3 after this . After this keep making cycle of length 3 and do m = m-3 and n= n-2 . If during any step m==(n+1) or n==1 or n==0 , attach remaining n vertices between two vertices of a cycle of length 3 and attach remaining edges to two vertices having least weight .

      check these 2 cases : https://www.imageupload.net/image/iFddA , https://www.imageupload.net/image/iFDVz

»
5 лет назад, # |
Rev. 7   Проголосовать: нравится +6 Проголосовать: не нравится

EDIT: Nevermind the algorithm below, I just found out it's incorrect as well — take a look at the other comments :)

Incorrect algorithm
»
5 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Well I dont really know weather or not my algorithm will work but here it is.

If m >= 2n we just connect each fridge to 2 cheapest other fridges. And with the rest (m — 2(n-2)) chains we connect two cheapest fridges. If n < m < 2m we make a cycle and we are left with m-n chains. Now I suggest removing the heaviest chains from the heaviest fridge. In your example it would be removing 5-4 chains and replacing them with 2 other chains connecting them with the fridge with minimal cost (5-1). But if the second fridge is already connected to the lightest fridge then we connect it with second lightest fridge(I.e 4-3). now we are left with m-n-1 chains. we repeat this process until we are left with no chains

Please tell me if my algorithm has any flaws or weather it is possible to implement it easily. Thanks Pogson

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    For the case m>=2n,You can implement it in a easier way. Just like the way mentioned in the above blog-"make a cycle plus take the cheapest edge m−n times".

    This would give exactly the same answer as your algorithm for the m>=2n case. Let us consider min1 and min2 as the two lightest(cheapest) fridges. In your algorithm you are first connecting each fridge to min1 and min2, then you are adding (m — 2(n-2)) edges between min1 and min2.

    Total cost = 2*(sum of weights of all the fridges except min1 and min2) +(n-2)*min1 + (n-2)*min2 + (m — 2(n-2))*(min1+min2)

    If you simplify it a little bit-

    Total cost = 2*(sum of weights of all the fridges except min1 and min2) +(m — (n-2))*(min1+min2)

    Total cost = 2*(sum of weights of all the fridges) +(m — n)*(min1+min2)

    Which is exactly the same cost if you first connect edges such that a cycle with n nodes and n edges is formed, and then you add (m-n) edges between min1 and min2.

»
5 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

Link for convenience: 1255B - Fridge Lockers

»
5 лет назад, # |
  Проголосовать: нравится +127 Проголосовать: не нравится

Let's assume that $$$a_{i}$$$ are sorted. We are paying $$$\sum_{i} a_{i} d_{i}$$$ where $$$d_{i}$$$ is the degree of vertex $$$i$$$. Each vertex should have at least two different neighbors, therefore $$$d_{i} \ge 2$$$. $$$\sum_{i} d_{i} = 2m$$$. If $$$m < n$$$ there is no solution. If $$$n = 2$$$ there is no solution. Otherwise there should be at least $$$\lceil \frac{n-1}{2} \rceil$$$ edges whose endpoints are not $$$1$$$ because each of $$$n-1$$$ "not-1" vertices should have at least 1 "not-1" neighbor. Other $$$m - \lceil \frac{n-1}{2} \rceil$$$ could have only one endpoint in vertex $$$1$$$. Therefore $$$d_{1} \le m - \lceil \frac{n-1}{2} \rceil$$$. Also $$$d_{1} \le 2m - 2(n - 1)$$$ Let's prove that we can use $$$d_{1} = \min(m - \lceil \frac{n-1}{2} \rceil, 2m - 2(n - 1))$$$, $$$d_{2} = 2m - 2(n - 2) - d_{1}$$$, $$$d_{i} = 2$$$ (for $$$3 \le i \le n$$$) and it is optimal.

Let's use induction on $$$m$$$ for fixed $$$n$$$.
Base case: $$$n \le m \le 2(n - 1) - \lceil \frac{n-1}{2} \rceil$$$ i.e. $$$d_{1} = 2m - 2(n - 1)$$$. In that case $$$d_{2} = 2$$$. Let's construct $$$\frac{1}{2} d_{1}$$$ chains of length at least two out of vertices $$$2-n$$$ and then connect vertex $$$1$$$ to their ends. We can do that if and only if $$$n - 1 \ge 2 \frac{1}{2} d_{1} = 2m - 2(n - 1)$$$. And it is true (use $$$\lfloor \frac{x}{2} \rfloor + \lceil \frac{x}{2} \rceil = x$$$).
Inductive step: Now $$$d_{1} < 2m - 2(n - 1)$$$ which means $$$d_{2} > 2$$$. Let's use solution for $$$m - 1$$$ and add edge $$$1-2$$$.

It is easy to see that it is optimal because $$$\sum_{i < k} d_{i}$$$ is maximal for each $$$k$$$.

  • »
    »
    5 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +36 Проголосовать: не нравится

    Dang, I was hoping to be the first to write this up and post it, but when I went back to this page I saw "Um_nik 7 minutes ago". :)

    Anyway, my code demonstrating this idea, if it helps anyone: 65400832 (findTheoreticalMin calculates the lower bound, findEdges actually solves the problem and returns an optimal list of edges that attains this bound). Note that I just submitted it to have a convenient way to share it, the Codeforces tests don't actually hit the $$$m > n$$$ case.

    I'm not 1000% sure the code is correct, but I am pretty sure -- tested it locally on a variety of $$$n$$$ and $$$m$$$ and randomized $$$a$$$ arrays.

  • »
    »
    5 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

    Nice proof.

    I think the physical interpretation of this is:

    Assume $$$n>2$$$, $$$m\geq n$$$, $$$a_i$$$ are sorted, and that we are consuming nodes and edges iteratively (initially node $$$1$$$ is consumed and no edges are consumed), where the number of remaining nodes is $$$n_r$$$ and the number of remaining edges is $$$m_r$$$ (initially, $$$n_r=n-1$$$ and $$$m_r=m$$$).

    1. While $$$n_r\geq 2$$$ and $$$m_r>n_r$$$, form a cycle of length $$$3$$$ between node $$$1$$$ and two new nodes ($$$n_r:=n_r-2$$$, $$$m_r:=m_r-3$$$).
    2. If $$$n_r>0$$$, add $$$n_r$$$ nodes and $$$n_r$$$ edges to any cycle already formed with node $$$1$$$ ($$$n_r:=0$$$, $$$m_r:=m_r-n_r$$$).
    3. while $$$m_r>0$$$, add an edge between nodes $$$1$$$ and $$$2$$$ ($$$m_r:=m_r-1$$$).

    Feel free to correct me for any mistakes.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      More intuitively, we want to make some cycles, giving vertices the minimum degree (2) is good, we want all vertices except the cheapest one to be in just one cycle because then each cycle just adds extra 2x the smallest cost to the total cost, and we want as many of these cycles as possible because that gives us more edges. If we still don't have enough edges even with the maximum number of cycles, then all other conditions need to be satisfied and we just add edges with the smallest cost. The minimum number of cycles is $$$\left\lfloor\frac{n-1}{2}\right\rfloor$$$.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    i don't understand that ceil((n-1)/2). i can't understand that thing. can you please elaborate it?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится -6 Проголосовать: не нравится

    from where do you find these symbols on keyboard..... umm... cant see them anywhere

»
5 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

Hope codechef learns something from this.... cf reported about the issue even before the contest ended..... if it is codechef nobody even cares to admit that they were wrong(ICPC)

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    Codechef is not allowed to make any announcements about the ICPC contest and all information after the contest will have to come only from the RCDs (ICPC Regional Contest Directors). These are strict instructions from the RCDs.

    I'd like you to point out a single instance in Codechef's own contests where a mistake has been intentionally hidden, or the announcement even been delayed.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      https://www.codechef.com/LTIME77A in this contest this problem had a precision issue in the model solution and they ignored my comment (and from others) until after the contest ended for a 3 hour contest. They did fix it and make the round unrated later though.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Apologies for that. But that was not a case of ignoring the comments, and nor was it a case of precision issue. It has been explained in detail here.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          Oof thanks for reminding me the importance of test validators.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

D E L E T E D

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    It would be an unsuccessful hack, because the setter/tester's program also ignored this special edge case. Hacks are always tested in accordance with setter/tester's code

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Yes, I considered the case above, and is there any wrong with my code?https://mirror.codeforces.com/contest/1255/submission/65375823 thanks.

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится -76 Проголосовать: не нравится

Hello, Is my idea for the initial B wrong?

Warning: silly, wrong solution! Don't bother to read it!

Here is how it goes: First, we sort the nodes from smaller to bigger weight. Let's call the new formation s1, s2, ..., an.

If m > n, then we use the first n edges to connect the nodes to form a cycle from s1 to sn (so that the total cost is 2 * (s1 + s2 + ... + sn (1) ). Ie. We connect s1 with s2, s2 with s3, ..., an with s1.

What about the rest m — n edges? The optimal way to connect them is by using all of them to connect the 2 nodes with the smallest weight (namely s1 and s2). Note that this is allowed as per the problem statement! So, we get (m — n) * (s1 + s2) (2)

If we sum (1) and (2), we get the answer!

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Я потратил час времени на то, чтобы решать эту версию задачи, в то время как мог бы сдать C, D — они явно были проще и для меня раунд все равно остался рейтинговым, все ли апелляционные формы читались внимательно?