MikeMirzayanov's blog

By MikeMirzayanov, 4 months ago, ,

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

 » 4 months ago, # |   +79 After seeing this, now the change in constraints make sense
 » 4 months ago, # |   +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?
•  » » 4 months ago, # ^ |   +15 If it affected you heavily, you can ask to be unrated for you. There is a link where the contest was published.
•  » » 4 months ago, # ^ |   +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? :(
 » 4 months ago, # |   0 how 1500 people solved this before changes?)
•  » » 4 months ago, # ^ |   0 The pre-tests were also incorrect. (Or at least didn't test the edge cases)
•  » » » 4 months ago, # ^ |   -11 i recieved wrong answer at test 2, but did all as written above. moreover, now it's full solving)
•  » » » » 4 months ago, # ^ |   +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 
 » 4 months ago, # | ← 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.
•  » » 4 months ago, # ^ | ← 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.
•  » » » 4 months ago, # ^ | ← Rev. 6 →   0 procedure is : 1.if mn .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
 » 4 months ago, # | ← 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 algorithmThe actual solution is somewhat similar to what many of us have done. First, we need to use a cycle that doesn't contain the cheapest edge. Now, by connecting the two cheapest edges n-m times, both the cheapest edge and the second-cheapest edge now have 3 neighbors, instead of only two needed. This means that we could make them drop a neighbor if we wanted to! This is not really a consideration for the cheapest edge since it already is the cheapest, but it is a consideration for the second-cheapest edge — because we can now remove an edge and give it to the cheapest vertex instead! In other words, our algorithm works like this: Find any cycle not including the cheapest edge Choose any neighbor v of the second cheapest vertex c_2, make sure the cheapest vertex c_1 isn't already connected to that neighbor (there's always at least one neighbor for which this is true except for the special case n=3), and replace the edge (c_2, v) with (c_1, v) Add the cheapest edge n-m times
 » 4 months ago, # |   +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 chainsPlease tell me if my algorithm has any flaws or weather it is possible to implement it easily. Thanks Pogson
•  » » 4 months ago, # ^ |   0 This is exactly what I had thought except I missed the n
•  » » 4 months ago, # ^ |   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.
•  » » » 4 months ago, # ^ |   +3 Thanks a lot, I didn't notice that it would give the same answer
 » 4 months ago, # |   -66 tourist Could you solve this problem, please ?
 » 4 months ago, # |   +29 Link for convenience: 1255B - Fridge Lockers
•  » » 4 months ago, # ^ |   -18 I think you are angel in codeforces
 » 4 months ago, # |   +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$.
•  » » 4 months ago, # ^ | ← 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.
•  » » » 4 months ago, # ^ | ← Rev. 3 →   -17 [Deleted]
•  » » 4 months ago, # ^ | ← 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$). 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$). 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$). 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.
•  » » » 4 months ago, # ^ |   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$.
•  » » 4 months ago, # ^ |   0 i don't understand that ceil((n-1)/2). i can't understand that thing. can you please elaborate it?
•  » » 4 months ago, # ^ |   -6 from where do you find these symbols on keyboard..... umm... cant see them anywhere
•  » » » 4 months ago, # ^ |   +1 Check under your keyboard xD
 » 4 months ago, # | ← Rev. 3 →   -30 65401775 Accepted..
 » 4 months ago, # |   +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)
•  » » 4 months ago, # ^ | ← 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.
•  » » » 4 months ago, # ^ |   +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.
•  » » » » 4 months ago, # ^ |   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.
•  » » » » » 4 months ago, # ^ |   +1 Oof thanks for reminding me the importance of test validators.
 » 4 months ago, # |   -9 Definitely, a good challenge for everyone here on codeforces, to solve this problem with the original constraints.
 » 4 months ago, # |   -8 Imagine someone hacking all the submissions with this test case
•  » » 4 months ago, # ^ |   +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
 » 4 months ago, # |   0 Yes, I considered the case above, and is there any wrong with my code?https://codeforces.com/contest/1255/submission/65375823 thanks.
 » 4 months ago, # | ← 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!
•  » » 4 months ago, # ^ |   +13 Did you even read the blog?
•  » » » 4 months ago, # ^ | ← Rev. 3 →   -55 Actually, I didn't! I jumped directly to writing the comment. Thanks for letting me know! :)
•  » » » » 4 months ago, # ^ |   +5 Mike says your solution first in the blog And rest of blog means that is wrong solution