Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### MikeMirzayanov's blog

By MikeMirzayanov, 19 months ago, ,

Hello!

This time decided to fill myself in the shoes of the problem writers. It is very exciting! My challenge was to prepare a round in one day. It's really incredible pleasure to surrender to my passion and all day just work on problems!

Despite the fact that in total I've wrote 8 problems, I made it in time. Initially, I prepared 7 problems, but two of them were found to be used before (thank you, 300iq and _kun_ for poining it) and I removed them and wrote a new problem.

Codeforces Round #496 (Div. 3) will start on 09.07.2018 18:35 (Московское время). You will be offered 6 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the Div. 1 not be at all interested by this problems. And for 1600-1899 the problems will be quite easy. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

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

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

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

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

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

Many thanks to the testers: kevinsogo, 300iq, _kun_, arsijo and adedalic. You really helped to make this round!

Good luck!

UPD 1: The round is over. Thank you for participation!

Official Top-5 (trusted only)

Unofficial Top-5 (+ untrusted)

UPD 2: The editorial is available by the link.

• +263

 » 19 months ago, # |   +87 You forgot to thank MikeMirzayanov XD
•  » » 19 months ago, # ^ |   +235 I've told him it personally.
•  » » » 19 months ago, # ^ |   +7 is that rated for me?
•  » » » » 19 months ago, # ^ |   +35 Common, did you read the text? Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.
•  » » » » » 19 months ago, # ^ |   +97 Starting rating is not shown, so it is not so obvious if their rating is less than 1600
•  » » » » » » 19 months ago, # ^ |   +47 Good point.
•  » » » » » 19 months ago, # ^ | ← Rev. 2 →   0 So, is the point of trusted participants just that those who aren't such participants will not appear in the Top X table, or they will not affect our ratings also?Because if the round will be rated for them, we must affect each other's ratings, mustn't we?
•  » » » » » » 19 months ago, # ^ |   +1 AFAIK, there are two separate rankings, one is for trusted participants and it is the official one, while the other is for the distrusted participants. The lists do not affect nor influence each other in any way. The idea is, if you are a smurf, you'll compete with other smurfs, and people who actually ARE Div3 level will compete against one another. You won't see distrusted participants in the official standings.
•  » » » » » » » 19 months ago, # ^ | ← Rev. 2 →   +1 Thanks for your reply.I don't think so, because if, for example, two distrusted participants participated in some contest, according to what you said, the one with higher rank than the other will have a positive change on his rating, and the other one will have the same change but negatively (because, AFAIK, the total sum of the rating changes in a round equals 0), but this didn't happen before.
•  » » » » » » » » 19 months ago, # ^ |   +1 You're right, but I think that this (one gets some points, the other loses) will actually discourage people who have smurf accounts because they won't achieve much by competing in such circumstances (they all solve everything, meaning some may even lose rating points as unrated and get < 1500), while the point of them competing in a div3 round is to "dominate" it. There are some new unrated accounts that solve all tasks in a div3 round, only they won't get the expected rating change (~+200) but something relative to other unrated folks who are clearly smurf accounts, and that effectively defeats the purpose of anyone having a smurf account (or that how it is supposed to work, anyway, I don't know if it's actually working :), but I guess it is ).
•  » » » » » 19 months ago, # ^ |   +2 Why untrustworthy participants appear in top5?
•  » » » » » » 19 months ago, # ^ |   0 What do you mean?
•  » » » » » » » 19 months ago, # ^ |   0 They participated in less than 2 rated rounds, so they should not be in the official table. So why are they included in the winner list?
•  » » 19 months ago, # ^ |   -30 haha, MikeMirzayanov is himself.
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 you forgot to thank the problemsetters of IOI 2018 day 1 q2 and q3 :o
 » 19 months ago, # |   +54 MikeMirzayanov a couple div3 contests back there was talk of the reduction in the penalty for wrong answers (20 is too much), any updates on that ?
•  » » 19 months ago, # ^ |   +85 I'll try to implement it before the round. Stay tuned!
•  » » » 19 months ago, # ^ |   +5 Any updates regarding the penalty time?
•  » » » » 19 months ago, # ^ |   -9 follower
•  » » 19 months ago, # ^ |   +29 I've implemented it. You can check how it works on the ranklist of Codeforces Round #494 (Div. 3).
•  » » » 19 months ago, # ^ |   0 Great job! Looking forward to it..
•  » » » 19 months ago, # ^ |   -11 penalty now is 10 minutes .. good
•  » » » 19 months ago, # ^ |   +6 Will Educational Rounds will have from now on just 10 minutes penalty for each wrong answer?
•  » » » » 19 months ago, # ^ |   +21 Yes
 » 19 months ago, # |   +54 How can one prepare 7 problems in ONE DAY? Amazing!!! THANKS
 » 19 months ago, # |   +55 I am a simple man I see MikeMirzayanov I "upvote".
•  » » 19 months ago, # ^ |   0 I am a simple man I see a "I am a simple man" reference I "upvote".
 » 19 months ago, # |   +24 Hopefully MikeMirzayanov had enough time to make some not so weak pretests.No one would like to see many solutions fail after systests & I wish Vovuh will be back in the next Div-3 round.
•  » » 19 months ago, # ^ |   0 Good point.
 » 19 months ago, # |   +5 This is insane. Thank you so much for putting in effort to make this an awesome site!
•  » » 19 months ago, # ^ |   +7 As awesome as TheOneYouWant.
 » 19 months ago, # |   -9 6th Div-3 Contest in the history of Codeforces Round. <3
 » 19 months ago, # |   -28 when i will be Expert..
•  » » 19 months ago, # ^ |   0 i do not go Expert .. so i still could participate in DIV3
 » 19 months ago, # |   +1 Thanks a lot for making another div3 contest. It would be better if provided with 7 problems. Hopefully, problem statement will be the short description. Best of luck.
 » 19 months ago, # |   +2 MikeMirzayanov Will you make some tutorial on How to become a good problem setter...
•  » » 19 months ago, # ^ |   -6 when you be a good problem solver and above ..
 » 19 months ago, # |   0 MikeMirzayanov Any updates about lowering down the 20min penalty time for the 2h/2h30 contests? (For Div3 and Edu)
•  » » 19 months ago, # ^ |   0 penalty now is 10 minutes
 » 19 months ago, # |   0 So many "MikeMirzayanov"s in this blog. Is it his birthday?
•  » » 19 months ago, # ^ |   +2 no,it is his contest <3
•  » » 19 months ago, # ^ |   0 no but MikeMirzayanov is father of codeforces
•  » » » 19 months ago, # ^ |   0 Wooow, you both are "soo clever" I didn't know those.
•  » » » » 19 months ago, # ^ |   +6 and u so dumb,we did know that:))
 » 19 months ago, # |   +26 MikeMirzayanov why don't you ever participate in any contest on codeforces, it would be fun to see the CF founder competing with others.
•  » » 19 months ago, # ^ |   0 nice Q wating for answers //
 » 19 months ago, # | ← Rev. 2 →   +2 Please correct me if I'm wrong, but I remember that edu rounds allow registration at any moment before the end of the contest. Why is it that this contest registration is the same as normal rounds (with extra registration) if its rule is the same as edu rounds?Edit: my mistake, registration closes for 10 minutes before and after start of contest only
 » 19 months ago, # |   +37 Some of the last codeforces contest were so much unbalanced. The questions in this contest were so nicely balanced. Enjoyed it. Looking forward to such more contests.
 » 19 months ago, # |   0 What was pretest 9 in D?
•  » » 19 months ago, # ^ |   0 Try 317878994 The answer is 5, it worked for me :)
•  » » 19 months ago, # ^ |   0 Try 14334. Ans: 2
 » 19 months ago, # |   +29 Loved this round. <3
 » 19 months ago, # |   +34 How to solve E2?
•  » » 19 months ago, # ^ | ← Rev. 2 →   +19 Let s1[l..r] be (number of elements > m) — (number of elements < m) and s2[l..r] be the number of occurences of m.You can prove that in order for a range to be valid, 1-s2[l..r]<=s1[l..r]<=s2[l..r].If you expand s1/2[l..r] into s1/2[0..r]-s1/2[0..l-1], the problem becomes 2D range sum queries with point updates.
•  » » 19 months ago, # ^ | ← Rev. 2 →   +40 I solved it by counting number of arrays having median>=m and subtracting from those, the count of arrays having median>=m+1.To count number of arrays having median>=X, we can replace all elements < X by -1 and >=X by +1 and count the number of subarrays having a non-negative sum (and taking special case of when the length of the array is even, in that case the sum must be positive), both of which are kind of standard problems.
•  » » » 19 months ago, # ^ | ← Rev. 2 →   +12 Lol, why am I so dumb? I was thinking of 2d segment tree :D
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   0 You're not dumb at all, I got AC with this approach for both E1 & E2
•  » » » 19 months ago, # ^ |   0 non-negative sum? what does that mean? how sum can be negative?
•  » » » » 19 months ago, # ^ |   0 Sorry, there was a formatting mistake in my comment! I have corrected it
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 For E1 after changing m to 0 and numbers less than m to -1 and greater than m to +1 one can iterate though the prefix sum and count answer with the help of a map like here Can a similar approach be used for E2 by accounting for the number of zeros also ? I was not able to think of any O(n)or O(nlgn) solution like iterating and using map in E1. Any help?
•  » » » 19 months ago, # ^ |   0 How to find the no of subarrays with positive sum efficiently?
•  » » 19 months ago, # ^ |   +13 I counted the number of subarrays that don't have the median equal to m, and subtracted that from n*(n+1)/2. There are two cases:1) L + ZEROS < R2) L >= R + ZEROSL: left part (< m), R: right part (>m), ZEROS = number of elements equal to m.In the first case, I change the values <= m to -1, others to +1 and find subarrays with strictly positive sum.In the second case, I change values < m to +1, others to -1, and find the subarrays with non-negative sum.
 » 19 months ago, # |   0 So, what was that test 11 in D?
•  » » 19 months ago, # ^ |   0 Whatever it was. But I must say it was disastrous.
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 let's say a are numbers such that a%3==1 and b are numbers such that b%3==2 if count(a)==3 and count(b)==0 or count(b)==3 and count(a)==0 you have to split.{ Edit : the complete approach is mentioned below }
•  » » » 19 months ago, # ^ |   0 What do you have to split?
•  » » » » 19 months ago, # ^ |   0 observation 1 : you have to make splits in the array (vertical splits) if the element is 0 or a multiple of 3 . the number of these elements are added to the ans.removing these elements creates some segments . within a segment you can encounter elements of two kinds . element type a (a%3=1) and element type b(b%3=2).while processing the segment let count of elements type a be |a| and similarly |b| :if min( |a|,|b|) == 1 , then we are sure to have encountered a subset of this segment whose sum is multiple of 3. we reset the counts here and continue looking for other such sub-segments.if the above doesn't hold either |a|=0 or |b|=0 ,in which case |b| should be a multiple of 3 to yield 3 sum sub-segment and similarly for |a|. if that happens we reset counts and continue.
•  » » 19 months ago, # ^ |   0 Try 112, the answer is 1
 » 19 months ago, # |   +156 The worst future you can imagine:
•  » » 19 months ago, # ^ | ← Rev. 2 →   -29 I'll be in your nightmares B)
 » 19 months ago, # |   +1 Why I got TLE on E1 test 27 ?
 » 19 months ago, # |   +14 How to solve E2? I thought of an approach to make every number unique by giving them id in increasing order.Now suppose m appears k times in array then all m will have values from some f + 1 to f + k where f is the number of elements less than m. Now solve as the previous problem where median should lie between f + 1 to f + k;
 » 19 months ago, # |   0 How to solve D? I wrote a DP solution but got WA at test 11 multiple times.
•  » » 19 months ago, # ^ |   0 It must be greedy then? I got to the same test using greedy approach.
•  » » » 19 months ago, # ^ |   0 Yeah it is greedy
•  » » » » 19 months ago, # ^ |   0 And whats the problem with test 11?
•  » » » » » 19 months ago, # ^ |   0 what is your code doing exactly?
•  » » » » » » 19 months ago, # ^ |   0 I first make prefix sums of digits in array pf. prvi[i][j] stores the nearest position k to the right such that pf[k] % 3 = j. Then I greedily choose the nearest number to go to,while updating the solution.
•  » » » » » 19 months ago, # ^ |   0 It's a very long number
•  » » » » » » 19 months ago, # ^ |   0 Thank you very much (;
•  » » » » » 19 months ago, # ^ |   0 Correct answers for 824 (1) and 824824 (2) let me pass test 11.
•  » » » 19 months ago, # ^ |   0 got the mistake in my implementation. dp always works!
•  » » 19 months ago, # ^ | ← Rev. 3 →   0 Let dp[i]=answer for prefix of size i. We can see that dp is non-decreasing. And let sum[i] be the sum of prefix modulo 3, and x[i] be the last j then sum[j]=i. Then dp[i]=max(dp[i-1], 1 + dp[x[sum[i]]], sum[i] == 0)
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 LINK. Can you tell what kind of case will this solution fail. I have used a recursive approach. EDIT: GOT AC!
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 I solved D on the fact that given a 3 digit number in which no digit is divisible by 3, there is at exactly 1 segment whose sum is divisible by 3.
•  » » » 19 months ago, # ^ |   0 Okay! DP was more intuitive to me as this problem was similar to a classic DP problem of recursive partitioning.
 » 19 months ago, # |   0 Can anybody please post and explain his/her Solution for D, if it is based on BINARY SEARCH.
•  » » 19 months ago, # ^ |   0 D is just greedy
•  » » 19 months ago, # ^ |   +1 In D you can observe, that every (at least) 3-elements-long subsequence will have correct combination. I swapped all the numbers a for numbers a%3 and then started greedy algorithm. For every i have sum of elements (i), (i + i-1), (i + i-1 + i-2), but first I check, whether any of those numbers was taken previously. For example I store a sum from range (i) (just a single element) and then check if element indexed (i-1) was taken. If it was I don't check further, if it wasn't I can add that in my sum. If my sum%3 == 0, then I mark element i as taken and add +1 to the answer. If I checked only one number, correct answer would only occur if it was == 0(mod 3). If I checked only two numbers, then I would have those combinations of modulo: (0, 0), (1, 0), (0, 1), (1, 1), (1, 2), (2, 1), (2, 2). As you can see only three of these are correct. If I checked three numbers then there would always occur at least one correct subsequence.
•  » » 19 months ago, # ^ |   +1 I solved D by dp
 » 19 months ago, # |   0 Anyone can tell what's wrong with my solution in problem C, I got WA test 12. http://codeforces.com/contest/1005/submission/40145706
•  » » 19 months ago, # ^ |   0 Overflow. Add more powers of 2 and it would work.
•  » » » 19 months ago, # ^ |   0 Aaaah :'(, I can't believe I didn't notice it xD Thanks man.
•  » » » 19 months ago, # ^ |   0 I've considered the last power of 2 which is less than 10^9, Still getting WA.. please check my solution :- My submission
•  » » » » 19 months ago, # ^ |   0 But the sum of two elements can be up to 2 * 10^9. Maybe you need one more power?
•  » » » » » 19 months ago, # ^ |   0 You are right.
 » 19 months ago, # |   +7 Good Contest.Can someone share the idea of E2? My Code work when median value exist only once in the array.
 » 19 months ago, # |   +1 test case 11 of problem D was nightmare for many contestant including me. :p
•  » » 19 months ago, # ^ |   +1 XD it's something like 112
 » 19 months ago, # |   +9 The most interesting div.3 round, with the last 2 problems pretty tough in my opinion.
 » 19 months ago, # |   +1 How did more people solve C than D? D is just classic greedy but I don't even have an idea about C...
•  » » 19 months ago, # ^ | ← Rev. 3 →   +3 If you are currently considering a particular number in the array, there are only log(n) other numbers which, if added to the number being considered, give a power of 2. So we can use hash maps to store numbers and so complexity is O(n*log(2*1e9))
•  » » 19 months ago, # ^ |   0 I don't solve D because I wrote if (!(digit + temp.front()) % 3), notif (!((digit + temp.front()) % 3)) or simple if ((digit + temp.front()) % 3 == 0). And... I don't find the mistake.
•  » » » 19 months ago, # ^ |   0 let x, y, z be the three left-most integers first check x then check y and x + y last, check z, y + z, and x + y + z
•  » » » » 19 months ago, # ^ |   0 ??? I solve this problem after the competition by adding two brackets, as I said before.
•  » » » 19 months ago, # ^ |   +1 Because !(digit + temp.front()) % 3 equals (!(digit + temp.front())) % 3
•  » » » » 19 months ago, # ^ |   0 Can anyone please provide a miniature version of tc 11 for problem D
 » 19 months ago, # |   0 Can anyone explain greedy approach for D?
•  » » 19 months ago, # ^ |   +2 hint: if x, y, z are integers, then at least one of x, y, z, x + y, y + z, and x + y + z is divisible by 3
•  » » » 19 months ago, # ^ |   0 Couldn't point out this fact during contest , instead I kept on storing them :(
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 can u provide a proof for the above statement or an idea to get to above conclusion @keima915
•  » » » » 19 months ago, # ^ |   0 You may use examples to get the feel of it ! eg : 714|3|0|888|222|57
•  » » 19 months ago, # ^ |   +1 Very straight away approach : Iterate over the array , if s[i] is divisible by 3 , increment counter and make num =0 , else store it in num . Each time check if num is divisible by 3 , and if its length crosses "3" , it** must** have already been divisible by 3 => Clear num and increase counter.
 » 19 months ago, # |   0 I'm wondering what would happen if MikeMirzayanov prepared this contest in more than one day.
 » 19 months ago, # |   +1 Whats making it TLE Im still wondering ?? problem — Bcheck
•  » » 19 months ago, # ^ |   0  while(slen>0 && s.equals(t)!=true) { count+=2; s=s.substring(1); t=t.substring(1); slen-=1; } You create new string every time. It is rather suboptimal.
•  » » » 19 months ago, # ^ |   0 But everytime im creating with first character removed from string.
•  » » » » 19 months ago, # ^ |   0 Everytime the whole new string is created, not only the first char is removed
•  » » » » » 19 months ago, # ^ |   0 Can u suggest me alternative for that part of while loop. Thanks
•  » » » » » » 19 months ago, # ^ |   +1 int i=slen-1; while(i>=0&&s.charAt(i)==t.charAt(i)) { --i; count+=2; } 
•  » » » » » » » 19 months ago, # ^ |   0 giving WA bro
•  » » » » » » » » 19 months ago, # ^ | ← Rev. 3 →   0 Checking if strings are equal take too much time — solution has square complexity. . WA — because you need to find the first index from the end of both strings, where s[s.length() — index] != t[t.length() — index]. . codeforces and yes — you are looking for s[9] and t[2], then s[8] and t[1] and s[7] and t[0].
•  » » » » » » » » » 19 months ago, # ^ |   0 Im using substring method of java. Is that making it TLE?? What is time complexity for substring ()?? — is it O(n) or O(1)?
•  » » » » » » » » » 19 months ago, # ^ |   0 I don't know Java, but I heard that it is O(n) in new versions and nearly O(1) in old versions, maybe I'm wrong. Also I'm not sure about the complexity of method equals — it's more probably that O(n).
 » 19 months ago, # | ← Rev. 2 →   0
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 Do you even read that problem? They ask different thing to do. You waste my time.
 » 19 months ago, # |   -8 I thought you said 6 problems "You will be given 6 problems and 2 hours to solve them.".But anyways I enjoyed the round thanks.
 » 19 months ago, # |   0 How do we solve C? Do we optimise the brute force method or use some other approach entirely?
•  » » 19 months ago, # ^ |   0 Enumerate each number, enumerate the power of 2, and subtract the number by 2 power, to see if the result is in the original set.
•  » » 19 months ago, # ^ |   0 From constraint I think brute force should work. Because for each iteration we r finding for two elements at a time.
•  » » 19 months ago, # ^ |   0 There a only 31 powers of two which are less than 2e9, so you can brute-forces over those powers.
 » 19 months ago, # |   0 I did a different approach in D, I first removed all 1 digit no.s and stored the rest no. as various segment, and then iterated over the segments for 2 digits and so on. I am not getting TLE, I and I can prove why my algorithm can pass TLE, but instead a wrong ans on TC 11. Code link: http://codeforces.com/contest/1005/submission/40144526 Thanks :)
•  » » 19 months ago, # ^ |   0 I had the same approach. Couldn't pass it
•  » » » 19 months ago, # ^ |   0 what was your ans for TC11
•  » » » » 19 months ago, # ^ |   0 At first I was getting TLE but my implementation was crazily bad. Then when I implemented properly I'm getting RTE on tc1.
•  » » 19 months ago, # ^ |   0 I too did the same . But there is no need to store segments of size more than 3 , as explained in above comments . So , its just wastage of memory....
•  » » » 19 months ago, # ^ |   0 Did you get AC
•  » » » » 19 months ago, # ^ |   0 Nope , rather I got Run time error on Test 11
 » 19 months ago, # |   +1 An awesome round!
 » 19 months ago, # |   +2 How to solve E1?
•  » » 19 months ago, # ^ |   +1 Note that, in any sequence of numbers that satisfy the condition, m should be included. Also, in total we only care that the number of numbers greater than m minus the number of numbers less than m is 0 or 1. Now, just find for each indez the greater-lesser factor, separately, for indices before the value m and after the value m. Now, just compute using the condition
 » 19 months ago, # | ← Rev. 2 →   0 There is other input similar to test case 11 in problem D? Just to check why I'm getting WA.
 » 19 months ago, # |   0 How to solve E2?
 » 19 months ago, # |   0 Got Wrong Answer on Test 11. What wrong am I doing here ? My Submission: 40139802
•  » » 19 months ago, # ^ |   0 A counter case: 382845 The answer should be 3 but it prints 2.
 » 19 months ago, # |   0 How to solve F?
 » 19 months ago, # |   0 mike's contributor is oo
•  » » 19 months ago, # ^ |   0 0^2 ?
•  » » » 19 months ago, # ^ |   0 oo = infinity
 » 19 months ago, # |   0 Can someone give a Dp solution of problem D and why we are using only 3 values i didn't undertand any solution.
•  » » 19 months ago, # ^ |   0
•  » » » 19 months ago, # ^ |   0 thanks man
•  » » » » 19 months ago, # ^ |   0 how u approach dp problems
•  » » » » » 19 months ago, # ^ |   0 It's two good rules: 1. Find a recursive solution 2. Look for the variable(s) changing in recursion, and store the result obtained for this variable(s) in a map or (something like that). Use this stored value when available.
•  » » » » » 19 months ago, # ^ |   0 https://www.geeksforgeeks.org/memoization-1d-2d-and-3d/ this might help you.
 » 19 months ago, # |   +4
 » 19 months ago, # |   0 I have some questions regarding Problem C: Consider these 2 solutions: *Sol1 *Sol2 In Sol1 on line 36, I have used mp[y]>0 check to see whether y exists in the map mp or not, here y can be negative as well but I have not checked that. This solution results in Memory Limit Exceeded error on 7 test case. However, if I use mp.find(y)!=mp.end() to check whether y is in the map of not, it passes.Can someone please point out why is this happening? If we use unordered_map then the approach in Sol1 will give an infinite loop. Why is this happening? Thanks a lot in advance.
•  » » 19 months ago, # ^ |   0 Mp[y] will insert y in map with default value 0.While Mp.find(x) return iterator to the key x without inserting it. Try this for(i = 0;i <  = 10000000: i +  + ){if(Mp[i] =  = 0){};}And check the memory used.
•  » » » 19 months ago, # ^ |   0 But even after the insertion of elements, only 120000*32 elements will be stored in the map, so why does it give memory limit error? As long long is 64 bit, it will be 29 MB roughly in the worst case. Please correct me if I am wrong.
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   0 you are iterating on the map and simultaneously inserting an element in it. This will cause the invalidation of references. Read thisHere, I have submitted your code just by storing the array in the different map and iterating over it. I have made the same mistake once in a div2 contest. And, BTW your calculation is wrong it is more than 150MB(See This).
•  » » » » » 19 months ago, # ^ |   0 Oh, I understand it now!But can you please tell me where I went wrong with the calculations?Thanks a lot for your generous help.
 » 19 months ago, # |   0 Its v.nice
 » 19 months ago, # | ← Rev. 2 →   0 I am getting runtime error with "Exit code is -1073741819" message on solution for D.here is my code : http://codeforces.com/contest/1005/submission/40144266Can anyone point my mistake out??
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 I don't think you can clear a set/list while iterating through it. So if you remove s.clear() from line 39 (from the first submission you linked) and only clear it if p is set to 1 after the loop, it should work without crashing.
•  » » » 19 months ago, # ^ |   0 I have a sort of similar query too:Consider a map mapmp. and now you are iterating it and using it like below: for(auto x:mp){ x.s=1; } This produces errors and undefined behaviors. Why? Thanks a lot in advance.
•  » » » » 19 months ago, # ^ |   +1
•  » » » » » 19 months ago, # ^ |   +3 Thanks a lot!
 » 19 months ago, # |   0 My last submission to problem C in the round has passed test 7 and 11 and it was AC and after system testing it's now WA on test 7 ! And I also want to know that why unordered_map worked her and map was so slow I didn't face such issues in a CF problems before !
 » 19 months ago, # |   0 My code of problem C got accepted on testcase 7 in contest time but gave TLE in system testing. Can anyone help. I total made 5 submission in which third one got accepted. In which 4 gave runtime error at testcase 7 while third submission got accepted. But in system testing got TLE. Please anyone explain.
•  » » 19 months ago, # ^ |   0 I have the same issue and after the contest I have submitted a a solution with unorderedmap and it is AC now while the solution with map failed in test 7 although it has passed this test before
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 It passed with simple map after the system testing and failed during the system testing. Both are same code.This is the code I submitted during contest: http://codeforces.com/contest/1005/submission/40135410This is the same code I submitted after the contest and got accepted http://codeforces.com/contest/1005/submission/40160479I didn't used unordered map. Passed with simple map. Anyone please explain this.
 » 19 months ago, # | ← Rev. 2 →   +1 Can anybody help me out I can't understand why my same solution is both TLE and AC. AC:40160742 TLE : 40160895 It has cost me a problem in this contest which I was sure would pass the test cases.
•  » » 19 months ago, # ^ |   0 Bro same happened to me.
 » 19 months ago, # |   0 Can someone please tell me what's the error in this approach from Problem D? Solution
 » 19 months ago, # | ← Rev. 2 →   +19 WoW! I get rank 2!I pass E2 with Balanced_Tree in Segment_Tree. But in fact using fenwick tree can pass E1 and E2, in this way, the length of code can be reduced much.
•  » » 19 months ago, # ^ | ← Rev. 2 →   +4 Orz Akfun!Akfun is our red_sun!
•  » » 19 months ago, # ^ |   0 Orz Akfun!Akfun is our red_sun!
•  » » 19 months ago, # ^ |   +4 Orz AKfun!AKfun is our red_sun!(human is fundamentally repeater
•  » » 19 months ago, # ^ |   +3 Orz AKfun!AKfun is our red_sun!
•  » » 19 months ago, # ^ |   +4 Orz Akfun! Akfun is our red_sun!
 » 19 months ago, # |   -6 Your crafting.oj.uz ratings are updated!
 » 19 months ago, # |   0 my code coincided with one of the other coders and i dont know how it got copied . I generally code on ideone but i dont know much about its settings . would i be penalised for that ??
 » 19 months ago, # |   0 if x, y, z are integers, then at least one of x, y, z, x + y, y + z, and x + y + z is divisible by 3 ****__ can anybody provide a proof for the above statement or an idea to get to above conclusion
•  » » 19 months ago, # ^ |   0 There aren't so many cases: 1) one of the numbers x, y and z is divisible by 3. 2) all of them aren't divisible by 3 — the variants for the rests of division are: (x % 3 = 1, y % 3 = 2) or (x % 3 = 2, y % 3 = 1) — then (x + y) % 3 = 0.Other cases: 111, 112, 221, 222. that's all.
 » 19 months ago, # |   0 For E1 after changing m to 0 and numbers less than m to -1 and greater than m to +1 one can iterate though the prefix sum and count answer with the help of a map like here Can a similar approach be used for E2 by accounting for the number of zeros also ? I was not able to think of any O(n)or O(nlgn) solution like iterating and using map in E1. Any help?
 » 19 months ago, # |   0 Any help will be appreciated, WA in test 11 problem D Link.
 » 19 months ago, # |   0 I don't know how halyavin was successful in hacking so many of our solutions for problem C. Can someone explain me the Generator Algorithm he used? It would be great to understand what that algorithm did to exploit the weakness in so many solutions. Thanks!His generator
•  » » 19 months ago, # ^ |   +1 It creates O(n2) test for Arrays.sort in Java. Only sorting of primitive arrays can be exploited — sorting Integer[] or Object[] is fine. All the complications are needed so that generator doesn't require O(n2) time itself.
•  » » » 19 months ago, # ^ | ← Rev. 3 →   0 Thanks a ton! This is sooo awesome!! :)
•  » » » 19 months ago, # ^ | ← Rev. 4 →   0 Thank you :)
 » 19 months ago, # |   0 Can anyone please explain me of problem C. I also read editorial. But still i didnt get it that how can it do easily to using map. Thanks.
•  » » 19 months ago, # ^ |   0 For every element you need to find , whether there is another number which on summing gives a number of the form 2^d (i.e.,a number which is a power of 2 ) . So , first create an array which stores all the powers of 2 till 10^9 , then for every element , iterate over this array (powers of 2) and take the difference between both and check whether this difference exits in your original array excluding the current index (You can do this using a map/binary_search). If there is no such element increment your count value and finally print it !
•  » » » 19 months ago, # ^ | ← Rev. 4 →   0 Thanks furious__ got AC.
•  » » » » 19 months ago, # ^ |   0 That's ok mate !
 » 19 months ago, # |   0 Sorry, I'd like to ask you. How can I solve problem D in DP?I can't understand why we solve this problem in DP.
 » 19 months ago, # |   -8 https://drive.google.com/file/d/1uBBOkG7DvJsU-W2NQV3q-TaurdH1XRGd/view?usp=sharing Is it a error? I test the program on my computer give a correct answer and the web give me a wrong answer.Can you test and check that ?
•  » » 19 months ago, # ^ |   0 In your solution the problem is with int t = log(i) / log(2). log() and power() works with double. Just remove this string and change to return i==pow(2,log(i) / log(2)). The type will be double and all will be OK.