By awoo, history, 3 years ago, translation,

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extented ACM ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov and me.

Good luck to all participants!

UPD: There certainly will be a discussion of the problems on the local Discord server shortly after the contest ends. I might join it as well)

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Anadi 7 266
2 HIR180 6 129
3 mrscherry 6 152
4 Vergara 6 158
5 Jeel_Vaishnav 6 185

Congratulations to the best hackers:

Rank Competitor Hack Count
1 teapotd 100:-4
3 MarcosK 32
4 tataky 28:-5
5 knotValid 23
721 successful hacks and 668 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A Dalgerok 0:01
B Nazikk 0:03
C neal 0:03
D tikz 0:14
F killer_god 0:34
G lxrvelory 1:03

UPD2: There was an error in problem D which caused some incorrect solutions to get accepted. We will investigate the number of users who were affected by this issue and decide whether the round is rated.

UPD3: We discussed the issue and came up with the following decision:

Those who got accepted earlier and get WA now won't be affected by rating changes. For everyone else (for those who got correct verdict) the contest will be rated.

UPD4: Editorial is out

• +107

 » 3 years ago, # |   +36 2 hours for 7 problems seem to be too less. Any chance extending the time to 2.30 hours? Specially for Educational Round, which should focus on having participants with low-mid ratings attempt more problems. C'mon beloved Codeforces! Give a thought.. :)
•  » » 3 years ago, # ^ |   -24 "Specially for Educational Round, which should focus on having participants with low-mid ratings attempt more problems".Not really that's what Div. 3 rounds are for.
•  » » » 3 years ago, # ^ |   +19 Div3 rounds (both frequency and problem difficulty level) are inconsistent, Edu Rounds are still the best way to get introduced with ideas that can be used in broader extent.
•  » » 3 years ago, # ^ |   +8 Most of the div2 people solve at most 5 of them anyway. Having 2h for 7 problems is good enough, since it gives a challenge for the better contestants too
•  » » » 3 years ago, # ^ |   +4 I'm saying just for education rounds though, the idea is to Educate, so why not give an extra half an hour?! That will surely benefit lots of programmers like me who are not yet to the level but trying to attempt and solve more problems than they usually do. There're lots of other div2 rounds where better contestants can be challenged by 2 hours time limit.
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   +145 Pretty sure the meaning of "Educational" rounds was lost a long time ago.Back when they started, educational rounds had classic problems which highlighted ideas and techniques that contestans should learn.Nowadays they are just normal contests with different rules ¯\_(ツ)_/¯
•  » » » » » 3 years ago, # ^ |   0 Maybe they ran out of ideas and techniques that new contestants should learn...
•  » » 3 years ago, # ^ |   0 that's a good idea but maybe 2 hours make us want to try faster .. for me at my best I would solve 3 problems in less than 2 hours so it won't make that difference but it could for others so I agree with you
 » 3 years ago, # |   0 Hoping to get some plus ratings in this round :p
•  » » 3 years ago, # ^ |   0 well... not anymore :/
 » 3 years ago, # |   +37 Lower, or lower and equal to 2100?
•  » » 3 years ago, # ^ |   +17 educational round == div2 round sponsored by harbour space
•  » » » 3 years ago, # ^ |   0 True
•  » » 3 years ago, # ^ |   0 If your rating is equal to 2100 then your rating will not change no matter what.
 » 3 years ago, # |   0 Hi, guys, is it rated for me too? I am participating after a long time and I have heard that some changes have been done in the divisions — div1,2 and 3. What are the rating ranges in these divisions and will my rating be affected if I participate in this contest? Thank you.
•  » » 3 years ago, # ^ |   0 You rating will change
•  » » » 3 years ago, # ^ |   +5 okay. Thanks
 » 3 years ago, # |   -12 An Educational round after several bad contests, time to get new high rating.
 » 3 years ago, # |   +24 69 ( ͡° ͜ʖ ͡°)
 » 3 years ago, # | ← Rev. 2 →   0 what is test 5 on E???????????????????Why can't we see the test cases?
•  » » 3 years ago, # ^ |   +15 wait are we allowed to discuss
 » 3 years ago, # |   +5 Why in E d can be>n?
•  » » 3 years ago, # ^ |   0 it doesn't matter. you can just take d=min(d,n).
 » 3 years ago, # |   +44 There was an error in problem D which caused some incorrect solutions to get accepted. We will investigate the number of users who were affected by this issue and decide whether the round is rated.I am really sorry :( Both bugs (in D and G) were mine.
•  » » 3 years ago, # ^ | ← Rev. 6 →   +23 <3
•  » » 3 years ago, # ^ | ← Rev. 2 →   +77 Why not consider it as a part of the hacking since Accepted here is not a final verdict because there is testing after hacking phase is finished
•  » » » 3 years ago, # ^ |   -12 Just imagine the number of people who attempted to other problems after submiting a wrong solution to problem D and its affection to the rankings...
•  » » » » 3 years ago, # ^ |   +58 The tests aren't exhaustive, and Accepted doesn't necessarily mean your solution is correct.
•  » » » 3 years ago, # ^ |   0 <3
•  » » 3 years ago, # ^ |   +51 Isn't that the whole point of having hacking-phase or system tests?
•  » » 3 years ago, # ^ |   -41 Should be unrated. Shit solutions passing 36 tests of D just not acceptable!
•  » » 3 years ago, # ^ |   +12 You are poset
•  » » 3 years ago, # ^ |   +7 Please don't unrated. Please. :(
•  » » 3 years ago, # ^ |   +8 Please turn on hacking phase to hack solutions with cout << 0 (to investigate the number of users who REALLY affected by this issue) and then run system tests.
•  » » 3 years ago, # ^ |   -15 Such a noob
•  » » 3 years ago, # ^ |   +3 Please don't be unrated
•  » » » 3 years ago, # ^ |   0 TOM TOM TOM
 » 3 years ago, # | ← Rev. 2 →   +26 i submit code for problem D with just cout << 0 << endl; and get AC but good vertices in my code ans simple test 1 are different why??
•  » » 3 years ago, # ^ |   +104
 » 3 years ago, # |   +59 NO!!! Plz be rated!!!! It's my first time to be MASTER!!! :(
•  » » 3 years ago, # ^ |   +33 I was gonna be an expert too:(
•  » » 3 years ago, # ^ | ← Rev. 2 →   +8 Poor you, bro. I hope this contest could be rated.How was your result today?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +10 After seeing that "cout << 0" passed all tests in D, it is really unnecessary to consider it should be rated or not:(
•  » » » » 3 years ago, # ^ |   +4 The system is judging at the moment. :)
•  » » 3 years ago, # ^ |   +8 I hope it's rated too.
•  » » » 3 years ago, # ^ |   +4 I agree
•  » » 3 years ago, # ^ |   0 The same thing man, I can be expert for the first time in my whole life after 2 years of work, if this round will be rated, please let it be so.
 » 3 years ago, # |   +23 Please don't unrate this contest.Could we rejudge problem D or some accepted incorrect solutions?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 I don't think so... I myself didn't solve D, but there might be some guys with little bugs, who would have solved this problem after getting WA.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +2 How does correct checker guarantee that you will get WA for the little bug? The little bug is the most common reason for hacking
•  » » » » 3 years ago, # ^ |   +2 It mustn't be that little you're thinking...Not everyone solve problem D in on try. But getting AC in pretest means don't working on it anymore.And the pretests was really weak, the guy posted above (alireza_kaviani) got AC with outputing only 0.
 » 3 years ago, # | ← Rev. 3 →   -7 Spoiler Alert:In D, is it true to:1- Find MST.2- If n  -  1  <  =  k then we have reached the answer, otherwise, erase edges starting from leaves until the number of remaining edges equals k.
•  » » 3 years ago, # ^ |   +21 I think it needs to be tree that grants minimum distances from the node 1 (like, dijkstra-tree)
•  » » » 3 years ago, # ^ |   +3 You're right. Dijkstra tree with the root at 1. Not MST.
•  » » » 3 years ago, # ^ |   -7 Thank you! I had forgot what MST represents, but have just remembered.
•  » » 3 years ago, # ^ |   +6 Shouldn't it be shortest path tree rather than MST?
•  » » 3 years ago, # ^ | ← Rev. 4 →   +3 Apply Dijkstra from source 1. Get tree with n-1 edges. Start removing leaves edges from that tree. Too bad I had a small bug in Dijkstra and could not submit on time.
•  » » » 3 years ago, # ^ |   0 @MatPhySC what if # of edges in optimal paths is greather than K, dijkstra tree should answer less edges than the solution
•  » » » » 3 years ago, # ^ |   0 If I understood your question correctly than if K >= N-1 then answer will be Dijkstra tree because all vertices are good
•  » » » » » 3 years ago, # ^ |   0 Sorry, poor english, but what i mean is that even when all vertices in Dijkstra tree are good, there could be another ones that belong to some other Dijkstra tree and they are also good edges
•  » » » » » 3 years ago, # ^ | ← Rev. 3 →   0 consider this case: 3 3 3 1 2 2 1 3 1 2 3 1if i understood your solution, it should give 2 1 2however, 3rd edge is also good, at least the way i get the problemUD: i got it now, it's good vertices, not good edges
•  » » » » » » 3 years ago, # ^ |   0 There are two Dijkstra tree. You can consider any of them.
•  » » 3 years ago, # ^ |   +7 Wrong solution:Consider the following case - 3 3 2 1 2 2 2 3 2 1 3 3Answer is — 2 1 3Answer from MST - 2 1 2Minimum distance from 1 to 3 is 3 units. MST gives 4 units distance from 1 to 3, so 3 is no more a good vertex.
•  » » 3 years ago, # ^ |   +3 This will fail. Consider this tree. 1 2 1 1 3 1 1 4 1 2 4 1 There are multiple MST. But taking any MST other then 1,2,3rd edges. Will give WA.MST does not guarantee that all edges are at the minimum distance from vertex 1.
•  » » 3 years ago, # ^ |   0 Thank you all!.Beautiful problem BTW :D
•  » » 3 years ago, # ^ |   0 I don't think MST works. I got AC on this problem with SPT(shortest path tree). and maximum number of good vertices is min(n-1, k).
 » 3 years ago, # |   +4 What is test 3 in D?
 » 3 years ago, # |   0 First time I wrote a buggy segment tree. :(
•  » » 3 years ago, # ^ |   +8 It means you get an Accepted for Problem E, don't you?Could I see your solution?
•  » » » 3 years ago, # ^ | ← Rev. 4 →   +1 Yep. It was accepted after the contest was over. In the last minute, I realized my mistake.My Soln.
•  » » » » 3 years ago, # ^ |   +3 Thanks, bro. Hope you high rating :)
 » 3 years ago, # | ← Rev. 2 →   +54 when I wondering how this guy passed D in 31 ms lol, lmaoI bet a lot of contestant will fail on D :|
•  » » 3 years ago, # ^ |   0 It seems like the checker was wrong, because the code is clearly wrong for even the sample cases.
•  » » 3 years ago, # ^ | ← Rev. 2 →   -9 This solution doesn't even take the input.
•  » » » 3 years ago, # ^ |   +7 It's not necessary to take the input. See this blog.
•  » » » » 3 years ago, # ^ |   +3 Thanks got it :)
•  » » » 3 years ago, # ^ |   0 It's not necessary to take input in any of the problems.
 » 3 years ago, # | ← Rev. 2 →   +4 I am sorry to be saying this but in my opinion it would be extremely unfair to declare this round as unrated because there would be many people who might not have done 'D' and have performed well in today's contest. If some incorrect solutions were accepted then it may as well be considered as a case of weak test cases. I urge you to consider the plight of many like me who believed they did well in today's contest and would be stranded disappointed if it is made unrated. PS Edit1: To all those who down voted this I am sorry to have hurt your feelings. I do respect your opinion and I totally accept that either of the scenarios I suggested would have been unfair. But the final decision taken by the contest makers is fair in everyone's eyes and no one loses out so I believe it is for the best.
•  » » 3 years ago, # ^ | ← Rev. 2 →   -7 feel about those coders who cannot improve his D solution to get actual AC solution. because of he/she already get AC.
•  » » » 3 years ago, # ^ |   +3 I can understand that but that's also the case in many contests when your pretests get passed and your main tests fail. I understand that either decision would be unfair to some but it comes down to which one is more on the fairer side. It comes down to 1 question vs 1 contest and I believe that making it unrated would be more unfair.
•  » » » » 3 years ago, # ^ |   +1 My solution on D is actually failing on pretest 2 but during contest it passed Now consider if the checker was correct i would have checked my code again and solved it after getting a WA.
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +16 Yes, I understand it wasn't fair to you. I sincerely apologise for ranting out.
•  » » 3 years ago, # ^ |   -6 To all those who down voted this I am sorry to have hurt your feelings. I do respect your opinion and I totally accept that either of the scenarios I suggested would have been unfair. But the final decision taken by the contest makers is fair in everyone's eyes and no one loses out so I believe it is for the best.
 » 3 years ago, # |   -22 make it unrated omfg !!
•  » » 3 years ago, # ^ |   +5 thats what you wont say when you did a heck good job today (or at least you think so). and the guys who got a crappy AC for that problem will get their ratings back to what they should have in the next contest or two ei?
•  » » » 3 years ago, # ^ |   0 Your English is not understandable You have anime profile picture have a nice day :) :P :>
•  » » » » 3 years ago, # ^ |   0 yeah i forgot most of the ,s and .s but yeah nice day too :D
•  » » 3 years ago, # ^ | ← Rev. 2 →   +3 you didn't submit any solution for D lol
 » 3 years ago, # |   0 When will we know if our submission for D is correct or not?
 » 3 years ago, # |   +3 Why can't simple dfs + 2 multiset pass problem E?
•  » » 3 years ago, # ^ |   +1 I passed with a simple DFS and a vector of maps.Perhaps you got some bugs? Personally I wasted 30 minutes for not realizing I overwrote queries instead of accumulating those lol.
•  » » » 3 years ago, # ^ |   0 You were right, I made insanely stupid bug. GG
•  » » 3 years ago, # ^ |   0 Mine passaed 45632893 (After the contest and the code is probably bad)
 » 3 years ago, # |   +12 rated plz!Just fix the problem(s) of specialjudge.And those best hackers will get everything done. ;)
 » 3 years ago, # | ← Rev. 4 →   +38 In system test, the code that pretest is passed can be wrong, naturally. I think there is no reason that this round will be unrated. Moreover, this round is educational round and hacking can't be attempted in the contest. So this round wasn't influenced by something wrong.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 If our solution failed on pretests we will have time to make that solution correct. But now we can't do anything. So if round gets rated it will be unfair for all participants whose solution failed on D because of bug in checker. So round should be unrated.
•  » » » 3 years ago, # ^ |   0 if your solution is this: then you obviously know your solution is wrong.and if its something different, how is it different then having very easy pretests if it passes sample correctly?
•  » » » » 3 years ago, # ^ |   +3 My solution is not even close to this. And we can't assume all 36/37 pretests are like samples (in running contest).
•  » » » 3 years ago, # ^ |   +1 Same would be the case when pretests are weak. but we don't make it unrated in that case.
•  » » » » 3 years ago, # ^ |   +3 36 weak pretests in D! We are not that unlucky
 » 3 years ago, # | ← Rev. 3 →   -9 Let's hit the unrated button.
 » 3 years ago, # |   +3 PikMike said this in Discord server...
•  » » 3 years ago, # ^ |   +6 damn that feels good..
 » 3 years ago, # |   +27 It seems that the special judge of problem D is incorrect. So I'm thinking about something like ummmmm.. unrated? In fact, I just wanna complain about the awful quality. Please check your contest more carefully.
 » 3 years ago, # | ← Rev. 2 →   -11 Let's make it unrated
 » 3 years ago, # |   +20 I feel that the contest should not be rated. Any opinions?
 » 3 years ago, # |   -41 please make it unrated
•  » » 3 years ago, # ^ |   0 It say people, who get WA1 on D.
 » 3 years ago, # |   +14 I'm wondering why my bruteforce solution on problem E could get Accepted... Can anyone explain why?
•  » » 3 years ago, # ^ |   +4 Don't worry fam, it's no longer accepted now :)The answer to "why" it was accepted before is because pretests are never perfect.
 » 3 years ago, # |   -18 Please keep it rated !!
 » 3 years ago, # |   -17 please rated
 » 3 years ago, # |   +38 So many people wanting the contest to be unrated are people who just did bad, not people who were affected by D.
•  » » 3 years ago, # ^ |   +1 I did bad and was also affected by D
 » 3 years ago, # |   -35 OK ,The contest must be UNRATED!! ;)
 » 3 years ago, # | ← Rev. 2 →   -24 I solved problems A, B, C, D and F. I was really happy with my results and now my D got wrong answer on test 1 (after the contest). I have A, B, C, F problems accepted, which worth less than A, B, C, D because solving A, B, C, D is faster than solving A, B, C, F. A similar problem was at round 485 (the queue froze during the contest): http://codeforces.com/contest/987 I lost 166 rating points there, I can't believe this is happening again. Instead of gaining points, I will lose :( Please make it unrated.
•  » » 3 years ago, # ^ |   +13 If you got wa on even sample who is to blame really?
•  » » » 3 years ago, # ^ |   0 I never check the 1st example, I don't get penalty if I get WA on test 1. And why would I check after it got AC?
 » 3 years ago, # |   -20 I messed up, got stock on C god please make this unrated
 » 3 years ago, # |   +3 Am feeling kinda stupid.... Anyways how to solve E ?
•  » » 3 years ago, # ^ |   0 Whenever you enter or exit any node, update BIT. I got that idea but implemented it with set instead of BIT during contest.
•  » » » 3 years ago, # ^ |   0 Thnx
•  » » 3 years ago, # ^ | ← Rev. 2 →   +11 You can do a simple DFS throughout the entire tree, starting at node 1 (i.e. root).Before starting, let's denote accumulated as an integer storing the sum of all added values for the current node. We'll get on with the way it worked below.When we start traversing from node z with depth depth, we'll do all these things: Taken all queries that have z as subtree root, and add the x values of all those queries into accumulated. Obviously, these queries don't apply for the entire subtree of z (only those with distance not larger than d). Therefore, we'll use a global array deactivated[] (more info in next steps). For each query with maximum depth allowed of d, add x into deactivated[depth+d+1]. Of course, since d ≤ 109, if depth+d+1 surpasses the maximum depth of the entire tree, ignore it. As a result, we'll have to subtract queries from ascendants' query that no longer affect the current node. To do this, we simply subtract deactivated[depth] from accumulated. Then, accumulated will be the answer for vertex z. Store it and start running DFS like usual. When done traversing, remember to undo all the above steps before leaving the function.My submission, for further clarity: 45624305
•  » » » 3 years ago, # ^ |   +2 Thnx. Got it. Simple!! My bad.
•  » » » 3 years ago, # ^ |   +5 Nice solution!
•  » » » » 3 years ago, # ^ |   0 Wait, another Kuroyukihime around here? <3
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +5 lotus is my wife!
 » 3 years ago, # |   +72 We discussed the issue and came up with the following decision:Those who got accepted earlier and get WA now won't be affected by rating changes. For everyone else (for those who got correct verdict) the contest will be rated.
•  » » 3 years ago, # ^ |   -7 very well
•  » » » 3 years ago, # ^ |   +31 Please make it rated for those who use cout << 0It is clear that someone might get lucky enough to try it and get ACBut it does not makes sense that many people were able to do it.It is clear that they clearly discussed the hack among themselves.
•  » » 3 years ago, # ^ |   -6 Can you explain what was the issue clearly? Incase if the WA was on hidden pretest then maybe next time make it unrated for everyone having WA after final system tests too in all rounds?
•  » » » 3 years ago, # ^ |   +16 For some solutions in problem D that should be rejected the checking program answered that they are accepted.
•  » » » » 3 years ago, # ^ |   0 How many such users are there? I still fail to understand if a solution gives correct answer on sample tests and gives WA on some hidden tests whats the problem... How is it different from having weak pretests..
•  » » » » » 3 years ago, # ^ |   +17 Because the checker gives AC even if the solution gives incorrect answer on samples.
•  » » » » » » 3 years ago, # ^ |   +16 2 categories: gets AC on samples previously, WA on samples now gets AC on samples previously, WA on hidden pretest now (eg: http://codeforces.com/contest/1076/submission/45623636) i think number 2 should be rated
•  » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 I think number 2 should be rated
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 The checker wasn't correct,It outputs ac if you just printed less than or equal to K distinct numbers from what i understand(even if you print 0).
•  » » 3 years ago, # ^ |   +90 What about the people who are getting +ve rating change even after being affected by WA in D? It doesn't make sense to make it unrated for them.
•  » » » 3 years ago, # ^ |   +20 Just unrated all, let this round be a practice round
•  » » » » 3 years ago, # ^ |   +3 Like traditional educational rounds
•  » » 3 years ago, # ^ |   +12 Make it like those who got accepted earlier and get WA now won't be affected by rating changes if their delta is negative. P.S. My delta shows positive by predictor
•  » » » 3 years ago, # ^ |   0 How about being unrated for negative deltas?? Seems cool!!But just a question, the unrated people will be considered out of contest(unofficial) or not??
•  » » » » 3 years ago, # ^ |   0 Similar thing happened in this contest
•  » » 3 years ago, # ^ |   0 Why “Those who got accepted earlier and get WA now won't be affected by rating changes” ? Why don’t we consider those are Accepted at the time it’s correct and ignore all submissons after that? This contest’s rule is ACM/ICPC, right? In ACM, it’s also rejudge as the way I mentioned. There is no ACM/ICPC contest skip a Accepted submission to judge final submisson in this case!
•  » » » 3 years ago, # ^ |   0 Sorry, I miss your mean.
•  » » 3 years ago, # ^ |   +1 Why different decisions for similar problem that happened in educational round 51?
•  » » » 3 years ago, # ^ |   +1 BledDest any comments?
•  » » » » 3 years ago, # ^ |   0 When there were only 10 contestants affected, it was easy to check them manually.When there are 500 of them, it is much harder since we can't automatically do it.
•  » » 3 years ago, # ^ |   +6 You should take the "unrated" users out of the rating pool entirely (i.e. make them unofficial). Rating deltas are comparative: if somebody gains rating, someone else is supposed to lose it. If you just make the users not affected by rating changes, you'll have some users who influence the ratings of others but don't get their ratings influenced themselves.I hope what I'm saying makes sense, I don't really know how to express my idea.
 » 3 years ago, # |   +29 D-Forces
 » 3 years ago, # |   +15 It's my first chance to become master, I'd like to see it rated, but if the wrong make the contest unfair seriously, it should be unrated.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 If you deserve it then you will get it
•  » » » 3 years ago, # ^ |   0 Actually I don't even it's rated, lol.
 » 3 years ago, # |   0 Hope to rank ,I want to see if I have made progress.
 » 3 years ago, # | ← Rev. 3 →   0 Can someone explain to me what I messed up? http://codeforces.com/contest/1076/submission/45631931It's just a dfs + 2 multisets. I must have looked over this more than 20 times. (I also put the updates to active/spent before and after the recursion, but that didn't do anything.)Thanks in advance.nvm solved, made stupid bug
 » 3 years ago, # |   0 Can someone explain me why this solution for problem A will fail ? http://codeforces.com/contest/1076/submission/45621631
•  » » 3 years ago, # ^ |   0 3 baz Your answer is ba when my answer is az.
•  » » » 3 years ago, # ^ |   0 Oh,shit thank you very much
•  » » 3 years ago, # ^ |   0 Deleting biggest one is not the solution check it 5 abcad
•  » » 3 years ago, # ^ |   +3 Consider this case: 3 bacYour code output "ba", while the correct answer is "ac".So, what you have to do is not removing the largest char in the string, instead you have to remove the first char s[i] such that s[i]>s[i+1], as this will result in smaller string.
 » 3 years ago, # |   0 Can someone explain me why I'm wrong? I made a submission to count number of good vertexes and with 50000 edges, one can't have more than 50001 good vertexes.45607996 // the original one, from the contest 45632353 // the modified one
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 The edges you give aren't necessarily connected. So you could have tree fragments everywhere. You have to do a dfs to get the edges and make sure they can actually reach the 1 node. (I might be wrong.)
•  » » » 3 years ago, # ^ |   0 I'm using Dijkstra starting from vertex 1, so the graph is connected for sure
 » 3 years ago, # |   0 I submitted problem D 3 times.In the second time, I get AC but the system said WA.When rejudge, My second submission is changed (it exactly the same solution of prolem A). I think this is a bug of Codeforecs. Could you consider my case?Submission number: 45627317Before rejudge, WA on test case 3. After rejudge, WA on test case 1, and the code is totally changed :( why ?
•  » » 3 years ago, # ^ |   0 Hi Mr.MikeMirzayanov,My submission 45627317 was changed after system rejudge. I sent a message to problem setter but he did not respond. Please check again I will support any thing.
•  » » 3 years ago, # ^ |   0 It maybe I submitte wrong file code. :’( Sorry
 » 3 years ago, # |   0 is your standing in the leaderboard affected by how many accomplished hacks do you have?
 » 3 years ago, # |   0 Please don't unrated, I probably become specialist after this round TAT.
•  » » 3 years ago, # ^ |   0 Don't worry, I think u can become specialist soon ~~~ fight!
 » 3 years ago, # | ← Rev. 4 →   0
•  » » 3 years ago, # ^ |   +19 Looked at your code — if you use the cin/cout speedup for C++, never mix them with printf/scanf — the streams are desynchronized so the output may not come out in the same order as you expect it to. That's what is happening here.
•  » » » 3 years ago, # ^ |   0 Thanks!! i got it.
•  » » 3 years ago, # ^ | ← Rev. 3 →   +12 You should look up what things do before you use them :)That #define timesave ios_base::sync_with_stdio(false); cin.tie(0);, isn't some magic fairy dust that you just sprinkle over your program to make it faster. It has some effects.To be more specific, ios_base::sync_with_stdio(false) means (as the name suggests) that you are disabling syncing between io with streams (the kind you do with cin and cout) and standard io (the kind you do with scanf, printf etc). You disable the sync, yet in your code you use both methods of io (you use cout for the "No" case and printf for other cases) and then expect them to be synced up.
 » 3 years ago, # | ← Rev. 2 →   +3 Why “Those who got accepted earlier and get WA now won't be affected by rating changes” ? Why don’t we consider those are Accepted at the time it’s correct and ignore all submissons after that? This contest’s rule is ACM/ICPC, right? In ACM, it’s also rejudge as the way I mentioned. There is no ACM/ICPC contest skip a Accepted submission to judge final submisson in this case!
•  » » 3 years ago, # ^ |   +3 The thing is that people could check their source once more if they knew that's wrong, but everyone usually stops at the AC verdict
•  » » 3 years ago, # ^ |   0 He meant, "those who got accepted due to the bug, and the same submissions got WA after rejudging".And for that, it's certain enough to say why it should be unrated (at least) for them.
•  » » » 3 years ago, # ^ |   0 Thanks, bro. I know his mean now.
•  » » » 3 years ago, # ^ |   +3 Isn't is unfair to those who are getting positive delta but it will be unrated for them.
•  » » » 3 years ago, # ^ |   0 Can you please proof the problem C ?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 It's a pure mathematical problem.According to the given formula, we can figure out , thus .You can draw the graph of the equation , and figure out a few things: If d = 0, obviously a = b = 0. If d < 4, no solution can be found. If d ≥ 4, the function d = f(a) is a monotone function. Thus, you can binary search the value a, and b can simply be obtained as d - a. Keep in mind that your precision has to be right to fit the output's relative/maximum error criteria.
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +5 For the last case (d ≥ 4) no need for binary search, instead, solve the equation which is actually a2 - d * a + d = 0. After that, b = d - a.Simple.
•  » » » » » » 3 years ago, # ^ |   0 I feel freaking odd to deny solving this simple quadratic equation and binary searching the answer during contest time :DWell, whatever that works :D
 » 3 years ago, # |   +14 if i did't got accepted, my rank will up. and now my rank won't up. sad :'(
 » 3 years ago, # |   0 And persons that haven't try the quest D? Is unrated or rated?
 » 3 years ago, # |   +5 Yo yo dudes, come on, the ones who got affected should have their rating increased if it shows +, and nothing if it shows -.
 » 3 years ago, # |   0
•  » » 3 years ago, # ^ |   0 Preview twice, post comment once.
 » 3 years ago, # |   +3 just another [partial unrated educational round rated for div 2]
 » 3 years ago, # |   +32 If I got D accepted with a wrong solution, but still managed to gain some rating after my D got WA, I do not see the point of why my rating should't increase.
 » 3 years ago, # |   0 How to solve C?
•  » » 3 years ago, # ^ |   0 x + y = d xy = d Math system
•  » » 3 years ago, # ^ |   0 binary search
 » 3 years ago, # |   +3 I spent a lot of time for D problem. And i have a nice score . Why my contest won't be rated. I don't do printf(0); I do bfs but my solution get wrong answer after rejudge. Please help me!!!.It is not fair.
•  » » 3 years ago, # ^ |   0 You are so right. Why do you ban from contest. Don't accept question but it should be rated for all.
 » 3 years ago, # |   0 Can anybody proof me B problem, pleace
•  » » 3 years ago, # ^ |   0 If n is even, then the smallest prime divisor is 2. After subtracting 2 from it, n is still even, so the smallest prime divisor will keep being 2. Therefore, the answer is how many times you can subtract 2 from n, which is n / 2.If n isn't even, find the smallest prime divisor d. You do one subtraction and get to n — d. Now, d is most certainly odd, therefore n — d is even, so the answer for n — d (as described above) is (n — d) / 2. Counting the subtraction of d from the start, the total answer is (n — d) / 2 + 1.
 » 3 years ago, # |   +38 "Those who got accepted earlier and get WA now won't be affected by rating changes. For everyone else (for those who got correct verdict) the contest will be rated."This is unfair for the users with positive rating changes even with WA on D. Please see if there is an alternate solution for this issue.
•  » » 3 years ago, # ^ |   +9 I totaly agree. Please make it rated for the ones who will increase their rating.
•  » » 3 years ago, # ^ |   0 BledDest why not doing this ?
 » 3 years ago, # |   +6 Atleast make it rated for those getting +ve rating change, no matter if they were affected by D or not.
 » 3 years ago, # |   +4 this contest should be rated for all those who got correct the 4th one but failed later..but still are getting their ratings better than before and unrated for the ones whose ratings would be decreased due to the 4th question.
 » 3 years ago, # |   0 Can anyone tell me how to solve problem D ?
•  » » 3 years ago, # ^ |   0 run dijkstra from vertex 1 to all other onesthat gives you a tree of shortest pathsall you need to do is remove leaf by leaf untill you have k+1 vertices (and k edges)it clearly maximizes the number of 'good vertices' and is always valid as well
 » 3 years ago, # |   0 Can anyone gives me a hint on problem E?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 My friend tell me its depth segment tree ， but i still no idea yet update： I pass the problem just now，here is my code http://codeforces.com/contest/1076/submission/45654052，I think u can get my idea easily。orz，the solution not very difficult，But I've been thinking about it for so long. It seems more practice is needed……
 » 3 years ago, # |   0 Can anybody please proof the problem C mathmatically. It would be greatly appriciated. Thanks :)
•  » » 3 years ago, # ^ |   0 it's just a quadratic equation. I've never been good with math proofs but here what I did: x + y = n, x * y = n, x * (n-x) = n, then solve x*x — n*x + n = 0.
•  » » 3 years ago, # ^ |   0 Consider a * b = a + b = d we can get 2 equations for a , a = (a+b) / b = d / b and a = (a * b) — b = d-b d / b = (d — b) -> b^2 — bd + d = 0 so , we can use quadratic equation to get b , then a = d/b But if there is no valid answer from quadratic equation then answer is N
•  » » 3 years ago, # ^ |   0 We know:1) (a + b) ^ 2 = (a ^ 2) + (b ^ 2) + 2 * a * b2) (a — b) ^ 2 = (a ^ 2) + (b ^ 2) — 2 * a * bSo we can calculate (a — b) ^ 2 as follows:1) (a — b) ^ 2 = (a + b) ^ 2 — 4 * a * bWe know also that a + b = d & a * b = d.let A = d ^ 2 — 4 * a * dSo we have (a — b) ^ 2 = ANow, in order for the problem to have answer, A must be positive. In case where A is negative simply output 'N'. In case it is positive, find it's square root and name it c.now we have to equations:1) a + b = d2) a — b = cSo a = (d + c) / 2 & b = d — aAfter calculating the values for a & b check them. The problem wants a & b to be non-negative real numbers. So if either of them is negative then output 'N' and else output the numbers.
•  » » 3 years ago, # ^ |   +6 By Vieta's formulas, we know that the sum of roots of the second degree polynomial ax2 + bx + c is equal to while their product is equal to . So if such numbers exist they will be roots of the polynomial x2 - dx + d.
 » 3 years ago, # |   +26 why exactly did people try to submit solutions with cout << 0 anyway?that feels just odd to me
•  » » 3 years ago, # ^ |   -44 I also saw some people submitted their code with "if(something == x or something == y)". It should be if(something == x || something == y).
 » 3 years ago, # |   0 Can someone please explain me why my answer is wrong for problem A in the shown test case? Input 1000 rkqggsabguejnkvqhflwqtndjqakicbgcirayhvustungfyjrvgvxdcpwaoyqmqrorxfjlmvqazvgqwbwkiwypcxclzhskvrjdxrgbanlngwymdlmgurflfvnersfqkwnsmsh...............Participant's output rkqggsabguejnkvqhflwqtndjqakicbgcirayhvustungfyjrvgvxdcpwaoyqmqrorxfjlmvqavgqwbwkiwypcxclzhskvrjdxrgbanlngwymdlmgu................Jury's answer kqggsabguejnkvqhflwqtndjqakicbgcirayhvustungfyjrvgvxdcpwaoyqmqrorxfjlmvqazvgqwbwkiwypcxclzhskvrjdxrgbanlngw..................(why is 'r' being cut instead of 'z'?)
•  » » 3 years ago, # ^ |   +8 Consider the simpler case: 3 bac Output: acYour code's output: baYou should delete the first character s[i] such as s[i] > s[i+1], not the largest character
•  » » » 3 years ago, # ^ |   0 oh. Thank you so much! I misunderstood the question!
 » 3 years ago, # |   0 Can anyone make me understand solution of D. Had a terrible round.
•  » » 3 years ago, # ^ |   +1 My solution is based on dijkstra's algorithm from vertex 1. So while we're running dijkstra , i just pick the first K node(that is not 1) that we visit by dijkstra , if we were about to exceed K just break the loop. (FYI my dijkstra is implemented in a while loop with a priority_queue as the main data structure , you can see the submission from my profile.)
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 Actually Dijkstra process built a shortest-path tree with N vertices from the graph. So we will build that tree, and repeat this N — k — 1 times: Find a vertex that is a leaf and delete it. This process make sure all the current vertex of the tree has as same shortest distance from vertex 1 as it was before the deletion, and the number of these vertices is largest. This can be done with dfsYou can make the deletion simpler, by dfs the shortest-path tree and build a subtree of k edges. Here is my submission 45633192.
 » 3 years ago, # |   0 How to solve problem G ?
 » 3 years ago, # |   0 Was the contest unrated for all..as my rating has not been increased.
 » 3 years ago, # |   +9 So we have just eliminated everyone affected by D... what?? This is just so stupid. Someone who has done E or F and whose rating might be +100 would be unfair for them!! Make it rated for those with +ve rating change please.
 » 3 years ago, # |   +7 " Those who got accepted earlier and get WA now won't be affected by rating changes. For everyone else (for those who got correct verdict) the contest will be rated. " — What if the those contestants will get a higher rating if we skip D submissions of those users?
 » 3 years ago, # |   0 My rating still hasn't changed, is everything fine? I haven't touched D at all.
•  » » 3 years ago, # ^ |   0 UPD. It did now, sorry.
 » 3 years ago, # | ← Rev. 3 →   -11 deleted
 » 3 years ago, # |   0 Yeah, my rating increased by +145 :p
 » 3 years ago, # | ← Rev. 3 →   +33 For those who got TLE on test 64 on D: When implementing Dijkstra, do not check edges from a vertex if it is already visited (in other words, if the distance from the PQ is greater than the one written in the distance array). A vertex can be pushed into the PQ O(V) times and it also can have O(V) outgoing edges, so it can be O(V^2) in the worst case. Furthermore, this can be repeated for multiple vertices and possibly reach O(V^3) in a complete graph.The generator is: #include using namespace std; int main() { int n = 200003, m = 300000, k = 0; printf("%d %d %d\n", n, m, k); for (int i = 2; i <= 100000; i++) printf("%d %d %d\n", 1, i, i); for (int i = 2; i <= 100000; i++) printf("%d %d %d\n", i, 100001, (int)1e9 - 2 * i); for (int i = 0; i < 100002; i++) printf("%d %d %d\n", 100001, 100002 + i, (int)1e9); } 
 » 3 years ago, # |   +13 This is unfair to me. Predictor was showing I will get +50 rating. But now this became unrated for me. This is unfair...ummmmmmmmm
 » 3 years ago, # |   0 Anybody wrote a dp solution for E?
 » 3 years ago, # |   0 Is there a way to look up what test was used to hack my solution, in case I want to debug?
•  » » 3 years ago, # ^ |   0 View test under the hack verdict: https://codeforces.com/contest/1076/submission/45608998
 » 3 years ago, # |   +14 Is there editorial?
 » 3 years ago, # |   0 For E is it possible to build some type of tour so that we can use segtree for range update and then push all the changes?
•  » » 3 years ago, # ^ |   0 I have the same question. Can someone answer this?
 » 3 years ago, # |   0 i was wondering how setters managed to change the rating based on a particular problem's verdict... is it a database sort or ??
 » 3 years ago, # |   0 Why TLE on Test Case 64? problem D
•  » » 3 years ago, # ^ |   0
•  » » » 3 years ago, # ^ |   0 Thanks. Accepted.
 » 3 years ago, # |   0 Where is editorial? And how to solve F? It looks like a interesting problem.
 » 3 years ago, # |   0 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
 » 3 years ago, # |   0 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
 » 2 years ago, # |   0 I think in "Meme Problem(C)" float and double will give different answers. Both the answers shall be considered valid since logic is same. If programmer is able to give any one of them it implies his/her logic is sound.