By MikeMirzayanov, 19 months ago, translation, ,

I apologize to the participants of the round. It happened that I accidentally had run improper script and it rebooted the judging machines. It is very insulting, because most problems were proposed by me and I hoped to host an interesting competition for you. A lot of effort was spent on preparation. Apparently, the mistake of just such a human character happened for the first time. I really hope not to repeat it in the future.

MikeMirzayanov

Want problems? We have some!

Codeforces Round 434 will start on September 17 (Sunday), 13:05 (UTC). It will be based on Technocup 2018 Elimination Round 1. So, if you are a Russian-speaking high-school student, please take part in the Technocup 2018.

Many thanks to KAN, 0n25, Ne0n25, ifsmirnov, irkstepanov and white2302 for their help in round preparation. Some problem ideas are mine.

I hope you will like problems. There will be 6 problems in div. 2 and 5 problems in div. 1.

Wish you good luck and bugless code.

•
• +80
•

 » 19 months ago, # |   +291 you forgot to thank MikeMirzayanov
•  » » 19 months ago, # ^ |   -35 Because he is the author :)
•  » » » 19 months ago, # ^ |   +110 you must be fun at parties :')
•  » » » » 19 months ago, # ^ |   -16 Actually, I tried to look like Captain Obvious... Overdid it :D
•  » » 19 months ago, # ^ |   +21 now i know why didn't thank MikeMirzayanov
 » 19 months ago, # |   -13 Mike himself to the rescue B)
 » 19 months ago, # | ← Rev. 3 →   +18 And thanks MikeMirzayanov for the codeforces platform,great polygon and also for this post.
 » 19 months ago, # |   -39 Is it Xxxxx ? (Please no downvotes)
•  » » 19 months ago, # ^ |   +27 Yes this is rated and every round which has the form Codeforces Round #no. is rated.
•  » » » 19 months ago, # ^ |   +22 are you sure?
•  » » » 19 months ago, # ^ |   +1 No. It Is Not Going To Be Rated Today.
•  » » » » 19 months ago, # ^ |   +1 Let me rephrase it. It was going to be rated.
•  » » 19 months ago, # ^ |   +2 You can see in Calendar
•  » » 19 months ago, # ^ |   0 Thx. Sorry for my naive question.
 » 19 months ago, # |   +5 Is this contest only for a Russian speaking student?
•  » » 19 months ago, # ^ |   +6 It is open for everybody.
•  » » » 19 months ago, # ^ |   +5 Hmm..Thanks
•  » » » » 19 months ago, # ^ |   -34 can i be your friend. can you help me when i get stuck in some problems.
•  » » » » » 19 months ago, # ^ |   -33 No i didn't mean in contest. please stop down voting.
 » 19 months ago, # |   +17
•  » » 19 months ago, # ^ |   +15 Arsenal is gonna be butchered by Chelsea..
•  » » » 19 months ago, # ^ |   -14 Arsenal better than Chelsea
•  » » » 19 months ago, # ^ |   +4 Yeah, David Luiz almost butchered someone on the pitch.
•  » » » » 19 months ago, # ^ |   0 He butchered himself!!!
 » 19 months ago, # |   -33 this round will be rated or not ?
•  » » 19 months ago, # ^ |   -10 rated ofcourse
•  » » » 19 months ago, # ^ |   0 Than You..
•  » » 19 months ago, # ^ | ← Rev. 2 →   -6 Yes.It was rated.
•  » » » 19 months ago, # ^ |   +9 Liar
 » 19 months ago, # |   0 Sorry for bad knowledge of codeforces, but will there be hacks in the official round?
•  » » 19 months ago, # ^ | ← Rev. 2 →   +5 Yes, You can hack in regular CF Rounds and Educational Rounds.
•  » » » 19 months ago, # ^ |   0 Thanks
 » 19 months ago, # |   0 I hope it will have begineer level A like yesterday... ;-)
 » 19 months ago, # |   0 is it....emmm, interesting ?
 » 19 months ago, # |   0 Please announce the scoring!
•  » » 19 months ago, # ^ |   0 They didn't say, they will. :D As soon as the contest starts, you can see it both on standings page, and on the right bar.
 » 19 months ago, # |   0 MikeMirzayanov, hack page is not loading. :(
 » 19 months ago, # |   +8 My solution is 'running on pretest 1' since 15 mins.
 » 19 months ago, # |   +11 testing system is stuck
 » 19 months ago, # |   +15 Such a long queue...!! I guess round should be declared unrated...
 » 19 months ago, # |   +8 Experiencing Queue on hacks for the first time
 » 19 months ago, # |   +2 What would happen if two person attempt to hack a code simultaneously when there is a queue on hacks ??
•  » » 19 months ago, # ^ |   0 Both get the points..!! hahahahahhaha
 » 19 months ago, # |   +73 Is Codeforces mining bitcoin?
 » 19 months ago, # |   +8 Will it be unrated?
•  » » 19 months ago, # ^ |   0 Good news or bad for you..??
 » 19 months ago, # |   +8 twenty minutes to receive a "Memory limit exceeded on pretest 1", RIP points
•  » » 19 months ago, # ^ |   0 Submit it after debugging again and you will not receive anything as contest would be over by that time..!
•  » » 19 months ago, # ^ |   0 Similar happened to me.
•  » » 19 months ago, # ^ |   0 Exact same happened to me.
 » 19 months ago, # |   +14 such a long queue :( waiting since 20 minutes.
•  » » 19 months ago, # ^ |   0 Slow and steady wins the race !!!
 » 19 months ago, # |   0 Well， this queue is unresonably long...I must say
 » 19 months ago, # |   +234 This contest
•  » » 19 months ago, # ^ |   0 good point
 » 19 months ago, # |   -7 Long queues... So most likely this contest is unrated.Moment of silence for all our brothers/sisters who realized this news after 2+ hours on this contest, as they were only giving the contest to increase their rating.
 » 19 months ago, # |   0 for sure it is not rated, is it ??? I submitted a solution 15 mins age, but until now it is in queue !!!!!!
 » 19 months ago, # | ← Rev. 3 →   +197 In queue... after the contest endWrong answer on pretest 7
 » 19 months ago, # |   +44 My Rating Graph clearly depicts the guy who is the mayor of the friendzone.I was about to break it through the friendzone and get laid today finally but long queues will most likely result in declaring the contest unrated.
 » 19 months ago, # |   -30 My 2D works OK on my computer but WA on CF, WTF
 » 19 months ago, # |   +16 Please make this round unrated. I still don't know whether my solutions have passed the pretests or not.
•  » » 19 months ago, # ^ |   0 Now it showed me wrong answer on pretest 7 for E problem now and time is increased by 10 mins. So much of adrenaline rush !!
 » 19 months ago, # |   +13 I waited for 30 minutes, but my code is still in queue. :(
 » 19 months ago, # |   -64 Up vote this comment if you like this round to be unrated. Down vote other wise.
 » 19 months ago, # |   +11 Yeeey, another unrated round, haven't seen for some months...
 » 19 months ago, # |   +27 I'm alone who's sad that round isn't rated?
•  » » 19 months ago, # ^ |   +2 me
•  » » » 19 months ago, # ^ |   +7 :(
•  » » 19 months ago, # ^ |   +4 i am so mad
•  » » » 19 months ago, # ^ |   0 same
 » 19 months ago, # |   +10 What happened on the juding system? I have participated in some rounds(and watch some) recent two months and found almost half of them get stuck in queue after 1 hour of the contest. What is the bug of this system? Could it be fixxed some time? Very eager to get a fluent contest without waiting for In queue and in queue and in queue..... Or finding the 404 and 403 and 504 and so on.... Hope Codeforces will be a better Online Judge System/
 » 19 months ago, # |   +4 A sad story.This round is unrated...
 » 19 months ago, # |   +23 Well, now I don't have to worry about my submissions failing systests because contest is unrated anyway :)
 » 19 months ago, # |   +8 Unrated :( Rip top 20 :( Huhu
 » 19 months ago, # |   0 I was gonna have a +120 rating change :(
•  » » 19 months ago, # ^ |   +1 me too
•  » » » 19 months ago, # ^ |   +1 me +190 :(
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 I had +119 expected as per the chrome extension which is a lot for someone rated pupil, also this was my first contest on this platform after a long time. Oh the disappointment is real, but the motivation to do better in the next one is even more real. :)
•  » » 19 months ago, # ^ |   0 how to judge rating change
•  » » » 19 months ago, # ^ |   0 I use NBHEXT but there's also CF-PredictorCF-PredictorNBHEXTOr you could use The rating formula and write your own scripts I guess.
 » 19 months ago, # |   0 I sumbit 2B with the same code for twice, and heres the results.3043768030439382
•  » » 19 months ago, # ^ |   0 It happens again, i think. 3044100630443306
•  » » » 19 months ago, # ^ |   0 Well,there must be something wrong with your algorithm.
 » 19 months ago, # |   0 How to solve Div.2 A?
•  » » 19 months ago, # ^ |   +3 contest isn't over yet.
•  » » » 19 months ago, # ^ |   +4 Oh sorry, I had an old tab open with the time before it was extended.
•  » » » » 19 months ago, # ^ |   0 Lol finished A on my IDE and tried to copy/paste before realizing that I forgot to sign up for the contest...
•  » » » » 19 months ago, # ^ |   0 And I think you just brute force it.e.g multiply n by 1, 2, 3, 4... 10^kWhere if n* 1, 2, 3, 4 .. 9 is not a k'th rounding, print out n * 10^k as numbers expressed in k'th rounding will never have primes larger than 9 in their factors.
•  » » 19 months ago, # ^ |   +5 Isn't answer just LCM(10k, n)?
•  » » » 19 months ago, # ^ |   0 Oh of course it is lol. I don't know why I couldn't think of that.
•  » » » 19 months ago, # ^ |   0 Lol!
•  » » 19 months ago, # ^ | ← Rev. 2 →   +4 my idea for A is: since number of zeros in the end is the minimum of powers of 2 and 5 in a number, I calculate the powers of 5 and 2 that are in the number, and I put more 2's and 5's as needed to make the minimum of powers of 2 and 5 at least k, for example n = 375 and k= 4, 375 contains 3 fives and 0 twos, so I add 4 twos and 1 five (2^4 * 5^1) = 80 and multiply it by 375 = 30000
 » 19 months ago, # |   +10 Finally, my solution for D passed after 30 mins. What a happy story!!!
 » 19 months ago, # |   +8 Really didn't expect this after yesterday's contest, especially considering how the system tests took like 10 minutes. A lot of people have to wait longer to get their submission judged than that entire system testing took. These sort of issues are really unfair on everyone, unfair on those who did well because they won't increase in rating, and unfair to those who got stuck in the 30 minute queue.
 » 19 months ago, # |   +9 Well still no red for me :')(Ehh why always when I do ok on a round it becomes either unrated or I have a stupid bug and one of my solutions fails)
•  » » 19 months ago, # ^ |   +14 Or both this time? Your E solution failed :(
•  » » » 19 months ago, # ^ |   +22 aham :')))
 » 19 months ago, # |   +104
•  » » 19 months ago, # ^ |   0 This...except I solved only 3
•  » » 19 months ago, # ^ | ← Rev. 3 →   0 your fourth submission pretests are still in queue. Hoping for your statement to come true soon. My E is also waiting.
•  » » 19 months ago, # ^ |   0 Perfectly described me.(P.S.:with +1:-3 Hacks by the way)
•  » » 19 months ago, # ^ |   0 Same opinion in Div.1...The first time for me to be in top 50...but unrated...
 » 19 months ago, # |   +5 You know you are a programming competition addict when you get your best rank, and you come to know that the contest is unrated(at the end of contest), and still you are alive.
 » 19 months ago, # |   0 How to solve F?
•  » » 19 months ago, # ^ |   +26
•  » » » 19 months ago, # ^ | ← Rev. 2 →   +49
 » 19 months ago, # |   0 I unaccepted 2B 4 times. thanks for the unrated. I don't worry about my rating!
 » 19 months ago, # |   +30 Looks like problem F from this round and http://codeforces.com/problemset/problem/406/C are the same.
 » 19 months ago, # |   0 Will it take a lot of time to system test? I want to go to bed because it's midnight in my country...
 » 19 months ago, # |   +9
•  » » 19 months ago, # ^ |   0 As I understand, the intended solution there is something called "string hashing". Does "string hashing" mean just cramming it all into a hash table as I did (and got AC) or is it supposed to be something more clever?
 » 19 months ago, # |   0 Can someone explain, why is this incorrect?(Problem D, wa 1st test) https://pastebin.com/gihJ16VG
 » 19 months ago, # | ← Rev. 2 →   +28 div1B is bad in my opinion. Just many maps/sets/hashsets will pass, although trie is intended(at least I think, that it is).UPD: And it's already well-known problem, link is 2 comments above.
•  » » 19 months ago, # ^ |   0 Why do you think solutions that require hashing are bad?
•  » » » 19 months ago, # ^ |   0 For this platform it's bad, because most probably it can be hacked. For instant full feedback contests it's fine.
•  » » » » 19 months ago, # ^ |   +9 Well for this problem if we do polynomial hash with base 13 it will fit in a 64-bit variable so I don't see how it can be hacked.
•  » » » » 19 months ago, # ^ |   +5 Even for this platform using for example polynomial hash with 4-5 random prime bases and random prime moduli, it may fail, but not by hacking.
•  » » » 19 months ago, # ^ |   +8 Because it's too easy for a Div1 B when you can very easily use map and set from C++
•  » » 19 months ago, # ^ |   0 Yeah, seems solutions with map gets pretests with 3500+ms, but I think they will fail at system tests...
•  » » » 19 months ago, # ^ |   0 My unordered_map solution ran pretests in 1.38 sec
•  » » » 19 months ago, # ^ |   0 I used unordored_map and it passed in ~2700ms which has a decent chance of passing system tests
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 I doubt that. There are only at most values to hash, and I don't think calling map, set, etc. that many of times would exceed the time limit of 4 seconds. Edit : edited after checking the problem parameters.
•  » » » » 19 months ago, # ^ |   0 noit is at most 45 * 7 * 10000 not 36 * 7 * 10000
•  » » » » » 19 months ago, # ^ |   0 Yes, I think your right. My notes do say 10C2. I forgot the problem parameters. But it doesn't change my argument that this is reasonable within the time limit.
•  » » » » 19 months ago, # ^ |   0 Yep. It does pass.30433941
•  » » 19 months ago, # ^ |   +17 I have a tricky solution. Using map with substring of length 8, for substring of length less than 8, just use array[2.10^7]. :)
 » 19 months ago, # |   0 My logic for D was -- for every suffix of a given string insert it into the trie then for ans for each string for every starting position calculate the depth of the position where trie[node] has only 1 index Can someone tell whether this logic is correct cuz I got WA.
•  » » 19 months ago, # ^ |   0 I did that, so it should work. Was tricky to not run out of memory though.
 » 19 months ago, # |   0 What is the pretest in div2 B?
•  » » 19 months ago, # ^ | ← Rev. 2 →   +5 2 2 3 1 5 2 answer =1
•  » » » 19 months ago, # ^ |   0 this should give '-1' right?my code didnt pass the pretests and i dont know where i'm making a mistake :(
•  » » » » 19 months ago, # ^ |   +1 if you know the third flat is on the first floor, on which floor is the second flat?
•  » » » » » 19 months ago, # ^ | ← Rev. 2 →   0 1st right?Update: I got my mistake. Shucks and thanks!
•  » » » » » 19 months ago, # ^ |   0 thanks dude, I haven't understood this
•  » » 19 months ago, # ^ |   0 How Can Someone Know before the systest finishes?
 » 19 months ago, # |   0 How to solve div1C/div2E ?
 » 19 months ago, # |   +13 When s̶y̶s̶t̶e̶m̶ pretest testing will be finished?
 » 19 months ago, # |   +26 I'm really disappointed ! Just spend the whole evening and the contest was unrated !
•  » » 19 months ago, # ^ |   +2 Well...I think despite the slow judgement,spending whole evening enjoying the problems themseves is OK.(Maybe I'm too weak to say that,but we do these problems to improve ourselves and get progress as well...
 » 19 months ago, # |   -20 I Think This Round Should Be Rated And Used This :- New_Rating = Old_Rating + max(rating_change_that_was_going_to_happen, 0);
•  » » 19 months ago, # ^ |   0 It is very bad idea, also not fair...
•  » » » 19 months ago, # ^ |   0 Why Not? Explain Please.
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   +5 Everyone had problems in this contest, so rating must be changed or not changed for everyone.One little update: Someone has rating ~1890 and with rating change he will be ~1910, but if there was not long queue in contest, s/he could make 2000+ rating which is better, because with 1910 rating you will fall expert if you write bad in your first contest, but this doesn't happen with 2000+ rating...
•  » » » » 19 months ago, # ^ |   0 Think for next contests, they are wrong again and we will continue to apply your formula and what will happen? Maybe all coder will have rating > 1900. All people will join Div.1 !!! And maybe I will get Red color soon :))))p/s: I solved 4 problems in this contest, but I don't care about rating.
•  » » » » » 19 months ago, # ^ | ← Rev. 2 →   0 I Talked Only About This Contest. Mike Said This Is Not Going To Happen Again.
•  » » 19 months ago, # ^ |   +17 instead of spamming these illogical comments. Do some practice your rating will increase for sure
•  » » » 19 months ago, # ^ |   0 Why Are You Calling This "Spam" ?
•  » » » » 19 months ago, # ^ |   0 Because this is just illogical
•  » » » » » 19 months ago, # ^ |   +4 Illogical != Spam (I Think).
•  » » » » » » 19 months ago, # ^ |   0
•  » » » 19 months ago, # ^ |   0 "You have no idea what HE is feeling. So shut up".ummm nice picture.
•  » » 19 months ago, # ^ |   +3 Taking such measures often enough would lead to unnecessary rating creep.
 » 19 months ago, # | ← Rev. 4 →   +5 UPDATE: the problem was just casting. Works as expected in GNU G++14, but not in GNU G++11. So, there is a weird bug with the GNU C++11 compiler... I was getting TLE in pretest 1 with http://codeforces.com/contest/861/submission/30432329 I got it solved by removing the pow call: http://codeforces.com/contest/861/submission/30432756pow(long long, long long)pow(10LL, k), where 0 <= k <= 8Doesn't seem to ever exit the function... but works fine in every other environment I've tested. Waiting for the end of system testing so I can make sure it's really the pow, and only in GNU C++11.
•  » » 19 months ago, # ^ |   0 pow() returns a double, not an integer or long long
•  » » » 19 months ago, # ^ | ← Rev. 4 →   0 UPDATE: okay, so I tried it and you are right, pow is returning. The problem is exactly the cast. In GNU G++11 (long long) pow(10, k) turns out 10^k - 1. In GNU G++14, however, it works as expected.I should have been more careful. Not the first time I have a problem with double -> int casts, and I keep making the same mistakes :). Since submissions can't be seen until the end of system testing, this is the line: long long k10 = pow(10LL, k); // k is a long longEven if it returns a double, it's then casted to a long long. The point is, it never returns, so it doesn't even matter what it returns...
•  » » » » 19 months ago, # ^ |   0 How do you know it never returns?Have you tried with CUSTOM INVOCATION?
•  » » » » » 19 months ago, # ^ |   0 Custom invocation was not working (would run forever with any code I submitted), but as soon as it started working again I tested it and now I know it is returning. The problem is the cast.
 » 19 months ago, # | ← Rev. 2 →   0 Todays contest be like
»
19 months ago, # |
+26

# When you finally did ok on a round

•  » » 19 months ago, # ^ |   0 How did you get that last delta column?
•  » » » 19 months ago, # ^ | ← Rev. 2 →   +3 Codeforces Predictor Chrome plug-in link
 » 19 months ago, # |   +143
•  » » 19 months ago, # ^ |   0 bad draw :v
 » 19 months ago, # |   +15 I made a video explaining my approach to problem div 1 a div 2 c https://www.youtube.com/watch?v=p4JGd5g9K9o&feature=youtu.be
 » 19 months ago, # |   +40 After waiting for 10min, my long-queued submission turned out to be WA on pretest 2.
 » 19 months ago, # |   +18 This all happened because there is no thank for Mike in announcement... :(
•  » » 19 months ago, # ^ |   0 What is the pretest 3 of div2.b?
•  » » » 19 months ago, # ^ |   +1 I don't know this test, but here is why you got WA3:When you check if you found another count of rooms for each floor, don't print -1 immediately, also check if n is not in the same floor with previous answer.
 » 19 months ago, # |   +5 top 100 get shirt?
•  » » 19 months ago, # ^ |   -9 What is the pretest 3 of div2.b?
 » 19 months ago, # |   0 I'm pretty curious, but what sort of technical errors can lead to a round being unrated? Like, I think with the timestamps of all submissions, rating modification is always possible (as long as the contest setter intends to do so).
•  » » 19 months ago, # ^ | ← Rev. 2 →   +10 What about if I waited for 30 mins for checking my solution then got WA and realized little bug immediately? 30mins is 1/4 of contest...
•  » » » 19 months ago, # ^ |   0 Ah... I got it now. I did feel the same thing when waiting for problem D, at least it turned out good (not sure if it could withstand the system tests). But okay, thanks.
•  » » » 19 months ago, # ^ |   0 i see, but i was going to be an expert if this round is rated
•  » » » » 19 months ago, # ^ |   0 It happens :) Just think what top10 feels now.BTW, I was going to be expert also :P
 » 19 months ago, # |   -16 MikeMirzayanov your apology is accepted :3
 » 19 months ago, # |   0 For problem F, would it be right to say the following? Construct a new undirected graph where the edges from the input graph are considered as vertices and if any two edges in the input graph are incident on some same vertex, then connect them in the new graph. The vertices from the input graph are not considered in this new graph. Now find the maximum matching in this new graph. This gives the answer. I know this won't work even if it is correct but I just want to know if this reduction is right. Thank you!
•  » » 19 months ago, # ^ |   0 This reduction is correct. Nevertheless, it cannot get AC, because in some cases it requires constructing too big graph. For example, imagine a test with n=100000, m=99999 and with edges {1,i} for each i from {2,3,...100000}. Then your sollution needs to contruct a new graph consisting of m*(m-1)/2 = 4999850001 new edges, which is far too much to hold in memory without getting MEM/RTE. Your sollution's expected time complexity is O(m+n+E*logm), where E is the number of edges in new graph, which is enough if E doesn't exceed 10^6. However, due to the fact that E can be O(m^2), pessimistic time complexity of your sollution is O(m^2*logm), which is too slow to be able to pass all tests.
 » 19 months ago, # |   0 test 43 on Div1C?
 » 19 months ago, # |   +34
 » 19 months ago, # |   0 My one of the best performance, but unrated :(
•  » » 19 months ago, # ^ |   +29 me too.
•  » » 19 months ago, # ^ |   0 Yes, for me to. It should happen more often, I perform better unrated.
 » 19 months ago, # | ← Rev. 2 →   +26 When can we submit the code in Practice. Can not currently :(Update: We can submit now :')
•  » » 19 months ago, # ^ |   0 Apparently Mirzayanov has accidentally rebooted the Practice machines too.
•  » » 19 months ago, # ^ |   0 now, finally :)
 » 19 months ago, # |   +12 When will the editorial be posted?
•  » » 19 months ago, # ^ |   +29 I think I have solutions to everything in Div 1, even though I couldn't get them to work in the contest. Here's the short, short editorial:A: Greedily extend the current word until adding another letter would violate the condition. Constraints are low enough that you don't have to be particularly clever (I think my solution is O(N^2) even though linear is quite easy).B: Make a frequency table of how many words contain each substring. You have to be a little careful because a substring might appear twice in one word. Then for each phone number, check every substring in increasing length until you find one that only appears in that number.C: Make two lists of initial filenames (examples and other), say I0, I1 and target filenames (examples and other), say T0, T1. Any file that already has a valid target name for its type gets crossed off both lists. If I0 == T1 and I1 == T0 then you have to rename some file to a temporary to break the cyclic dependency. After that or otherwise, you can always find some target in T1 \ I0 (or T0 \ I1), and then pick the source from I1 & T0 (or I0 & T1) if not empty, otherwise any from I1. You can prove that applying this renaming is safe and will again allow a subsequent renaming.D: In each component it's always possible to use half the edges. In fact, it's possible to picks off episodes such that the component remains connected. Build the DFS tree. Where a vertex has two up-edges, combine them into an episode — removing up-edges won't affect the DFS tree. Now pick the deepest leaf, picking one with an up-edge if possible. There are a few cases to consider, but it's always possible to use the edge from the leaf to it's parent plus some other edge in a way that won't disconnect the tree.E: I'm using a heavy-light decomposition and small-into-large merging. My solution was running out of memory (it turns out a deque per node uses a surprisingly large amount of memory even if they're empty), and I want to check if it's fast enough before posting my approach — I'm not 100% sure it is actually O(N log N).
•  » » » 19 months ago, # ^ |   0 There is a near-linear solution for E using LCA and a stack.30443098
•  » » » » 19 months ago, # ^ |   0 Would you explain your solution ?
•  » » » 19 months ago, # ^ |   0 Your solution seems to be O(N*sqrt(N)). The code below gives test cases where your solution performs a little over 0.6*N*sqrt(N) calls to push_down. I think that is about the worst you can do, since only the push_down call on the heavy child seems suspect (I think) and because of the merging of light childs before it, it seems a vertex can receive at most O(sqrt(N)) such calls. int n = 500000, d = 0; while (3 * n - 3 * (d + 1 + (d + 1 + 2)*(d + 1 - 1) / 2) >= 2 * n) ++d; vector p(n); p[0] = -1; FORE(i, 1, d - 1) p[i] = i - 1; int at = d; REPE(i, d - 2) { int prv = i; REP(j, d - i) { assert(at < n); p[at] = prv; prv = at++; } } while (at < n) p[at++] = d - 1; printf("%d\n", n); REP(i, n) { if (i != 0) printf(" "); printf("%d", p[i] + 1); } puts(""); 
•  » » » » 19 months ago, # ^ |   0 Yes, I'd also concluded that my solution is O(N sqrt(N)). Once I fixed the memory usage it passes system tests though, so the tests are probably not that strong. I think the push_down calls can be improved because they'll always operate on a contiguous range of the vertices at each level, so they can be made O(depth of light subtree) rather than O(size of heavy subtree to depth of light subtree).
 » 19 months ago, # | ← Rev. 2 →   +13 Rating changes for contest: Div. 1, Div. 2, Технокубок.
•  » » 19 months ago, # ^ |   +5 Wait a sec, it's unrated....
•  » » » 19 months ago, # ^ |   +26 CF-Predictor makes every contest rated:)
•  » » » » 19 months ago, # ^ |   0 It's awesome but the CF rating doesn't change :(
•  » » » » » 19 months ago, # ^ |   0 Sorry, it is not in my power
 » 19 months ago, # |   0 Does anyone have an O(n log(n)) approach for div1 E ?
•  » » 19 months ago, # ^ |   0 Can you please share your approach.Solutions are not public yet.
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 Yes, me. Also, it is possible to get O(N) if I use LCA in O(N) precomputation and O(1) query, but it's just theory. Add nodes in layers and construct the compressed tree with the current nodes and do some partial sums
 » 19 months ago, # |   +19 When will we be able to see testcases/resubmit? I'm curious about WA76 in Div1C.
 » 19 months ago, # |   0 Simple O(n) Div 2 C solution in 20 lines in Java https://pastebin.com/siR9vnyt
 » 19 months ago, # | ← Rev. 3 →   +23 I think using O(nlogn) for intended solution in 1E and trying to make O(nlog^2n) can't pass is not a good idea in cf :/I thought O(nlog^2n) is really fast and submitted without thinking and got TLE in the system test. UPD: resubmitted the TLE code without editing and got AC :/
 » 19 months ago, # | ← Rev. 2 →   +10 i have an issue, my code pass div 2 problem D's pretest, then my code get time limit exceeded on test 3 when system testing, then i resubmit again after system testing, and ac,,, what is going on???
 » 19 months ago, # | ← Rev. 2 →   0 This is quite weird. My answer for div2 A here gives correct answer 30000 for pretest 1 on my system but is giving wrong answer 29952 on CF. What can be the reason? Any help is appreciated.
•  » » 19 months ago, # ^ |   +3 pow() returns double, write one that calculates in integral type by your self!
•  » » » 19 months ago, # ^ |   0 Thanks, that worked.But here both arguments are integers, then why should returning double be a problem (I am typecasting the result in long long)?
•  » » » » 19 months ago, # ^ |   +17 Cause pow(base, exp) = {base}exp = (eln(base))exp = eexp * ln(base)This is how pow function implemented among almost every C++ compiler. Both functions ln and ex calculate result by Taylor series. So there always will be some error. If you want integral-type based implementation you should do it by yourself.
•  » » » » » 19 months ago, # ^ |   0 oh. Thanks for that.
 » 19 months ago, # |   +1 editorials please?
 » 19 months ago, # |   0 Can anyone please help in Div2C.I am constantly getting WA on test case 40.Here is my code.
•  » » 19 months ago, # ^ |   0 Try this input: dfacccbabcOutput that you should be gettingdfaccc babc
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 I am getting "dfacccbabc" when i am running locally.I am not able to get my mistake.
•  » » » » 19 months ago, # ^ |   +11 Yeh i get it. That's why i gave this input. So now you know what's your mistake, should be easy to correct i guess.
•  » » » 19 months ago, # ^ |   0 I can not figure out , why the answer should be dfaccc babc?? Will you please explain?
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   0 From what i can figure out this is your mistake-Once you're getting consecutive consonants which have all the same character you're printing all of them, which you shouldn't. Suppose you've got cccccba then printing cccccba is incorrect as you'll have a substring ccb which is a typo and should have been printed cc b or rather the whole string ccccc ba.Hope this helps :'). Haven't looked at you code but i'm guessing this is the mistake.
•  » » » » » 19 months ago, # ^ |   0 Yes, absolutely. I understood my mistake.Thank you so much.
 » 19 months ago, # |   0 I submitted my TLE code for D after the contest and it gets AC. Can someone please comment on this?TLE submission during contest: http://codeforces.com/contest/861/submission/30435774Submission after the contest: http://codeforces.com/contest/861/submission/30459324
•  » » 19 months ago, # ^ |   0 I have got the same result as you do...TLE during contest: http://codeforces.com/contest/861/submission/30432570probably the server lagged during the contest since there were too many submissions to judge...?
 » 19 months ago, # |   0 Editorial please!
•  » » 19 months ago, # ^ |   0
•  » » » 19 months ago, # ^ |   0 Thank you! :)