### vovuh's blog

By vovuh, history, 9 months ago, translation,

Pay attention to the unusual round start time.

UPD: We cannot determine difficulty of some problems thus we recommend you to read all problems and think about each of them.

<almost-copy-pasted-part>

Hello! Codeforces Round #611 (Div. 3) will start at Dec/28/2019 20:05 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria ZeroAmbition Stepanova, Mikhail pikmike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</almost-copy-pasted-part>

UPD2: Editorial is available!

• +152

 » 9 months ago, # |   +119 ![ ]()
 » 9 months ago, # | ← Rev. 5 →   0 Three back to back contests today — AGC 041, Codechef December Lunchtime, CF Round 611. GLHF!
•  » » 9 months ago, # ^ |   -7 I wanted to upvote but accidentally downvoted. Sorry about that.
•  » » » 9 months ago, # ^ |   0 The damage has been done...
 » 9 months ago, # |   0 When I registered for this round my rating was less than 1600. But will this round be rated for me if my rating become 1600+ before starting the round (after updating rating based on Educational round 79)?
•  » » 9 months ago, # ^ |   -11 Haha but you're an LGM... XD
•  » » 9 months ago, # ^ |   +1 no(
•  » » 9 months ago, # ^ |   0 Doubt that the scores will be updated before the next match.
•  » » 9 months ago, # ^ |   0 No. It won't be rated for you.
 » 9 months ago, # |   0 ??????THE BEST HAKER?????
 » 9 months ago, # |   0 Funny magic！
 » 9 months ago, # |   -34 Huh, really friendly time for us:For Chinese users.
•  » » 9 months ago, # ^ |   -8 What the actual fuck?
 » 9 months ago, # |   0 Before yesterday's contest, I had a rate of 1599 and it was planned to have 0 rate change so that I could participate in today's div3 contest, and yes I am 1599 again :DMy plane now is to get +100 rate change, Can I achieve my goal again? :3 I hope sooooo
 » 9 months ago, # |   +1 vovuh always have good contests so I hope it will be one of them. good luck everyone :D
 » 9 months ago, # |   0 Why codeforces contests are not always scheduled at this period of time?
 » 9 months ago, # |   +19 ![ ]()
 » 9 months ago, # |   +3 Some experts are listed as official participant. Please fix it.
•  » » 9 months ago, # ^ | ← Rev. 3 →   +2 Checkout the magic option at your profile page. You can change your color from there (I am not an LGM :3). This feature gets activated around each new year. Maybe they are not experts, they just changed their color :3
•  » » » 9 months ago, # ^ |   +2 I do know about that. That is not the case.
 » 9 months ago, # |   +1 What does the post mean by "Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes." Does this mean 10 minutes is taken off your clock for a wrong submission?
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 yes (A wrong submission adds to your time penalty).
•  » » » 9 months ago, # ^ |   +9 I took part in a competition yesterday that also had this penalty and nothing happened to my time when I submitted a wrong solution, what was happening there?
•  » » » » 9 months ago, # ^ |   +1 I checked your results in the last contest, your total time without counting the penalty for wrong submissions is 39 + 15 = 54. You had 3 wrong submissions -> 3 x 10 = 30. Therefore your total time penalty is 54 + 30 = 84 (This number is shown under penalty in the standings).
•  » » » » » 9 months ago, # ^ |   +8 Oh i thought it meant you would have 10 less minutes to do the problems.
•  » » 9 months ago, # ^ | ← Rev. 3 →   +8 No! This mean that your penalty is increasing by 10.
 » 9 months ago, # |   +3 0h5 — 2h5 AM I'm here :(( but i will try participate.
 » 9 months ago, # |   +12 UPD: We cannot determine difficulty of some problems thus we recommend you to read all problems and think about each of them.Hmm, something's fishy.
•  » » 9 months ago, # ^ |   0 the first question may be the toughest lol
•  » » 9 months ago, # ^ |   +2 At last the fishy thing was Task-C. Weak pretests and some solutions don't make sense
•  » » » 9 months ago, # ^ |   0 Near one third of the solutions for c were hacked (including mine:( )
 » 9 months ago, # |   0 Today's leaderboard will be colorful :)
•  » » 9 months ago, # ^ |   -6 You're definitely misleading people with that photo...
 » 9 months ago, # |   0 Hope this contest will be rated for us disguising as grandmasters lol
 » 9 months ago, # | ← Rev. 2 →   -15 s
 » 9 months ago, # |   -28 The announcement for E was very late Costed me 2 wrong submissions Pls look into it
•  » » 9 months ago, # ^ |   0 "For example, let the initial positions be x=[1,2,4,4]. The final ones then can be [1,3,3,4], [0,2,3,3], [2,2,5,5], [2,1,3,5] and so on. The number of occupied houses is the number of distinct positions among the final ones."You could infer it from the statement.
•  » » » 9 months ago, # ^ | ← Rev. 3 →   0 Still the statement was pretty unclear. Look at statement now, its perfect
 » 9 months ago, # |   +12 Nice F, thanks)
 » 9 months ago, # |   +1 numberline forces
 » 9 months ago, # |   0 I couldn't understand problem F completely. Can someone clarify it more ?
 » 9 months ago, # |   +6 Difficulty : A < B < C << D,E << F
•  » » 9 months ago, # ^ |   0 I think E was a lot easier than D in Implementation. Though getting the idea was the main thing.
 » 9 months ago, # |   +2 what is the 4th/7th/11th test case in problem E? or what can it be?
•  » » 9 months ago, # ^ |   0 Yes I was also geting WA on tc 4 with my without DP approach I dont know what is wrong
•  » » 9 months ago, # ^ |   +1 try these cases: 5 2 3 3 3 4 ans: 1 5 9 1 1 2 3 4 6 7 8 9 ans: 3 9
 » 9 months ago, # |   +1 Great Contest. Managed to solve 4 problems.
 » 9 months ago, # | ← Rev. 3 →   0 can someone help me figure out whats wrong with my solution 67835457 for C PROBLEM
 » 9 months ago, # | ← Rev. 2 →   0 How to solve D within the time limit?
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 Greedy problem using a priority queue (min heap) and a flag checker.you can keep minimum distances in the queueFor example, n = 2, m = 3, x1= 1, x2 = 5 Then initially, you need to push (0, 1) and (0, 5) // (dist, position) and set(1) = visited and set(5) = visitedIf -pq,top.first != 0, then add this position to your answer array. and check whether you can insert position+1 and position-1 with your checker. If position+1 is possible, then push(-(dist+1), position+1)until you gather m position
•  » » » 9 months ago, # ^ |   0 I did the same thing nearly but got wrong answer on test 3. Is it because of unordered map? It would be great if anyone can help me find my mistake!! my submission Thanks .
 » 9 months ago, # |   0 E was dp or greedy ?
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 dp i maintained 3 states, first calculate frequency array for input from 0 to n+1 and if it is greater than 4 make it 3 States are as follow: 1) idx : index of location or houses 2) x : number of friends previous location is asking to me 3) y : number of friends i will give to next location
•  » » 9 months ago, # ^ |   +7 Greedy af
 » 9 months ago, # |   0 Can we use bfs to solve problem D? i always get memory limit exceeded on test 12 :(
•  » » 9 months ago, # ^ |   +4 Yes. I managed to solve it using something like bfs. Submission : LINK
•  » » 9 months ago, # ^ |   +1 Yup, you can have a look at this — https://codeforces.com/contest/1283/submission/67841418
 » 9 months ago, # |   +5 1283E - Новогодние посиделки is similar to 1203E - Боксёры .-.
•  » » 9 months ago, # ^ |   0 I would say it is half-similar :) Btw I cannot understand how didn't I remembered this problem, lol.
•  » » 9 months ago, # ^ |   0 Except for the fact that we couldn't go from 1 to 0 in the old problem
 » 9 months ago, # |   +1 Thanks for the contest!
 » 9 months ago, # | ← Rev. 2 →   +3 I had an hour after solving C. I looked D and thought set+pq naive. But I thought it's not the model solution, and gave up. 10 minutes left, I started to code naive, and I've done it after contest. Submit it, AC.wtf
•  » » 9 months ago, # ^ |   +3 this happened with me in E , i solved very late and forgot to memoize the dp.Till then i memoize it time was over :(
 » 9 months ago, # |   +11 $F$ was cool. Here's a fun fact: You can prove that number of trees in $n$ vertices is $n^{n-2}$ if you have a working algorithm for $F$!Your algorithm is deterministic, so it generates exactly one output for each input. Also, as each output corresponds to a unique ordering of edge importance, each output will correspond to exactly one input. But number of different inputs with $n$ vertices $= n^{n-1}$ and number of different outputs $= nT(n)$ where $T(n)$ is number of undirected simple graphs in $n$ vertices which are trees. (We are multiplying by $n$ because same graph with different roots are considered distinct in the output.) Thus, as inputs and outputs have a bijection, $n^{n-1} = nT(n)$. Thus, $T(n) = n^{n-2}$!This is kinda similar to other proofs of Caylee's formula like Prufer Codes and proof of Caylee's formula by double counting.
 » 9 months ago, # |   0 Can someone help me figure out what is going wrong in my submission for Problem E 67835042. Thanks in advance.
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 Try this: 3 1 1 3 output should be 1 3
 » 9 months ago, # |   0 HOW TO SOLVE E? PLS EXPLAIN IN BRIEF!
•  » » 9 months ago, # ^ |   0 Max can be computed by sorting the array and greedily shifting elements as left as possible to maximise the houses occupied. My logic is going wrong on min (So I don't know)
•  » » » 9 months ago, # ^ |   0 There is also a possibility of you shifting to the right
 » 9 months ago, # |   +6 Why should C problem this submission 67826496 should be ac? Something wrong with the judge program?
•  » » 9 months ago, # ^ |   -20 Looks like a good round is going to be unrated :(
•  » » 9 months ago, # ^ |   0 WHAT????
•  » » 9 months ago, # ^ |   0 Hacked it, thanks
•  » » » 9 months ago, # ^ |   0 Pretest data should have hacked this submission, the question is about judge program.
•  » » » » 9 months ago, # ^ |   0 Yeah, I'm not 100% sure what the judge is doing. Here's the hack though https://codeforces.com/contest/1283/hacks/604551
•  » » » » » 9 months ago, # ^ |   +1 It is not visible
•  » » » 9 months ago, # ^ |   -7 How could one hack that if the judge was fucked up
•  » » » » 9 months ago, # ^ |   0 The judge at least compares constants, I think?https://codeforces.com/contest/1283/hacks/604551
 » 9 months ago, # |   0 What are the hacks for C ?
•  » » 9 months ago, # ^ |   0 5 5 0 4 0 0 is what I used
•  » » 9 months ago, # ^ |   0 3 0 0 1 and 3 3 0 0
 » 9 months ago, # |   +2 I really liked this Div $3$ contest because The difficulty balance was decent. It was not too difficult, yet not too easy. The problems were not very implementation based (like $598$ for example). After getting the basic idea, it was easy to implement it. There were no subtasks A great Div $3$ Contest to end the year !mango_lassi I generally refer your solutions. How to solve $F$ ?
 » 9 months ago, # |   +3 In C, can we also change the value which is not 0 ?
•  » » 9 months ago, # ^ |   0 I think no.
•  » » 9 months ago, # ^ |   0 I also have the same doubt, eg 5 4 0 0 1 2 ans- 5 1 2 3 4 is also getting accepted
•  » » 9 months ago, # ^ |   +2 it is clearly stated that you have to fill unknown values(zeroes)..
•  » » » 9 months ago, # ^ |   +1 then why the above soln. that I mentioned is getting accepted? And even I am not able to hack those solutions
•  » » » » 9 months ago, # ^ |   0 How did this hack work? I'm confused.. https://codeforces.com/contest/1283/hacks/604551
•  » » » » » 9 months ago, # ^ |   0 It seems that there's a problem in the checker see -> comment
 » 9 months ago, # | ← Rev. 2 →   +11 problem D I used unordered_map but I got TLE. I instead of map is AC??? why? I think umap is faster than map. please explain for me, thanks!
•  » » 9 months ago, # ^ |   +6 I had the same issue!https://codeforces.com/contest/1283/submission/67820013. Here you can see my first implementation using unordered_set. This submission received TLE on test case 6.https://codeforces.com/contest/1283/submission/67838787. AC submission. In this submission I only changed the unordered_set to set.Initially, I thought that this discrepancy was due to unordered_set having a very large constant factor, but the strange thing is that it seems that in general, unordered_set performs better than set for this implementation. For example, in test cases 3, 4, and 5 (which all have very big n), the unordered_set implementation has about 1.5 to 2.5 improvement over set in runtime. It seems that test case 6 is an outlier where unordered_set performs at least 5x slower than set.I didn't know that unordered_set could be exploited. Is there a different reason that this may be happening?
•  » » » 9 months ago, # ^ |   0 same thing happened with me https://codeforces.com/blog/entry/72541?#comment-568565
•  » » » 9 months ago, # ^ |   0 My guess is that set has a tree underneath while unordered_set has a hashtable. The latter has O(n) worst case performance for basic operations against guaranteed O(log n) of the set.
•  » » 9 months ago, # ^ |   +6 umap uses an inbuilt hash function to map the values and as you all know that hashes are collision prone hence that TLE you got.umap is O(1) as long as it doesn't face collisions but as collision increase its complexity turns O(n), it's basic knowledge.
•  » » » 9 months ago, # ^ |   +4 everything is basic for future LGMs
•  » » » » 9 months ago, # ^ |   0 Its sad to see that we lost a one and only n(b)oobita of ours :(
•  » » » 9 months ago, # ^ |   0 Thanks, I had never gotten into this kind of situation before, so I was thinking the inbuilt hash functions are really efficient XD , I will be avoiding unordered stuff from now onwards XD
•  » » » » 9 months ago, # ^ |   0 There is a chilli hash which i dont remember but is known to be quite efficient so its recommended to use chilli hash when using unordered map. IDK if any hacks of it have been found yet though
•  » » 9 months ago, # ^ |   0 Yeah, because unordered_map can have a lot of collisions because it's implemented as a hash table...
 » 9 months ago, # | ← Rev. 3 →   +99 For all who is surprised by why this was the accepted solution: I am surprised not less than you. Thank you badcw for noticing this.I will try to explain why this happened: when I wrote the checker I forgot to check the stupidest thing — check that all $nf_i = f_i$ for such $i$ that $f_i \ne 0$. I don't understand how could I forgot to do this, but this happened. As you can understand, nobody noticed the mistake and during the round nobody informed me about such weird thing. The comment above is the first source where I found this issue.I'm very sorry about my stupidity and I didn't want to ruin your fun from participating in this round. I apologize to everyone who was and will be affected by this mistake. I know that MikeMirzayanov who is the (usual) author of the whole problemset is upset by this fact and I understand that many of you are also upset by this fact. Now I cannot do anything with it and can only apologize.We will make a decision to make or not make this round unrated a little bit later and will inform you as soon as possible.P.S. I can't even imagine how many participants can be affected by this issue and I'm so scared to find out it :( Spoiler
•  » » 9 months ago, # ^ |   +20 Rated!
•  » » 9 months ago, # ^ |   +5 It appears the person who you linked got hacked. Did anyone else get affected by this error?If not, even if there was an error in the checker, nobody really got affected. I don't think the round should be unrated in this case.
•  » » » 9 months ago, # ^ | ← Rev. 2 →   +1 In fact, all my checker does is check if the printed array is a permutation without fixed points. So any solution that prints any permutation without fixed points can be accepted. And, as I can see, we already had 400+ hacked solutions and... further — more.
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   +2 Just out of curiosity, are most of the hacks occurring because of incorrect checker, or just because there was some case that people failed to check/some wrong idea that would have failed even with correct checker?
•  » » » » » 9 months ago, # ^ |   0 I cannot check all 550+ hacked solutions (wow, 150 hacks during several minutes) by hand but I think that there are not so many people who wrote absolutely incorrect solution on purpose. I think many hacks are because of some special cases, but because of incorrect checker it can happen that these cases appear in the test data but checker just didn't checked them.And the second issue I forgot about (but compared to the incorrect checker this is a small issue): almost all 15 tests I add are useful, but this is not enough to cut off all incorrect ideas and possible bugs. I forgot to add test cases to this problem. But because of the checker it does not matter now.
•  » » » » » » 9 months ago, # ^ | ← Rev. 2 →   +3 So the issue is that the incorrect checker just made pretests weaker? Because people who passed weak pretests still ended up getting hacked, so the checker didn't make incorrect solutions become correct.In that case, no round should be unrated because of weak pretests. If that was true, CodeCraft should be unrated every year.
•  » » » » » » » 9 months ago, # ^ |   0 Yes, the mistake of the checker was false negative (correct me if I'm wrong in the terminology) (accept some incorrect solutions, but not vice versa).But I don't sure we can say that this issue can be reduced to "bad pretests" because at least the solution I linked above cannot even pass the first example.
•  » » » » » » » » 9 months ago, # ^ |   0 So this is the reason of so many hacks going on, thanks for confirming that anyways
•  » » » » » » » » 9 months ago, # ^ |   0 Nope it's false positive. falsely label wrong solutions as right.
•  » » » » » » » » 9 months ago, # ^ |   +4 That's fair.I still don't believe it should be unrated, because at least people could check sample, but it would definitely make sense if it was. Thank you for confirming the issue.
•  » » » » » » 9 months ago, # ^ |   0 We cannot even see the test case on which our solution failed. I even don't know the corrected checker is working fine or not.
•  » » » » » » » 9 months ago, # ^ |   +3 Resubmit your hacked solution and you will definitely see the error in the output (and in that way you can make sure that the checker works fine now).
•  » » » » » » » » 9 months ago, # ^ |   0 I didn't wrote wrong solution on purpose for problem c ! but if known during the contest I would have changed code ! submitted my code again and it shows WA on test 17 ! It's unfair. Please keep the round unrated !
•  » » » » » » » » » 9 months ago, # ^ |   0 @_@ your solution is WA :)) this case, you distribute into slot but don't check index == value :)) not relative!
•  » » » » » » » » 9 months ago, # ^ | ← Rev. 2 →   0 nvm
•  » » » » » » » » » 9 months ago, # ^ |   +7 I think your solution will be rejudge :3
•  » » » » » » » 9 months ago, # ^ |   0 That is because you are not careful!
•  » » 9 months ago, # ^ |   +6 I think you should make it unrated for only affected people, so every one wil be satisfied :D
•  » » » 9 months ago, # ^ |   +4 The total amount of rating changes should be zero if I get it right, so everybody will be affected.
•  » » » » 9 months ago, # ^ |   +9 Rating is negative sum game, but your point still holds.
•  » » » » 9 months ago, # ^ |   +3 No it's not necessary.The same thing happened in codeforces round 601 and they made a form for the affected people.
•  » » » 9 months ago, # ^ |   +1 i solved abcde at the time of the contest but i've got c hacked. Despite that, i don't want that the round be unrated for me.
•  » » 9 months ago, # ^ |   0 Will hacked solutions be rejudged?
•  » » » 9 months ago, # ^ |   0 Read this comment. All solutions that which are hacked are already "rejudged" in some way (after the checker fix).
•  » » » » 9 months ago, # ^ |   +2 Sir, Please let the round remain rated as the ones who got C accepted by wrong means will be hacked by the end of hacking phase.
•  » » » » » 9 months ago, # ^ |   +1 yeah. I would love to end the year at blue rating
•  » » 9 months ago, # ^ |   +1 Rated!! It isn't the checker's fault if people randomly submit without testing sample cases.
•  » » 9 months ago, # ^ |   +23 Vovuh you are a lucky guy! The round is rated!Only 15 official participants have been affected noticeably by the issue in the problem C checker: I reviewed all the verdicts after the final testing and found such submissions that failed on the examples (but didn't fail on them while the contest). Only 9 of them have non-positive rating changes. So I excluded all of them from the official participants. They are: Miracles happen! Happy New Year!
•  » » » 9 months ago, # ^ |   +5 Thank you! You can imagine how glad I am when I got the top 750 for the first time and it's rated @@
•  » » » 9 months ago, # ^ |   -9 I got stuck in C for about an hour and you just saved me from getting -100!Thank you so much MikeMirzayanov and Happy New Year!
 » 9 months ago, # | ← Rev. 2 →   +6 My approach for problem C is to sort the array containing not_occupied position. Iterate from 1 to n and if at any i ar[i] is 0 and i!=maximum_not_occupied_position ar[i] = max_not_occupied_position else ar[i] = min_not_occupied_position. Still my soln gets hacked what is the counter case please tell
•  » » 9 months ago, # ^ |   0 Well I think there is some problem in judge that is leading to all those hacks
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 3 0 0 1
 » 9 months ago, # |   0 in problem 3. if we print n 1 2 3 4 . . . n-1; for all n. will it be correct solution ??
•  » » 9 months ago, # ^ |   +2 I think it's wrong to change a value that's not 0.
 » 9 months ago, # |   +4 Can we hack randomized solutions for C? https://codeforces.com/contest/1283/submission/67811299
•  » » 9 months ago, # ^ |   +16 The probability that a random permutation is a derangement is approximately $1/e$, and that is dense enough for randomised solutions to work.
 » 9 months ago, # |   +1 What is the correct way to solve C ?
•  » » 9 months ago, # ^ |   0 You can maintain two sets:The one which are bad positions set (i.e Index = unfilled element in array) and the other good positions set(i.e are missing from array but no problem as their value != unfilled_position in array)Now, you just need to handle the bad positions set first.I did it in the following way, there can be various other ways.for example, if my array was 3, 4, 6 of bad positions. I would circularly assign positions, example a[3] = 4, a[4] = 6, a[6] = 3;and for the remaining 0's positions, you can assign as you wish from good_position set.Here is my submission — https://codeforces.com/contest/1283/submission/67828215
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 I listed all the ones who did not give gift and all the ones who did not receive gift. sorted these 2 lists. compare a[i] and b[i] if equal: swap a[i] and a[i+1] 5 2 1 0 0 0 a=[3,4,5] b=[3,4,5] i=0 a becomes [4,3,5] i=1 a stays the same i=2 a becomes [5,3,4] 
•  » » » 9 months ago, # ^ |   0 When i==1, swap shouldn't happen as now a[i]!=b[i] ?
•  » » » » 9 months ago, # ^ |   0 oops i fixed it now.
•  » » 9 months ago, # ^ |   0 Let s be the set of people who didn't give their gifts yet. Let t be the set of people who didn't receive their gifts yet.For every person in s, assign to him any person (different from him) in t. Note that this is possible for all people in s except the last one (If we assign greedily). However, it's guaranteed that at most 1 person will be assigned to himself. Assume this person p exists. To fix this issue, choose any person (!= p) in s (This is guaranteed since it's given that the size of s is at least 2) and swap his answer with the answer of p. Done :)
 » 9 months ago, # | ← Rev. 2 →   0 Hello everyone... I need help >_<. Can anybody check what's wrong with my solution of problem C if you don't mind. (Although it's already hacked xD, but I don't know how to see the test case) https://codeforces.com/contest/1283/submission/67820446I'm trying to figure out the correct way to solve this. Thank you!
•  » » 9 months ago, # ^ |   0 Already found my mistake. :"D
•  » » » 9 months ago, # ^ |   0 Can you tell me on which testcase your code is going wrong as my solution for problem C is also been hacked but still I'm not getting my mistake. Thank You!
 » 9 months ago, # |   0
 » 9 months ago, # |   +5 Very nice contest with interesting problems. Thank you vovuh.
 » 9 months ago, # |   0 Can anyone here tell why using unordered_set is giving me TLE on D , where as using only set is passing the tests? the unordered set soln was working fine until test case 5, which is of same order as test case 6, but giving TLE in test case 6;
•  » » 9 months ago, # ^ |   0 issue resolved -> https://codeforces.com/blog/entry/72541?#comment-568531
 » 9 months ago, # |   0 same E from past div3 round https://codeforces.com/contest/1203/problem/E
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 old version cannot become equal to zero and no more than n. but this not, max result can greater than with n + 1
•  » » 9 months ago, # ^ |   0 https://codeforces.com/contest/1203/submission/67844337 this code solved both problems , just change variable prev initial value
•  » » » 9 months ago, # ^ | ← Rev. 3 →   0 case: n = 3 and a = [3 3 3]. result1: 1 2. result2: 1 3
•  » » » 9 months ago, # ^ |   0 https://codeforces.com/contest/1203/submission/67844337 https://codeforces.com/contest/1283/submission/67809780 different problems , same code
 » 9 months ago, # |   +1 The procedure in F defines a bijection between set of all trees with labeled $n$ vertices with one vertex picked and set of sequences of length $n - 1$ with entries from $[1, n]$, which proves, that there are $n^{n - 2}$ labeled trees with $n$ vertices. Really nice :).
 » 9 months ago, # |   +8 Press F for vovuh :(
 » 9 months ago, # |   0 For C task, were we aloud to change spots that weren't 0 or not? Cause the task says we need to fill in spots that have 0s in them, but during hacking phase I saw a solution that just printed sequence 2 3 4 5 ... n 1 (which was accepted).
•  » » 9 months ago, # ^ |   0 Stop crying for that now . Lets see what vovuh ans mike decide .
•  » » » 9 months ago, # ^ |   +1 It's Rated!
 » 9 months ago, # |   0 Can someone help me find the reason why my submission for problem D get TLE on 12, and it's memory is too large, it works pretty fast before test 12.Thanks in advance :)
 » 9 months ago, # |   +23
 » 9 months ago, # | ← Rev. 2 →   +50
 » 9 months ago, # |   +6 Problem D is a beautiful application of all-sources BFS.
 » 9 months ago, # |   +1 How to solve F?
 » 9 months ago, # |   0 Code Can Someone help I am getting WA on testcase-19 of Problem E
•  » » 9 months ago, # ^ |   0 2 1 3 I think your solution will fail on this
•  » » » 9 months ago, # ^ |   0 Yes I got it thanks
 » 9 months ago, # |   0 How to find the first answer in problem E?
 » 9 months ago, # |   +1 Can someone provide an explanation to the greedy solution for task E. I am able to calculate the max value ; however I am slightly missing something while calculating the min value Why Am I saying SLIGHTLY MISSING can be found looking at my answer and jury's answer to the failing test caseThis is a fully commented code and explains what I am trying to do.I think there is maybe some more ways to merge than I have taken into account. A deeper insight on the greedy approach to the problem would be appreciated. Thanks in advance.
•  » » 9 months ago, # ^ |   +1 4 1 2 4 5 
•  » » » 9 months ago, # ^ |   +1 well first of all thanks for the reply. But isn't it invalid input as numbers need to be less than or equal to n ( Mentioned in input format )!
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   +1 Yeah. I didn't notice it. But it doesn't matter. 10 1 2 4 5 10 10 10 10 10 10 
•  » » » » » 9 months ago, # ^ | ← Rev. 2 →   0 Oh thanks now I get it. Basically I am seeing 2 and 4 first ; dragging them to mid 3 ; and thus we will be left with 1 5 and lots of 10s.Then that 1 5 increases the answer. The first thing that is coming to my mind is switching the order in which I wrote down the conditions. I don't know whether that will work or not... but I am going to try that.Update : Oh ; that also fails. Now I need to do something clever I guess...
•  » » » » » 9 months ago, # ^ |   0 Could you give me some hints on : 1 : How could I correct that. 2 : How did you come up with that test case. I mean your thought process while test case design !
•  » » 9 months ago, # ^ |   +1 well i was stuck on max so i used your idea and got AC. here is what I did for min:sort array and remove duplicates in array last = -2 for( i=1;i1 : x[i] += 1 last = x[i] else: if x[i] - last ==1: x[i]-=1 last = x[i] then you count all unique numbers
•  » » 9 months ago, # ^ |   +16 Update : Done ! Code : https://codeforces.com/contest/1283/submission/67847724Special Thanks to stefdasca and I_love_chickpea for providing valuable inputs whether related to test cases or the code/approach itself !I think stefdasca's idea to find min is really really simple ; both to think and prove ; those benefitting from this discussion should really look into his code https://codeforces.com/contest/1283/submission/67847914
 » 9 months ago, # |   0 I see too many hacks for C...wonder why??
•  » » 9 months ago, # ^ |   0
 » 9 months ago, # | ← Rev. 2 →   0 CodeCould anyone tell me what problem is in my code? (min part)I merged 3 consecutive values to center one. (I marked flags)And then I merged 2 consecutive values to right one. (I marked flags to avoid a wrong move)Finally, I merged possible (exist none exist) cases to the center(none).Thank you for helping me!.
•  » » 9 months ago, # ^ |   0 Oh, I found the problem.
 » 9 months ago, # |   0 Here is my solution for problem C. It is been hacked but still I'm not getting any testcase where it is going wrong. Can anyone please look into my code and say where will it go wrong!67816712Thanking you in advance for your help
•  » » 9 months ago, # ^ |   +3 66 0 2 0 3 1i don't know what the problem is, but here is a wrong test case.
•  » » » 9 months ago, # ^ |   0 okay, got it. Thank You!
 » 9 months ago, # |   0 Since problem C has been rejudged , is there anyone who's solution got hacked but now it's accepted or it will be done at later stage?
 » 9 months ago, # |   +5 Is the round rated?
 » 9 months ago, # |   +1 Really weak pretests :(
 » 9 months ago, # |   +4 So what's the result after about 12 hours of discussions. Is it rated?
•  » » 9 months ago, # ^ |   +22 Yes, only 15 official participants have been affected noticeably by the issue in the problem C checker. The ratings will be updated in 10 minutes. I unrated all the participants from this list who has non-positive rating change.
•  » » » 9 months ago, # ^ |   +17 You seems to be a good guy
•  » » » » 9 months ago, # ^ |   +19 He is the best guy ever!
 » 9 months ago, # | ← Rev. 2 →   0 My first 1700+ !!
•  » » 9 months ago, # ^ |   +3 Hey, me too...
•  » » » 9 months ago, # ^ |   +1 happy & lucky 2019~~
 » 9 months ago, # |   0 I hacked 7 people in open hacking phase but still didn't get any positive response on my rating or my total score, isn't it weird ??[user:vovuh][user:MikeMirzayanov]
•  » » 9 months ago, # ^ |   +6 In educational round & div 3 ,there is no point for hacking.
 » 9 months ago, # | ← Rev. 2 →   -15 Hi,...I Participated in yesterdays's codeforces round 611 div3 ...My solutions got skipped....I got a notification saying my soln for C problem concided withh my friend's soln...The only reason this might have happened is that I and My friend use the same template for Cp ....please help me with my ratings.......I've really worked hard for them....thanks in advance vovuh
 » 9 months ago, # |   +3 Nice contest, especially F problem))))
•  » » 9 months ago, # ^ |   0 I understand that there are n lamps and n-1 wire And you need to chooce a root lamp and every lamp can connect max 2 other lamps.What is the required, can you clearfiy it a bit ?
 » 9 months ago, # |   0 For problem D, can somebody help me understand why am I getting TLE. I shall be very thankful. my code: https://codeforces.com/contest/1283/submission/67828742
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 bcoz there can be a case of xxxx..1e5 times ... xxx .. x = trees each time u r inserting at 1st and last , so worst case tc is mn.you need to erase trees from ur set that r useless.