By isaf27, 4 weeks ago, translation, ,

Hi all!

I'm happy to welcome you at the Div.1 and Div.2 shared rated round Mail.Ru Cup 2018 Round 1, it will start at Oct/18/2018 19:35 (Moscow time). The problems were prepared by me — Ivan Safonov. I'd like to thank Dmitry _kun_ Sayutin for an idea and preparation of one of the problems and Egor I_love_isaf27 Gorbachev for an idea for another one.

This round is the first round if the new championship called Mail.Ru Cup, you can learn more about it following the link. The round will be rated for everybody!

The championship feature the following prizes:

• First place — Apple MacBook Air
• Second and third place — Apple iPad
• Fourth, fifth, sixth places — Samsung Gear S3
• Traditionally, the top 100 championship participants will get cool T-shirts!

In each round, top 100 participants get prize points according to the table. The championship's result of a participant is the sum of the two largest results he gets on the three rounds.

Huge thanks to Grigory gritukan Reznikov and Ilya izban Zban for testing the problems, to Nikolay KAN Kalinin and Ildar 300iq Gainullin for their help in preparation, and to Mike MikeMirzayanov Mirzayanov for Codeforces and Polygon platforms.

The round will feature eight problems to solve in two and a half hours. The scoring will be announced closer to the beginning of the round.

I hope everyone will find some problems interesting. I wish everybody a successful round and a positive rating change!

Good luck!

UPD1，Scoring distribution:

500 750 1250 1500 2000 2250 3000 4000

Congratulations to the winners of Round 1!

UPD2

Editorial

Announcement of Mail.Ru Cup 2018 Round 1

•
• +241
•

 » 4 weeks ago, # | ← Rev. 2 →   +38 I hope scoring will be based on 2.5 hrs contest, unlike as happened in Practice Round i.e. for 500 pts problem points deducted per min = 2*(2)/2.5 per min instead of 2 pts per min.
 » 4 weeks ago, # |   0 Is the contest is combined (div1 + div2 ) or it will separately div1 and div2__
•  » » 4 weeks ago, # ^ |   +19 Div.1 and Div.2 shared rated round So I assume combined.
 » 4 weeks ago, # |   +41 Lol. isaf27 and I_love_isaf27.
•  » » 4 weeks ago, # ^ |   +53
•  » » » 4 weeks ago, # ^ |   -32 Lol
•  » » » » 4 weeks ago, # ^ |   +14
•  » » » » » 4 weeks ago, # ^ |   +10 /r/KarmaRoulette/
•  » » 4 weeks ago, # ^ |   +2
 » 4 weeks ago, # | ← Rev. 2 →   +10 " I wish everybody a positive rating change! "This is one of the wishes that everyone knows that can't happen :( .
•  » » 4 weeks ago, # ^ |   0 Are you sure? If a lot of new users take part in round then, probably, everyone will increase his rating
•  » » » 4 weeks ago, # ^ |   +7 Then let's wish for a lot of fake accounts!
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 If the sum of ratings before the contest equal to A and the sum of ratings after the contest equal to B, then A=B. So if a rating increases, there is some ratings have negative rating change.(new users rating is 1500)
•  » » » » 4 weeks ago, # ^ |   0
•  » » » » » 4 weeks ago, # ^ |   0 Wow! But what is that?
•  » » » » » » 4 weeks ago, # ^ |   0 A lie. 9 year old post, it's probably outdated.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Positive rating change means if you lose rating, you will realize its positive aspect, like a kind of lesson you get after your failure.
 » 4 weeks ago, # |   0 I know learning is Psychologically difficult, but solving thousand easy problems doesn't make you a champion
•  » » 4 weeks ago, # ^ |   +12 It will put you on top of the problemset scoreboard at least.
 » 4 weeks ago, # |   -96 Let's hope for a lot of algorithmic and data structure problems and no math/ad-hoc garbage.
•  » » 4 weeks ago, # ^ |   +34 ad-hoc is not a garbage!!!
•  » » » 4 weeks ago, # ^ |   -86 Yeah, Numb, ad-hoc problem do suck everytime. They just plain suck. I've seen problems suck before but ad-hoc are the suckiest bunch of sucks that ever suck. But I gotta go now, the damn wiener ad-hoc lovers might be reading.
•  » » » » 4 weeks ago, # ^ |   +14 if you have problems with ad-hoc then you need to think better.also i disrespect data structures ans algorithms because i suck at them
•  » » » » » 4 weeks ago, # ^ |   -41 I can't believe people downvote me for saying ad-hoc is garbage while they upvote you for saying that you disrespect algorithms and data structures. Jesus Christ! We're in a programming community! Algorithms and data structures should be glorified!
•  » » » » » » 4 weeks ago, # ^ |   0 Ad-hoc problems are more interesting because you can come with many kinds of novel solutions even without much prior experience, but for algorithms/ds problems if you don't know the algorithm/ds that the problem requires you're screwed :(
•  » » » » » » » 4 weeks ago, # ^ |   +14 If you go to a Scrabble tournament and you don't have a wide vocabulary, you're screwed too.And I can't see the Scrabble committee modifying the rules so that newcomers can beat experienced players.
•  » » » » » » » » 4 weeks ago, # ^ |   -6 Scrabble != competitive programming. Also, are you saying really good competitive programmers won't necessarily be able to solve ad-hoc problems as well? I don't think that makes sense.
•  » » » » » » » » » 4 weeks ago, # ^ |   0 No, I'm saying that a lot of purple or orange coders spent a lot of time studying techniques that are obsolete because of the current problem setting trends.
•  » » » » » » » 4 weeks ago, # ^ |   0 With many ad-hoc problems, contests end up being more of an IQ Test than a programming competition. And that's not the idea behind CP.
•  » » » » » » » » 4 weeks ago, # ^ |   +1 But if you don't think a lot about the problems but just keep coding and coding, it would be really boring!
•  » » » » » » » » » 4 weeks ago, # ^ |   0 Actually, I think it's the other way around. Thinking a lot about the same problem and getting stuck is what's boring and frustrating. Coding is always nice and fun.
•  » » » » » » 4 weeks ago, # ^ |   +38 Forget about programming. We are not in the programming community. We are not in the math community. We are in the game community. We just use programming and math to compete, but we don't actually do any exploring here. We just compete here. We learn data structures and math theorems only to compete better and have more rating.
 » 4 weeks ago, # |   -29 This contest will be rated (div.1 & div.2) or unrated?
•  » » 4 weeks ago, # ^ |   +4 Rated.
•  » » 4 weeks ago, # ^ |   -10 A little bit of both.
•  » » 4 weeks ago, # ^ |   0 Equivalent to "IS IT RATED". So down vote -_-
 » 4 weeks ago, # | ← Rev. 3 →   +1 fourth, fifth, sixth places will be unlucky if they hadn't Samsung smart phone xD
•  » » 4 weeks ago, # ^ |   -6 They would be very lucky if they don't have Samsung and give them Xperia instead.
•  » » 4 weeks ago, # ^ |   +8 You can use them with any phone :)
•  » » » 4 weeks ago, # ^ |   0 Today you may fullfill your 35 challange, lol
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +9 Maybe, he can't since he was involved in preparation.
•  » » » » » 4 weeks ago, # ^ |   0 Himitsu I didn't realized before you pointed out, thanks and sorry to 300iq
 » 4 weeks ago, # |   0 why Syloviaely is not in top 10 !!! as per his rating he must be in top 10
•  » » 4 weeks ago, # ^ |   +1 He didn't join any contest in the last six months
•  » » 4 weeks ago, # ^ |   -15 He's invisible.
 » 4 weeks ago, # |   +6 bet who will be gifted the macbook air :v
•  » » 4 weeks ago, # ^ |   0 tourist
•  » » 4 weeks ago, # ^ |   +40 We can use the exclusion method, first of all, this person is definitely not me :)
 » 4 weeks ago, # |   +17 Prizes are up for grabs, so I guess Tourist is gonna participate :-p
•  » » 4 weeks ago, # ^ |   +8 Don't predict anything ever!
 » 4 weeks ago, # |   0 hope i get my rating back :)
 » 4 weeks ago, # |   0 i hope that we dont have 15 min late :(
 » 4 weeks ago, # |   -7 Is it rated?
 » 4 weeks ago, # |   -41 :3
•  » » 4 weeks ago, # ^ |   +17 No Delay yet.
 » 4 weeks ago, # |   +22 Wow, I found net in a train (no way to connect from my phone since I forgot a USB cable), so it seems I'll actually be able to do this round...Also 300iq wants to dye his hair pink.
 » 4 weeks ago, # |   0 Wish i was able to compete:(
 » 4 weeks ago, # |   +63 Difficulty curve today, turning point = Problem D:
 » 4 weeks ago, # |   -9 Another sad day for a panda :(
 » 4 weeks ago, # |   +36 So apt :)
 » 4 weeks ago, # | ← Rev. 2 →   0 So , how to solve D ?
•  » » 4 weeks ago, # ^ |   +12 I did a greedy thing that means iterating over the array and changing the number to its complement if its better . i passed pretests somehow
•  » » » 4 weeks ago, # ^ |   +1 But why does it work??
•  » » 4 weeks ago, # ^ |   0 https://ideone.com/vmH4pj It works correct on sample test, will have to wait for systest to get over to submit. Too bad I was considering over k+1 bits and could not submit on time.
 » 4 weeks ago, # |   +8 seriously, why is the time limit in E 1s? There can be 16 * 10^5 outputs! What difference would it make to set the time limit 2s like NORMAL PROBLEMS!
•  » » 4 weeks ago, # ^ |   0 oh shit
 » 4 weeks ago, # | ← Rev. 2 →   +12 Does anyone know what is pretest 3 in F or can share tricky input?
 » 4 weeks ago, # |   0 What is hack of A?
•  » » 4 weeks ago, # ^ |   0 1 2 1 5 1 2
•  » » 4 weeks ago, # ^ |   +3 set z = x, some guys used added 2*t3 in case when z = x, instead of 3*t3
•  » » » 4 weeks ago, # ^ |   0 Also, some people forgot abs(z-x) and/or abs(x-y).
 » 4 weeks ago, # |   +27 Was F finding maximal independent set using konigs?
•  » » 4 weeks ago, # ^ |   +8 Yes
•  » » » 4 weeks ago, # ^ |   0 Damm.. finding minimum value of H+V was easy but than finding those wires was just too much work..
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +2 It is easy if you see question in terms of mincut. mincut is just one dfs after flow.Even vertex cover and independent set also same but you need to remember the construction technique for both.
•  » » » » » 4 weeks ago, # ^ |   0 But how are u finding min vertex cover using that? i think u r confusing between mincut and min vertex cover?
•  » » » » » » 4 weeks ago, # ^ |   +8
•  » » 4 weeks ago, # ^ |   +20 Didnt have just couple of seconds to get AC on F.Submitted on last minute and only in the last seconds, i get that i have WA1.I printed first vertical and then horizontal lines.When i push to sumbit new code, just got message contest is over. ((
 » 4 weeks ago, # |   +16 Is F, computing mincut of bipartite graph with all possible small horizontal wires on one side and similar vertical wires on one side. Now edge of size inf between all horizontal and vertical wires which intersect at a point not given in input. This gives n*n edges right, will it pass?
•  » » 4 weeks ago, # ^ |   +3 Yes, it's a correct solution
•  » » » 4 weeks ago, # ^ |   +3 O(n*n) edges works or can we prove that number of edges are less (on top of my mind it seems we can create a tight bound of O(n*n) edges)??
•  » » » » 4 weeks ago, # ^ |   0 Number of edges <= n*n/4. And on practice, it works very fast.
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +8 You can compute maximal independent set instead which is complement of minimal vertex cover.
•  » » » 4 weeks ago, # ^ |   0 i think he means no of edges in bipartite graph.. which can be of order n^2 i think?
•  » » » » 4 weeks ago, # ^ |   0 Yes, misunderstood the meaning of edge.
 » 4 weeks ago, # |   0 Any ideas on pretest 7 for C?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 Maybe something like 6 0 0 0 0 0 0 5 4 3 2 1 0 I had a submission that failed on 7, that also failed on this case.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 5 0 0 2 1 3 2 0 2 0 0 YES 3 5 1 4 2 
•  » » » » 4 weeks ago, # ^ |   0 Mine is correct for this one. Ok, will check after system tests.
•  » » » 4 weeks ago, # ^ |   0 YES 1 2 3 4 5 6
•  » » » » 4 weeks ago, # ^ |   0 Ok maybe not then, what is your approach to the problem?
•  » » » » » 4 weeks ago, # ^ |   0 num = n loop: find all i for which L[i] = R[i] = 0, put a[i] = num adjust L, R for indexes j where a[j] = 0 num-- go to loop. if in the and any a[i] is zero => no, if any L[i], R[i] is not zero => no 44506024
•  » » » » » » 4 weeks ago, # ^ |   0 Same logic and I still can't figure what's wrong with test 7.
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 Something like 4 0 1 1 3 0 0 0 0 The moment I fixed this case, pretest 7 passed
•  » » » 4 weeks ago, # ^ |   0 YES 4 3 3 2
•  » » 4 weeks ago, # ^ |   0 Maybe this? 4 0 1 2 3 3 2 1 0
•  » » » 4 weeks ago, # ^ |   0 This should be NO right? I still can't figure what's test 7.
 » 4 weeks ago, # |   +1 Can someone please tell me how to solve D?
•  » » 4 weeks ago, # ^ |   0 My (probably incorrect) idea is to maintain prefixes of xors and the count of them. Whenever I reach a number with even number of occurrences of xor prefix, I change it. Finally calculate number of subarrays using the same idea.
•  » » 4 weeks ago, # ^ |   0 My solution passed pretests but I'm not sure of it though. I solved it greedily by iterating over each element and see if flipping it is better I flip it. To check whether flipping it is better I used trie tree. I hope not fail on system test :D
•  » » 4 weeks ago, # ^ |   +30 Sub-string [l, r] xor can be calculated as pref[r] ^ pref[l-1], where pref[i] is the xor-sum of prefix ending at i. So, sub-string [l,r] xor can be 0 if and only if pref[r] == pref[l-1]. Now, what is the impact of inverting some ai? pref[i], pref[i+1], ..., pref[n] will be inverted. So in general, you can invert some ai's to invert some specific pref elements.Let the answer (ans) be initially n(n+1)/2. You can iterate on every pref element and its complement, check the counts of both elements (using map for example). Let the counts are c1 and c2. If you didn't invert any elements, c1(c1-1)/2 and c2(c2-1)/2 will be subtracted from ans.To minimize the subtracted value, you can imagine you inverted some pref elements resulting in changing c1 and c2 to floor((c1+c2)/2) and ceil((c1+c2)/2), let these new values be x1, x2. So, x1(x1-1)/2 and x2(x2-1)/2 will be the values subtracted from ans.
•  » » » 4 weeks ago, # ^ |   0 What is complement of a number?
•  » » » » 4 weeks ago, # ^ |   +1 Its bit-wise not under k bits. For ex. under k=3, 1 (001) will be 6 (110).
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 can you please explain .how did you changed c1 to floor(c1+c2)/2 and c2 to ceil(c1+c2)/2.?
•  » » » » 4 weeks ago, # ^ |   +1 Suppose you are considering some value v1 from pref array, its count is c1. Let v2 be the bit-wise complement of v1 and its count is c2. if c1 is 9 and c2 is 2 for example, you can imagine you inverted 4 instances of v1 (becoming v2). So now c1 is 5 and c2 is 6.
•  » » » 4 weeks ago, # ^ |   0 I did same thing. Can you please explain what is wrong 44531845
•  » » » 2 weeks ago, # ^ |   0 mohamedeltair how can u prove we can always do operation such that half of occurences in prefix array can be change by doing invert operation in array?
 » 4 weeks ago, # |   +38 In problem E you get the general strategy by looking at Jury's Answer for pretest 1. What the hell is this? I saw this at the end of contest :(.
 » 4 weeks ago, # |   +55 Fact that Errichto's A got hacked by a specialist scares me.
•  » » 4 weeks ago, # ^ |   +22 Yoss))
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   -6 What's the hack?
•  » » » 4 weeks ago, # ^ |   0 Quite the opposite)
•  » » 4 weeks ago, # ^ |   +91 ;_;
•  » » » 4 weeks ago, # ^ |   0 That's kinda sad
 » 4 weeks ago, # |   +4 How did you guys solve C? I spent 2 hours and didn't find a solution.
•  » » 4 weeks ago, # ^ |   +3 For every index sum the left and right. The answer is n-sum[k] for k < n.Then you loop through the answer you found and check to see if it produces the correct left and right arrays.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +4 But how did you get this? Please tell ? How should i think this way?
•  » » » » 4 weeks ago, # ^ |   +4 Idea is that if you have l+r bigger then l+r of other child, then you have more candies. And if you have same l+r then you have same number of candies
•  » » » » » 4 weeks ago, # ^ |   0 i also used the same strategy but can't submit. Waiting for system test to complete and will submit then :(
•  » » » 4 weeks ago, # ^ |   0 Can you guys tell me please, Why this is array[i] = n — l[i] — r[i]? I spent 1:30 hours but still didn't understand why this works. Any hint would be greatly appreciated. Thanks.
•  » » » » 4 weeks ago, # ^ |   0 The sum of left[k] and right[k] is the total number of cells that are greater. If this is your answer, you will get a larger value for a cell for less candles, and a smaller value for a cell with more candles. Since this is the opposite of what you want and all the answers need to be between 1 and n, n-(l[i] + r[i]) gives one possible solution.
•  » » 4 weeks ago, # ^ |   +5 I solved it using the logic of fill from max to min. Max element should have l,r = 0,0. So fill all such elements in answer as max (we can use max = n). Let's move to the second max element (let it be n-1), It exists in the positions where l = the number of elements already filled in the left, and r = number of elements already filled in the right. And so on till you fill the array.If at the ith step the array is not filled yet and there is no such element where you can put the ith max, there will be no answer.
•  » » » 4 weeks ago, # ^ |   0 so this will be O(n^2) isnt it?
•  » » » » 4 weeks ago, # ^ |   0 O(n^2) will pass in C
•  » » » » 4 weeks ago, # ^ |   0 Yes, but n ≤ 1000 so it will pass. Keep in mind that constraints can give you hints about the required algorithmic complexity.
•  » » » 4 weeks ago, # ^ |   0 perfect solution could not come to this even thinking for an hour
 » 4 weeks ago, # |   +6 Friend's standing not working??
 » 4 weeks ago, # |   +11 How to solve H?
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +2 My solution: let's write . As we can see, here is polynomial which is same for all , we only have to compute its values for . We should take instead of j3 so polynomial will be of reasonable size. Now you should note that mod is prime and it has generating element g such that each element x can be represented as x = gi. Now only think you need to do is to compute value of polynomial in all powers of g which can be done with Chirp-z transform. But since you'll have to take in elements, you can actually compute only powers of g2, i.e. all values in points g2k. But you can transform your polynomial to count all values in g2k + 1 as . The last thing to mention is that you can half the size of polynomial you need to calculate values in by abusing the fact that you calculate 'em in g2 (see my unreadable code below to get the notion of what's going on).I couldn't make it below 4s during the contest, because author is probably a cuck and thinks that you can't say that you solved a problem if you didn't optimize all constants in your code or if you don't think exactly as the author does. But at the very end I realized that there is 2 times optimization in the length of vectors which probably would allow my solution to pass after system tests end. Optimized solution itself: #Jq5TzC. (I used quasisphere code for fast mod multiplication)
•  » » » 4 weeks ago, # ^ |   0 UPD: fixed solution gets AC with ~2900ms :(
 » 4 weeks ago, # |   +8 H: let's say the problem asks for a[i] * b[j] * c^(i^2 + j^3) find the sum of that for every possible value K == c^(i^2 + j^3)this problem is a lot easier, since you can find a primitive root R for 490019 (I'll call it MOD from now on) and write any A > 0 as R^(some value % (MOD — 1)) and R^x * R*y == R^(x + y). From this point, you can use FFT to calculate the answer easilly.Now, we want to turn a[i] * b[j] * c^(i^2 * j^3) in the type of problem above. Notice that MOD — 1 = 2 * 491 * 499 so it has only 8 divisors. We'll group i^2 and j^3 into groups of gcd(value, MOD — 1). Note that X % (MOD — 1) can be represented as a tuple (X % 2, X % 491, X % 499) using the chinese remainder theorem. Now, for each pair of divisors of MOD — 1, you can put together those values ignoring the positions in the tuple that are 0 (since in multiplication you multiply the tuple and it remains 0). All that's needed now is finding a common primitive root between 491, 499 and 2 and use it for the calculations as explained before. Now, just pass through the values and plug them together using CRT or something else with the positions that were 0.Is this correct?
•  » » 4 weeks ago, # ^ |   0 I believe your solution is correct, we have something very similar to what you have written.
•  » » » 4 weeks ago, # ^ |   0 I just finished coding and it's working on samples, I'm gonna kick myself if this doesn't work. I failed E because I read that it pushes to the back and wasted too much time on H without finding the common primitive root part, found that minutes after the contest.
•  » » » » 4 weeks ago, # ^ |   0 Well, actually there is no need to have a common primitive root. It is not important since you apply discrete logarithms, sum up and exponentiate discretely component-wise.
•  » » 4 weeks ago, # ^ |   0 I had some trouble with precision but it passed, the primitive root idea isn't needed. You can take the discrete logarithm of ANY primitive root for every prime in the pair of groups and group it together after. http://codeforces.com/contest/1054/submission/44524051
 » 4 weeks ago, # |   0 In D, I thought of a greedy approach but it didn't work as I did not take into consideration the number of bits (k), so the complement operator didn't work the way it should for this problem. What is the ideal way to solve this problem of using custom-size integers? STL bitset doesn't seem to work as it doesn't allow the size to be defined at runtime.I wrote a solution using vector after the contest, but it seems to be a very inefficient way of doing this.
•  » » 4 weeks ago, # ^ |   0 Let c=2^k-1.In that case complement to a is just c-a;
•  » » 4 weeks ago, # ^ |   +8 You can take the compliment and then mask the right k bits by taking bitwise AND with 2^k-1
 » 4 weeks ago, # |   +46 Slowest System Test Ever
•  » » 4 weeks ago, # ^ |   0 Nah. Crashed systests were slower. Systests taking hours just because they're slow aren't so uncommon on CF.
 » 4 weeks ago, # |   +56 Is it me or was the system testing faster before moving to ITMO?
•  » » 4 weeks ago, # ^ |   +3 Are you sure it's related to being in ITMO? Some contests take longer to judge than others. It looks like today's was rather heavy in this regard; it seems like problems have a lot of tests. Also, problem B was solved by a lot of people, but had O(n) complexity with n = 105. Often, problems that get a lot of submissions have like O(1) complexity or much smaller n.
 » 4 weeks ago, # |   0 Can anyone please explain me clearly about problem B. I still didnt get it. Thanks.
 » 4 weeks ago, # |   +87
 » 4 weeks ago, # |   -8 How to solve D?
 » 4 weeks ago, # | ← Rev. 2 →   +5 In Problem D, using greedy to iterate over the numbers and flip if it's better passes systests. Can someone please explain why/how does greedy work here?
•  » » 4 weeks ago, # ^ |   0 If you build prefix xor array, then xor of interval can be 0 if there is x and x in that array. If we count occurencies of min(x,x^((1<
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +70 We need to minimize the number of subarrays with xor==0.Let's build a prefix xor array, P, and use a map, F, to track the frequency of each element in P.If we cannot change any element, then answer would be: If we can change elements to its complement, we can try minimizing the summation. To do so, we can try breaking up a single element with large frequency to many elements with lower frequency. This will decrease the sum because of the property a12 + a22 + ... ≤ (a1 + a2 + ...)2 for non-negative integers. We can iterate over the prefix array and if x is the current element and as its complement, we choose the element with the smaller frequency until this point and increment its frequency. Now, the only case left is how do we handle choosing when .It actually does not matter. Suppose we choose x over , then it would only negatively impact us when we have another element later on with x as one choice and the second choice being some other value apart from . But this will never happen because each x is associated with only one, unique . Hence, the greedy algorithm would work.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Very Clear explanation!! Thanks :)Can you please explain why curr is not getting updated respectively based on whether we take complement for a particular v[i] or not. Why curr always assigned with a?
•  » » » 4 weeks ago, # ^ |   0 Got it, thanks.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I am a little confused. In these codes why value of curr does not matter. curr stores the current greedy cumulative xor till i.Here if frequency of bb is less, then curr should be update to bb but every time if we update curr to aa it is giving correct answer.aa denotes cumulative xor if element a[i] would have been taken, bb denotes if complement(a[i]) would have been taken till i.Can someone please explain why?https://ideone.com/VEJHBMBoth are giving AC
•  » » » » 4 weeks ago, # ^ |   +1 If original P had the values x0, x1, x2, x3 and suppose you flip x1, then P would become .( prefix xor is basically prefix sum for each bit mod 2. If you flip the parity of any bit, then all the parities of further elements in that bit would be flipped too.) Then if you flip x2, it would become .So, regardless of the elements you've flipped, either the current prefix xor is correct or it's complement is correct. Knowing which one is correct does not matter since you will be comparing both of them anyway.
•  » » » » » 4 weeks ago, # ^ |   0 Got it!! Thank you :)
•  » » » » » 3 weeks ago, # ^ |   0 I am not getting the reason for F[0]++ in your code. We have not seen any prefix xor array element.
•  » » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   +5 (F[x] * (F[x] - 1)) / 2 should give us the number of subarrays with XOR == 0.This works for all positive x and fails when x = 0.The correct formula when x = 0 is (F[0] * (F[0] + 1)) / 2. (You can just take a prefix of the array with ending element as 0 but this is not possible when x!=0 ). Also (F[0] * (F[0] + 1)) / 2 = ((F[0] + 1)) * ((F[0] + 1) - 1)) / 2. So we can just increment F[0] at the beginning to handle this case.
•  » » » » » » » 3 weeks ago, # ^ |   0 Thanks! Got it now.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I thought about the greedy approach but didn't implemented it, I learned it's better not to try proving things in contests, specially greedy ones... damn life
 » 4 weeks ago, # |   +9 update rating please...
 » 4 weeks ago, # |   0 Just check out these two solutions for problem C ....there's a difference in code in the first loop ...still both the solutions got accepted? Weak test cases or something else? 44516044 and 44522031.He skipped his first solution to get it right.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Not sure what's going on, but the second solution is giving correct outputs too. It's just offset by a certain number (idk how), e.g. the first testcase is offset by 2 from the jury answer. The problem statement doesn't require for the smallest number to be 1, so that is fine. I don't think the testcases were weak.
•  » » » 4 weeks ago, # ^ |   +3 Thanks dude for looking into it.
 » 4 weeks ago, # |   +10 Standings page down and still waiting for rating update :/ I understand the ongoing transition to ITMO may have delayed things, but please look into these issues. Thanks.
 » 4 weeks ago, # |   +6 when the rate is upd??
 » 4 weeks ago, # |   +85 Failed on the problem H because of the precision error in my FFT library code. T_T
 » 4 weeks ago, # |   +8 This contest will have Editorial?
•  » » 4 weeks ago, # ^ |   0
 » 4 weeks ago, # |   0 Please provide with the Editorial ASAP. Really nice set of problems. Looking forward to the upsolving :)
•  » » 4 weeks ago, # ^ |   0
•  » » » 4 weeks ago, # ^ |   +5 Any English Version of it?
 » 4 weeks ago, # |   0 Please find my solution at : http://codeforces.com/contest/1054/submission/44512450The algorithm I am following is this,for each student, find out how many student have more chocolates than him, by adding l[i] and r[i].This basically gives the standard competition ranking. see[1].Next step is I am simply verifying if the ranking I am getting is a standard competition ranking.And chocolate distribution is (n-rank[i])My solution is failing on test case 6. And I am not able to download the whole test case( it is big).Any body will be kind enough to point out what I am doing wrong ?
 » 4 weeks ago, # | ← Rev. 2 →   +3 a
•  » » 4 weeks ago, # ^ |   0 See here
 » 4 weeks ago, # |   +15 Here's a solution for G:Let xi be the number of people in the i-th group. In any solution, we expect to get have exactly xi - 1 edges between these people (we can't have less since they wouldn't be connected, and we can't have more or it wouldn't be a tree).Let wi, j be the number of groups that node i and node j have in common (and suppose we have these counts).Let's find a max weight spanning tree on the complete graph where the weight of an edge between nodes i and j is wi, j. If the weight of this MST is equal to , then the answer is yes and we can print any max spanning tree, otherwise it is no.To show this is optimal, if a solution exists, the weight of that tree is exactly , so our algorithm will find it. The other way is if we do find a tree with this weight, then this is a valid solution, each group can only contribute at most xi - 1 to the weight of the max spanning tree, which shows it is also a valid solution since each group is connected.The only other tricky part is computing wi, j fast. This part can be done with bitsets
•  » » 4 weeks ago, # ^ |   +11 Really neat!I had something else in mind:let's imagine any correct solution, and find any leaf l in the tree. It's connected to some other vertex v. Then we can see that for each group A of vertices in the input such that |A| ≥ 2, from follows (l is connected to v only, so any "non-trivial" set containing l has to contain v). Moreover, if we find any two vertices (l, v) fulfilling the property above, we can safely assume that l is a leaf connected to v only. (Proof: let's take any solution. If a group of people contains l, then it also contains v, which means it also contains a whole path between l and v. We can safely remove l from the tree, attaching all subtrees that were connected to l to the second vertex on the path. Then we can reattach l as the leaf connected to v only.)The idea is now straightforward: find a leaf, remove it, find a leaf in the remaining tree and so on. The only problem is how to find a pair of vertices (l, v) as above. For each pair of people i, j, I am maintaining bi, j, the number of groups larger than 1 containing i, but omitting j. (These can be computed directly from wi, j in the parent post.) A pair of vertices (l, v) fulfills the condition above if bl, v = 0. bi, j's can be straightforwardly updated after the removal of a single vertex.This leads to another solution in time.
 » 4 weeks ago, # |   +10 How to solve E?
•  » » 4 weeks ago, # ^ |   +14 My approach: Move everything from (0, 0) to (1, 0) and from (1, 1) to (0, 1). Move all zeroes and ones from every cell to (0, 0) and (1, 1), respectively. Fill all cells (i, j) having j ≥ 2 with target value. If there are two moves needed (because the row AND column differs from (0, 0), resp. (1, 1)), first move within the same column. Fill all cells (i, j) having j < 2 and i ≥ 1 with the target value. If there are two moves needed, first move within the same row. Assemble the target value of (0, 0) in (1, 0) and target value of (1, 1) in (0, 1). Assemble the target values of (1, 0) and (0, 1) in their cells. Move the value of (0, 0) from (1, 0) to (0, 0). Similarly with (1, 1). In the steps 1 and 2, we move every digit at most twice. In the moves 3-7, we again move each digit at most twice.
•  » » » 4 weeks ago, # ^ |   +1 Thank you :)
•  » » » 4 weeks ago, # ^ |   +3 There's a classical idea that you can go from the beginning and the end to some "ideal" state, and then output something along the lines of [beginning to ideal] + reversed([end to ideal])With that your solution stops at step 2 out of 7
•  » » 4 weeks ago, # ^ |   +13 I moved all 0-s to (0, 0) and all 1-s to (0, 1), then moved from them. Handling columns  ≥ 2 is easy, then rows  ≥ 1 need to be processed (columns 0 and 1 give you two queues, you can either move a number from the front of one queue to the back of the other or just move it to row 0) and finally, the initial strings in (0, 0) and (0, 1) can be processed using empty (1, 0) and (1, 1) as temporary queues. Moving everything the other way is very similar.The condition that we can't move from the front of a queue to its own back makes this problem a lot more complex than it seems.
•  » » » 4 weeks ago, # ^ |   +10 Yeah looks pretty similar to majk's solution above. Thanks :)
•  » » 4 weeks ago, # ^ |   +3 I did it using at most 3·s steps. Let's assume we don't have the restriction (x0, y0) ≠ (x1, y1).Step 1: Move all 0s to the first row, and all 1s to the second row. Including all that already belong to the 1st and 2nd row. Since I remove the restriction of moving one digit from one cell to itself this is easy. We move each digit once in this step, so exactly s steps are performed.At the end of step 1, all 0s are in the first row, and all 1s are in the second row.Step 2: Calculate how many 0s and 1s belong to each column, and how many are currently in, so we can rebalance them in order to have in column jth as many 0s and 1s are needed. In this step, each digit does at most 1 step (moving to the right column).At the end of step 1, all 0s are in the first row, all 1s are in the second row, and the number of 0s in the jth columns coincide with the final amount of 0s in the jth column. The same happens with the 1s.Step 3: Build the target board. Just move each 0 and 1 to build properly each cell using only 0s and 1s that are in their current columns, i.e. each digit moves vertically. Notice that we need to build also cells on the first two rows, and we can do that in any order we want. In this step, each digit moves exactly once, so we need at most 3·s steps in total (counting moves from step 1, 2, and 3).Finally, this works fine, because I assumed we can move one digit from cell c to itself. But, when is this going to happen? and how can we fix it? From this point on you can think on several fix that will work fine, here goes mine.Invalid movements will happen in step 1 and 3. Since we are performing step 2 optimally we won't try to move one digit from one cell to itself.The fix in step 1 is really easy. If we find a 0 at the end of some cell in the row 0, instead of moving this digit from its cell to itself (as suggested in this step) we can move it to any other cell in this row. I move it from (0, j) to a different cell in the same row.What can we do in step 3? Here the solution was a little bit trickier. Regarding 0s, I shifted the first row one step to the left (cyclic) and when counting (on step 2) number of 0s on column jth, I counted that on the shift-ed board. That way, after step 2 on the cell (0, j) there are only 0s, and the amount of 0s is equal to the number of 0s on the jth column minus 0s in the cell (0, j) + 0s in the cell . So, on step 3, instead of pushing 0s from (0, j) to itself I moved them from to (0, j).I found this solution easier (except for the fix of moving one digit from some cell to itself) than other solutions, and the funny thing is it performs at most 3·s movements.My solution
 » 4 weeks ago, # |   0 Well, I understood the problem C clearly. But cant find a proper way that how to solve it. Can anyone give me some hints how to solve C. Any hint would be greatly appreciated. Thanks.
•  » » 4 weeks ago, # ^ |   0 Set last element as 1Increase element on left according to left arrayDecrease element as per right arrayCheck if your array now satisfies the left and right array bothIf yesThen print all elements as arri - minarray
•  » » » 4 weeks ago, # ^ |   0 Thanks a ton. But can you tell me please whis this works array[i] = n — l[i] — r[i]?
 » 4 weeks ago, # |   +8 Please publish the editorial for this contest.
 » 4 weeks ago, # |   0 How to solve E ?How to prove the greedy solution to D ?
•  » » 4 weeks ago, # ^ |   0 Can you tell me please, Why this is array[i] = n — l[i] — r[i]? I spent more than 1:30 hours but still didn't understand why this works. Any hint would be greatly appreciated. Thanks.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Sure. Keep in mind that l[i] + r[i] represents the number of people which are greater than i. So, if l[i] + r[i] > l[j] + r[j], it means that the i-th person has more people greater than it, than the j-th person does. In other words, it implies that the i-th person gets fewer candies than the j-th person.Let f(x) be the function which decides how many candies person x gets. Then, f(x) must obey few properties — 1 <= f(x) <= n, for everyone. If (l[i] + r[i] > l[j] + r[j]), then f(i) < f(j) The function f(x) = N — l[x] — r[x] satisfies both these properties. :)
•  » » » » 4 weeks ago, # ^ |   0 Thanks a lot man.
•  » » » » » 4 weeks ago, # ^ |   0 Here is my code for reference. :)No problem :)
•  » » » » » » 4 weeks ago, # ^ | ← Rev. 3 →   0 Can you explain me,how & why f(x) = N — l[x] — r[x] works?I cannot feel it.
•  » » » » » » » 4 weeks ago, # ^ |   0 I explained right ? It obeys the two conditions necessary. It ensures the person with highest (l[x] + r[x]) gets least candies and the lowest (l[x] + r[x]) gets highest candies. Please elaborate your doubt :)
•  » » » » » » » » 4 weeks ago, # ^ |   0 Thanks,now i can feel it. :)
 » 4 weeks ago, # | ← Rev. 3 →   -6 .