Hi everyone!
I'm pleased to announce Codeforces Round #410 (Div. 2) that will take place on Friday, 17:35 MSK. I'm the writer of the round.
I'd like to say thanks to Alex netman Vistyazh and Marcel please_delete_account Bezdrighin for feedback and help in preparing the round and to MikeMirzayanov for awesome platforms : Codeforces and Polygon.
I hope you will like the problems.
Good luck and have fun!
UPD: Scoring distribution: 500 — 1000 — 1500 — 2000 — 2500
UPD 2. The round is finished. Congratulations to winners:
Div 2:
Div 1:
Editorial: Link
Why are Div.1 participants able to register in-contest and are not shown out of competition?
UPD: It is Fixed now.
good luck.
Good luck to everyone!
Really Nice & Short Announcement... Hope to have the Problems will be similar to the size of announcement and interesting. All the best for all the contestants :)
Don't worry :) This bug will be fixed soon.
I am afraid because your previous round was damn hard. :(
Hard rounds are good because you always learn something new.
But why learn things if it means losing juicy rating /s
Then what for are you there?? To solve easy problems and get nice colour or to learn new interesting algorithms?
Both. I mean, getting nice color and to learn new interesting algorithm
that's true. but even A only ~60% solved in his previous round. wasn't that pathetic?
Is it rated, you know.
That's not interesting and cool if you ask this question Do you think it's funny? Or you are so cool? Why the hell people don't understand this shit :/
You don't, why should I kek XD lol memes
It maybe the last round before retired,i hope this round quickly judged. Better rating! (:
why retired ?
why 36 upvote?? :(
I love this scoring distribution :)
God Bless Let's go...
Queue already 45 pages long...
queue :'(
This queue can make round unrated
Queue. :(
I submit, get WA in like 10 mins and lose points. Do smth please.
This queue made me lose 10-15 min, thinking that my solution is correct! :/
Yah, same happened with me
I tried to submit the solution for Q- A but after clicking on submit button it's not get submitted and the cursor is still moving from last 45 min...but my solution is still not in the queue list even why ???
WHAT IS PRETEST 8 IN PROBLEM A ITS DEPRESSING...
bbb, ans=YES
guys look at this Problem after Contest its really interesting Problem :) http://codeforces.me/problemset/problem/23/C
anyone who gave up and start reading comments and blogs!
They are not the same.
I didnt say they are same
Who are 'they' ? ;)
me and earl and the dying girl
Why did you stop participating?
To stay out of cyan :) That place is scary
I was competing with you and always checked your score. Now I miss that =)
Maybe one day when I can be more courageous, I will submit again :)
How do you find such problems? Did you do it before or did you make a google search?
Hint : He's actually in div 1.
I am div 1 but I didnt find it. So I am a fake div 1 ????
I didn't say that.
Then what is the relation between being in div 1 and finding the problem ? As you gave it as a hint.
Chances of having solved it previously is higher.
Well you are saying it in certainty but not "higher chance".
even if he solved it, I think it is remarkable to be able to be able to find the problem. I cant remember which contest half the problems I solved is at.
A pretest 8 Damnnnn
Interesting round! First time I solved all the problems (mentally) :D
Народ как решаеться 2 задача? каким методом ? тут что то связання с префикс функциями?
перебор
эх зря не попытался ( думал по времени не пройдет
Я тоже так сперва думал, но потом перемножил 3 числа 50 * 50 * 50 и успокоился.
я также перемножил эти 3 числа но не успокоился думал префиксами решаються
там 50 * 50 * 50 * 50
Ну, у кого как :)
How do I do C?
You can make them all multiples of 2.
But this is always minimal?
Yes
click
Unless gcd is already greater than 1, yes this is always minimal. Because by the operation mentioned in the problem, you can never introduce a new odd factor which wasn't present previously in the array (you can easily prove this by setting a-b=k*n1 and a+b=k*n2 where k is odd , figure out how n1 or n2 will look like). The best you can do is introduce an even factor, namely 2
I tried to do this but it gave me WA, though maybe my code is just wrong.
check the following test:
Edit: Answer should be 5
The answer given by my code is "YES 5"
Okay I found my mistake, thanks :)
I wrote something like this, but it failed in pretest #4, did I just fail to implement properly?
If gcd is greater than 1 the answer is 0, otherwise the only solution is to transform all the numbers to even numbers so they are dividable by 2.
How to solve D?
The best-case scenario is to take the biggest K. After that I try to randomize the solution's sequence of length K, but TLE ....
I did that and got AC :) maybe your random-sequence generation is too slow
Fix k to floor(n / 2) + 1, then sort the array with a or b together. then choose 1,3,5,...,n (maybe one more number which optimize the answer, it depends on the parity of 'n') for array a obviously bigger than sum / 2. There is two condition now:
I almost solve it in time and submit in the last minute, but i forget to output k.....TT
I feel so stupid now :)
Thank you for the solution :)
How the hell do you solve C ???
if gcd is 1, make all the numbers even.
I proved this:
a[i] = t*k1, a[i+1] = 2*k2 where gcd( a[i], a[i+1] ) = 1, then you can't make their gcd > 1 in less than two moves :)
Proof:Let's show that it can't be made in only one move.
b[i] = a[i] — a[i+1] = t*k1 — 2*k2,
b[i+1] = a[i] + a[i+1] = t*k1 + 2*k2
b[i+1] = b[i] + 4*k2.
Assume b[i] = c*k2, for b[i] and b[i+1] to have gcd > 1 in this move itself. Notice that b[i] is odd.
b[i] = t*k1 — 2*k2, b[i] = c*k2. This meaans t*k1 = (c+2)*k2.
gcd(k1, k2)=1 from our initial condition that gcd=1. This means t=k2. But this contradicts the same assumption.
There's no case where the answer is NO, right?
1 1
This case is where ans is NO.
n >= 2
Your testcase isn't valid.
nope. answer is 1. after 1 operation- it turns 0 2 gcd(0,2)=2
0 0
Two elements. Both 0
all elements >=1
"1 ≤ a_i ≤ 10^9"
True. [odd even] can be made [even even] in two moves, and [odd odd] can have either already gcd>1 or they can be made so in one move.
ahhh i didn't pen and paper for [even even], i thought that if [even even] exist the answer will be NO, ahhhh what a day
less than two
do you mean <= or < 2? <= right?
You can't make in less than 2, which means you CAN make in >= 2 moves by simply adding them together twice.
Yes, sry I misread :D
So 2 is always possible, interesting
I wrote something stupid for C and it worked. But still, could someone tell me the actual solution?
sequences sequences everywhere
What's the hack case for C?
2 7 14
Maybe n=2, a={3, 3}. Case of gcd(a1, a2,..., an) > 1, the answer is 0.
How to solve D? I think it is too hard for D problems in div 2 :((
How to solve A ?
My greedy algorithm for D works like this : sort by value of a in descending, then store it in temporary array A' sort by value of b in descending, then store it in temporary array B'
then greedily I pick between the larger point in A'[i] and B'[j] if the i-th and j-th index haven't been picked already. Wrong answer on pretest 7, can anyone give me a counter case for my algorithm?
Submission : Here
EDITED : I change my solution with random shuffle and get accepted. Looks like Luck beats hard work this time
fonmagnus I also had the same mistake . What I did was pick max in A and B alternatively . It passed 7 but failed in pretest 8 :).
Btw I think I got my mistake for 8 and tried submitting it but contest ended as my internet was a bit slow.
I also checked that if I choose k-1 largest values in sorted A, what is the minimum value in the remaining sorted A that I can choose, and I discard all values( along with their Bs ) that are lesser than this smallest value.
is there a "NO" case in C?
1 1
That's an invalid input.
n >= 2
ans is 1 right? 1 1 -> 0 2. So 1 step?
length of sequence >=2 pls dont give me a heartattack
I think it's YES (only one operation)
0 2
n > 1 dude
NO
hope that's true
всплакнул)
Как задача D решается?
My idea for problem C.
If their GCD is > 1 then for sure the answer is 0.
If not then we want to make their GCD > 1.
Assume that we want to make their GCD = x. Where x > 1
Then there should Exist an a[i] such that a[i] % x != 0 (else their gcd would have been >= x which is > 1).
So now we need to change a[i] to something which is divisible by x.
Assume that we will make the new a[i] using a[i + 1], by deleting both and putting a[i + 1] — a[i], a[i] + a[i + 1]
if initially a[i] % x = A and a[i + 1] % x = B, we need B — A to be 0 (B = A) because we need (a[i + 1] — a[i]) % x to be zero.
Then now we know that A should be equal to B, and since B + A = x or now we can say (A + A = x) then now we know that our x should also be even. and if x is even then we need their gcd to be divisible by 2.
Then try to make them all divisible by two with the minimum cost.
Then if there exist an a[i] % 2 = 1 & a[i + 1] % 2 = 1 then make them together with cost 1. else you will need to make every a[i] % 2 = 1 with the number before or after it with cost 2.
What was test-case 5 for problem A?
Something like
abccba. Answer isNO.I guess it like this: abcba
Answer is YES.
If string was already palindromic, it would be NO, since the problem says exactly one letter, not <= one letter. I also spent quite a while on this same bug :(
OH No! I spend 2 hours debugging my code
Not if the string is of odd length, one can change the centre character
True that. Luckily my code is brute force, so I don't have that as a bug ;)
My solution of C:
1) find gcd of the sequence
2) go through the sequence two times: a) check for pairs (odd, odd) b) check for pairs(odd, even) and (even, odd)
but i still don't understand is it ok or not
omg that thing worked
so full explaination:
check if the gcd of the seq is > 1 than ans is: YES 0
else: go through the seq and do the operation once on pairs where both nums are odd
go through the seq again and do the operation twice on pairs where one num is even and one num is odd
answer is: YES
Very good tasks ! Harder than usual, I couldn't invent anything normal for fourth problem. Still I believe I could get AC with choosing random subarrays ( on first view and some easy probability it looks that you have 50% chance to guess answer each time), but I start to implement that idea very late and of course it is not expected solution.
Is E just a simple topological sort?
how to approach D?
Hi, Can anyone prove that making all numbers even in problem C will yield an optimal solution. I figured that but could not prove it :(
Here's the approach Link Try to prove it yourself first. It will be fun.
Consider cases where adjacent numbers are even,even; odd,odd; even,odd; odd,even and see how the operation affects them.
Link
Question B, WA at test 94 :)
What are you so happy about? Is 94 some lucky number? :)
No. Just because am speechless. So why not just smile :)
How to solve D? Any hints?
I used random_shuffle to solve it. In the example:
100000
1 1 1 1 ... 1 1 1 2
2 1 1 1 ... 1 1 1 1
We could easily find out that we should choose as many numbers as possible.
So we choose 50001 numbers.
Also, we could find out that we must choose number 2.
So, the possibility of choosing the number 2 in the array A is:
1-C(99999,50001)/C(100000,50001),approximately 1/2.
So, the possibility of choosing the right answer is 1/4.
We can see that the possibility is actually very high. I hope that my solution could help you:)
на чем B падает?
У тебя — на переполнении.
What a weak acmer I am!! I got 4 WA at the first problem.
Very cool problems!
Any deterministic solution for D?
Check mine.
Actually it is some constructive + working with different cases.
Start with sorting all items by weight in B's in descending order, then declare all even-indexed (0, 2, ..) elements as "set1" and other as "set2".
First observation: total in B's of "set1" is greater or equal then total of "set2", and the equality is only possible for even n and all B's equal.
Second observation: total of "set1" minus total of "set2" is no more than largest (first) element of "set1", (draw a pic).
Then calculate total in A's of "set1" and "set2" and declare one as answer, possibly adding one element from the other set. (For details check mine solution -- it is checking all cases).
LOL, are u serious about D tests ? 26562304
I passed D using randomized algorithm.
Just random k elements from A and B with equal indexes until correct answer got.
http://codeforces.me/contest/798/submission/26561705
What's the complexity of that? how many time it spends finding the solution and why did you decide to code it? I mean, what was your insight?
There is another similar problem using randomized algorithm in Codeforces
Wait a minute, I'm seaching this problem.
I will post this problem later.
http://codeforces.me/problemset/problem/364/D
Finally， I found it.
It is really a hard task to find one problem from this large problemset.
Almost one year ago, someone ask for me this problem. I do not think it can be solved by traditional algorithm. I mean maybe we can random.
There is a simliar word in Today's Promblem. It's HALF. So， I try it with similar algorithm.
These kind of randomized algorithms are called as Las Vegas algorithms . These algorithms always produces the correct result but gambles with the resources used for the computation .
Here is another randomized solution!!! http://codeforces.me/contest/798/submission/26560973
look at it :p . I found this pretty cool!
Can anyone calculate the probability of getting the right answer? I think it's cool, and I didn't work this algorithm out during contest. Maybe we can prove this algorithm is right? (if the probability of getting the right answer if very big, like 99.999% :) )
WTF!! I didn't submit my solution for problem C because I didn't find the case for "NO".
So easy E, why only 3 ACs?
Because it's not easy.
Maybe
From the editorial, it looks like it was just a topological sort. People were stuck on D for long time, plus long queues.
toposort + avoiding quadratic time
For problem D, anybody know how to approximate the probability of not getting a valid subset while taking one randomly? I got AC but it was just a feeling, couldn't get the probability
thanks :)
Sigh, I was solving the wrong problem A the whole time. I was solving "change at most one letter" instead of "exactly one letter", even if that was in bold in the problem statement :(
i am not able to submit solution.On clicking the submit button,nothing is happening.i am not getting why this is happening but because of this am not able to give contest nd also it is not sumbitting after contest for any of the problem.
Isn't problem D the same as CF23C?