### BledDest's blog

By BledDest, 13 months ago, translation,

Hello Codeforces!

Codeforces Round #585 (Div. 2) will be held on Sep/15/2019 13:35 (Moscow time). The round will be rated for Div. 2 contestants. There will be 6 problems for 2 hours. Please, notice that the start time is unusual.

The round will be rated for the participants with rating lower than 2100. The statements will be available in Russian and English.

The round will start 2 hours after the start of the Qualification Stage, so they will finish around same time. That's why we ask the participants of the Quals to stay silent and don't share the statements of the contest with anyone. Unfortunately, we cannot add all the problems from Quals to the round, it will contain only six problems.

The problems were prepared by Alex fcspartakm Frolov and me.

We also would like to express our gratitude to Mike MikeMirzayanov Mirzayanov for the permission to make a mirror and Codeforces and Polygon platforms, Ildar 300iq Gainullin for his help with testing the problems and preparing the round. Also big thanks to the testers: Adilbek adedalic Dalabaev and Roman Roms Glazov.

As usual, the scoring distribution will be announced just before the round.

Good luck!

• +134

 » 13 months ago, # |   0 I'm newbie. i want to know how to contribute problems for contests???
•  » » 13 months ago, # ^ |   +17 You can know more here: https://codeforces.com/blog/entry/49569
•  » » » 13 months ago, # ^ |   0 thanks <3
 » 13 months ago, # |   +20 Overlaps with atcoder bc141 D:
 » 13 months ago, # |   -35 Well I did a good jod in 584
 » 13 months ago, # |   +3 isn't that a clash with AtCoder Beginner Contest 141?
 » 13 months ago, # | ← Rev. 3 →   -138 [deleted]
•  » » 13 months ago, # ^ |   +35 Not Original, Copied it from some previous post because it was hilarious. xD
 » 13 months ago, # |   -61 To be honest, there should be more Division 3 rounds!
 » 13 months ago, # |   +4 Friendly time for Chinese users!
•  » » 13 months ago, # ^ |   0 YES，very nice
 » 13 months ago, # | ← Rev. 2 →   -6 It is clashing with ABC141. Since ABC always starts at that particular time, can you please prepone this round by 35-40 mins? Many of us don't want to miss either of them.
•  » » 13 months ago, # ^ |   +15 I think they can't move it because it's like online mirror of the on-site contest.
 » 13 months ago, # |   0 Hope it will be like last round
 » 13 months ago, # |   -11 Good 好好！
 » 13 months ago, # |   0 I want to take part in this contest. But whether I can take part depends on whether I can finish my homework in 4 hours and I don’t think I can. QWQ
•  » » 13 months ago, # ^ |   0 How old are you?
•  » » » 13 months ago, # ^ |   +2 14.
•  » » » » 13 months ago, # ^ |   -14 Cool!! CM at 14!!!
•  » » 13 months ago, # ^ |   0 Maybe you finished it just now...I'm just like you.
 » 13 months ago, # |   +60 I'm going to do screencast with commentary in English of this round first, and then jump to ABC141. YouTube
•  » » 13 months ago, # ^ |   0 waiting for it :)
•  » » » 13 months ago, # ^ |   +7
 » 13 months ago, # |   +15 Friendly time for Chinese! I can participate even in my school!!!!!
•  » » 13 months ago, # ^ |   +7 School on Sunday?
•  » » » 13 months ago, # ^ |   0 In many schools in China (including primary school, junior and senior high school, and most of them are boarding schools), students always go back to school one day before school days. Through sometimes it's illegal. (but truly all the boarding schools do so)
•  » » » » 13 months ago, # ^ |   0 Well, I am also a Chinese student. I do not agree with your opinion. The school is not wrong, even though the time of contest is friendly to us……
•  » » » » » 13 months ago, # ^ |   0 Yeah they're not wrong... But it's the truth...
 » 13 months ago, # |   +16 Scoring distribution?
 » 13 months ago, # |   +27 What is the hack for D?
 » 13 months ago, # | ← Rev. 2 →   0 Is there a simpler solution to F than 2sat with segtree?
•  » » 13 months ago, # ^ |   +15 I hope 2-sat with segtree won't pass (I tried to eliminate non-linear solutions).The easiest linear solution is to take care of $f$ by introducing variables of the form $f \ge i$, that way every station adds only $2$ clauses (with $f \ge l_i$ and with $f \ge r_i + 1$).
 » 13 months ago, # |   +11 How to solve E in this contest? Why more than 200 participants solved it?
•  » » 13 months ago, # ^ |   -30 I think it's googlebale, if you google it you might find a solution, Am not sure thought :(
•  » » » 13 months ago, # ^ |   0 Very similar ?
•  » » 13 months ago, # ^ |   0 Compute for each pair of color i,j the cost of putting color i before j and the cost of putting j before i (number of inversions between the two colors), and add the minimum to the result.
•  » » » 13 months ago, # ^ |   +3 Are you sure this doesn't end up in a cycle?
•  » » » » 13 months ago, # ^ | ← Rev. 4 →   0 I didn't prove it, but I couldn't find a counter-example, it felt true, and it gets AC so it should be good ? Kudos if you find a hack or a proof :-)It's faster also, just the complexity of precomputing inversions in 20 * 4e5
•  » » » » » 13 months ago, # ^ | ← Rev. 2 →   +18 Unfortunately, I'm not in division 1 right now, so I can't hack your solution; but your assumption fails with: Spoiler26 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 2 2 1 1 1 1 2 2 2 2
•  » » » » » » 13 months ago, # ^ |   +23 Oh nice ! thanks. Too bad for weak systest though.
•  » » » » » » 13 months ago, # ^ |   +8 your hack works: 60632025
•  » » » » » » » 13 months ago, # ^ |   +5 Ohh, actually I wanted to hack it if I managed to return to div 1 next week :D
•  » » 13 months ago, # ^ |   +22 DP on bitmask, like travelling salesman problem, except this time the distance is number of inversions.
•  » » » 13 months ago, # ^ |   0 Is there a way to precompute the number of inversions? My submission got TLE on test case 7
•  » » » » 13 months ago, # ^ |   +3  for (int i = 0; i < n; i++) { for (int j = 0; j < 20; j++) { inversions[values[i]][j] += counts[j]; } counts[values[i]]++; } 
•  » » » 13 months ago, # ^ |   0 can u explain briefly how u did this problem!! it would be a great help
•  » » » » 13 months ago, # ^ |   +33 Ok, so you know that normally the answer is the number of inversions if you just want to sort the array, right? So the idea is that we want to create an ordering of the 20 different colors so that sorting it requires the minimum number of moves. This means we want to find the ordering with the minimum number of inversions. What we do is precompute the number of inversions between each pair of numbers. Then we do a bitmask DP with complexity 20^2 * 2^20. Each state in the bitmask represents "we have considered these certain digits", and when we transition to another state with other digits, just figure out how much this will "cost" us -- it is the sum of inversions where (items in bitmask) < (next item). Then just take the minimum of dp[(1 << 20) — 1] and that's the answer.
•  » » » » » 13 months ago, # ^ |   0 20^2 * 2^20 (~4e8) felt slow to me when I thought about it but it's true there's 4s
•  » » » » » » 13 months ago, # ^ |   0 It even fits in 1 sec. My submission, 60632871 is 717ms
•  » » » » » » » 13 months ago, # ^ | ← Rev. 2 →   0 True ! But my unproved solution needs only 78ms 60641026 EDIT : it's been hacked, bad assumption and weak systests...
•  » » » » » 13 months ago, # ^ |   0 thanx a ton!! it really helped.
•  » » » » » 13 months ago, # ^ | ← Rev. 2 →   0 [DELETED]
 » 13 months ago, # |   0 Lose in the contest and Ticket Game. :(
 » 13 months ago, # |   +19 I will become specialist,);
 » 13 months ago, # |   +3 For D, can somebody mathematically prove why the average possible value of first half must be equal to average possible value of second half for Bicarp to be the winner?
•  » » 13 months ago, # ^ |   0 if ? only on one side: Bicarp always can add (9-a) value on the same side where "a"=previous step from MonocarpIf ? on both side: Bicarp always can add the same value on 2nd side like Monocarp on previous step on 1st side
 » 13 months ago, # |   0 how to do D，sos！！！
•  » » 13 months ago, # ^ |   0 I made some observations, but I may be incorrect.(1) If you remove a question mark from each half, the winner does not change. I could not fully prove this, but a partial proof is if Bicarp was the winner before, then adding a ? to each side means that any Monocarp's move can be countered by Bicarp by doing the exact same move on the other side. (2) So we can keep removing question marks until only one half has a question mark. Now if there are odd number then Monocarp has the last move and can always win. (3) Define difference as subtraction of question_mark half from other_half. If even then if the difference/9 = question_marks/2 then Bicarp wins, else monocarp wins (also difference%9 must be 0 and difference must be positive). This is because any move Monocarp makes, Bicarp can make a move so that the sum of their moves goes up to 9.
•  » » » 13 months ago, # ^ | ← Rev. 3 →   0 Intuitively it hit me that it has something to do with average value of both halves. I calculated sum1= sum of first half by replacing all '?' with 0,sum2= sum of second half by replacing all '?' with 0,max1= sum of first half by replacing all '?' with 9,max2= sum of second half by replacing all '?' with 9, Then observed that it was Bicarp who was winning if sum1+max1= sum2+max2 and it passed. Not able to prove it mathematically as to why this is happening.
•  » » » » 13 months ago, # ^ |   +1 Proof:1, as above, we can assume there are question marks only on one side 2, assume that left half has no question marks. Suppose the right string is xxxxx????. Then if Monocarp plays any value i, then Bicarp can play 9-i, and can always make the string reach the average_value as you calculated. 3, Bicarp cannot make the string reach any other value, because then Monocarp would simply deviate.
•  » » » 13 months ago, # ^ |   +8 After you delete same number of question marks from each side the remainder of question marks is guaranteed to be even. Let s be the remaining number of question marks and f be the difference of both halves. Now first move is made by Monocarp as there was even moves removing question marks from both sides. Now for the last part if the remaining question marks are from the bigger half, Monocarp is guaranteed to win as you can't put minus digits. Now if from the lesser half, if (s / 2)*9 == f, Bicarp wins by putting (9 — (digit monocarp put)) every turn. In other cases if (s / 2)*9 < f Monocarp just puts 0 every turn and f is unreachable. Else if (s / 2)*9 > f Monocarp just puts 9 in every turn and f is surpassed.
 » 13 months ago, # |   0 Can someone give hints for problem C?
•  » » 13 months ago, # ^ |   +1 Find (b,a) pairs, (such that first string has 'b' in that position and second string has 'a'), and use one swap to fix. Find (a,b) pairs and use one swap to fix. Then find the remainder (b,a/a,b) pairs if there exist, and use two swaps to fix.
•  » » » 13 months ago, # ^ |   0 After reading your cooment and seeing some code, I got to know that string only contains alpha 'a' and 'b'. I wasted so much time on it after solving D. Is it possible to solve when each alphabet is allowed.
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 Look for all pairs (i, j) of discrepancies such as s[i] != t[i] and s[j] != t[j] and s[i] != t[j], and swap them. If there is no such a pair now, swap s[i] with t[i]. Continue until all is fixed.
 » 13 months ago, # |   +2 How to solve B ?
•  » » 13 months ago, # ^ | ← Rev. 2 →   +1 Use dynamic programming — calculate the number of negative and positive substrings ended at each position. The accumulated value will be the answer.
•  » » » 13 months ago, # ^ |   0 can you explain your recurrences in both the cases, I can only understand for negative value which add one from previous positive when a[i] < 0
•  » » 13 months ago, # ^ | ← Rev. 5 →   +8 Define dp(i,+) as the number of arrays that end on the i'th array that are positive, and dp(i, -) as the number of arrays that end on the i'th array that are negative.Then the dp states are updated as follows. if the current number is positive then dp(i,+) += dp(i-1,+) + 1 dp(i,-) += dp(i-1, -)if the current number is negative dp(i,-) += dp(i-1,+) + 1 dp(i,+) += dp(i-1,-) (the + 1 is because the number itself adds to the answer if it is positive or negative)Final answer is sum of all dp(i,-) and dp(i,+)60616510
•  » » 13 months ago, # ^ | ← Rev. 3 →   +1 my submission first go through whole array and count start from idx 0 and end at 0 to n — 1;and count if segment is negative or positive;neg, pos;set positives = 0, negatives = 0;and go through idx 0 to n -1 again. if current array element is positive pos--; else if current element is negative neg--; swap(pos, neg) positives += pos; negatives += neg;time complexity is O(n)
•  » » » 13 months ago, # ^ |   0 Is there any similar question like B
•  » » » 13 months ago, # ^ |   +1 Amazing idea !
•  » » » » 13 months ago, # ^ |   0 Thank you!
 » 13 months ago, # |   +16 Is there something wrong on score board?
 » 13 months ago, # |   +12 Back to green :)
 » 13 months ago, # |   +13 When I finished the program of problem C, the contest just had ended.I am too slow!What a pity! I need to practice more! Practice makes prefect.
•  » » 13 months ago, # ^ |   0 Exactly the same thing, half hour more and I would solve it also. Today with minor fixes my solution has passed.-rating but +knowledge
 » 13 months ago, # |   +5 Is there something wrong with the rating board?I can see my E,F both accepted in status,also when i click the -1 on the rating board.But the rating board shows that they fail in the system test(FST).
 » 13 months ago, # |   +9 Wow, so many WA on D...
 » 13 months ago, # | ← Rev. 2 →   +6 Just what the heck is D test case 23, literally hacked half the solutions. Btw, How do we solve D, and what's the intuition for it?
•  » » 13 months ago, # ^ | ← Rev. 2 →   +3 I solved D with greedy:Try to maximize left half, minimize left half, maximize right half, or minimize right half for Monocarp, then if at least in one case Bicarp can't make it equal, Monocarp win, else Bicarp.
•  » » » 13 months ago, # ^ | ← Rev. 2 →   0 So basically we need to simulate the process of maximizing one part and check if the other part can still be equal?
•  » » » » 13 months ago, # ^ | ← Rev. 5 →   +3 Basically i let Monocarp play his ceil(cnt / 2) turn with the mentioned strategy, and let Bicarp try to equalize. (cnt = number of ? in string).Actually checking first 2 case is enough.
•  » » 13 months ago, # ^ |   0 Split the string into two part, calc the sum of left and right parts (denoted as s1 and s2), and how many unknown digit for each sides(denoted as c1 and c2).Then this problem become: there is a number s=s1-s2, you can do c1 times plus operation and c2 times subtract operation, if the result is 0, then the second guy win, else the first one. Now it's still difficult, so let's transform subtract operations into plus operations. Because of subtract x equal to plus y-9 while y = 9-x.So now the problem is about a number s'=s-9*c2, you can do c1 + c2 times plus operation.It's easy to prove only when res = s' + 9 * (c1 + c2) / 2 equal to 0, the second guy will win.If res < 0, then first guy can always plus 0 in each turn, else plus 9 in each turn.I don't know whether the idea is right because I haven't submited it.
 » 13 months ago, # |   0 Ihacked other's problem D successfully during the contest;Ion problem D got a FST;Iwrote a "if(tmp==(a-b)/9)" while it's supposed to be "if(9*tmp==(a-b))".
 » 13 months ago, # | ← Rev. 2 →   +42 Why is the submission 60623002 still running on pretest 8
•  » » 13 months ago, # ^ |   +32 His code has been running on pretest 8 for 2 hours lol
 » 13 months ago, # |   +30 So good pretests for D
•  » » 13 months ago, # ^ |   +2 Probably Bleddest and his team are fans of trash rounds from '...' with lots of hacks and being in love with bad pretests. OR THEY THOUGHT THAT IT WOULD BE EDUCATIONAL ROUND LMAO
•  » » 13 months ago, # ^ |   0 Many solutions on D failed because several contestants did integer division by 9. That works if Bicarp wins, but may give a false alarm if Monocarp wins.
 » 13 months ago, # | ← Rev. 2 →   0 I got a wrong on test 9 on problem B coz i wrote (int n) instead of (long long n ) . now I feel sad , I spent time on it and didn't get it till the contest is finished .
•  » » 13 months ago, # ^ |   0 Everyone of us has gone through this phase my friend :)
 » 13 months ago, # |   +31 Me: ratings -110 in a weekend, life sucks
•  » » 13 months ago, # ^ |   0 :(Frequently
 » 13 months ago, # |   +3 I wrote D in a different way.Consider their moves, at first, it must be M try to enlarge the gap between the sum, and B try to make it smaller.So we can brute force their choices, and just consider edge cases that they need to move on the same side. It is easy to find that the maximum gap and minimum gap can M create can calculate in O(1), so the problem can be solved.
 » 13 months ago, # | ← Rev. 2 →   0 On problem C, why this answer: 3 {1 3} {2 6} {7 8} is not good for this test: 8 babbaabb abababaa It seems ok...
•  » » 13 months ago, # ^ |   0 never mind.
 » 13 months ago, # |   0 why is the system testing taking so long!!!
 » 13 months ago, # |   0 how to solve A? I didn't get the idea
•  » » 13 months ago, # ^ | ← Rev. 3 →   +5 My solution: (not the optimal solution)For the minimum: Consider C is the number of players and k is the amount of cards a player can get before being banned. Every player can receive k-1 cards and still be in the game so you can give every player k-1 cards and since every player is one card away from being banned the number of cards left is the minimum number of players. min = min_team1+min_team2; (if minimum is negative result = 0 !!)For the maximum: you can pick the team with the smallest k and while players > 0 and n-k >= 0 you can pick a player then n = n-k; then same for the second team. you can do this with math equations but I find Greedy easier to understand
•  » » 13 months ago, # ^ |   0 A more naive solution: Just use priority queue to simulate the process.My solution can be found here.
 » 13 months ago, # |   +8 Any idea how to solve problem C, if the strings are allowed to have any characters from lowercase English alphabet?We can reduce the strings to atmost $26×25$ length by removing matching pairs and reducing similar non matching pairs like we did with all indices where $s[i]=a$ and $t[i]=b$ in problem C. Will greedy work after that?
•  » » 13 months ago, # ^ |   +3 Well, one observation is that any operation must increase the number of matching indices (s[i] == t[i]) by at least 1. So we might iterate over all pairs of indices and check whether we can make an operation such that for one of those indices, say j after the operation, s[j] == t[j]. If we find such a pair, we remove j and continue. Otherwise, we stop and if the string is non-empty, then there is no solution.That works in time O(alphabet_size ^ 6), which seems to be well enough.
 » 13 months ago, # |   0 The 3rd Test Case for C question . Can it be done in 2 moves rather than 3 ??
 » 13 months ago, # |   0 can someone help me the case where my solution for B fails.. My-solution
•  » » 13 months ago, # ^ |   +1 pref[i] *= arr[i] / abs(arr[i]) We dont need array a we just need sign of a and if you do just pref[i] *= a[i] then after 3 iterasions with 10^9 it becomes 10^27 which doesn fit anywhere
•  » » » 13 months ago, # ^ |   0 Thanks got it
 » 13 months ago, # |   +11 The editorial is out!I am really sorry for the issue with problem E. Looks like before the contest I was too inattentive to think about solutions without subset DP and how to eliminate them. After seeing this idea in a comment, I started stressing a test against it and simultaneously trying to prove it, but by the time the countertest has been found, it was already too late (something like 2 hours after the round).
•  » » 13 months ago, # ^ |   +13 How were you generating testcases? Spoiler71 2 2 3 1 1 2I found this is the smallest case that should prevent people from calculating cost the wrong way and it's only 7 digits long.
•  » » » 13 months ago, # ^ |   0 I tried stressing on 3 different colours and small length of the input (from 5 to 15), and only after increasing length I actually generated something useful (a testcase with $n = 284$ which breaks these solutions).Maybe it was bad to choose a range of possible lengths instead of some fixed length.
 » 13 months ago, # | ← Rev. 2 →   +8 Can anyone please tell why my B passed? When I looked at it after contest and ran it through some cases, It didn't make sense. https://codeforces.com/contest/1215/submission/60621363
•  » » 13 months ago, # ^ |   +9 I also didn't understand your code at first and tried to come up with countercases, but I couldn't and in the process, I came to the conclusion that the algorithm was correct.So here's a small proof:First notice that pref[i] % 2 == 0 iff the product of numbers up to i is positive.When calculating the number of positive subsegments, you have 3 terms: The number of ways to choose two indices, i and j, such that the products of numbers up to i (inclusive) and j (inclusive) are both positive / both negative. That means that, in both cases, there is an even number of negative numbers between i + 1 and j (we use a similar property when constructing prefix sums). Thus, the subsegment (i, j] is suitable. The number of indices i such that the product of numbers up to i (inclusive) is positive. This means that the subsegment [1, i] is suitable (1-based indexing). So we proved that all those subsegments are positive. It remains to prove that we haven't missed any other positive subsegments.Let's make the proof by contradiction. Assume there is a subsegment (i, j] such that the products of numbers up to i and j (both inclusive) have different signs. That means that there is an odd number of negative numbers in the interval [i, j] (again, remember prefix sums), and the subsegment is negative.The number of negative subsegments is simply this amount subtracted from the total number of subsegments.Overall, B was a bit tricky, even though it's obvious that the problem is classic. It took me the longest to solve from [A, D], and I have only a vague understanding of why my code works.Hope that helped!
 » 13 months ago, # |   +3 Can someone tell what's wrong with my solution for D. I've greedily simulated the game by M increasing the difference and B reducing it. Code
•  » » 13 months ago, # ^ |   0 maybe sometimes if M reducing the difference is a better choose. like this example:4 ??01if M choose write a number>=2 on the left sum(right)-sum(lift) will be negative，and M will win. but you code will cout B.
 » 13 months ago, # |   0 This is my code for D which simulates the game optimally .My code
 » 13 months ago, # |   0 Lovely contest. Keep up the work
 » 13 months ago, # |   0 Still waiting for the editorial.!
•  » » 13 months ago, # ^ |   0 It was already out when you asked about it: editorial
 » 13 months ago, # |   0 When will the winners be announced? :3
 » 13 months ago, # |   +15 The full Qualification Stage has been added to the Codeforces Gyms. Note that the problem "The Number of Products" is different from the one used in the round.
 » 13 months ago, # |   +3 Problem difficulties have not been assigned yet.
•  » » 13 months ago, # ^ |   0