MikeMirzayanov's blog

By MikeMirzayanov, history, 4 years ago, translation,

On May, 5, 16:05 (UTC) Codeforces Round 350 is going to start! Yes, pay attention to the non-standard start time.

I took advantage of my official position and the round is expected to be a bit experimental with an expanded set of problems. Perhaps for experienced participants (sorry, Div 1) it could seem easy. This time, emphasis was placed on the main target audience of the round: so in the round will be a lot of very simple problems, but even the top of the second division will find something interesting. In addition, one of the problems will be offered in two versions — in a simplified version with small constraints and in a harder version with greater constraints. Thus, if you immediately realize solution for large constraints, you can write and submit the same code on the both version.

The problem writers are me and fcspartakm. We hope that you will enjoy the problems and the round will be fun and useful!

The expected scoring is:

• A: 500
• B: 750
• C: 1000
• D1: 1000
• D2: 500 (i.e. the complete solution of D is 1500 points)
• E: 2000
• F: 2500

Good luck!

UPD: As it was pointed in the comments we have a tricky point about hacks with problems D1/D2.

1. To avoid the situation when participant locks the problem D1 and looks the solution of the problem D2 in his room, you are allowed to lock the problems D1/D2 only together in the same time and only if both of your solutions for this problems passed the pretests. In the other words, the possibility to lock D1/D2 will appears only after you solved both problems. The problems D1/D2 will be locked together in the same moment.

2. To avoid the situation of double reward for hack of D1 and D2 of the same participant, the participant A after successful hack of the participant B on the problem D1 loses the possibility of the hack B on the problem D2. Similarly if the participant A successfully hacks the participant B on the problem D2, then A loses the possibility of the hack B on D1.

UPD 2: The round is over. My congratulations to the winners! Here are the heroes of the round.

The Top-5 among the official participants:

The Top-5 among the unofficial participants:

UPD 3: Problem analysis is now available.

• +466

 » 4 years ago, # |   +63 So is CodeForces trying to move towards larger problem sets for a contest? Cause I think it'd be a lot more fun if there were more problems to try and solve per round.
 » 4 years ago, # |   +12 Will it be rated?
•  » » 4 years ago, # ^ |   +113 Sure.
 » 4 years ago, # |   +5 Will contest duration remain the same?
•  » » 4 years ago, # ^ |   +36 /contests page shows it is 2 hours and 30 minutes.
 » 4 years ago, # | ← Rev. 3 →   +11 If D2 score decrease 8 per minute (as a usual round) . then what will remain after 30 min?! only 250 points?!
•  » » 4 years ago, # ^ |   +34 I thought that the decrease was dependent on the problems score? If a problem is worth 500, at the very end of the contest it will decrease to be 250 points. In a regular 2-hour contest, it decreases at 2 per minute, but in a 2.5-hour contest it will decrease at 1.67?
 » 4 years ago, # |   +5 Also notice that problems are becoming harder and harder as the scoring distribution has also changed.
 » 4 years ago, # |   +254 Having a problem with two subproblems in a regular Codeforces round with hacks may be exploited in a following way: suppose there are two coders in the room. One of then solves only D1 and successfully submits it, while second solves both D1 and D2 with the same source code. Then, if first coder locks his code, he is able to read a solution for larger constraints if he opens a solution of D1 by the second guy.Something has to be tuned here. How about leaving a possibility to hack only for D2?
•  » » 4 years ago, # ^ |   +77 Locking D as a whole should work too
•  » » 4 years ago, # ^ | ← Rev. 2 →   +10 But if the first coder solved only D2, there may be people who submitted same solutions for D1 and D2 so if the first coder locks his D2 solution, he can find out the solution for D1 without being able to hack D1 solutions.UPD: vice versa for D2 and D1
•  » » » 4 years ago, # ^ |   +9 All correct D2 solutions will probably be correct D1 solutions
•  » » » » 4 years ago, # ^ |   +1 Not necessarily. I have a correct D2 and an incorrect D1. When submitting D2 there was an overflow error which I forgot to fix in my D1 submission :(. Maybe D2 should have been worth at least as much as D1.
•  » » 4 years ago, # ^ |   +3 There is also a possibility that D1 is "solve it" and D2 is "now write a checker".
•  » » » 4 years ago, # ^ |   +6 in a simplified version with small constraints and in a harder version with greater constraints I don't think so, I think it will be like write quadratic solution for D1 and quasi-linear for D2.
•  » » 4 years ago, # ^ |   +8 What if a rule can be made like this "To hack any of the sub part of D you need to solve both of them first." ?
 » 4 years ago, # |   -18 Good, I am in!
 » 4 years ago, # |   -18 this gonna be Enjoyable , I'm in !
 » 4 years ago, # |   +40 I have my Exam tomorrow.But this round looks interesting. I'm in!
•  » » 4 years ago, # ^ |   +38 That's the spirit !
•  » » 4 years ago, # ^ |   +18 Who cares about exams?
•  » » » 4 years ago, # ^ |   +18 After a backlog, I started caring!
•  » » » » 4 years ago, # ^ |   0 I feel sorry for you .
 » 4 years ago, # |   +8 I think this new form---one of the problems will be offered in two versions is very great!The equivalent of i could not finish big data algorithm can also get scores，right？For the beginners like us is really nice！I hope this form will be keep in the next rounds.I will support codeforces forever and i am expect codeforces can launch more good forms like this!Come on,codeforces!!!
 » 4 years ago, # |   +4 Partial Marking. This is going to be pretty interesting. :)
 » 4 years ago, # |   +27 Rule number 2 is not good ! In case someone submitted same code twice and I hacked one code in 90% of cases it means the second code is also not good. So some other will see it and receive points for second subtask despite he didn't find bug after first chacking.
•  » » 4 years ago, # ^ |   +3 Also there can be 2 completely different solutions, why hacking one of them prevents from hacking another?
•  » » » 4 years ago, # ^ |   +3 I think that better option is receiving 200 points for hacking both solutions, or not allow hacks for D task.
 » 4 years ago, # |   -18 You forgot to thank yourself.
•  » » 4 years ago, # ^ |   -11 I saw what you did there
 » 4 years ago, # |   +10 Test #11 is Evil
 » 4 years ago, # |   +13 well, look at this Desperation on a whole new level :v
•  » » 4 years ago, # ^ |   0 This guy was trying so hard...
•  » » 4 years ago, # ^ |   +43
•  » » » 4 years ago, # ^ |   +35
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I think Hedgehogy gave up at the end. x)
•  » » » 4 years ago, # ^ |   +1 Nope, unfortunately, he did not.
 » 4 years ago, # |   +1 What a Binary Search Round! Enjoyed it to the core...
•  » » 4 years ago, # ^ |   0 I solved C using binary search LOL XD. it was 100 lines of code :D :D.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 And solved D1 ,D2 without binary search.
 » 4 years ago, # |   +9 Too easy IMO.
 » 4 years ago, # |   +9 How to pass test 4 in problem F? Easy problem, but I can't find bug in my code :(
•  » » 4 years ago, # ^ |   0 Same. test 4 for F killed me.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Maybe this test can help you: 330055 33,the answer is 33005
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 Weak tests at F,my solution doesn't work for 323445 32,didn't have time to fix that,feel so bad...
•  » » » » 4 years ago, # ^ |   +5 My solution works for both but failed Pretest 4. T_T
•  » » » » » 4 years ago, # ^ |   0 in pretest 4,you put the second string first,and after that the rest of digits,i know that for sure
•  » » » 4 years ago, # ^ |   +3 What is the substring?
•  » » » » 4 years ago, # ^ |   0 fixed
•  » » » » » 4 years ago, # ^ |   0 I pass both "330055 33" and "323445 32", but still fail on pretest 4.
•  » » » » » » 4 years ago, # ^ |   0 Same. LOL. Magic test 4
•  » » » » » » 4 years ago, # ^ | ← Rev. 3 →   0 don't know what is your mistake,i checked these tests and after fixing my bug i got pretests passed
•  » » 4 years ago, # ^ |   0 I suppose pretest 4 is huge. I've tested my solution with test generator, still no idea what fails.
 » 4 years ago, # |   0 how to solve Div2 A?
•  » » 4 years ago, # ^ |   0 First of all we are bound to have 2 off days in each week , so first find the number of weeks and multiply it by 2. Next in case total days are not divisible by 7 we need to see if there are any remaining days or not (i.e. total days % 7) Now if there are 1 extra days if we are unlucky it will not be an off day , thus min off day is unchanged , but if we are lucky it will be an off day thus max off day is incremented by 1 , again if there are 2 extra days those 2 may not be off days thus min day is the same , but those two can be off days so max day is incremented again ( i.e. week*2 + 2 ) This logic extends up to extra day = 5 , but if the extra day =6 we are bound to have 1 off day so min day will be incremented then and max off day as before incremented twice ( i.e. week*2 + 2).
 » 4 years ago, # |   +52 halyavin used my successful challenge of D2 to identify the wrong solution and got challenge of D1. :)
 » 4 years ago, # |   +115
•  » » 4 years ago, # ^ |   0 Revenge is sweet and cold, like ice-cream
 » 4 years ago, # | ← Rev. 2 →   +19 Does this happen alot??? But still it was a great round.
 » 4 years ago, # |   0 What do you say when you try to submit and the contest gets over — "Every second counts"Just a heartbeat away. RIP Question F.
•  » » 4 years ago, # ^ |   +4 Bro there is high chance of getting it wrong still :P
 » 4 years ago, # |   0 Can string k contains 0 digits in last task ?
•  » » 4 years ago, # ^ |   0 No
 » 4 years ago, # |   +2 Am I the only one who miss-read E's statement (such that you need to delete just the pair of brackets but not the whole substring) and implemented an implicit treap?
 » 4 years ago, # |   -6 I think it should be a better contest but ...!!! :)
 » 4 years ago, # | ← Rev. 2 →   +6 spent so much time writing nice code for Ehttp://codeforces.com/contest/670/submission/17746555only to forget to change the size of the segment treeI feel like shit
•  » » 4 years ago, # ^ |   0 Next time generate maxtest & check your solution before submit.It helps me avoid this mistake.)
 » 4 years ago, # | ← Rev. 2 →   -13 Problem E why my solution Got Tle on test 12 Here is code:code..
 » 4 years ago, # |   +4 how did a O(n log(n)^2) in problem C gets TLE on test 125 17726278 ?!!!!
•  » » 4 years ago, # ^ |   +7 My O(N) Time Limit.http://codeforces.com/contest/670/submission/17727212How is that even possible -_-
•  » » » 4 years ago, # ^ |   0 It may be N log N, maps requires O (log N).
•  » » » » 4 years ago, # ^ |   0 it's "UNORDERD MAP"
•  » » » » » 4 years ago, # ^ |   +14 unordered_maps constaint may be worse than log in some tests
•  » » » » » » 4 years ago, # ^ |   0 Maybe exactly this problem http://stackoverflow.com/a/11634689/440168 ?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 shouldn't also be fine for that problem?
•  » » » 4 years ago, # ^ |   +21 Anti hash-map test.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Why would they put an anti hash-map test leaving the normal map passing in NlogN? are they trolling us ?!
•  » » » » » 4 years ago, # ^ |   0 Actually it seems there is something wrong with unordered_map in C++ or the authors designed the test cases that fail hashing only for unordered_map.Java's HashMap works normally. Which to be honest, I find pretty weird, if you are going to TLE hashing solutions, then make sure you TLE them on all languages.
•  » » » 4 years ago, # ^ |   0 Mine too! SolutionToo strict! :(
•  » » » » 4 years ago, # ^ |   0 Maybe bad default size of hash-table inside unordered_map?
•  » » » » 4 years ago, # ^ |   0 Not too strict because map works in ~800 ms,it's your fault you used unordered_map
•  » » » » » 4 years ago, # ^ |   0 Hi, isn't unordered map supposed to be faster, Please correct me if I am wrong.
•  » » » » » » 4 years ago, # ^ |   0 In what sense "faster"? Do you mean asymptotically faster or what?
•  » » » » » » 4 years ago, # ^ |   0 Sometimes it is faster but sometimes it is the very slow,imagine you have a Hash modulo MOD,then when you'll have test like MOD + 1,MOD + MOD + 1,...,MOD * n + 1 it will run in linear time.
•  » » » » » » 4 years ago, # ^ |   +2 It's supposed to be faster on average (runs in O(1)) but in the worst case it runs in up to O(N). The test must have been specially designed to backstab us who used unordered_map. :(((
•  » » » » » 4 years ago, # ^ |   0 Can you explain me please where is a problem in my solution: http://codeforces.com/contest/670/submission/17731716 ? I think the complexity of solution is O((N + M) * log(N)) so it don't have to get TLE verdict.
•  » » » » » » 4 years ago, # ^ | ← Rev. 3 →   0 Reading with cin 600.000+ numbers?
•  » » » » » » » 4 years ago, # ^ |   0 I think, it's true but I'm very angry because, for example, this solution http://codeforces.com/contest/670/submission/17742515 got OK verdict.
•  » » » 4 years ago, # ^ |   0 Nice profile pic.
•  » » » 4 years ago, # ^ |   0 Hi !Use reverse trick.Like this : 21771219.More information here : Link
•  » » 4 years ago, # ^ |   0 Constants from STL...
•  » » 4 years ago, # ^ |   0 Similar problem happened in this problem.O(n^2) gave TLE.Click
 » 4 years ago, # |   +5 I think test data for D is weak, 17727910 can be broken with an overflow, with large N, large Ai, and small Bi.
 » 4 years ago, # | ← Rev. 2 →   -19 Problem C got TLEd with O(n+m) Solution, But passes with scanf and stdio sync off.Maybe the problem setters shouldnt keep it that borderline where 2 solutions of the same complexity have different result cause of I/O Methods.EDIT: I was wrong, It is not the IO, but the use of map instead of unordered_map, but that still confuses me, even more so.
•  » » 4 years ago, # ^ |   0 Choosing I/O is the same as choosing data structures for the problem. There are more comfortable ones, and less comfortable but faster
•  » » 4 years ago, # ^ |   0 Looks like solutions with map passed add tests, with unordered_map doesn't.Maybe bad default size of hash-table inside unordered_map?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +10 Regular cin/cout is hella slow — it's one of the first things you learn when competing. If you were to complain, for example, that sync off didn't pass while only scanf did, that'd be somewhat reasonable — but using regular cin/cout on 400,000+ numbers? Come on.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 it may pass only reading but there is also unordered_map,in genereal all the unordered_map solutions don't pass the test 132.
•  » » » 4 years ago, # ^ | ← Rev. 4 →   0 EDIT 2: It's not inserts it's the access see this on unordered_map documentation time to go and punish myself for misjudging :)EDIT 1: It's definitely unordered_map's hashing So many inserts on a map must have been done in amortized constant map passed but all unordered_map solutions TLEI am not sure if I/O is taking time or is it unordered_map's hashing. Eh, I feel like it was a brutal test My stdio sync was off http://codeforces.com/contest/670/submission/17737941 Still TLEd I am going to test Python with raw_input(), it that passes , then cin,cout with sync off should have been allowed to pass
•  » » » » 4 years ago, # ^ |   0 There is an anti-unordered_map test (I hope mine is #132). The reading part should not be the problem.
 » 4 years ago, # |   +29 wat
•  » » 4 years ago, # ^ |   +7 Ouch. It is better go to sleep, rather than waiting for the end of systests.tnx.
•  » » 4 years ago, # ^ |   0 same :/
 » 4 years ago, # |   +7 Great contest.Very soft increase in the difficulty of the problems. I want to repeat the experience :)
•  » » 4 years ago, # ^ |   0 Same here. enjoyed it a lot . although I did pretty terrible. i am now solving D2 . almost done .
 » 4 years ago, # |   +31 I'm gonna ask a very professional question: how do you use your time efficiently till system testing end? (except pressing f5 rapidly which I'm doing right now)
•  » » 4 years ago, # ^ |   +9 switching between friend standing and common standing :)
•  » » » 4 years ago, # ^ |   +1 That's what I am doing too, actually. It works well, I must say!
•  » » 4 years ago, # ^ |   +1 Instead of pressing f5 clicking the refresh button of your browser =D
 » 4 years ago, # |   +6 How come this submission gave TLE on the C problem? 17725819
•  » » 4 years ago, # ^ |   0 Maybe it has something to do with mixing cin and scanf?
•  » » » 4 years ago, # ^ |   +8 Maybe because of unordered_map?Change into map and see what happens.
•  » » 4 years ago, # ^ | ← Rev. 4 →   0 I used the same algorithm:17733793but, i prefeer use only "cin" and "cout"and add: "std::ios::sync_with_stdio(false);"UPD: in worst case: MAP: O(log(N))UNORDERED_MAP: O(N)
•  » » » 4 years ago, # ^ |   0 You shared your solution for problem D1
•  » » » » 4 years ago, # ^ |   0 oh thanks :)Edited! :D
 » 4 years ago, # |   0 What is the difference between simple map and unordered map ? I see many people prefer using the later.
•  » » 4 years ago, # ^ | ← Rev. 3 →   -40 I said shit. I've learnt my lesson :(
•  » » 4 years ago, # ^ |   +18 map is balanced bst (red black tree), the other one unordered is hasing based. While map guarantees O(log n) access, unordered_map generally gives constant time access however in worst case can lead to O(n) per access too
•  » » » 4 years ago, # ^ |   0 Thanks that was helpful. BTW, in which cases unordered map can lead to O(n) per access .Any general idea ?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   -51 I said shit. I've learnt my lesson :(
•  » » » » » 4 years ago, # ^ |   +33 std::unordered_map does NOT do linear search.
 » 4 years ago, # |   +15 Too slow............System Testing?
•  » » 4 years ago, # ^ |   +17 Because 100+ tests for each problem.
•  » » 4 years ago, # ^ |   0 Actually, it is better to have more complete testing rather than fast and accepting wrong solutions.
 » 4 years ago, # |   0 That feeling when you finished task E for 30 seconds right after the contest ends... :( Need to write code faster next time...
 » 4 years ago, # |   +5 Problem D1 gives more points than D2, but it's actually the easy one. Isn't it?
•  » » 4 years ago, # ^ |   0 The idea is if you pass the large one you can submit it to both... so D2 is basically a bonus for passing the large input.
•  » » » 4 years ago, # ^ |   +5 I get your point, but how that could be better? It decreases the value of solving the hard version (if it turned out to be pretty hard, then it should be optimal to skip it and just submit the easy version, and your score wouldn't change significantly) IMO. Maybe I'm missing something.
•  » » » » 4 years ago, # ^ |   +3 Doofenschmirtz Evil Incorporated!
 » 4 years ago, # |   0 Slowest System Testing EVER!!!
 » 4 years ago, # |   +3 Is multiset much slower than map ? I got TLE for C due to multiset. I was trying something new and now it failed. :(
•  » » 4 years ago, # ^ |   +11 The complexity to search for a single item is same as in map. However to count number of occurences of item is linear! ouchhttp://www.cplusplus.com/reference/set/multiset/count/
•  » » » 4 years ago, # ^ |   +8 oh my god :((
•  » » » 4 years ago, # ^ |   +3 Holy... I should have checked. God.
 » 4 years ago, # |   +34
 » 4 years ago, # |   -11 Am I the only one who didn't study the complete general announcement for D1-D2?
 » 4 years ago, # |   +3 I got WA for setting High=1e9 in binary search for D2 . How to calculate maximum value High can get ?
•  » » 4 years ago, # ^ |   0 Didn't it failed on pretests? The first pretest had 2000000000 as answer
•  » » » 4 years ago, # ^ |   0 NO it didn't . I first calculated the number of dish I can make assuming value of k to be 0 . then I BSed the answer with k involved and sum of the 2 was the answer . (For pretest 2e9 can be accomplished using k=0 and 0 after consider k so total ans =2e9 >.<)
•  » » 4 years ago, # ^ |   0 You can prove that 2e9 is the highest value of hi.If n=1 k=1e9 a[0]=1 b[0]=1e9 then the ans is 2e9 , and note that there can be no worse case than this.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Suppose all ai's are equal to 1 All bi's are equal to 1e9k is equal to 1e9In this case the answer will be 1e9+1 but you have set high already lower than this so you will get wa. Above comments show that max hi = 2e9
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 I was lazy to calculate it so I just set:High = (sum of all bi + k)/(sum of all ai) + 2(the +2 is redundant but you can never be too safe). This is a simple and obviously correct estimate. Using only that estimate we can conclude that High at about 1014 should for sure do the job.(ofc you can get better bounds but ain't nobody got time for that)
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 >.< funny How 1 character makes a difference .
•  » » » 4 years ago, # ^ |   +3 For D1 I just used 1e9 (WANTED to be safe) for the upper bound and failed cause I wasn't aware of int overflow due to such small inputs! (But passed D2...) T_T
•  » » 4 years ago, # ^ |   0 The top possible value is 2e9. This can be seen by an example with one ingredient, where you have 1e9 of the ingredient and 1e9 of the magic powder, and you need 1 of the ingredient to make a cookie. You can then make 2e9 cookies with what you have.
•  » » » 4 years ago, # ^ |   0 1<<33 is enough
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 It's 2e9 + some const, but be patient, 2e9 + C not anytime is equal to 200...00 + C due to floating point precision error
 » 4 years ago, # | ← Rev. 2 →   0 Can someone explain me why I got TLE on pretest with this (problem B)? I used std::sqrt, don't think it will work so slow... http://codeforces.com/contest/670/submission/17732164
•  » » 4 years ago, # ^ |   0 I don't know if it is ok, to read long long with %ld?
•  » » 4 years ago, # ^ |   0 %ld is for long, which in most cases is equal to int by size, for long long you need to use %lld, reading by %ld gave you some trash inside n and k — http://ideone.com/NDPC4R
 » 4 years ago, # |   0 I liked the round, but if the system tests have to be this long, then no, just stick to the regular rounds.
•  » » 4 years ago, # ^ |   0 Why does the testing time bother you at all? :)
 » 4 years ago, # | ← Rev. 2 →   0 DAMN!!! tomorrow is comming,but there're only 75% checked !!! So slooooww!!
•  » » 4 years ago, # ^ |   0 Winter is coming!
 » 4 years ago, # |   +3 To be safe,I set the high in D2 to 4e9. But my code fails on test #128 T-T
•  » » 4 years ago, # ^ |   0 Did you use int or long long for the 4e9 variable?
•  » » » 4 years ago, # ^ |   0 Long long int
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   -11 Nope, there is some other error
•  » » » » » 4 years ago, # ^ |   0 Nope, works fine.
•  » » 4 years ago, # ^ |   +3 if (k
•  » » » 4 years ago, # ^ |   0 Works fine
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   +3 i think expected answer is 1 and your code is returning 0 correct me if i am wrong
•  » » 4 years ago, # ^ |   0 I used BigInteger and passed 128 =) 17735769
 » 4 years ago, # |   0 Can someone explain why have i got RE13 on B with this code http://codeforces.com/contest/670/submission/17726464/. It literally ruined this round for me.
•  » » 4 years ago, # ^ |   0 When i*(i+1)/2 == k you would get data[-1]
•  » » » 4 years ago, # ^ |   0 Nope. I would get data[i-1]. i*(i+1)/2 — i*(i-1)/2 = i.
•  » » » » 4 years ago, # ^ |   0 Then it's overflow, i * (i+1)
 » 4 years ago, # |   +3 Waiting for system test to end like...
 » 4 years ago, # |   0 Why is there a penalty for Wrong Answer for pretest 2 in D2? Pretests 1 and 2 don't have penalties right?
•  » » 4 years ago, # ^ |   +11 as far as i know , Only Pretest 1 does not cost u penalty .
 » 4 years ago, # |   -10 like a boss! problem E:
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I did it the same way , it took me 20 mins of coding and more than 40 mins of debugging :)
 » 4 years ago, # |   +5 That hash table hit me HARD!! What a great lesson by the problem writers :). Thank you, you guys make me learn something new.
 » 4 years ago, # |   0 Shouldn't this solution:http://codeforces.com/contest/670/submission/17745728 Fail on cases like "(((((.....)))))" if you start deleting right from the middle of the string this solution would keep iterating over all of the characters in the original string?
 » 4 years ago, # |   +7 anti-hash table test was MESSED up...
 » 4 years ago, # |   0 Why did this solution — http://www.codeforces.com/contest/670/submission/17743870 receive a compilation error?
 » 4 years ago, # |   0 I know that it is unbelievable but I sure that it is happen, during the system test after all my problems have been test I found my rank is 644 and after the contest finished I found it 640 HOW!!!
•  » » 4 years ago, # ^ |   +1 This already happened to me. I don't have any explanation.
 » 4 years ago, # |   +26 D1 should be of 500 points and D2 should be of 1000 points. Higher constraints problem should ideally be having more points.
•  » » 4 years ago, # ^ |   0 And I automatically agree with you since I failed D1 but not D2 LOLBut to not be biased, I think either scoring is fine. In the way it is it seems the large input is just a bonus score. Those who solve D2 are supposed to also solve D1 correctly anyway. (Well, except in the case of some overflows which many and I have overlooked because of small inputs...)
 » 4 years ago, # | ← Rev. 4 →   0 Nice
 » 4 years ago, # |   0 So tell me how the problem setters (or a contestant?) generated anti-unordered_map case? How to prevent our solutions from being hacked (´･_･)
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I googled and tried to read gcc headers, but it's too sophisticated. What I could understood are: unordered_map has a normal hash table implementation; it divides items into some bucket by its hash value and items with the same hash value are stored by linked list in same bucket. hash function for int is just identical function (hash(x) = x). item x seems to be stored at (hash(x) mod the number of bucket)-th bucket. the number of buckets sometimes changes by rehashing operation.
•  » » » 4 years ago, # ^ |   0 Hashmap has O(n) complexity in worst case (when all the elements store in same bucket). So the solution with unordered_map has O(n^2) complexity.
•  » » » » 4 years ago, # ^ |   0 Yes I realized that, but when you find hashmap while seeking challenge, can you always generate TLE input?
•  » » » » » 4 years ago, # ^ |   0 For programs which don't take measures against anti-unordered_map inputs, it seems easy.Random input: http://ideone.com/bjvJKgAnti-unordered_map input: http://ideone.com/LAzKjm
•  » » » » » » 4 years ago, # ^ |   0 Thank you! http://ideone.com/atUji0
 » 4 years ago, # |   0 Problem D2. Not able to find any error in my solution. It fails in test case 128. Can someone please help in finding out the error. I uploaded the same code for D1 which got accepted. Here is my solution. Please help :p http://codeforces.com/contest/670/submission/17734861
•  » » 4 years ago, # ^ |   0 mine fails on 128 as well Code
•  » » 4 years ago, # ^ |   0 Overflow, now it passes 17779411
 » 4 years ago, # |   0 I've been doing F and my code got Runtime_error after cout the output nad I dont know why. Here's my code: http://codeforces.com/contest/670/submission/17828267 Anyone can help, pls?? P/s: my English is not good sry if u mind.