pitfall's blog

By pitfall, 5 years ago, translation,

Hello everyone

On Monday, December 19 at 19:35 MSK held Codeforces Round # 388 for participants from the Div.2. Participants from the Div.1 may participate out of the competition.

This round was prepared by Denis pitfall Bezrukov, Alexey dalex Dergunov, Vyacheslav Slamur Muravev, Egor Petruchcho Ponomarev, Pavel craus Semushin и Andrey Shlakoblock Gaidel.

For me and Slamur and Petruchcho this will be the first round. We hope that everyone will find interesting problems.

Great thanks to Gleb GlebsHP Evstropov for his help with the contest preparation and Mike MikeMirzayanov Mirzayanov for the Codeforces and Polygon systems.

UPD: You will be offered 5 problems and 2 hours for solving them.
Scoring: 500-1000-1500-2000-2500

Congratulations to the winners!

Div.2:

1. just29
2. tnbt
3. el_smurfo
4. SimB4
5. skydog

Div.1:

1. I_love_Tanya_Romanova
2. W4yneb0t
3. enot110
5. Um_nik

UPD: Editorial available here

• +257

 » 5 years ago, # |   -109 It is incomplete without this. ** ** *****?
•  » » 5 years ago, # ^ |   +68 Yes, it is rated.
•  » » » 5 years ago, # ^ |   +13 Why does the guy who answers that question get upvoted? Anything can happen on CF. :/
•  » » » » 5 years ago, # ^ |   +25 He is the writer, that's why :p
•  » » » » » 5 years ago, # ^ | ← Rev. 3 →   0 LOL didn't see that. Forgive me Master pitfall ! :P
•  » » » 5 years ago, # ^ |   -7 Can one please help me As Scoring: 500-1000-1500-2000-2500 But whose rank is in be 2000 to 2200 Got negative ratings Please explain
•  » » » » 5 years ago, # ^ |   0 Before updating your rating after the end of the round, for each participant his seed is calculated, that is the place that the participant is expected to take in this competition. Thus, two things are known for each participant — his seed (the expected place) and rank (the actual place). Depending on the difference between these two values, your rating increases or decreases. If the difference is higher, your rating changes more.You can read more about it here: Codeforces Rating System — Codeforces
•  » » 5 years ago, # ^ |   -32 Fixed: It's held at the unusual usual time.
•  » » » 5 years ago, # ^ |   0 No, it is held at the usual unusual time.
 » 5 years ago, # |   +30 It would have been much better to have these contests on two different days this week instead of having 2 contests on the same day and then not having any contest till next week.
•  » » 5 years ago, # ^ |   +6 If this is the time chosen by the CF management, there must be a reasoning behind it.
•  » » 5 years ago, # ^ |   +6 Acctually Codeforces round 386 and 387 is held on the tasks of the municipal stage All-Russian Olympiad of Informatics 2016/2017 year in city Saratov. But the Codeforces round 388 is an usual Codeforces div2 round. That's why we have 3 contest in just under 24 hours, the first 2 is like mirrors of the Olympiad and the last is the usual round.
 » 5 years ago, # |   -24 Time is usuall but nember of problem isnt : (
 » 5 years ago, # |   +154
 » 5 years ago, # |   +15 A previous contest had very fast system checking and rating changes. Hope this one will be the same! Though it is so unusual to write contest in the morning and then on the same day at the evening =))
 » 5 years ago, # |   0 Hope I will not repeat my usual mistakes and solve first three problem ASAP. Maybe life is nicer as Blue.
•  » » 5 years ago, # ^ |   0 All the best !
•  » » » 5 years ago, # ^ |   +3 Thank you. But It didn't happen. C was easier for me than B, but B eaten all the time :(
•  » » 5 years ago, # ^ |   0 It will be!
•  » » 5 years ago, # ^ |   0 epic comment :P
 » 5 years ago, # |   +10 thx a lot for these consecutive contests (#388,#387,#386,#385)...it helps our ACM team for ICPC-Tehran Region
 » 5 years ago, # |   +13 Wish me luck! I'm at only 25 points of Div. 1. These 2 days of contests have favoured me.
•  » » 5 years ago, # ^ |   +4 Good luck! And I wish I can be the witness^_^
•  » » 5 years ago, # ^ |   +3 Just 3 points, fighting!
•  » » » 5 years ago, # ^ |   0 Oh, you got blue! Congratulations!
•  » » » » 5 years ago, # ^ |   0 Thx :D
 » 5 years ago, # | ← Rev. 2 →   +7 Perfect time for programmers from Bangladesh :)
 » 5 years ago, # |   0 There are a great many of contests in the end of term :D
 » 5 years ago, # |   +2 Expecting interesting and doable problems.Thanks Codeforces for organising so quick rounds and really appreciable work done by all the problem setters.All the best everyone!!! :)
 » 5 years ago, # | ← Rev. 3 →   +4 Good decision the number of problems decreased to 5! (Pennyroyal_Tea this is not factoriel). thanks
•  » » 5 years ago, # ^ |   +29 I guess even tourist can't solve 120 problems in 2 hours, so 5! is too much I believe.
•  » » » 5 years ago, # ^ |   0 The joke is cold haha
•  » » » 5 years ago, # ^ |   -11 You never know , he is GOD !
 » 5 years ago, # |   +1 Hope not to drop after doing well last contest.
 » 5 years ago, # |   +5 my 3rd contest on CF in 30 hours!
 » 5 years ago, # |   +4 Good luck everyone ! Hope everyone gets what he deserves !
 » 5 years ago, # |   +11 and now the pleasure comes to it's end...
 » 5 years ago, # |   +1 I wish this contest will be great for all of us
 » 5 years ago, # | ← Rev. 2 →   +5 I think, this is my first time when I Submitted 3 code, all got pretests passed. I hope it stays as good. I gave up on problem D and E.Actually 5 submission, but the other two was wrong programming language, and forgetting reading input which make it fails on the first testcase.lesson learned, if you hardcode the problem testcase: don't use the first example.
•  » » 5 years ago, # ^ |   0 Don't give up yet!! You can do it!!
•  » » 5 years ago, # ^ |   +1 Also the first time for me by solving A,B and C!All three passed :D
 » 5 years ago, # |   0 Can someone explain problem E's statement?
 » 5 years ago, # | ← Rev. 2 →   +14 First time solved 4 problems. Hope they will all pass :D
•  » » 5 years ago, # ^ |   +11 Your rating will go up like a rocket :)
•  » » 5 years ago, # ^ |   0 Nice rating change :D Congratz!
•  » » » 5 years ago, # ^ |   +4 Thanks :D
•  » » 5 years ago, # ^ |   +11 Look at your new rating color! Anyway, nice rating graph :)
•  » » 5 years ago, # ^ |   0 congratoulation ✌
 » 5 years ago, # |   +4 Bbye Blue
•  » » 5 years ago, # ^ |   0 Was Blue for less than a day. Back to Cyan for me now!
•  » » 5 years ago, # ^ |   0 You will be back to blue soon!
 » 5 years ago, # |   0 What's the C hacking case was please?
•  » » 5 years ago, # ^ |   0 Mine was: 21 DDDDRRRRRDRDRDRDRDRDR
•  » » » 5 years ago, # ^ |   0 What should be the answer?
•  » » » » 5 years ago, # ^ |   0 Answer is R
•  » » » » » 5 years ago, # ^ |   +3 Why is it R?
•  » » » » » » 5 years ago, # ^ |   0 I explained here
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 My answer is DUPD: wrong
•  » » » » » 5 years ago, # ^ |   0 Yes, it's wrong. 21 DDDDRRRRRDRDRDRDRDRDR: here first 4 D's will beat any 4 R's but one R in first R's group will stay anyway. So, after each full iteration we will have this sequence of state: 11 DDDDRRRRRRR => 4 DRRR => 2 RR, so R is winner.
•  » » » » » » 5 years ago, # ^ |   0 could you please explain test#21 of this problem? (7 RDRDDRD) i am getting R in this (correct is D).
•  » » » » » » » 5 years ago, # ^ | ← Rev. 3 →   +3 RRDDRD RRDRD RRDD RDD RD D D
•  » » » 5 years ago, # ^ |   +3 What is answer?
•  » » » 5 years ago, # ^ |   +4 The answer is R, isn't it?
•  » » » » 5 years ago, # ^ |   +3 Yes
•  » » » 5 years ago, # ^ |   0 What's the correct output?
•  » » » 5 years ago, # ^ |   0 What is the answer for that?
•  » » » 5 years ago, # ^ |   +3 Well RIP my C :(
•  » » » » 5 years ago, # ^ |   0 mine too :)
 » 5 years ago, # |   0 Hack case for C
 » 5 years ago, # |   0 :( :( :(
 » 5 years ago, # | ← Rev. 2 →   +3 I think I will lose around 50 points.. I checked my program for B on wrong input, thought it was wrong and resubmitted it again.. Turns out it was correct earlier.. Lost 300 points, and fell 700(!) spots on the standings... :(
 » 5 years ago, # |   +10 Very interesting contest, thanks to pitfall
 » 5 years ago, # |   +3 Who else tried to simulate C? Worst decision of my codeforces life -_-
•  » » 5 years ago, # ^ |   +4 I got passed pretest with simulation.
•  » » 5 years ago, # ^ |   0 I did... It was passing pretests with 998ms. So I rewrote it and now I realized my rewritten solution is wrong.
•  » » » 5 years ago, # ^ |   0 And I didn't even finish my first solution ;_; . Linked list and shit. I knew it was a hacking problem, so simulation felt safe. Never again would I ever again.
•  » » 5 years ago, # ^ |   +2 If you simulated using a queue, it was easy and fast. (And correct, I hope)
•  » » » 5 years ago, # ^ |   0 Queue didn't come to mind sadly. Sets take a lot of time to erase( from previous experience ), so I jumped to linked lists ;_;
•  » » 5 years ago, # ^ |   0 You could simulate and even afford an extra log factor(I did this and got 778 ms main tests) for total O(n lg^2 n)
•  » » 5 years ago, # ^ |   0 I used simulation and got Accepted
•  » » 5 years ago, # ^ |   0 I simulated it, but I used next array (using DSU) to avoid TLE. Which is to jump over the cells that are already deleted. 23151066 my run time is 15 ms because the complexity in total is O(n).
•  » » » 5 years ago, # ^ |   +5 I used simulation on input array with two pointers and bool array of deleted and got AC. You won't get TLE cause it's O(n*logn). 77ms in my case
•  » » 5 years ago, # ^ |   0 I simulated it. I used two set and lower_bound in them. 23155161.PD.: Sorry for my horrible English.
•  » » 5 years ago, # ^ |   0 I'm simulating using list as well, (well array because python doesn't have native list, but it behave like list)
 » 5 years ago, # | ← Rev. 2 →   +5 Solution to B could easily be found on google.
 » 5 years ago, # |   +4 Seems like editorial for problem B is published even before starting the contest. :3Link
•  » » 5 years ago, # ^ |   0 Finding vertices from midpoints of sides of a triangle.
 » 5 years ago, # |   0 Can someone explain why this interpretation of E is wrong?Choose the segments: [2], [3], [1], [2, 3], [3, 1], [2, 3, 1]For the first three, there is 0 chance of an inversion. For the fourth and fifth, there is 1/2 chance, so the expected value from those is 1/6*1/2*1 = 1/12. For the sixth, you can have [1, 2, 3] = 0, [1, 3, 2] = 1, [2, 3, 1] = 2, [2, 1, 3] = 1, [3, 2, 1] = 3, [3, 1, 2] = 2. So the expected value is 1/6 * 1/6 * 9 = 1/4.Isn't the answer then 1/3?
•  » » 5 years ago, # ^ |   +6 You permutate the smaller segment but the whole array still exists.
 » 5 years ago, # |   +3 It didn't take me much time to solve ABC, but failed to figure out the last two
•  » » 5 years ago, # ^ |   0 I know that feel, bro. I hope we don't fall in our ranking
 » 5 years ago, # | ← Rev. 2 →   0 if your C solution is just deleting the first undeleted instance of opposite party (which apparently passes pretest) then it can be hacked. My hack case for this was: 6 DRRDRD. As an example, the wrong program would say: pos 0 kills pos 1, pos 2 kills pos 0, pos 3 kills pos 2, pos 4 kills pos 3, and pos 5 kills pos 4, hence the only alive is pos 5 which is D.
•  » » 5 years ago, # ^ |   0 What should be the correct answer?
•  » » 5 years ago, # ^ | ← Rev. 6 →   0 How can the answer be D?My answer is R, btw.And I use the 'wrong' algorithm.UDP: And I passed the system test.
•  » » » 5 years ago, # ^ |   0 Everyone here seems to misunderstand what he meant. He said the first undeleted instance not the next one. My hack case for this was: 6 DRRDRD. As an example, the wrong program would say: pos 0 kills pos 1, pos 2 kills pos 0, pos 3 kills pos 2, pos 4 kills pos 3, and pos 5 kills pos 4, hence the only alive is pos 5 which is D. If he meant the next undeleted instance, he would write "pos 2 kills pos 3" and so on.
•  » » 5 years ago, # ^ |   +1 My solution is just deleting the first undeleted instance of opposite party,and it PASSED the system test.
 » 5 years ago, # |   0 How solve E?
•  » » 5 years ago, # ^ | ← Rev. 6 →   +5 Consider positions i and j, then element at pos-j can be less than element at pos-i only if we choose a segment that covers both i and j and then choose an appropriate permutation. Suppose we fix the segment, then above prob = P(for any r-length segment) = (put j before i if i is placed at pos=k) = 1/r*(sum(k=1..r) (k-1)/(r-1)) = 1/2. So, just calculate number of segments that cover positions i and j(for all i,j) and multiply overall by 0.5. 1. For ij a[i]>a[j] we have to sum P=1-(i+1)*(n-j)/(n*(n+1)) to our final result. Both can be done similar to finding inversions either using divide and conquer(like my solution: http://codeforces.com/contest/749/submission/23156836 ) or BIT for O(n*log(n)).
•  » » 5 years ago, # ^ |   0 linearity of expectation for a pair i , j , such that i < j the probability of j become more than i is p where , so if ai < aj , add p to answer else add 1 - p to answer. To do this in O(NlogN) , use bit.
•  » » » 5 years ago, # ^ |   0 Can you explain a little more? i and j affect other indices as well. Can you show that linearity is justified here?
 » 5 years ago, # |   +8 No more contests? But I got used to these consecutive contests :(They were really fun though, thanks codeforces :)
 » 5 years ago, # |   0 How to solve C without simulating it?
•  » » 5 years ago, # ^ |   +1 Actually you have to simulate it, but in an efficient way. One way is to use queues, you can use, 1 for all people who is available to vote, other for people in R and other with people in D. The trick here is to realize than in every "iteration" people alive is greatly reduced.
 » 5 years ago, # |   0 I was trying D with square root decomposition. In each bucket, I maintained how many times a number is occuring in cnt[bucket][x] and tot[bucket] is the number of elements in this bucket. Finally start from last bucket and if count of numbers (given in query) in present bucket equals to the tot[bucket], then this bucket is useless and go to bucket-1. I couldn't submit and check though. Has anyone done like this?Link to code
 » 5 years ago, # |   0 D was awesome ! However, I couldn't finish it's coding before the contest ended. I was using segment tree and storing bids in it. Was I going in correct direction ?
•  » » 5 years ago, # ^ |   0 YES :D. I use the same solution :)
 » 5 years ago, # |   0 How to solve D?
•  » » 5 years ago, # ^ |   +3 i used parallel binary search but i guess its probably overkill
•  » » 5 years ago, # ^ |   0 I used the following approach. Let's insert every people into set. And just delete peoples in query when query comes. Now last element of set is people who won. And now you can erase last element of set and find money. After everything is done you should insert everything you deleted.
•  » » » 5 years ago, # ^ |   0 Did this solution passed system tests?
•  » » » » 5 years ago, # ^ |   +8 yes
•  » » » 5 years ago, # ^ |   0 Sir I used the similar approach but i m getting TLE (Time Limit Exceeded)I inserted all auctions in a map with keys as the amounts (since they are distinct) I stored all amounts and auctioners in two arrays(named as arra,arrp) to store sequence in which the auctions were made.Now in each question, I deleted the k elements and on deleting each one of such k element , i check the position of this deleted auction in arrays arra and arrp .Let it be pst. Then i check if pst-1 and pst+1 have same auctioner. if yes i delete the auction at pst +1 I m getting TLE . This is my code How did u check the condition if we remove an elemment its prev and next may be same How to remove right one?Even if we ignore that for q questions we are inserting k elements in the set or map each insertion/deletion taking log(n) time giving total time complexity of O(q*k*log(n)) where n <= 200000 and q<= n and k <= n will this approach satisfy constraints?
•  » » » » 5 years ago, # ^ |   0 You are deleting all of k people's bids, which can be equal to n some times if you sum the number of bids for each k peraon. This way there can be a test case with 2 people, each made 100,000 bid, and 200,000 queries asking you to delete these 2 people.. this way the complexity will be O(n*q*log(n)) which is too much.
•  » » » » » 5 years ago, # ^ |   0 Then sir what is the correct approach?
•  » » » » » » 5 years ago, # ^ |   0 You must keep only one version of each person (only the last bid) and sort them by their last bid in a set for example. now if you remove the k people deleted, then the total complexity for all queries will be O(x * log(n)) where x is the sum of all k s which is at max 200,000. After removing the k people, the person who won is in the end of the set. To determine in which bid this guy won, you should have a vector for each person which his bids. You can do a binary search to find the answer. now before moving to the next query. Add the deleted people back to the set. also total of O(x*log(n)).
•  » » 5 years ago, # ^ |   0 i used a set to put every person's "best" bid in it. i also made sets for each individual person which contained all of their bids. Now for every query , i traversed the bestbid set from end, when i found the bestbid whose bidder is still available (to do this i used binary search on all bidders who didnt come). the bidder no can be known using this,let him be y.but the bid maybe lesser than the bestbid of this person,so i again travelled the bestbidset to find another such person who came. if his bid was x , then i have to search bid greater than x in y's bids.i used lowerbound for this purpose.i use x=0 if no x is available.
 » 5 years ago, # | ← Rev. 2 →   0 why does this code passess while this does not for problem B? I only used 'cout<<3<
•  » » 5 years ago, # ^ |   0 You shouldn't use printf with ios base synchronisation turned off.
•  » » » 5 years ago, # ^ |   0 The order between printfs and couts has no guarantee
•  » » 5 years ago, # ^ |   +3 Because you use std::ios::sync_with_stdio(false). If you use this line in your code then it's better not to use scanf/printf. It will be a mess because iostream and stdio can't sync thus the order of output won't be same as you expected.
•  » » » 5 years ago, # ^ |   0 bummer i didnt know that i only saw on a blog of cf that it makes cin and cout as fast as scanf and printf and thats y i was using it just like that :(
 » 5 years ago, # |   +10 C test case 21 anyone? :(
 » 5 years ago, # |   +13 Extremely fast system testing...
 » 5 years ago, # |   +24 Wow this system testing was faster then the time it took me to fall from expert to specialist
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 The C is easier than B, but I failed C.:P
•  » » » 5 years ago, # ^ |   +7 In my opinion, B was much easier.
 » 5 years ago, # |   0 My solution C simulating statement is accepted. is there any solution without simulating?
 » 5 years ago, # |   0 In problem B, Test Case 4:1000 1000 -1000 -1000 -1000 1000Ans shouldn't be 3?3 1000 -1000 1000 3000 -3000 -1000-3000 and -1000 does make a parallelogram with other 3 points, doesn't it?
•  » » 5 years ago, # ^ |   0 Yes it does.
•  » » » 5 years ago, # ^ |   0 My silly mistake. Stupid I am. :|
•  » » 5 years ago, # ^ |   0 For all case answer will be three and one can easily get the solution in google. A little bit changed in problem would be better.
 » 5 years ago, # |   +2 Is it just me or was the system testing really really fast ????:)
•  » » 5 years ago, # ^ |   0 Yeah, Ive also noticed this
 » 5 years ago, # |   0 Hi guys,Could anybody tell me where is the editorial for the problems? Got stuck in C.Thank you very much!
•  » » 5 years ago, # ^ |   0 It's not posted yet but U can look at my solution here if U want...my code:)
 » 5 years ago, # |   0 So what's the real solution for C please , I'm pretty sure i'll be around 1899 because of this C haha.
•  » » 5 years ago, # ^ |   0 I used a queue to simulate..
•  » » 5 years ago, # ^ |   0 You can use set to simulate the optimal moves.
•  » » 5 years ago, # ^ |   +11 The solution I used is O(nlogn). The current candidate removes the next voting candidate of the opposing party. Use std:: to keep track of available voters.
•  » » 5 years ago, # ^ |   0 I kept two treesets (ordered sets for c++) holding the indexes of each R and each D. starting from 0, I simulated each D skipping the next valid R, and each R skipping the next valid D. What I would do is delete them from the tree set when someone was skipped. Additionally, Tree sets allow you to query the lowest number greater than a given index in log(n) time. So my solution was O(n*lg(n))
•  » » 5 years ago, # ^ |   +4 I think simulation is the correct solution. It can be proved that after each step, the total no of non eliminated voters will be at least halved. That guarantees atmost log(n) steps of the simulation. Using queues the simulation can be done in linear time. So the overall complexity is O(nlogn).
 » 5 years ago, # | ← Rev. 3 →   +3 The pretests of C are very weak
 » 5 years ago, # |   +1 When you finish your code and it gets AC just after contest ... :(
•  » » 5 years ago, # ^ |   +3 lol i understand that,it happened to me twice today ... mrning and night :(
•  » » » 5 years ago, # ^ |   +6 that is better than not getting the solution
 » 5 years ago, # |   0 Great! Two contests and I was first in my room in both! :)Today is definitely my lucky day...
 » 5 years ago, # |   -6 What the ***k is going on C on 21!!!
 » 5 years ago, # | ← Rev. 2 →   0 7 RDRDDRD How the ans is D for this case ? :/
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 R at pos 1 will ban pos 2 from voting.R at pos 3 will ban pos 4 from voting.D at pos 5 will ban pos 6 from voting.D at pos 7 will ban pos 1 from voting.Now string is RDD.Pos 1 bans pos 2.Pos 3 bans pos 1.So D.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 RDRDDRDINITIALLY R-1,3,6 D-2,4,5,7POS=1 R-1,3,6 D-4,5,7POS=3 R-1,3,6 D-5,7POS=5 R-1,3 D-5,7POS=7 R-3 D-5,7POS =3 R-3 D-7POS =7 R- D-7ANS D
•  » » 5 years ago, # ^ |   +5 everyone will play optimally.RDRDDRD ->R.RDDRD ->R.R.DRD ->R.R.D.D ->..R.D.D ->..R...D ->......Dhope you understand.
 » 5 years ago, # |   +7 find difference between this two solutions:except that they are stupid
•  » » 5 years ago, # ^ |   0 jury take a long time to check your solution , jury's problem
 » 5 years ago, # | ← Rev. 2 →   0 Why RE36? Problem C link
•  » » 5 years ago, # ^ |   0 S1.erase (pos); u[*pos] = 2;You are deleting the iterator before accessing it.
•  » » » 5 years ago, # ^ |   0 Okey, thanks)
 » 5 years ago, # |   0 can someone say why in C : 7 RDRDDRD must be D ? i traced it and found it is R
•  » » 5 years ago, # ^ |   0 R at pos 1 will ban pos 2 from voting.R at pos 3 will ban pos 4 from voting.D at pos 5 will ban pos 6 from voting.D at pos 7 will ban pos 1 from voting.Now string is RDD.Pos 1 bans pos 2.Pos 3 bans pos 1.So D.
•  » » 5 years ago, # ^ |   0 First two R-s kill their neighbor D-s.It turns to RRDRD, where the third D is about to vote. Next you expell the fourth R -> RRDD, the rightmost D is voting.RDD -> D wins
•  » » 5 years ago, # ^ |   0 mmm, now i see, i didn't think that killing the 1st unkilled instance would make a difference
 » 5 years ago, # |   +1 In problem C, many submissions fails with test case:8 DRRDRDRD
•  » » 5 years ago, # ^ |   0 answer is R ??
•  » » » 5 years ago, # ^ |   0 yes
 » 5 years ago, # |   +1 Almost TLE (**1996 ms**). http://codeforces.com/contest/749/submission/23157019
 » 5 years ago, # |   +5 Lol...the system testing was fast so I guess CF will take its time on the rating change :D
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 They didn't..
 » 5 years ago, # |   0 nice contest!
 » 5 years ago, # | ← Rev. 5 →   +1 Wait, what?"Became Expert" instead of "Became Candidate Master""Became Specialist" instead of "Became Expert"Update: ok, it was fixed. :-)
 » 5 years ago, # |   +4 My solution to problem C keep 4 variables how many D's are left ( cntd ) , how many R's are left (cntr) , how many D's will be removed (remd) and how many R's will be removed (remr) also keep a boolean array (ban) to know if the current char is banned or not.now iterate over the string if you found a 'D' you check first if it is banned or not , if not you check the variable remd which is incremented when an 'R' is encountered if remd was zero this means that the number of 'D's to be removed is zero, so you survive this round and also get to vote to ban an 'R' so you increment remr (so that next time you iterate on an 'R' char you ban it and decrease remr since you already banned one 'R' )you keep repeating this while(cntd && cntr) so you will exit the while loop whenever the number of R's is zero or the number of 'D's is zero then its easy to determine which party have won if cntd ==0 then 'R' won otherwise 'D' have wonmy submission link : http://codeforces.com/contest/749/submission/23153380
•  » » 5 years ago, # ^ |   0 Similar solution
 » 5 years ago, # | ← Rev. 2 →   +3 pitfall Plz reply, Why am I skipped?
•  » » 5 years ago, # ^ |   0 becuase you are cheater!
•  » » » 5 years ago, # ^ |   +6 You sure about that?
•  » » » » 5 years ago, # ^ |   0 possibly because in any of your submission your code matches with someone else code if it happens even in one problem only then also your contest is skipped i guess you shouldn't try to cheat next time
 » 5 years ago, # |   +14 problem D today... let's do a binary search.... ohh... let's do that again... just one more time :3
•  » » 5 years ago, # ^ |   0 hahaha .. true that
 » 5 years ago, # |   0 Guys help. my compiler shows right answer but displays another answer on judge's compiler. why is that ? am i submitting my code using the wrong compiler ? my code
•  » » 5 years ago, # ^ |   0 Is there any variable that is used uninitialized? Different compiler on different machines will assign different values to those variables;
•  » » 5 years ago, # ^ |   0 You'll see the true code from pitfall. Just wait.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +4 My compiler does not even allow it to compile, because error C4700: uninitialized local variable 'rf' used error C4700: uninitialized local variable 'df' used 
•  » » 5 years ago, # ^ |   0 Variable rf is not initialized, so it gets a rubbish value which can be 0. thus rf = 0 => no while loop => !rf is true => printed answer is D.
•  » » » 5 years ago, # ^ |   +5 Thanks!
 » 5 years ago, # |   0 I can't find bug in my code. According to other contestants my algorithm is OK, but it contains bug. Can someone help me please?
•  » » 5 years ago, # ^ |   +3 Line 59: long long cur = check(mid); if(cur + 2 <= n - mid) { ans2 = mid; l = mid + 1; } Cur + 2 is incorrect. There can be more than one bid of same person after mid value. Check this case: 5 1 1 2 2 1 3 2 4 1 5 1 1 2 `
•  » » » 5 years ago, # ^ | ← Rev. 4 →   0 I know, but (this) second binary search just needs to find the second not deleted element. It doesn't matter if it is from the same person as first binary search. And I think, that my answer to your test case is OK (my program outputs 1 3).UPD: Thank you very much, now I understand what is the problem.
 » 5 years ago, # |   0 Dealing with an odd issue with problem B my solve is here https://paste.ubuntu.com/23655011/ it's showing every thing ok in my IDE but showing less output in codeforceInput 0 0 1 0 0 1my IDE output 3 -1 1 1 -1 1 1codeforce output 2 1 -1 1 1remember the order doesn't metter
•  » » 5 years ago, # ^ |   0 Same, changed set to map and got TLE(yet the output was correct)
 » 5 years ago, # |   +1 std::set contest :(
 » 5 years ago, # |   0 I think there are like 5-7 players from div1 with fake accs in top10 of div2. Is this legit? Why are not such people get banned?
•  » » 5 years ago, # ^ |   +17 The only important thing in this site is learning. If someone's first priority is high rating update then why should we bother? We need to concern about how much we learn new things from every contest and can apply them in the future. May be banning them is a solution but its not the best solution. Cause there will always be fake ids. So just ignore them and keep focusing on learning new things. Thanks :)
 » 5 years ago, # |   +1 Missed D because of not checking if the lower_bound exceed the range. Such a disappointment :(
 » 5 years ago, # |   0 Ummm...tutorial???:)
 » 5 years ago, # |   +6 Regexing in C — 23162742 (more readable version — 23154376)
 » 5 years ago, # |   0 Can one please help me As Scoring: 500-1000-1500-2000-2500 But whose rank is in be 2000 to 2200 Got negative ratings Please explain
•  » » 5 years ago, # ^ |   0 Your rating change depends on your position in the standings not on problems scores .If your position in the standings was better than your expected position(you can sort the registerants in the contest by rating to get an idea of your expected position in the standings before the contest starts) your rating increases otherwise it decreases .
 » 5 years ago, # |   0 Hoping some C++ expert can help me understand this issue. Here is my submission to problem D: http://codeforces.com/contest/749/submission/23158205Strange behaviour 1. It fails for 2nd query on #56. If I run the code on local, I observe the 2nd query is indeed answered correctly. 2. It fails on #56 when C++ 11 is chosen, but fails on #54 when C++ 14 is chosen.My local env:Apple LLVM version 8.0.0 (clang-800.0.38) Target: x86_64-apple-darwin16.1.0 Thread model: posixMac OS sierra 10.12.1
•  » » 5 years ago, # ^ |   +6 Deleting iterator/element from map, then using its values like a boss? Slight changes makes it accepted: http://codeforces.com/contest/749/submission/23164706
•  » » » 5 years ago, # ^ |   0 Hey, thanks !!! Should have noticed it.
 » 5 years ago, # |   0 Can anyone provide me the test case 54 of 749C - Голосование or any shorten form of it ?
 » 5 years ago, # | ← Rev. 2 →   0 23166401 and 23166364 are nearly the same. Yet one passes and the other fails on testcase 10! I believe that the largest difference is the use of vector reverse in the failed submission, but how would this matter?
•  » » 5 years ago, # ^ | ← Rev. 3 →   +5 UPDATE: I found you've reverse the relationship so what I said was wrong , now I didn't see what's wrong either. UPDATE2: I was stupid and compared with the wrong submission number, actually you did forget to reverse the binsearch function
•  » » » 5 years ago, # ^ |   0 Oops. Thanks!
 » 5 years ago, # | ← Rev. 3 →   0 DIV 2 PROBLEM D http://codeforces.com/contest/749/submission/23409556 http://codeforces.com/contest/749/submission/23175395 The first code gives TLE on Case 10,the second one gets accepted. Can someone help me in figuring out what is wrong in Code 1 that gives the verdict as TLE though the approaches used are same ?