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?
After seeing this, now the change in constraints make sense
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?
If it affected you heavily, you can ask to be unrated for you. There is a link where the contest was published.
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? :(
how 1500 people solved this before changes?)
The pre-tests were also incorrect. (Or at least didn't test the edge cases)
i recieved wrong answer at test 2, but did all as written above. moreover, now it's full solving)
I am assuming you are talking about this submission. This submission is incorrect because your calculation of
min2is incorrect. Consider the following test case:Here, you will find the two smallest elements to be
1and1, so you saymin1is0(correct) and thatmin2is1+min1 = 1. However, as you can see,min2should actually be2, so your output is wrong.Your Output:
Correct Output:
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.
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.
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
EDIT: Nevermind the algorithm below, I just found out it's incorrect as well — take a look at the other comments :)
The 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-mtimes, 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:vof the second cheapest vertexc_2, make sure the cheapest vertexc_1isn't already connected to that neighbor (there's always at least one neighbor for which this is true except for the special casen=3), and replace the edge(c_2, v)with(c_1, v)n-mtimesWell 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
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.
Thanks a lot, I didn't notice that it would give the same answer
Link for convenience: 1255B - Fridge Lockers
I think you are angel in codeforces
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$$$.
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 (
findTheoreticalMincalculates the lower bound,findEdgesactually 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.
[Deleted]
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$$$).
Feel free to correct me for any mistakes.
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$$$.
i don't understand that ceil((n-1)/2). i can't understand that thing. can you please elaborate it?
from where do you find these symbols on keyboard..... umm... cant see them anywhere
Check under your keyboard xD
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)
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.
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.
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.
Oof thanks for reminding me the importance of test validators.
D E L E T E D
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
Yes, I considered the case above, and is there any wrong with my code?https://mirror.codeforces.com/contest/1255/submission/65375823 thanks.
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!
Did you even read the blog?
Actually, I didn't! I jumped directly to writing the comment. Thanks for letting me know! :)
Mike says your solution first in the blog And rest of blog means that is wrong solution
Я потратил час времени на то, чтобы решать эту версию задачи, в то время как мог бы сдать C, D — они явно были проще и для меня раунд все равно остался рейтинговым, все ли апелляционные формы читались внимательно?