By pikmike, history, 5 months ago, translation, ,

Hello Codeforces!

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

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

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

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir Vovuh Petrov, Ivan BledDest Androsov, Maksim Ne0n25 Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Hello Codeforces,

We would like to invite all of you to Mike Mirzayanov's course Advanced Algorithms and Data Structures, which will take place in Barcelona, from the 6th to 24th of January, 2020.

The course will consist of three weeks of training, 5 training days each week. The program includes daily lectures and practical exercises. It will be quite educational, insightful and entertaining!

And you will have the opportunity to meet and talk with Mike, who will be happy to share his knowledge and stories about the history of Codeforces.

We are happy to offer a special price of 1,000 EUR* for all Codeforces users.

Register on the page below and we will contact you for the next steps. Hurry up! Only 10 spots available.

* The cost does not include travel or accommodation.

REGISTER HERE→

We would also like to recommend you an article published on our blog last week about the 5 reasons why traditional universities can’t keep up with humanity.

UPD: The start of the round is postponed by 30 minutes.

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 neal 7 199
3 risujiroh 7 208
4 imeimi 7 229
5 jiangly 7 273

96 successful hacks and 196 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A cxk0707 0:02
B wangziji 0:05
C ZwariowanyMarcin 0:06
D guyan 0:16
E1 TwentyOneHundredOrBust 0:15
E2 TwentyOneHundredOrBust 0:14

UPD: Editorial is out

• +158

 » 5 months ago, # | ← Rev. 2 →   -73 Time to farm contribution
 » 5 months ago, # |   0 I hope the statement will be clear and simple this time .
•  » » 5 months ago, # ^ |   +6 Your hope prevailed :)
•  » » » 5 months ago, # ^ |   +6 yeah ^_^
•  » » 5 months ago, # ^ |   0 could u plz tell me where can i find the statement ? i'm a green hand.
 » 5 months ago, # |   +104 We are happy to offer a special price of 1,000 EUR* for all Codeforces users.Is it more expensive for Codeforces users than for other people? 1.000 EUR without accomodation and travel. Wow
•  » » 5 months ago, # ^ |   -28 And that too for only 15 days xD
 » 5 months ago, # |   -22 Wish You all high rating after contest.
•  » » 5 months ago, # ^ |   -27 Wish you lots of upvotes
 » 5 months ago, # |   +3 Can anybody tell me the difference between Educational Codeforces Round XX and Codeforces Round XX? Thanks in advance.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +28 Educational rounds (Edit: and div 3 rounds) are in ICPC format (Each problem has same score) + has 12 hours open hacking phase after contest. Other Codeforces rounds are in CF format, different problems have different scores, which decay over time.
•  » » » 5 months ago, # ^ |   0 Thank you very much!!!
•  » » » 5 months ago, # ^ |   0 Sometime the contest wasn't an educational contest , but it also has 12 hours open hacking phase.
•  » » » » 5 months ago, # ^ |   +6 That is Div3 Round
•  » » » » » 5 months ago, # ^ |   0 Thanks.
•  » » » 5 months ago, # ^ |   0 could you please tell what does hacking phase means?
•  » » » » 5 months ago, # ^ |   0 You can read other participant's solution and suggest an input that could make their code to fail or to give a wrong answer. If you achieve that you have hacked the other participant solution and he/she loses the points of the problem. I believe you obtain some points also
•  » » » » 5 months ago, # ^ |   +4
 » 5 months ago, # |   +3 Please try to put an interactive problem.They are interesting to solve.
•  » » 5 months ago, # ^ |   -14 Problemset has already been prepared
•  » » » 5 months ago, # ^ |   +18 Or has it?
•  » » » » 5 months ago, # ^ |   -26 How am I supposed to know
•  » » 5 months ago, # ^ |   0 Yes, I agree on some part with you, they are interesting to solve, but the very code for maintaining the query limit, and doing query at various steps is a bit frustrating,not to forget the flushing of output.I cannot copy paste the test cases :(
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +3 Don't name it as frustrating call it as challenging.
 » 5 months ago, # |   +46 I think MikeMirzayanov should once conduct a course on DSA in India.
•  » » 5 months ago, # ^ |   +3 Yes, it would have much registrations.
•  » » 5 months ago, # ^ |   0 Any particular reason why you mentioned India?
•  » » » 5 months ago, # ^ |   0 "Because everyone wants to learn".
•  » » » » 5 months ago, # ^ |   -22 So other countries people don't want to learn?
•  » » » » » 5 months ago, # ^ |   +21 Did I say that? I am saying that he should also conduct once in India.
•  » » » » » » 5 months ago, # ^ |   +20 Some people just want to watch the world learn.
•  » » » 5 months ago, # ^ |   +2 Because India has highest number of people who want to do coding. Maximum participation is always from India
•  » » » » 5 months ago, # ^ |   0 Yeah, but how many people will participate because it certainly will not be free
•  » » » » » 5 months ago, # ^ |   +1 As enthusiastically as they participate in ICPC(" It is also not free ").
•  » » » » » » 5 months ago, # ^ |   +10 See charges in the blog entry a special price of 1000 euros, I don't know how this charges will translate into INR but it will be high, how much are you ready to pay if you get a training from him?
•  » » » » » » » 5 months ago, # ^ |   0 I think Money never comes in between learning!
•  » » » » » 5 months ago, # ^ |   +1 Yeah, you are right at this
 » 5 months ago, # |   +11 Is it just me or nobody can see any top rated users??? not a single user in the page.!
•  » » 5 months ago, # ^ |   0 same here
 » 5 months ago, # |   +3 delayed!
 » 5 months ago, # |   +3 The start of the round is postponed by 30 minutes. Начало раунда отложено на 30 минут.
•  » » 5 months ago, # ^ |   +22 Why?
•  » » » 5 months ago, # ^ |   -28 How Could a Game Developer even Write a comment ?
 » 5 months ago, # | ← Rev. 5 →   +64 I don't like when contests are delayedIt ruins the organization of our days. 30 minutes is a lot.But I can understand, if there's an issue with the problems. Better to delay + fix. :/
•  » » 5 months ago, # ^ |   +1 Yeah !
 » 5 months ago, # |   +35 I wanted to give the round badly but it looks like I can't :( because I have to catch a train by 23:00 IST. All the best to everyone out there and I wish everyone a high rating :)
•  » » 5 months ago, # ^ | ← Rev. 2 →   +9 Your train has been delayed by 30 minutes
•  » » » 5 months ago, # ^ |   +20 I wish that indeed was the case xD
•  » » » 5 months ago, # ^ |   0 But you'll know about it 15 minutes before departure
 » 5 months ago, # |   +3 It's frustrating to wait for another half n hour.
•  » » 5 months ago, # ^ |   0 But it was life saver for me as the prev time for contest was clashing with the dinner time in my college XD
•  » » » 5 months ago, # ^ |   0 It nearly clashes with every college's dinner timing...but we can manage
•  » » » » 5 months ago, # ^ |   0 Agreed
 » 5 months ago, # |   +5 Why delay :/ Now I won't be able to participate.
 » 5 months ago, # |   -11 Delayforces is back 8)
•  » » 5 months ago, # ^ |   +7 It's for the better
 » 5 months ago, # | ← Rev. 2 →   +29 Hooray! Now i can finish my dinner.
•  » » 5 months ago, # ^ |   +12 Same for me Yaay.
 » 5 months ago, # |   -26 Time to farm contribution.
 » 5 months ago, # |   +1 In fact, I had to go to sleep later because of the contest been put off :( (start at 23:05 here)
•  » » 5 months ago, # ^ |   +2 keep in touch
 » 5 months ago, # |   +4 I think it is better to delay the contest, than to have huge queue time's or unresponsive contest page....
•  » » 5 months ago, # ^ |   +24 let's look at the timeline CF has bad performance latelyeveryone is mad about long queue and 50413000 registrants for this round, incredibly highthe lovely pikmisha delays the roundbunch of people have to go sleep or leave for other thingsless people participating in the roundthis time 504 only lasts for a minute coincidence? i think not
 » 5 months ago, # | ← Rev. 5 →   +29 A Bad Day :(
•  » » 5 months ago, # ^ | ← Rev. 2 →   +33 I had a very bad day too. Didn't have a good idea for B & C. That's strange because these days I spend hours practicing on much harder problems. I found D much easier than C. I spent too much time on C and B and couldn't come up with a solution.Finally, near to the end of contest, I submitted solutions for B & D and it got Accepted. However, my ranking is currently 1900 something and I would probably get back to blue. It was a really bad day!
•  » » 5 months ago, # ^ |   +10 Well,I think my template of NTT needs changing :(
 » 5 months ago, # |   0 I am still unable to solve C in Contest. WTF am I?
•  » » 5 months ago, # ^ |   0 I wasn't even able to solve B, even though I believe I came up with a correct solution! Such a disappointment for me as well. :(
•  » » » 5 months ago, # ^ |   0 Let's practice more together :'(
 » 5 months ago, # |   0 How to solve D?
•  » » 5 months ago, # ^ |   +3 Binary search for the answer.
•  » » » 5 months ago, # ^ |   +9 I was doing the same(binary search) but Wa on test 2 can you explain your idea ?
•  » » » » 5 months ago, # ^ |   0 Yes, of course. So, to check if one answer $X$ is valid, we need to have at least $n/2 + 1$ numbers >= $X$ in our set of numbers. After having all this numbers, we exclude the ones that decrese the most our sum (from $X$ to $l_i$).
•  » » » » » 5 months ago, # ^ |   0 How do we know that if X is valid, then X-1 is also valid?
•  » » » » 5 months ago, # ^ |   0 maybe u missed that for employees that you are assigning as >= median they may have L more than the median value thats what stuck me on test 2.
 » 5 months ago, # |   +27 I thought E1 was pretty pointless, it would be better if it was replaced by a task with difficulty between D and E2?
 » 5 months ago, # |   +9 The questions were really nice they challenged my implementation skills, kudos to the setter
 » 5 months ago, # | ← Rev. 2 →   +5 Is F solvable without FFT? I know a solution where you need to calculate $(1+2 \cdot x)^a \cdot (1 + 2 \cdot x + x^2)^b$ or something like that—is it the only way to do it?
•  » » 5 months ago, # ^ |   +18 I solved it using NTT in $\mathcal{O}(kn \log{} n)$.First if we look at coefficient of $x^j$ in $(1 + 2 \cdot x)^a$ then it is equal to $\binom{a}{j} \cdot 2^j$. Similarly coefficient of $x^j$ in $(1 + 2 \cdot x + x^2)^b$ is $\binom{2 \cdot b}{j}$.Now it's enough to use one NTT/FFT to evaluate this multiplication. But I think it was possible to get accepted on solution you described.
 » 5 months ago, # |   +5 What would be the right way to approach E1 or E2?
•  » » 5 months ago, # ^ |   +55 We can approach it in a greedy fashion.First of all, consider each voter as a pair (Mi, Pi) and sort all the pairs in ascending order of the Mi values.Now lets iterate in the reverse order (i.e from the voter with highest Mi value to the one with the least).We want to be sure that we are buying a vote only when its necessary, do be sure of this lets define whats the necessary condition of buying a vote.Suppose we are at index i (when iterating backwards), and have purchased cnt votes from the suffix of voters [i + 1, n], and in the worst case scenario we can buy votes from every voter in the prefix [1, i — 1], thus getting a total of i-1 votes from them. So at best we can have (i — 1 + cnt) votes. If (i — 1 + cnt) < Mi, we are forced to buy a vote thus this is our necessary condition.To buy a vote we can use a minheap which at any index j stores the values Pk for all voters k from j to n, whose vote we have not bought yet. If after checking for the necessary condition to buy a vote at index i, there is a need to buy a vote, we can take the minimum value of Pk from the heap and increment cnt and add this cost to our result, otherwise we keep iterating backwards.Implementation of the above idea: 63349135
•  » » » 5 months ago, # ^ |   +1 I found that sorting cost $p_i$ for the same $m_i$ dont matter, but I cant tell why. Some one have idea?
•  » » » 5 months ago, # ^ |   +4 Can anyone provide more formal proof? Thank you
 » 5 months ago, # |   +10 https://wcipeg.com/problem/ccc17s2p5 E2 problem...
 » 5 months ago, # |   +7 WA test 2.
•  » » 5 months ago, # ^ |   +1 Checked your submissions on your profile, TC 2 hit you hard.
•  » » » 5 months ago, # ^ |   0 Darn. I got WA on TC 2 for each of B, C, D too before AC, but this was...
 » 5 months ago, # |   0 How to solve C ?? and D, was it binary search ?
•  » » 5 months ago, # ^ |   +3 For C, note that if you divide the number into vectors of odd and even integers, you can see that you will always be able to get any merged sequence of those two vectors. Then just merge as in mergesort. For D, you can just binary search and use greedy.
•  » » » 5 months ago, # ^ |   0 I did the same, but why this code gives TLE? any help.https://codeforces.com/contest/1251/submission/63335135Thank you :)
•  » » » » 5 months ago, # ^ |   0 You were making a vector of a large size for every test case. In this case, it would be easier to push_back elements, and would also pass the limits.
•  » » » 5 months ago, # ^ |   +1 Can you explain 'D' in good detail?
•  » » » » 5 months ago, # ^ |   +3 For D, you do a binary search on the value of the median. The upper and lower bounds on the median value can be deduced from the minimum and maximum possible values of the medians without the constraint of the sum. Now we need to check whether the median m is achievable. For that we need to check if we can add some w_i's to the l_i's so that w_i + l_i <= r_i and the sum of the w_i's is not more than the total money — sum of l_i's, and the median is equal to m. So find those i's with l_i < m <= r_i, and also those j's with l_j >= m. We can find how many numbers we need to set equal to m using this, and the best way would be to choose the i's with the largest l_i's from the first set of i's we had. This is the essence behind the solution.
•  » » » » » 5 months ago, # ^ |   0 suppose this m is achievable, but then how can we be sure that m — 1 is also achievable, what if we reach a mid after decreasing such that there exist only mid < l, can you please explain it.
•  » » 5 months ago, # ^ |   +3 C: Make a vector for even numbers and vector for odd numbersNow we can see that the number who will print first is the first number of odd numbers or the first number of even numbersAnd same for the second number.Be careful when you use all of odd numbers or all of evens numbers
 » 5 months ago, # |   0 in Problem C. Is it possible to write a comparator that describes the desired switching property and then use merge-sort to get the answer? My attempt got WA on test 2 63337083.
 » 5 months ago, # |   +7 My solution for B that passed the pretests-Count the number of 1's in all the strings ( let's call it c1) Count the number of 0's in all the strings ( let's call it c2) If c1 and c2 are both odd and there is no string given of odd length — answer is n-1 else answer is n.Is this correct and if yes can someone please explain why?
•  » » 5 months ago, # ^ |   +1 For B, for the n-1 strings, we can do this - For each of the first n-1 strings, traverse towards the middle and check if it is a palindrome. If there is a change, just swap with the first element of the nth string. This gives you n-1. Now the answer can only be n or n-1. If there is any odd length string, you can do the operation mentioned above keeping that string as the last string and doing stuff to the middle element (instead of the first element). If there is no odd length string, you can get away with parity arguments and show that the answer is n-1.
•  » » » 5 months ago, # ^ |   0 Why is that strategy always optimal though?Can't there possibly be some setup where there is no odd string and picking greedily from the last is sub-optimal?
•  » » » » 5 months ago, # ^ |   +1 From the strategy given, the answer is either n-1 or n, as in the earlier post. My solution was to check if the last one had an even number of 1s or not. Let us suppose that the last string has an even number of ones. Construct the string from the ends and towards the middle. Let r be the reference to the first element of the first string. If you find a difference, at the left and the right indices, then one of them must be equal to the element at r, wlog, let it be 0. Now since there is an even number of ones in the last string, between the indices left and right (both exclusive) there must be an odd number of both 1s and 0s. So we can swap the element (element at right or left) that was not equal to the element at r with the element at r, and then swap the digit (which was originally at r) found between the indices left and right with the element currently at r. This whole operation keeps the element at r fixed, and also preserves the fact that the substring from 0 to left is the same as the reverse of that from right to size-1. We can keep doing this till left and right are separated by at least 2 elements. If the number of 1s is even, we would end up with 00 or 11 in the end, and this would provide a construction for n. Now suppose that the number of 1s is odd, and there exists a construction where all n strings are palindromes. In that case, every string would have an even number of 1s and even number of 0s because every string is of even length. But this is a contradiction, and hence we are done. The answer is thus < n, and therefore must be n-1.
•  » » 5 months ago, # ^ |   +4 StrategyLet's grab all 0's and 1's, and remove them from their spots. Then, wile we have at least a pair of 0's or a pair of 1's, keep putting them into the free spots symmetrically (skip the middles of odd-length strings, and call them just middles). If we are done with symmetrical positions, continue filling the middles as much as we can. At some point we will only have {0, 1} or {1} or {0} or {} left. ProofIf nothing is left (=both c1 and c2 are even), hooray. If only one 0 or 1 is left (=either c1 or c2 is even), that means we have only one position left, and it has to be some middle — and we can fill it with that number, hooray. The last case is when both c1 and c2 are odd, and then we have {0, 1} left. There are 2 cases how this could happen: either we had two middles left free (then we can fill them, and this requires having at least 1 (in fact, there will be 2) string of odd length), or we have two free symmetrical positions left in some even-length string. In the latter case we indeed cannot complete it, because all strings are of even lengths, and therefore, to make all of them palindromes, all 1's and 0's have to be paired, which is not the case.
•  » » 5 months ago, # ^ |   0
 » 5 months ago, # |   +2 At a certain time during the contest, there are more people who have solved E2 than that of E1, that's interesting.
•  » » 5 months ago, # ^ |   +4 It's because of people with rating more than 2100. They don't need to care about rating as the round is unrated for them. So maybe some of them didn't bother to submit their solution of E2 at E1.
•  » » 5 months ago, # ^ |   +16 In the last contest I was using an already deleted pointer, and this solution passed E2, but gave RE on E1. I was going nuts before I found that mistake.
 » 5 months ago, # |   0 How to solve problem B?
•  » » 5 months ago, # ^ |   0 Pure bruteforce works lmao https://codeforces.com/contest/1251/submission/63319464Notice that to construct a palindrome you need two of the same character so each time subtract two. I am pretty sure the answer is either n or (n — 1) but I was too lazy to think.Oh and also length 5 palindrome = length 4 palindrome + any character so just let it as length 4 :) (ABCBA) <-> (ABBA) + (C)
•  » » 5 months ago, # ^ |   +1 if there is an string with odd length then all of the strings can become palindrome.(ans =n) else (all lengths are even) you count number of 0's if its odd you can fix at most n-1 strings else (its even) you can fix all of them and answer is n
•  » » » 5 months ago, # ^ |   0 Why if there is an string with odd length all of the strings can become palindrome?
•  » » » » 5 months ago, # ^ |   +1 Because the middle digit in the odd palindrome becomes kind of an option so you can use it to help other strings become palindrome.
•  » » » » » 5 months ago, # ^ | ← Rev. 4 →   0 I got this, but the second case when number of zeros are odd, why we can fix at most n-1?
•  » » » » » » 5 months ago, # ^ |   +1 when you have odd number of zeros there will always be a string with odd number of zero and odd one (since all string are even o+o=e).. This string cant be a palindrome, hence n-1.
•  » » 5 months ago, # ^ |   +1
 » 5 months ago, # | ← Rev. 3 →   -15 solutions for A,B and C hint for A... keep a iterator i set to 0.then if a[i]==a[i+1] then don't add a[i] in answer and increase i by 2 else add a[i] in answer and increase i by 1 hint for C...1.Notice that if i and j are 2 indices with same parity with i
 » 5 months ago, # | ← Rev. 3 →   +8 I can't write binary search in a proper manner. $Binary\, search$ gods, take me.
•  » » 5 months ago, # ^ |   -7 I can't either, it never converges >:(Workaround: make break condition (r — l > 3) and check each value from [l, r] after that instead. Always works :) :) :)
•  » » » 5 months ago, # ^ |   0 I ended up doing this sh*t too: int can[7] = {mid-3,mid-2, mid-1, mid ,mid+1, mid+2, mid+3}; 
•  » » 5 months ago, # ^ |   +7 If you are looking for a maximum $x$ that satisfies certain condition ($func(x) = true$), always keep the range such that $func(left) = true$, and $func(right) = false$. It is then quite easy to update: while (right - left > 1) { int middle = (left + right) / 2; if (func(middle)) { left = middle; } else { right = middle; } } answer = left; 
•  » » » 5 months ago, # ^ |   0 Can u tell the condition for finding minimum value... Thanks..
•  » » » » 5 months ago, # ^ |   0 func(i) = arr[i] < arr[i + 1]
•  » » » » » 5 months ago, # ^ |   0 Thanks for replying but I want code like dantrag is given for finding maximum value...
•  » » » » 5 months ago, # ^ |   0 Just reverse the condition for left and right;Always keep the range such that $func(left) = false$, and $func(right) = true$ while (right - left > 1) { int middle = (left + right) / 2; if (func(middle)) { right = middle; } else { left= middle; } } answer = right
•  » » » 5 months ago, # ^ |   0 but this failed for test case 4 i.e. 1 1 1000000000 1000000000 1000000000It was giving 999999999.So I used this : while(l<=h){ int mid=(l+h)/2; if(check(mid)){ ans=mid; l=mid+1; } else h=mid-1; } 
•  » » 5 months ago, # ^ |   +8 check out the topcoder tutorial
 » 5 months ago, # |   +46 E is duplicate of a canadian problem: https://dmoj.ca/problem/cco17p5
 » 5 months ago, # | ← Rev. 2 →   +1 Can any one help me to find the test case where Exactly my code is failing?UPDATE:Found The test case :aaakka ->Ans : a
 » 5 months ago, # |   0 Why are contestants allowed to hack their own submissions? Shouldn't this be disallowed? You should be able to hack anybody else's test case but not your own.
»
5 months ago, # |
Rev. 3   -53
Can someone hack it. It's solution for B.
 » 5 months ago, # |   0 Been scratching my head for over an hour, trying to find out a mistake in my D solution. The idea of my solution is the same as discussed by many in the comments. Got WA on test case 2.Can someone please help me find it?My submission: 63336144
•  » » 5 months ago, # ^ |   0 I did the same thing and got WA :(
•  » » 5 months ago, # ^ | ← Rev. 2 →   +13 mid_sum += (mid_ls.size() - (n / 2) + lc)Maybe cast mid_ls.size() to int? Maybe an overflow happens, because size() is unsigned. It probably isn't this, but maaaybe?
•  » » » 5 months ago, # ^ |   0 I'm surprised, it worked! Thanks!Earlier I had the practice of typecasting size_t every time I used it, but then sometimes I used to think that anyways, it's going to typecast by itself, then why bother! Well, I guess I know now why to bother!Thanks again!AC submission: 63345119
 » 5 months ago, # |   0 This guy https://codeforces.com/submissions/amr_abdelazim is hacking his solutions of his own fake account https://codeforces.com/profile/Amr_Abdelazim01 . He tried very hard to hide the coding style of both account but it is revealed to be same in these 2 solutions https://codeforces.com/contest/479/submission/59876211 https://codeforces.com/contest/474/submission/63271187 Kindly look into the matter cheaters like these are ruining the platform.
 » 5 months ago, # |   +2 In problem D i did not find the function to be monotonic as for many cases I found the function to be discrete.Can anyone help me how there is solution by binary search for such a case.
•  » » 5 months ago, # ^ |   +7 Start with the lowest possible answer. That will be the case, when all the employees get their lowest possible salary, and the median salary will be the median of the list of l of all employees.Now try to increase the answer by 1. For the sake of simplicity, imagine that currently, all the employees have distinct salaries.CASE 1: Now if the r of employee having salary = median salary is greater than median salary, then you can directly increase that employee's salary by one, and your overall median salary will increase by one.CASE 2: Otherwise, let's suppose that the r of the employee having his salary = median salary is itself equal to median salary. In this case, we will try to find an employee whose current salary is less than median salary, but whose r is greater than median salary, then increase that employee's salary to median + 1, so that the overall median salary will increase by one.If neither of the above case is possible, then it is just not possible to increase the median salary anymore.
•  » » 5 months ago, # ^ |   +1 Suppose that the maximum median is $m$, and you sorted employees in ascending order of their given salaries, where the $\lceil\dfrac{n}{2}\rceil^{th}$ employee is given salary $m$. To show that you can achieve all the medians down to the lowest one, you will always need to decrease one or more of the salaries of the first $\lceil\dfrac{n}{2}\rceil$ employees so that their maximum becomes $=$ the new median. If a new median $m_2$ can't be obtained because $l>m_2$ for some employee, you can swap him with an employee among the last $\lfloor\dfrac{n}{2}\rfloor$ employees whose $l\leq m_2$ (and his $r$ is obviously $\geq m_2$ because it is $\geq m$). If no such employee exists, then there are at least $\lceil\dfrac{n}{2}\rceil$ employees with $l>m_2$, and the median can't be decreased more.
 » 5 months ago, # |   0 These are two of my submissions for problem D. The 1st one gave run-time error on test-2 and the 2nd one got accepted. The only difference between these 2 submissions was in cmp() function. (I used > in 2nd one whereas >= in the 1st one)Can anyone please help me figure out why did 1st one give run-time error whereas the 2nd one got accepted?
•  » » 5 months ago, # ^ |   +10 This is expected behavior. See https://stackoverflow.com/questions/45929474/why-must-stdsort-compare-function-return-false-when-arguments-are-equal
•  » » » 5 months ago, # ^ |   +1 Got it. Thanks!
•  » » 5 months ago, # ^ |   +15 You can never use = in a comparator function because if a=b it will return true for comp(a,b) and true for comp(b,a) which is ambiguous behavior. A comparator should be such that if it returns true for comp(a,b) it must return false for comp(b,a).
•  » » » 5 months ago, # ^ |   +1 Got it. Thanks!
 » 5 months ago, # | ← Rev. 2 →   +5 Help! What does "Unexpected verdict" mean in the verdict of hacks? This verdict comes out at hack #594802.Does that mean I have hacked the std solution or the validator?
•  » » 5 months ago, # ^ |   +5 It is fixed now.
•  » » » 5 months ago, # ^ |   +20 Thanks! Now up to 16 solutions of F were hacked by me. It's amazing that there are no such tests prepared by the authors.
 » 5 months ago, # |   +12 This guy is just unbelievable see this hacked solution https://codeforces.com/contest/1251/submission/63344943He deliberately put the if condition to print 1 so that he can hack his own fake account solution . and see this https://codeforces.com/submissions/Amr_Abdelazim01He hacked his fake account solution almost 12 times with different if conditions to print 1. Strict action needs to be taken against users like this https://codeforces.com/profile/amr_abdelazim
 » 5 months ago, # |   +18 These are all the fake accounts that I have discovered so far whom the owner have hacked by putting a if condition to print something nonsense when the input is something specific like if(string=="dfsfdfh45") print("456");https://codeforces.com/contest/1251/submission/63335128https://codeforces.com/contest/1251/submission/63316807https://codeforces.com/contest/1251/submission/63342216https://codeforces.com/contest/1251/submission/63341635https://codeforces.com/contest/1251/submission/63344050God people will do anything for the rating . People like these should be banned.
•  » » 5 months ago, # ^ |   +21 They punished themselves by spending time on the most useless effort in the world, because hacking does not even influence rating in Educational rounds.
•  » » » 5 months ago, # ^ |   0 Oh I didn't know that seems like they are also unaware about it . But this tactic is brought to light now who knows for how long people having been using tactic to gain rating through hacking in other rounds.
 » 5 months ago, # |   -17 Below is my solution for the $B$NOTE: The binary string with odd number of digits can always be changed to palindromic one, by swapping digits among itself, no matter what. This suggests us that we can use this odd string for feeding other even strings with either 1s or 0s as required to make them(even) palindromic. You just need to maintain 3 counts while taking the inputs. oddcount $\rightarrow$ the number of strings with the odd number of digits. evenpalindrome $\rightarrow$ the number of strings which have even number of digits and also has even number of 1's and 0's. (They can be made palindromic by swap amongst themselves) evennotpalindromes $\rightarrow$ the number of strings which have even number of digits and has odd number of 1's and 0's. Now if oddcount $>~0$ it means that we can make every string palindromic by using one single odd string. So answer will be $n$ in this case. Now if there is no odd string, then there is a max of two types of strings with us The even palindromes(The one with even number of 1s and 0s), they add up to our answer,and we'll not touch them The even NOTpalindromes(The one with odd number of 1s and 0s), by swapping between every two such strings, we can make them palindromic. In case we have their quantity odd in number, one of them will be left and will not be palindromic(in case they are 3, we can couple any 2 to make them palindromic) Our final answer, in this case, will be $\text{evenpalindrome}+(\dfrac{\text{evenotpalindrome}}{2})\times{2}$.
•  » » 5 months ago, # ^ |   -6 Is it wrong? Why so many negative votes. Please correct me atleast
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 Let the number of strings with odd number of ones and odd number of zeros be $a$, and the number of strings with odd length be $b$. Answer is $n$ if $b \geq a\ \%\ 2$, else $n-1$.Reason: Only strings with an odd number of both bits can't be made into palindromes by themselves, but two such strings can swap bits to make each other palindromic. That leaves at most one string if we have an odd number of such strings. This string can only swap bits with strings of odd length, which will make the number of both bits even, and hence make the string potentially palindromic. So at most one string can be left potentially non-palindromic if we do not have strings of odd length.
•  » » » 5 months ago, # ^ |   +15 It is not wrong. Maybe it's too lengthy to read. Also, when a negative vote comes, lot of people just pounce on downvoting. Like when there is one piece of garbage on road, everyone starts throwing the garbage at that place, thinking thats the designated place.
•  » » » » 5 months ago, # ^ |   +33 This is sad, as it was the first solution that I've ever written here on Codeforces. I thought that I should explain it in complete detail.
 » 5 months ago, # |   0 in problem D why almost all solution use the same formulae in binary search that is mid=(l+r+1)/2 and the low=mid and high=mid-1?? My question is why not they use mid=(l+r)/2 and then low=mid+1 and high=mid-1 based on the condition.. But second give wrong answer..Why?? Pls help Thanks in advance
•  » » 5 months ago, # ^ | ← Rev. 2 →   +2 low = mid + 1, high = mid — 1 worksfirst thing you need to take while(low <= high) because you are changing low = mid + 1 and you need to check case when they equaland second thing is answer would be low — 1, why, because you are every time taking low + 1 when it works then, low would be final answer + 1, then result is low — 1
•  » » » 5 months ago, # ^ |   0 Thanks, now i got it.
•  » » 5 months ago, # ^ |   0 I prefer 2nd Style :v
 » 5 months ago, # |   +14 How to solve E1 with DP?
•  » » 5 months ago, # ^ | ← Rev. 2 →   0
 » 5 months ago, # |   0 Can someone explain the solution for problem C in easier manner.. Thanks in advance...
•  » » 5 months ago, # ^ |   +1 the order of appearance of even\odd numbers in the sequence will never change because you cannot swap two even\odd numbers so it remains the same. so the easiest way is to make two sequence of even and odd number and every time display the smaller Example:- input : 2531764 the even sequence : 264 the odd sequence : 5317 step #1 : we choose the smaller 2 or 5 its 2 "2" step #1 : 6 or 5 its 5 "25" step #2 : 6 or 3 its 3 "253" step #3 : 6 or 1 its 1 "2531" step #4 : 6 or 7 its 6 "25316" step #5 : 4 or 7 its 4 "253164" step #6 : only 7 remains so the answer will be "2531647" 
 » 5 months ago, # |   0 Can someone please explain the binary search for D with an example, it will be really helpful. Thanks in advance!
•  » » 5 months ago, # ^ | ← Rev. 2 →   -21 you have to binary search on the median, the range of median is from 1 to 1e9 you will binary search on that, each iteration in the BS you pick the middle and check if it can be the median or not, in-case of yes make the start = middle+1 in-case of no make the end = middle-1 link to Ac code
 » 5 months ago, # |   +3 Ok. Looking through the hacks of the round, I've noticed that there are some users who are hacking submissions made by accounts that are clearly their own alt accounts. Though this isn't a huge deal in Educational Rounds, where hacking is mostly irrelevant, but I think it amounts to cheating in regular rounds, where you get 100 points for a successful hack. Imagine creating 10 accounts, who all submit 5 hackable solutions, and then your main account hacks them all to gain points.What do you guys think?
•  » » 5 months ago, # ^ |   +3 It isn't possible to hack just anyone's solution — they must also be in the same room as you. Getting 10 alts in the same room as you claim has extremely low probability. Anyway, would be better if you could post examples.
•  » » » 5 months ago, # ^ |   0 That is seriously a stupid way to increase the rating. I would rather spend time improving myself rather than spend time getting my alt accounts in the same room :p
 » 5 months ago, # |   +12 please publish the editorial
 » 5 months ago, # |   +24 editorial pls
 » 5 months ago, # |   +10 Please publish editorial
 » 5 months ago, # |   0 Can anybody please explain to me why this code is giving TLE. (Question C) Link: https://codeforces.com/contest/1251/submission/63324481
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Use ans += odd[b] instead of ans = ans + odd[b]. For strings always use += to append.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 It's working. Nice tip mohmahkho. I will make it in practice from now onwards. How come ans += odd is better than ans = ans+odd? Can you please explain to me how it works?
•  » » » 5 months ago, # ^ |   0 Thank You. Can you please explain the reason behind this?
•  » » » » 5 months ago, # ^ |   +2 Suppose we have two strings, s and t of and we want to append t to the end of the s. If you write s = s + t what it does is that it creates a new string (that is invisible to you which means you don't have access to it by a variable name but it exists) which holds the resulting concatenated string. To create that invisible string it will copy s and t which basically means it iterates over both of them once which again means the time complexity would be $O(|s| + |t|)$. On the other hand when you use += it does not need to iterate over s, it just allocates enough amount of memory to append t which is like iterating over t once, with time complexity of $O(|t|)$. Your TLE solution was $O(n^2)$ because of the reason that you were basically iterating over ans while appending to it.
•  » » » » » 5 months ago, # ^ |   +5 Thank You so much.
 » 5 months ago, # |   +14 Will there be an editorial published?
 » 5 months ago, # |   0 Simple logic for B:- If there exists an odd length string. Ans=nIf the number of even length strings with odd number of 1's is even. Ans=nElse Ans=n-1https://codeforces.com/contest/1251/submission/63376630
 » 5 months ago, # |   +11 Thanks for fast editorial.
 » 5 months ago, # | ← Rev. 5 →   +1
 » 5 months ago, # |   0 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 5 months ago, # |   0 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 5 months ago, # | ← Rev. 3 →   +3 Can someone please help me finding bug in my solution for the problem E2. It's giving WA on test case 3, the test case is really large so I'm not able to find out which input is giving WA.UPD: Debugged it nowLink to my code
•  » » 5 months ago, # ^ |   0 Can u explain your idea? pls, thanks in advance.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +3 We will approach the problem in a greedy fashion. First of all sort the pair vector(input) in increasing order of the number of votes required. Now make a multiset (it's similar to set but it can store multiple elements which are same) which is initially empty. Traverse from the bottom, and one by one push the current element into the multiset. Note that, say if you are at an index $i$, and the candidate requires minimum votes, $M_i$ and the cost of buying it is $P_i$. And you have currently bought a total of $v_1$ voters. To be sure that by the end of the traversal the current guy will vote us, we need to check if $(i — 1 + v_1) >= M_i$. If the condition is not satisfied, buy the vote of the guy in the starting of the set (cheapest till now), add his cost to your answer and erase this guy from the multiset. Iterate backwards.
 » 5 months ago, # |   0 balanced problems, thank you.
 » 5 months ago, # |   +1 Please link the editorial directly to the contest dashboard.
 » 5 months ago, # |   0 Problem D has a greedy tag on it. Can anyone please provide a greedy solution?
 » 5 months ago, # |   0 http://codeforces.com/contest/1251/submission/63422680 can some one tell why this code is giving me tle to problem 3 thanks in advance