By isaf27, 2 years 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

 » 2 years 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.
 » 2 years ago, # |   0 Is the contest is combined (div1 + div2 ) or it will separately div1 and div2__
•  » » 2 years ago, # ^ |   +19 Div.1 and Div.2 shared rated round So I assume combined.
 » 2 years ago, # |   +41 Lol. isaf27 and I_love_isaf27.
•  » » 2 years ago, # ^ |   +53
•  » » » 2 years ago, # ^ |   -32 Lol
•  » » » » 2 years ago, # ^ |   +14
•  » » » » » 2 years ago, # ^ |   +10 /r/KarmaRoulette/
•  » » 2 years ago, # ^ |   +2
 » 2 years ago, # | ← Rev. 2 →   +10 " I wish everybody a positive rating change! "This is one of the wishes that everyone knows that can't happen :( .
•  » » 2 years ago, # ^ |   0 Are you sure? If a lot of new users take part in round then, probably, everyone will increase his rating
•  » » » 2 years ago, # ^ |   +7 Then let's wish for a lot of fake accounts!
•  » » » 2 years 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)
•  » » » » 2 years ago, # ^ |   0
•  » » » » » 2 years ago, # ^ |   0 Wow! But what is that?
•  » » » » » » 2 years ago, # ^ |   0 A lie. 9 year old post, it's probably outdated.
•  » » 2 years 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.
 » 2 years ago, # |   0 I know learning is Psychologically difficult, but solving thousand easy problems doesn't make you a champion
•  » » 2 years ago, # ^ |   +12 It will put you on top of the problemset scoreboard at least.
 » 2 years ago, # |   -96 Let's hope for a lot of algorithmic and data structure problems and no math/ad-hoc garbage.
•  » » 2 years ago, # ^ |   +34 ad-hoc is not a garbage!!!
•  » » » 2 years 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.
•  » » » » 2 years 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
•  » » » » » 2 years 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!
•  » » » » » » 2 years 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 :(
•  » » » » » » » 2 years 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.
•  » » » » » » » » 2 years 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.
•  » » » » » » » » » 2 years 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.
•  » » » » » » » 2 years 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.
•  » » » » » » » » 2 years ago, # ^ |   +1 But if you don't think a lot about the problems but just keep coding and coding, it would be really boring!
•  » » » » » » » » » 2 years 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.
•  » » » » » » 2 years 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.
 » 2 years ago, # |   -29 This contest will be rated (div.1 & div.2) or unrated?
•  » » 2 years ago, # ^ |   +4 Rated.
•  » » 2 years ago, # ^ |   -10 A little bit of both.
•  » » 2 years ago, # ^ |   0 Equivalent to "IS IT RATED". So down vote -_-
 » 2 years ago, # | ← Rev. 3 →   +1 fourth, fifth, sixth places will be unlucky if they hadn't Samsung smart phone xD
•  » » 2 years ago, # ^ |   -6 They would be very lucky if they don't have Samsung and give them Xperia instead.
•  » » 2 years ago, # ^ |   +8 You can use them with any phone :)
•  » » » 2 years ago, # ^ |   0 Today you may fullfill your 35 challange, lol
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +9 Maybe, he can't since he was involved in preparation.
•  » » » » » 2 years ago, # ^ |   0 Himitsu I didn't realized before you pointed out, thanks and sorry to 300iq
 » 2 years ago, # |   0 why Syloviaely is not in top 10 !!! as per his rating he must be in top 10
•  » » 2 years ago, # ^ |   +1 He didn't join any contest in the last six months
•  » » 2 years ago, # ^ |   -15 He's invisible.
 » 2 years ago, # |   +6 bet who will be gifted the macbook air :v
•  » » 2 years ago, # ^ |   0 tourist
•  » » 2 years ago, # ^ |   +40 We can use the exclusion method, first of all, this person is definitely not me :)
 » 2 years ago, # |   +17 Prizes are up for grabs, so I guess Tourist is gonna participate :-p
•  » » 2 years ago, # ^ |   +8 Don't predict anything ever!
 » 2 years ago, # |   0 hope i get my rating back :)
 » 2 years ago, # |   0 i hope that we dont have 15 min late :(
 » 2 years ago, # |   -7 Is it rated?
 » 2 years ago, # |   -41 :3
•  » » 2 years ago, # ^ |   +17 No Delay yet.
 » 2 years 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.
 » 2 years ago, # |   0 Wish i was able to compete:(
 » 2 years ago, # |   +63 Difficulty curve today, turning point = Problem D:
 » 2 years ago, # |   -9 Another sad day for a panda :(
 » 2 years ago, # |   +36 So apt :)
 » 2 years ago, # | ← Rev. 2 →   0 So , how to solve D ?
•  » » 2 years 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
•  » » » 2 years ago, # ^ |   +1 But why does it work??
•  » » 2 years 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.
 » 2 years 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!
•  » » 2 years ago, # ^ |   0 oh shit
 » 2 years ago, # | ← Rev. 2 →   +12 Does anyone know what is pretest 3 in F or can share tricky input?
 » 2 years ago, # |   0 What is hack of A?
•  » » 2 years ago, # ^ |   0 1 2 1 5 1 2
•  » » 2 years ago, # ^ |   +3 set z = x, some guys used added 2*t3 in case when z = x, instead of 3*t3
•  » » » 2 years ago, # ^ |   0 Also, some people forgot abs(z-x) and/or abs(x-y).
 » 2 years ago, # |   +27 Was F finding maximal independent set using konigs?
•  » » 2 years ago, # ^ |   +8 Yes
•  » » » 2 years ago, # ^ |   0 Damm.. finding minimum value of H+V was easy but than finding those wires was just too much work..
•  » » » » 2 years 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.
•  » » » » » 2 years ago, # ^ |   0 But how are u finding min vertex cover using that? i think u r confusing between mincut and min vertex cover?
•  » » » » » » 2 years ago, # ^ |   +8
•  » » 2 years 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. ((
 » 2 years 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?
•  » » 2 years ago, # ^ |   +3 Yes, it's a correct solution
•  » » » 2 years 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)??
•  » » » » 2 years ago, # ^ |   0 Number of edges <= n*n/4. And on practice, it works very fast.
•  » » 2 years ago, # ^ | ← Rev. 3 →   +8 You can compute maximal independent set instead which is complement of minimal vertex cover.
•  » » » 2 years ago, # ^ |   0 i think he means no of edges in bipartite graph.. which can be of order n^2 i think?
•  » » » » 2 years ago, # ^ |   0 Yes, misunderstood the meaning of edge.
 » 2 years ago, # |   0 Any ideas on pretest 7 for C?
•  » » 2 years 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.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 5 0 0 2 1 3 2 0 2 0 0 YES 3 5 1 4 2 
•  » » » » 2 years ago, # ^ |   0 Mine is correct for this one. Ok, will check after system tests.
•  » » » 2 years ago, # ^ |   0 YES 1 2 3 4 5 6
•  » » » » 2 years ago, # ^ |   0 Ok maybe not then, what is your approach to the problem?
•  » » » » » 2 years 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
•  » » » » » » 2 years ago, # ^ |   0 Same logic and I still can't figure what's wrong with test 7.
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 Something like 4 0 1 1 3 0 0 0 0 The moment I fixed this case, pretest 7 passed
•  » » » 2 years ago, # ^ |   0 YES 4 3 3 2
•  » » 2 years ago, # ^ |   0 Maybe this? 4 0 1 2 3 3 2 1 0
•  » » » 2 years ago, # ^ |   0 This should be NO right? I still can't figure what's test 7.
 » 2 years ago, # |   +1 Can someone please tell me how to solve D?
•  » » 2 years 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.
•  » » 2 years 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
•  » » 2 years 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.
•  » » » 2 years ago, # ^ |   0 What is complement of a number?
•  » » » » 2 years ago, # ^ |   +1 Its bit-wise not under k bits. For ex. under k=3, 1 (001) will be 6 (110).
•  » » » 2 years 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.?
•  » » » » 2 years 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.
•  » » » 2 years ago, # ^ |   0 I did same thing. Can you please explain what is wrong 44531845
•  » » » 2 years 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?
 » 2 years 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 :(.
 » 2 years ago, # |   +55 Fact that Errichto's A got hacked by a specialist scares me.
•  » » 2 years ago, # ^ |   +22 Yoss))
•  » » 2 years ago, # ^ | ← Rev. 2 →   -6 What's the hack?
•  » » » 2 years ago, # ^ |   0 Quite the opposite)
•  » » 2 years ago, # ^ |   +91 ;_;
•  » » » 2 years ago, # ^ |   0 That's kinda sad
 » 2 years ago, # |   +4 How did you guys solve C? I spent 2 hours and didn't find a solution.
•  » » 2 years 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.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   +4 But how did you get this? Please tell ? How should i think this way?
•  » » » » 2 years 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
•  » » » » » 2 years ago, # ^ |   0 i also used the same strategy but can't submit. Waiting for system test to complete and will submit then :(
•  » » » 2 years 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.
•  » » » » 2 years 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.
•  » » 2 years 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.
•  » » » 2 years ago, # ^ |   0 so this will be O(n^2) isnt it?
•  » » » » 2 years ago, # ^ |   0 O(n^2) will pass in C
•  » » » » 2 years ago, # ^ |   0 Yes, but n ≤ 1000 so it will pass. Keep in mind that constraints can give you hints about the required algorithmic complexity.
•  » » » 2 years ago, # ^ |   0 perfect solution could not come to this even thinking for an hour
 » 2 years ago, # |   +6 Friend's standing not working??
 » 2 years ago, # |   +11 How to solve H?
•  » » 2 years 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)
•  » » » 2 years ago, # ^ |   0 UPD: fixed solution gets AC with ~2900ms :(
 » 2 years 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?
•  » » 2 years ago, # ^ |   0 I believe your solution is correct, we have something very similar to what you have written.
•  » » » 2 years 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.
•  » » » » 2 years 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.
•  » » 2 years 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
 » 2 years 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.
•  » » 2 years ago, # ^ |   0 Let c=2^k-1.In that case complement to a is just c-a;
•  » » 2 years ago, # ^ |   +8 You can take the compliment and then mask the right k bits by taking bitwise AND with 2^k-1
 » 2 years ago, # |   +46 Slowest System Test Ever
•  » » 2 years ago, # ^ |   0 Nah. Crashed systests were slower. Systests taking hours just because they're slow aren't so uncommon on CF.
 » 2 years ago, # |   +56 Is it me or was the system testing faster before moving to ITMO?
•  » » 2 years 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.
 » 2 years ago, # |   0 Can anyone please explain me clearly about problem B. I still didnt get it. Thanks.
 » 2 years ago, # |   +87
 » 2 years ago, # |   -8 How to solve D?
 » 2 years 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?
•  » » 2 years 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<
•  » » 2 years 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.
•  » » » 2 years 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?
•  » » » 2 years ago, # ^ |   0 Got it, thanks.
•  » » » 2 years 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
•  » » » » 2 years 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.
•  » » » » » 2 years ago, # ^ |   0 Got it!! Thank you :)
•  » » » » » 2 years ago, # ^ |   0 I am not getting the reason for F[0]++ in your code. We have not seen any prefix xor array element.
•  » » » » » » 2 years 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.
•  » » » » » » » 2 years ago, # ^ |   0 Thanks! Got it now.
•  » » » 2 years 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
 » 2 years ago, # |   +9 update rating please...
 » 2 years 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.
•  » » 2 years 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.
•  » » » 2 years ago, # ^ |   +3 Thanks dude for looking into it.
 » 2 years 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.
 » 2 years ago, # |   +6 when the rate is upd??
 » 2 years ago, # |   +85 Failed on the problem H because of the precision error in my FFT library code. T_T
 » 2 years ago, # |   +8 This contest will have Editorial?
•  » » 2 years ago, # ^ |   0
 » 2 years ago, # |   0 Please provide with the Editorial ASAP. Really nice set of problems. Looking forward to the upsolving :)
•  » » 2 years ago, # ^ |   0
•  » » » 2 years ago, # ^ |   +5 Any English Version of it?
 » 2 years 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 ?
 » 2 years ago, # | ← Rev. 2 →   +3 a
•  » » 2 years ago, # ^ |   0 See here
 » 2 years 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
•  » » 2 years 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.
 » 2 years ago, # |   +10 How to solve E?
•  » » 2 years 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.
•  » » » 2 years ago, # ^ |   +1 Thank you :)
•  » » » 2 years 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
•  » » 2 years 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.
•  » » » 2 years ago, # ^ |   +10 Yeah looks pretty similar to majk's solution above. Thanks :)
•  » » 2 years 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
 » 2 years 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.
•  » » 2 years 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
•  » » » 2 years ago, # ^ |   0 Thanks a ton. But can you tell me please whis this works array[i] = n — l[i] — r[i]?
 » 2 years ago, # |   +8 Please publish the editorial for this contest.
 » 2 years ago, # |   0 How to solve E ?How to prove the greedy solution to D ?
•  » » 2 years 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.
•  » » » 2 years 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. :)
•  » » » » 2 years ago, # ^ |   0 Thanks a lot man.
•  » » » » » 2 years ago, # ^ |   0 Here is my code for reference. :)No problem :)
•  » » » » » » 2 years ago, # ^ | ← Rev. 3 →   0 Can you explain me,how & why f(x) = N — l[x] — r[x] works?I cannot feel it.
•  » » » » » » » 2 years 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 :)
•  » » » » » » » » 2 years ago, # ^ |   0 Thanks,now i can feel it. :)
 » 2 years ago, # | ← Rev. 3 →   -6 .