Hello Codeforces!

I am glad to invite you to Codeforces Round #601, which will take place on 19.11.2019 17:35 (Московское время). The round will be rated for both divisions.

All problems in this round were created and prepared by a team of all-Vietnamese setters: MofK, I_love_tigersugar, UncleGrandpa, ngkan. This is the first Vietnamese Div1 round. We tried to make both the problems and the statements interesting and hope that you will enjoy them!

There is an interactive problem in the round. You can read the guide for interactive problem here.

We would like to give a lot of thanks to:

MikeMirzayanov for the amazing platforms Codeforces and Polygon.

arsijo for excellent coordination and many valuable advice for the round.

Our team of testers: MikeMirzayanov, KAN, tanphatls987, Kuroni, AomeII, ngfam, goodthingstaketime_._, dush1729, lannh2207, nhakhoa, Sumeet.Shirgure, BledDest, NatInTheHat, AlexPop28 for testing the round and give feedback about the problems.

We wish you an exciting round!

**UPD:** The message from MikeMirzayanov. If the issue heavily affected you and you want the round to be UNRATED for you, you can fill the appeal form by the link: https://codeforces.com/userForm/f0458e24fa295 Please do not fill it just in case. Be honest, fill in only if the problem broke your participation in the contest. Mike.

**UPD:** There will be **five** problems for Division 1 and **six** problems for Division 2. The score distribution is as follows:

Division 1: 750 — (500 + 750) — 1500 — 1750 — 2500

Division 2: 500 — 1000 — 1500 — 1750 — (1000 + 1250) — 2750

**UPD2:** : Thanks for participating! Congratulations to the winners!!!

Div. 1: Top 5 are also the only 5 contestant managed to **solve all problems**!

Honorable mention: taeyeon_ss for solving problem E in just **31mins**!

Div. 2:

MbahSA1937 (solved all problems!)

mintwhale (solved all problems!)

**UPD3:**Editorial is out!

from VNOI with love =))

me too :>> From VNOI with love <3

From VN with orz!

orz

orz

orz

3 was clearly enoughwe still need more orz smh

Is it supposed to last 2:15 opposed to the standard two-hour competition?

Interactive problems are always fun and challenging.

If it is not a binary-search problem :)

It indeed is not :) how do you feel about today's interactive problem?

Wish everyone the best of luck and get a good rating after the contest!!

.

Don't worry. Sometimes when we feel that we are not good, then we need to try a lot harder. For example, you should try to do harder problems such at Div 2 D E F, and aim that in a contest you need to finish A B C D E in 2 hours ( maybe F if you're able to ). Just don't giveup halfway through.

Wish so :)

Why will contest be held on Tuesday ? There is a Vietnam football match on this day.

From VN with love

Vietnam national team will play football at 20:00 :(( oh no

Trust me, by that time Vietnam would have the game in their bag anyway, so please join our contest! :)

Not yet calculated the case of rejected goals?

So many downvotes lol.

Just how butthurt people were seeing your comment, or those ignorant dudes not getting the context and still trying to be superior.

I feel you, I can't stop supporting my national team. So I will write the contest later. =)))

Good luck everyone, from Vietnam with love <3

There will be Hanoi Tower problems?

A character smarter than the cat in your profile picture doesn't exist.

But I always wondered, what if someone pass the

9999 ratingin the future?Actually the 9999 upper-bound is modifiable from the contest panel. Can change it to 1e9+7

.

forget 9,999.

It's not even possible to be rating.

That means one day tourist will be affraid of being banned from div1

Good luck everyone, from Peru with love <3

I should be aware of I_love_tigersugar's tricks

highly expecting Prof.PVH throwing some maniac traps into the statements like how he's done those National/Regional problemsHope to see both tourist and Benq participate in this round.

Have a nice round!

Hoping to see tourist become the highest rated coder on cf again

The only question about the contest

Will the

No. 1 spotin the rating change ?tourist or Benq or

Anyone elsebut tourist is not registered yet

but Benq can lose ratings

Agreed.

I love you

not registering does not means your rank can't increase or decrease.

Everything is relativeIt seems tourist made the smartest decision: to stay away from this contest. The easiest way to regain the top spot!

It may also be possible that tourist wants to give others a chance to be at the top position.

Like.... me?

And it comes true now

For some reason I am not able to register for the contest :/ There is no register link displayed anywhere.

Register now for extra rregistration

Why close the Registration when the competition begins? I forget to register before the competition.

I have no electricity right now and i have made submissions. Can you please make the round unrated for me because i am writing now from my phone with 4G. It is completly dark in my house and the only thing i can do is participate from my phone in a div1 contests which is absurd. Please understand my problem and help me.

I just submited from my phone and got accepted xdddd. Still can you please make it unrated for me. I dont know how to prove to you that i dont have any electricity now.

Image checks out

help in B DIV2

This round should be unrated. Sample and constraints should not be modified in-between contests. This creates an overall negative experience.

Sorry, we are all not perfect. This time I suggested such a change for the problem and it leads to a much more harder problem. This problem is really minor, all participants solved (thinking that they are solved) harder version actually solved the simplified version. I'll give a chance to exclude yourself from the rating if it really affects you. But 99% (or more) of users weren't really affected.

Actually, I saw what diligence and efforts were put by both the writers and the coordinator. They really tried to do their best. All the other problems are great.

Sorry again for the issue. I feel it mostly my mistake (I didn't ask writers to stress it with naive solution).

I hope you liked the problems!

No, I hate the problems

Thanks, Mike for proactively addressing the issue.

I was impacted as I was trying to solve a different problem all this time (as you can look from my submission history). I would want to be excluded from the rating.

Codeforces is the best platform out there and a minor glitch here and there does not change the fact regarding how much effort goes into every round all thanks to admins, setters, testers and co-ordinators in maintaining the continuous high quality of every contest. Thank you for herding all the cats to keep things in order.

If the issue heavily affected you, you can fill the appeal form by the link: https://codeforces.com/userForm/f0458e24fa295

Please do not fill it just in case. Be honest, fill in only if the problem broke your participation in the contest.

Thank you.

"Hardly" means "not much", heavily/strongly seems to be what you mean.

I think, a more appropriate word here would be "significantly".

There are a lot of near-synonymous options.

"Near" is the key. :)

Um, no? Any near-synonymous words work well enough if you're not dealing with formal writing and even more will convey the point, although awkwardly. The thing here is that "hardly" has the

oppositemeaning.programmers have their own English. It is as simple as possible

Sorry , but how can i get unrated if my electricity was cut out a minute 47 of the contest and then i submitted for fun from my phone problem A an it passed. I had no way of participating for more than half a contests , i know that i can't prove it but may be somehow you can check where from my last submission was made, please help.

Submit a notarized affidavit from the utility company.

Sorry but i didn't understand what you just said.

I am really disappointed of that. I solved the problem 2 min after the change. I lost a lot of time , 3 wrong submissions and maybe I could solve E1 Div2 I just needed more time to do that. I don't know what you gonna do but I really think I was affected to much by this. Thanks anyway the problems were amazing and I learnt new things.

I solved E1 .... I think this is a real affect now..

The only issue for each and everyone who actually solved B initially was that we spent close to 45 mins more or less which reduces to less than 5 mins of time spent after the constraints changed, time that one could have utilized to solve C which was not a mighty hard problem.

It's okay if you want to keep this rated but it makes user experience pretty weird.

Basically, if:

then appeal, otherwise, move along :)

What was the problem with $$$m>n$$$?

https://codeforces.com/blog/entry/71562

Tell before the contest that you are not perfect and no one will ever participate

;

lol you haven't even participated in a single contest, why are you whining?

MikeMirzayanov Sir can you please tell us what was the problem with the problem that it required modification of constraint .

Was it to make the problem easy or the tester code was designed for m <= n ?

MikeMirzayanov

May you explain what do you mean "by all participants solved (thinking that they are solved) harder version actually solved the simplified version"? Was the problem with the checker?

~~The solution is the same but only with adding edge between the 2 lightest fridges m-n times~~(which is a very easy addition that I doubt being the reason for the change in constraints).EDIT: Have just seen this Tricky Case in 1255B (Fridge Lockers) if m>n now.

make it unrated for Benq, he was strongly affected

Why my submissions are skipped? :/ It was hard to me to get that position :c

maybe u copy code from some one else

No, this is my only account and I would never do that. :/ If I had done that, I wasn't claiming now.

It is unfair: c

Anyone else thought in Div2D/Div1A that the

ricecells assigned to every chicken form a connected area? I was going nuts trying to solve that, would be a really nice problem though.Div1A reminds me of this CF995A — Tesla when people go derp mode real hard.

Contestants tried heuristic solutions, dijkstra, weird heaps, while you only need loops to solve it.

Crazy, but what a nice chicken story behind, isn't it?

Div2 D and E1 should not have been together because they don't require much concepts and their implementation took a lot of time.

How to solve div. 1 C Point ordering ?

Find the next point to first using second type of queries (n-2 queries used).

Now we have 2 adjacent points. Now find areas of all the others with these 2.(n-2 queries).

Now the take highest area point (lets say h). Now using 1,h,i we can decide side of i to h. And with information of area we can sort points in each side.

Div. 2 Was just a coding contest, sorry but not the best contest :)

How to solve Div1 C?

ex) (1,2,3) -> 1 save 2,3 and 2 save 1,3 and 3 save 1,2

i used set supervising the array

then, that number is what we start to solve the problem

also erase the already using number from the other set

the size of set of that number is three , then that is not proper number to keep going

sorry, i am not good at english.. so i can't write any more

Hmmm, looks like Div2 C

sorry

Username checks out.

First of all, lock the first and second point. We'll consider other points to be on either side based on those two points.

We can see that the query $$$(2, 1, i, j)$$$ can tell that in a permutation starting from $$$1$$$, which point will come first: if the response is $$$1$$$, $$$i$$$ comes before $$$j$$$, and the other way around if the response being $$$-1$$$.

Loop through point from $$$3$$$ to $$$n$$$ to find out if each of them comes before or after $$$2$$$ in the permutation, using the query $$$(2, 1, 2, k)$$$. Here we can see that the points have been separated into two halves.

For each half, we can see that, following the permutation's order (i.e. the points' counter-clockwise order), the area of the triangle with point $$$1$$$, point $$$2$$$ and point $$$k$$$ forms a bitonic sequence: the area increases until the maxima value, then it decreases. From this knowledge, we may do the following:

Total number of queries used will not surpass $$$3n-6$$$.

Amazing contest, thanks for it! All tasks were very interesting!

bullshit contest.

Why?

Sorry, in B I was missing n=2 case, it took me 1 hour to find it, so contest went bad for me..Contest was good.

Div2 C & D are just implementation problems.. got stuck with some sily bug in both..

the same for me , and problem B changed during the contest was very confusing to me, !Rated.

What changed in div2b during contest?

Example inputs.

what is pretest 5 in C it's so weird to me it's WA ...

isn't it we just see the first 3 numbers and then we can detect the next number

well i thought if div2b if m<n the ans=-1 otherwise just 12/23/34..n1 ans = 2*sum

what's the counter-case?

got it, stupid i am! and thank you

when n == 2 && m == 2, then answer is -1

why?

because in that case both the chains will be (1 <-> 2) and anyone (1 or 2) can unlock all the chains, so no fridge is private.

n = 2

How to solve div2B ?

I was thinking of connecting each of them to the 2 with the smallest values

case where you have 3 fridges and 2 chains, your code will fail. answer should be -1.

What was your solution?

Solution:

SpoilerIts possible only when n<=m. Create a cycle connecting all fridges (1-2-3-4..-n-1), now connect the remaining chains to 2 fridges with least values.

That's incorrect, consider N = 5 nodes with weights 0 1 2 3 4, and M = 6

After building the cycle with 5 edges, you can remove the edge between 2 and 3 to create two edges between (0 and 2) and (0 and 3), which costs the same and uses all edges instead of creating a new one that costs 1 more.

So to replace a chain between any 2 fridges with 2 chains coming from the smallest-weighted will cost 2*(smallest-weighted). And add a chain between 2 fridges with least values will cost (smallest-weighted + second-smallest-weighted).

If the first one is smaller then you can just replace any pair of fridges k time. If not, you can add k number of chain between 2 fidges with least values.

You certainly can't "just replace any pair of fridges k times" since in the example above you can't replace the edges 0 and 1, 1 and 2, 3 and 4 or 4 and 0

Solution BSo you notice that you need to connect each fridge to minimum of 2 other fridges for it to be secure. If only 1 man knows answer or no answer is needed, it is not secure. So each fridge contributes to sum with 2*its_weight + weights for connected fridges to him. Well we can get greedy and try to achieve getting 2*weight for each fridge contribute to the answer. We cannot get less, and this we can get by forming a cycle. n = 2 is edge case because that cycle we do not like. If we need any more chains, just take the cheapest one k times to fill the gap. And if we took more than we could take, then answer is no

problem B is bad..

Felt like C in difficulty to me, both implementation and solution

I felt c was horrible in implementation, what did you do for c?

Not too horrible if you store everything in sets, cause you just need to know if it contains stuff or not, something like 3 loops it makes

wa9 on E1 and pretests passed on E2. cmooon. Does it means that solution differ or threre are just different tests?

I was getting wrong in e1 easy. My strategy was to accumualate lowest prime factors of total 1 at one place(middle of that prime factors) . can any tell me what i m doing wrong?

first i did the same, wa at 8. check all factors(no need prime) and pp

thanks

why should we check all factors? I had solution on contest that passed E2 pretests and failed on E1. It is probably a bug, but i can't find it. Idea is to find all prime factors and enumerate over it. For each prime factor find an answer, grouping by this number to it's meridian. I checked test i failed on, but it is too big. (submission 65381763)

In array 1 1 1 0 0 1 1 1 The best solution would be 4 (divisible by 3)

thanks for reply and test case.

you can collect 3 on 2-nd and 7-th place. What is wrong with idea of accumulating prime factors?

Why were constraints for B changed??

When you realize that its not the boxes to be shuffled but the units in them in E1.......

When you realize you passed pretests with a blatantly incorrect solution ...

Which question are you talking about sir?

The same problem you are :P

Aah, actually I could say that for my solution as well :(

After one hour of round I see message with words "sorry, we gave you wrong task". What is it?

What was the required time complexity for DIV2 c ?

If a number X appears just 1 time in all triplets, it must be the first/last one in the original permutation. Save number->triplet mapping and start finding with X. It's an O(n) solution.

Those pretesting times on div1 D...

I guess that the std of D is O(n^1.5) . (because of so large time limit)

I'm pretty sure O(n^1.5) wouldn't need a large time limit, especially not for such low constraints. I've got $$$O(Q \sqrt{N \log N})$$$ where the log factor comes only from binary search. It still got TLE, but on pretests 29 and then 34, so it must be pretty close to passing.

It can be done in $$$O(Q \sqrt{N})$$$ online

Could you please tell how to solve it in $$$O(Q\sqrt N)$$$?

I've seen your submission which perform (# different subtree size of $$$v$$$) for each update on $$$v$$$.

The tightest bound I know is $$$O(Q\sqrt N log N)$$$ for (# different subtree size of $$$v$$$) can't be too much.

I believe it has tighter bound but can't come up of a proof. (Ignore this line, found myself stupid :( )

You can eliminate the log factor as described in my other comment

I think D's O(nlogn) solution is very interesting, but unfortunately std is O(n^1.5)

"std" is the namespace, do you mean the intended solution and that there's a log solution?

Okay, so the time limit is just intentionally loose and a lot of slow solutions had a chance thanks to that. I'll try squeezing through with my own.

what is the $$$n \log n$$$ solution?

Root the tree at node 1. Suppose we iterate through all the neighbors of node $$$v$$$ for some type 1 query; we can update a child's subtree or the parent's subtree in $$$O(log(n))$$$ with a segment tree. Since the number of neighbors can be $$$O(n)$$$, this solution is $$$O(qnlogn)$$$. So we can't really traverse every child of an update node. Instead, for an update, we will update the biggest child's subtree and the parent's subtree "normally". We won't update the other children but we will keep a running sum of type 1 updates for each node $$$u$$$, which can be used later. The answer for a node will be the value of that node in the segment tree + some of it's ancestor's updates which we didn't apply. We can traverse through each such ancestor and sum up the answer. The number of such ancestors will be $$$O(log(n))$$$. So, our total complexity is $$$O(QlogN)$$$.

The number of such ancestors will be $$$O(log(n))$$$Can you explain this?

If the biggest subtree of node u is that of child v, then we call edge (u, v) heavy. Others are light edges. Starting from a node, if we go up to the root, there will be at most $$$O(log(n))$$$ light edges. Proof

I was not familiar with this technique. Thank you!

That's cool. Thank you!

I am the author of this problem. My solution runs in $$$O(QT\log{N} + QN/T)$$$ with some predefined constant $$$T$$$. I divide all queries into blocks of $$$T$$$. Choosing every $$$T$$$ between $$$175$$$ and $$$350$$$ should give you AC, unless your implementation has huge constant factor.

Might give you AC if you haven't put effort into keeping your constant factor explicitly low. That's how it always is with these problems, you need to check.

UPD: I just didn't have high enough $$$T$$$ to pass (I had 350), but more optimisations speed it up massively.

I had $$$T=\sqrt{N/\log N}\approx93$$$. Where did you get 175 and 350?

It turns out (a bit counterintuitively) that with such sqrt solutions, the branch "update values after processing a block" has a much worse constant than "answer query", probably because it's basically DFS and that's cache-inefficient and just more to calculate. You need less blocks than the theoretical value implies.

Maybe you should learn from the god of sqrt decomposition ODT

bad div2 B, the first time to get ranked 3k+...

Can you explain the problem statement

I can't even understand it

u need to take care of the case with n = 2(ans = -1), n=3, n=4, when n > 4 && m > n, the smallest ans will not be the circle cause the head and tail can connect to the smallest node, the left edge just link the smallest and second smallest node, just it...

if n = 2 or m < n, ans =-1, otherwise answer is circle and (m — n) edges between two smallest nodes. To lock fridge, you must connect it with two different fridges, so each node must have min 2 edges. So in cost weight of each fridge will be counted minimum 2 times, it just turns out when you connects all fridges in circle and in this case all fridges are private. It takes n edges and other (m-n) edges must have minumum weight, just connect two smallest fridges (m-n) times. Its not clear explanation, but i hope it helps to understand solution.

look this blog https://codeforces.com/blog/entry/71562 and you will notice that you were wrong.

WTF??? https://codeforces.com/gym/102396/problem/I == https://codeforces.com/contest/1255/problem/C

It was my problem in the round. I didn't know (also the coordinator and writers) about the previous problem. Yes, it is very similar. Sorry about it. My problem was invented completely independently by myself. You see, it is not the first, not the last case when problems coincide. Sometimes it happens, sorry. Moreover, it can happen even on more important official contests. It's a life. The only way to prevent prepare a similar problem, just do not invent any problems. But I don't think it is the right way.

Maybe I have a solution that differs from yours, but I can't get how one can solve this problem using the solution to the problem you mentioned.

Yeah it's subtly different. In the old problem, the permutation is treated as circular.

That is interesting

I'm not saying it's the same code, but it's interesting submit during the contest somewhere else

What is testcase 2 for div2 C ?

Took a long time to implement B & C. Problem D, a zig-zag scan will do but i don't have time to finish it correctly. sad.

deleted

I thought of a solution for Div2. B as it was originally.Any review would be appreciated : I thought of first making 1 cycle of size N(in case when m>=n) and from set of total edges sorted by weight, to remove edges till my graph contains M edges.Is it a correct solution?Please confirm.

but it allow multiedge between two nodes

Yes, thank you!I was missing that

if all fridges have same value except 2 that have a larger value than the others, you might break the cycle of n. (if m=n+1, the last edge you remove is the one between the 2 larger valued fridges).

In fact, I solved D2/B and still do not get was was wrong with it, why the change?

If you have n = 5 and m = 6, with 0 1 2 3 4, you will get cost 21 with your strategy (assuming that your strategy is the one everyone used — build a cycle of size N and add the edge between the 2 minimums how many times it is needed), while the correct answer is 20 with: 0-1 1-2 2-0 0-3 0-4 3-4.

You can add same edge several times so just add the one with minimum weight instead of removing things which might result in incorrect solution

Oh sorry, my bad..

Didn't like the problems of this contest, got stuck in Div2/C with some more or less stupid implementation problems. Now, afterwards, having read D and E it would have been better to not work on C.

Afterwards we allways know better.

I was not able to register within like first 10 minutes of contest. That sucks.

Not Satisfied with Today's Contest

1 10 10000 1 1 1000 1000 1000 1000 1000 1000 1000 1000

Here is the test case that made me thinking for over an hour in B and finally your announcement came.

Contest should be unrated for everyone

how did you solve for m > n, same was troubling me for more that hour, when new constraint was announced, I got the idea in 2 minutes but due to some silly mistake and debugging, took some time to get B accepted.

Mathematically if m = 2 * n — 3 Then we can perfectly select two smallest cost fridges and connect all with them.

MikeMirzayanov I guess if you go for previous constraints where m<=2000 80% of people who solved it till that would get WA so I am still wondering why this contest can't be unrated.

Still wondering why people who couldn't able to figure out for 1 10 10000 1 1 1000 1000 1000 1000 1000 1000 1000 1000 and go for making a cycle just for n==m should get benefit over people who wasted time.

I was thinking of selecting two smallest cost fridges and adding all else to them but what if m > n && m < 2 * n — 3 ?

Here you can think of select any smaller x<n where this condition could be satisfied and you have remaining m i.e. m-=(2*x)-3 which are enough to join remaining n-=x fridges with at most 2 other fridges. That's where I wasted so much time

Make a cycle of length n, you're left with m — n edges, use them all to connect two smallest fridges. Works for all m and n

except when m < n or n = 2

you could make multi-edges though

I do but with the new constraints for this test case

1 10 10000 1 1 1000 1000 1000 1000 1000 1000 1000 1000

total cost is 36k approx

but in old constraints, it should be 16k approx.. that's what I'm saying..

it doesn't affect jury's solution right?

and your test case not satisfying 1 <= m <= 2000 in the old constraint and 1 <= m <= n in the new constraint

How about 1 10 1000 1 1 1000 1000 1000 1000 1000 1000 1000 1000

it's 17984

And what if we connect 1 and 2 node to all and then just 1 and 2 m — n + 1 times?

This is invalid. All nodes $$$i$$$ ($$$i>2$$$) will not be private (node $$$1$$$ or $$$2$$$ can unlock them working alone).

They can't for opening any i both 1 and 2 would be required.

$$$1$$$ and $$$2$$$ will be required if only every $$$i$$$ ($$$i>2$$$) was connected to both $$$1$$$ and $$$2$$$. And it will give no lower cost (than in the cycle construction method) as weight of every $$$i$$$ ($$$i>2$$$) is still added $$$2$$$ times to the total cost.

EDIT: I have just seen this Tricky Case in 1255B (Fridge Lockers) if m>n now. Got the issue.

aight from mohamedeltair's link I can see the problem now, thanks for discussing :)

Am I the only one who solved div2 D within 50min but could not solve C:(

BTW, how to solve div2 C?

Solution CFor each number, count number of times you have seen it in any triplet. Notice that you see first one only in one triplet and last one only in one triplet. Pick any of them, the second value will be the one you see twice in any triplet and the third one will be the one left. Now, iterate over array to find next value. To find next value, find a triplet containing last 2 values and another unseen value. This unseen value is our next candidate. Finding id's of triplets might be done in O(1) by storing them in an array. So the solution is O(N)

How are we going to sort the triplet's array?

Don't sort it, just know for each number the three triplets that contains it. Map, vector, anything

I wasted 20 minutes because I missed the $$$p_1 = 1$$$ condition in C (interactive problem). Not reading statements carefully hurts :(

I would highlight it or write something like "all these conditions mean that the output is unique", that would help.

Also, I didn't like the round. Problems A-D didn't require much thinking. Just my opinion.

Daaaaaamn I didn't even see that, luckily my solution does that by default

I also missed it, got WA on pretest 1, read the sample error message, fixed it and resubmitted.

wtf, that thing is always displayed?

For samples, yes — it sure is better than dealing with eternal "I got WA on the first sample but my solution works on it!". I didn't even rely on that, just automatically clicked on my submission and scrolled down.

It is helpful, obviously. I just didn't know it exists and it should be this way. Can I see that msg for all problems with a checker?

Yes you can. This is actually a very useful feature of Codeforces that not many people know. I only discovered this during an ICPC training with 10 WA on test 1.

This should definitely be considered as bug not a feature and be fixed asap.

+1, don't rules say that you only see WA/TLE/etc. verdict for the first failed test?

As I mentioned, it helps avoid questions about samples, so I'm not opposed to changing it and creating a Polish Brigade for answering questions during contests (for free, ofc). It would be like Microsoft Tech Support except with Poles instead of Indians!

What kind of a twisted reasoning is that? Maybe we should write some machine learning algorithm that tells you which line of your code contains bug in order to omit questions?

That would be interesting, you can even try to pitch it as a startup idea.

The same argument can be used for introducing rule "show what first failed test looks like". No other platform displays some detailed verdict for test 1, right?

The first failed test is always in the statements?

Only if you fail a sample test...

Topcoder displays checker verdict for test 1 as well :)

What exactly is wrong with that? The only problem I see is lack of awareness, and yes, it can be improved.

Well, that's why you can see it for sample tests. When you have undefined behaviour, you see a different output and a comment for that output. Otherwise, it doesn't give you extra info beyond which rule from the Output section you're failing.

It sounds like you're glad you spent so much time on it.

You are right that Topcoder does that too.

The lack of awareness is a big deal (knowing that you should click something and then you will get a hint). Two small issues are being different than other platforms and the fact that a participant can check this way if there is indeed a checker in the problem.

It's more convenient to see this thing, but I need to know about this feature in the first place. It's something easy to forget, I don't like it.

What the actual fuck?

So, what will happen to me because I had 3 WA submits for prob B and after rejudging, I got 3 AC submits in total, tbh I dont like this contest because of rejudging and in prob D, number of rows is r and c for columns and I followed it, then it took me a lot of time to debug because I used variable with same name (in other contest, they use m and n instead of r and c) and I cant like this kind of trick at all. If it had been m and n, I would have been able to solve this prob on time (with some luck). Anyway, I will try my best till I get to my goal. Have a nice day everybody!!

Tbh, you can make your life easier, instead of

just do

It isn't really a "trick", it's just your implementation skill.

Use meaningful variable names in your code, you will never be confused.

Or just H and W, as in height and width.

Can anybody tell me why I get a lots downvotes here? I dont think I had any very big mistakes in my comment. Quite annoying when seeing it without any acceptable reasons, hmm...

Your comment is quite boring. Yes, people make bugs. Complaining about the contest because $$$r$$$ and $$$c$$$ are bad variables seems stupid. And you could use some more sentences (dots at the end and then an uppercase).

But don't care too much about downvotes in CF, they are quite random.

Your comment helps me feel a little better. Thank you!

What's the correct solution for Div2B in case n < m < 2n — 4? Does greedy work?

Wasn't the solution of both the cases (m>n and m<=n) of DIV2 B was to create a cycle and thus the answer will be 2*(sum of weights of all fridges) and if m<n or n=2 answer will be -1 ?

Edit : I think in case of m>n we have (sum of least two weights ) * (m-n) + 2*(sum of weights of all fridges )

Create the cycle, so every fridge has two locks, then add chains between the two cheapest fridges until m is reached.

Edit: Turns out that this is wrong.

take $$$n = 4, m = 4, a = [0, 0, 1000, 1000]$$$. For "cycle" solution, the answer is $$$4000$$$, but you can get $$$2000$$$ if you connect $$$2-0$$$, $$$2-1$$$, $$$3-0$$$, $$$3-1$$$

2 — 0 costs 0 + 1000

2 — 1 costs 0 + 1000

3 — 0 costs 0 + 1000

3 — 1 costs 0 + 1000

total: 4000

I think answer will by cycle only since to avoid other person to open the fridge , each fridge should be connected to two other fridges and thus it's weight will be added twice in final answer.Hence answer will be 2*(sum of weights of all fridges) + (sum of least two weights) * (m-n) .

Is this correct ?

I believe so, because every fridge MUST contribute 2x their weight. So with leftover edges it must be optimal to connect the lightest fridges.

If you have n = 5 and m = 6, with 0 1 2 3 4, you will get cost 21 with your strategy, while the correct answer is 20 with: 0-1 1-2 2-0 0-3 0-4 3-4.

Is this a corner case (i.e when of the fridge has weight 0) or there is any other counterexample ? Oh Mike has written a blog on it ! https://codeforces.com/blog/entry/71562

Not a corner case. Just what happens when m > n. The problem basically asks for a graph of minimum cost having each node contained in at least one cycle. Doing a big cycle and adding edges on it is just a greedy solution which is not correct if m > n. However, it is correct for n == m because all nodes should have at least 2 edges so the minimum cost has a lower bound of sum(2 * w[node]). And this is also the answer of the greedy approach.

"If the issue heavily affected you and you want the round to be UNRATED for you, you can fill the appeal form by the link"

Looks like only positive deltas this round!

If people who did poorly withdraw, then this depends on whether the ratings for the rest of us will be calculated based on their absence or presence. If they are ignored when computing our ratings, then we can expect all our deltas to drop, due to our ranking relative to the size of the group diminishing. I hope this does not create a runaway effect, where contestants fear that their rating would drop due to people who did poorly withdrawing, thus withdrawing themselves and exaggerating this effect.

If my rating is still increasing after getting affected, will it be unrated for me?

Was the modification in Div2 problem B made to simplify it?

The edge count was limited to value of N.

Even though I might not gain much rating from this contest, It was indeed educational for me, to work on my weak points.Thank you to all the organizers.

Implementation problems occur now and then. It's a nice contest overall. Kudos to setters.

Too much implementation for a slow coder like me :( Really regret not being able to finish the div2D in time.

Thanks for the contest!

Deleted .... i am sorry

I didn't see the clarification of div2-B ,because I used "m2.codeforces.com" : (

Does anyone have the same situation as me? : (

Then I guess you have all the right to fill that form. If you want it to be unrated for you. :)

I think Div1-B2's Time Limit is a little severe and I got TLE on the system test...

How to avoid TLE?

My code is following:

https://codeforces.com/contest/1254/submission/65368643

(I've only used prime numbers as $$$k$$$)

I got TLE on pretest because of high constant also. Many of friends did the same

It affected me lots but I want this Round to be Rated for me ^^ From Vietnam with love <3

I could not really understand what is the issue with div2 B. what is wrong with the case if(m>n).

I don't think there is any problem. They just wanted the problem to get simpler I guess.

When will editorials be released?

Why my 1st AC submission skipped and counted as a wrong submission?? and minimized my score from 748 to 690?? Please check out this issue.(skipped : 65373327 AC : 65391169) Thanks

in normal codeforces rounds(except div3) last pretest passed sollution is judged in maintest. You will also get resubmission penalty. But today's div2 B has a special case. Contraint changed during contest. That may be considered if it is applicable for you.

Can someone please tell why this code of div2B is giving TLE? 65391058

You do a nested loop here

Since n is up to 1e5 this is to long.

Back to codeforces after my cultivation days, I became stronger, go to blue!

is round rated today?

I think that the testcases in D might be weak. My time is 420ms while I'm able to create test on which my program runs 3790ms.

A lot of solutions got TLE on either high-numbered pretests or systests, so they can't be that weak. It's more like your solution happens to not have a strong countertest among these tests. (You can uphack other solutions to find out if it's the case for them too.)

Probably not so many people did it like me and this is strange in my opinion as the solution is very simple.

If vertex $$$v$$$ has some subtree of size $$$x$$$, then ofc. we want to add $$$(n-x)\cdot d$$$ to all the vertices in the subtree. As there can be at most $$$\sqrt{n}$$$ different sizes of subtrees, we can do the query with $$$\sqrt{n}$$$ operations on BIT.

Is there anybody who also solved it this way?

Yeah, I solved it that way and used Segment Tree instead. Just hacked myself. 65387642

I too solved it this way and am getting TLE because of unnecessary %mod operations.

Each query can contribute atmax (1.5e5)*(1e7) to a vertex. (1.5e5)*(1.5e5)*(1e7) is less than 1e18 hence you can just get away with mod and before printing final result take mod and multiply it with inv(n).

Yeah, I know. Thats why I wrote unnecessary xD

I solved it like that but I used a cool trick to eliminate the log factor — sqrt decomposition! When there are many more writes than reads to a data structure like BIT, updates work in $$$O(1)$$$ and queries work in $$$O(\sqrt{n})$$$.

Interestingly enough, it is possible to make this solution faster by applying sqrt-decomposition ideas.

Fix some $$$k$$$ and do the segment tree operations only for vertices with at most $$$k$$$ different subtree sizes. For vertices with more than $$$k$$$ different subtree sizes (let's call them

special), simply precalculate how an update in them with $$$d = 1$$$ "influences" the answers for other vertices.I claim that for $$$k = n^{1/3}$$$ the number of special vertices is $$$O(n^{1/3})$$$. The proof is kind of long and technical, so I hid it under a spoiler:

ProofLet's call a vertex of the tree (not necessarily special)

aliveif there are special vertices in its subtree anddeadotherwise. For each special vertex $$$v$$$ let's say that there are $$$a_v$$$ alive and $$$d_v$$$ dead vertices among its children. Because $$$v$$$ is special, $$$a_v + d_v \geqslant k + 1$$$. Let's say that a special vertex $$$v$$$ is aforkvertex if $$$a_v \geqslant 2$$$ andnon-forkvertex otherwise. Let $$$S$$$ be the number of special vertices and $$$R$$$ be the number of non-fork special vertices. Then, the number of fork special vertices is $$$S - R$$$.Let's prove that $$$2R \geqslant S$$$. For special vertices $$$u$$$ and $$$v$$$ let's say that $$$u$$$ is a

direct descendantof $$$v$$$ if $$$u$$$ indeed is a descendant of $$$v$$$ and there are no other special vertices on the path between $$$u$$$ and $$$v$$$. The notion of "direct descendant" induces a rooted forest structure on special vertices. Moreover, all fork special vertices have at least two direct descendants — at least one in each subtree of an alive son. Moreover, direct descendants of different fork vertices are different, because, as mentioned above, "direct descendancies" form a rooted forest. Therefore, $$$S \geqslant 2(S - R)$$$, or, in other words, $$$2R \geqslant S$$$.Now, let's prove that $$$R = O(n/k^2)$$$. Then $$$S = O(R) = O(n/k^2)$$$ will follow. This is pretty easy, because all non-fork special vertices have at least $$$k + 1 - a_v \geqslant k$$$ dead children with different subtree sizes, therefore the total subtree size of dead children for one non-fork special vertex is at least $$$1 + 2 + \ldots + k = \frac{k(k+1)}{2} = \Omega(k^2)$$$. Moreover, by definition, all dead vertices have non-intersecting subtrees. Therefore, there are $$$O(n/k^2)$$$ non-fork special vertices. Hooray, the proof is over!

Now, we can handle the queries of the first type in $$$O(k \log n)$$$ for non-special vertices and $$$O(1)$$$ for special vertices: simply increase their value in some separate array. Similarly, the queries of the second type can be handled in $$$O(\log n + \texttt{#special vertices}$$$): the influences of all non-special vertices are taken from the segment tree and the for special vertices we add up their influences separately.

The total complexity is $$$O(q \cdot n^{1/3} \log n + n^{4/3})$$$. From theoretical standpoint, it is possible make the complexity slightly better by choosing $$$k = (n / \log n)^{1/3}$$$.

The code is here: 65440117. It runs unnaturaly quickly, probably for the same reason your code did on the contest: there are no tests in the current testset where it achieves its worst perfomance.

UPDThe previous implementation I linked (65398024) had a bug that made it produce incorrect answers on some tests (to be exact, I forgot that vertex influences itself, not only its subtrees). Thanks to alex9801 for the hack.UPD 2I rewrote the proof of the fact that there are $$$O(n/k^2)$$$ special vertices, because the argument I used before did not actually make much sense (you still can see the old argument on the lower edit levels of this comment, if you wish).Well I personally think for D, there are a bunch of different approaches, solutions and techniques that can be used to solve it. Even just sqrt decomposition, I have currently seen at least 6 or 7 different ways people did it. So I can tell that preparing test cases for this problem was indeed a pain, and the setters did a pretty good job on it (proved by the number of TLEs on System Tests).

I'm not saying that having an unique way (maybe got TLE on some unprepared test for large const) can give you a free AC on it. But passing all the test cases with a solution that none of the setters and testers were aware of really deserved an AC.

On the other hand, I really like your approach for it. Learning the fact that all the subtrees having the same size can be treated similarly really made my day.

How does number of TLEs prove anything? Most people had correct asymptotics and struggled with constant optimizations, so to me it seems that TL was pretty bad.

I solved it this way too and was wondering why would it run so fast :/

..and got immediately uphacked. I guess it's nearly impossible to make hard test against this solution unless authors were aware of it.

WEAK TESTCASE

I was looking at the solution of Div2 problem B of one of my friends. Although it gives the correct minimum total cost, it prints a wrong network of connection. Here is the code This code got AC but it fails to print out a correct output for the following input:

1

4 6

100 1 100 1

I think the test cases for this problem are very weak

yeah i think the same

In the problem they said m <= n then there is two cases when m < n or m == n

My bad. Didn't notice the change of constraints.

Div.1D is very usual I think, at least what about $$$N \cdot \sqrt{N}$$$ solution. Unfortunately, I did not manage to write it fast enough for having time to solve E, so don`t like the contest very much. Although, problem C was interesting for me.

:(

65393283 65387986

By the way,I think Div1-C is one of the best problem in geometry! It's my favorite!

Why my submissions are skipped? :/

How to solve Div1 — D. Tree Queries?

Have a buffer of $$$\sqrt{q}$$$ queries of type 1. When the buffer is full, flush the answer to permanent storage. For each query of type 2, the answer is the permanent storage for that node + the expected value each of the buffered query gives it. Implement an $$$O(1)$$$ LCA query and you have yourself an $$$O((q+n)\sqrt{q})$$$ solution.