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!
I'm newbie. i want to know how to contribute problems for contests???
You can know more here: https://codeforces.net/blog/entry/49569
thanks <3
Overlaps with atcoder bc141 D:
Well I did a good jod in 584
isn't that a clash with AtCoder Beginner Contest 141?
[deleted]
Not Original, Copied it from some previous post because it was hilarious. xD
To be honest, there should be more Division 3 rounds!
Friendly time for Chinese users!
YES,very nice
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.
I think they can't move it because it's like online mirror of the on-site contest.
Good 好好!
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
How old are you?
14.
Cool!! CM at 14!!!
Maybe you finished it just now...
I'm just like you.
I'm going to do screencast with commentary in English of this round first, and then jump to ABC141. YouTube
waiting for it :)
Here it is
Friendly time for Chinese! I can participate even in my school!!!!!
School on Sunday?
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)
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……
Yeah they're not wrong... But it's the truth...
Scoring distribution?
What is the hack for D?
Is there a simpler solution to F than 2sat with segtree?
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$$$).
How to solve E in this contest? Why more than 200 participants solved it?
I think it's googlebale, if you google it you might find a solution, Am not sure thought :(
Very similar ?
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.
Are you sure this doesn't end up in a cycle?
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
Unfortunately, I'm not in division 1 right now, so I can't hack your solution; but your assumption fails with:
26 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
Oh nice ! thanks. Too bad for weak systest though.
your hack works: 60632025
Ohh, actually I wanted to hack it if I managed to return to div 1 next week :D
DP on bitmask, like travelling salesman problem, except this time the distance is number of inversions.
Is there a way to precompute the number of inversions? My submission got TLE on test case 7
can u explain briefly how u did this problem!! it would be a great help
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.
20^2 * 2^20 (~4e8) felt slow to me when I thought about it but it's true there's 4s
It even fits in 1 sec. My submission, 60632871 is 717ms
True ! But my unproved solution needs only 78ms 60641026 EDIT : it's been hacked, bad assumption and weak systests...
thanx a ton!! it really helped.
[DELETED]
Lose in the contest and Ticket Game. :(
I will become specialist,);
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?
if ? only on one side: Bicarp always can add (9-a) value on the same side where "a"=previous step from Monocarp
If ? on both side: Bicarp always can add the same value on 2nd side like Monocarp on previous step on 1st side
how to do D,sos!!!
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.
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.
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.
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.
Can someone give hints for problem C?
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.
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.
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.
How to solve B ?
Use dynamic programming — calculate the number of negative and positive substrings ended at each position. The accumulated value will be the answer.
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
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.
time complexity is O(n)
Amazing idea !
Thank you!
Is there something wrong on score board?
Back to green :)
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.
Exactly the same thing, half hour more and I would solve it also. Today with minor fixes my solution has passed.
-rating but +knowledge
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).
Wow, so many WA on D...
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?
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.
So basically we need to simulate the process of maximizing one part and check if the other part can still be equal?
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.
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.
I
hacked other's problem D successfully during the contest;
I
on problem D got a FST;
I
wrote a "if(tmp==(a-b)/9)" while it's supposed to be "if(9*tmp==(a-b))".
Why is the submission 60623002 still running on pretest 8
His code has been running on pretest 8 for 2 hours lol
So good pretests for D
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
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.
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 .
Everyone of us has gone through this phase my friend :)
Me: ratings -110 in a weekend, life sucks
:(
Frequently
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.
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...
never mind.
how to solve A? I didn't get the idea
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
A more naive solution: Just use priority queue to simulate the process.
My solution can be found here.
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?
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, sayj
after the operation,s[j] == t[j]
. If we find such a pair, we removej
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.
The 3rd Test Case for C question . Can it be done in 2 moves rather than 3 ??
can someone help me the case where my solution for B fails.. My-solution
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
Thanks got it
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).
How were you generating testcases?
7
1 2 2 3 1 1 2
I found this is the smallest case that should prevent people from calculating cost the wrong way and it's only 7 digits long.
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.
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.net/contest/1215/submission/60621363
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 toi
is positive.When calculating the number of positive subsegments, you have 3 terms:
The number of ways to choose two indices,
i
andj
, such that the products of numbers up toi
(inclusive) andj
(inclusive) are both positive / both negative. That means that, in both cases, there is an even number of negative numbers betweeni + 1
andj
(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 toi
(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 toi
andj
(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!
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
maybe sometimes if M reducing the difference is a better choose. like this example:
4 ??01
if 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.
This is my code for D which simulates the game optimally .My code
Lovely contest. Keep up the work
Still waiting for the editorial.!
It was already out when you asked about it: editorial
When will the winners be announced? :3
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.
Problem difficulties have not been assigned yet.
MikeMirzayanov