MikeMirzayanov's blog

Tricky Case in 1255B (Fridge Lockers) if m>n
By MikeMirzayanov, 5 years ago, In English

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?

  • Vote: I like it
  • +184
  • Vote: I do not like it

Comments Comments (37)
| Write comment?
»
5 years ago, # |
  Vote: I like it +79 Vote: I do not like it

After seeing this, now the change in constraints make sense

→ Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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?

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

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

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

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

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how 1500 people solved this before changes?)

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

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -11 Vote: I do not like it

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

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

        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
        → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 6   Vote: I like it 0 Vote: I do not like it

      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

      → Reply
»
5 years ago, # |
← Rev. 7   Vote: I like it +6 Vote: I do not like it

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

Incorrect algorithm
→ Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

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

    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.

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

      Thanks a lot, I didn't notice that it would give the same answer

      → Reply
»
5 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Link for convenience: 1255B - Fridge Lockers

→ Reply
»
5 years ago, # |
  Vote: I like it +127 Vote: I do not like it

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$$$.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +36 Vote: I do not like it

    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.

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it

    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.

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

      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$$$.

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

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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it +29 Vote: I do not like it

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)

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    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.

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

      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.

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

        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.

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

          Oof thanks for reminding me the importance of test validators.

          → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

D E L E T E D

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

    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

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -76 Vote: I do not like it

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!

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

    Did you even read the blog?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it -55 Vote: I do not like it

      Actually, I didn't! I jumped directly to writing the comment. Thanks for letting me know! :)

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

        Mike says your solution first in the blog And rest of blog means that is wrong solution

        → Reply