### reality420's blog

By reality420, history, 12 months ago, ,

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 yosei-san 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:

•
• +240
•

 » 12 months ago, # | ← Rev. 4 →   +70 Why are Div.1 participants able to register in-contest and are not shown out of competition?UPD: It is Fixed now.
•  » » 12 months ago, # ^ |   -17 good luck.
 » 12 months ago, # |   -12 Good luck to everyone!
 » 12 months ago, # |   +2 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 :)
 » 12 months ago, # |   -6 I hope I won't feel too much down tomorrow :|
 » 12 months ago, # |   +50
•  » » 12 months ago, # ^ |   +29 Don't worry :) This bug will be fixed soon.
 » 12 months ago, # |   +9 I am afraid because your previous round was damn hard. :(
•  » » 12 months ago, # ^ |   +27 Hard rounds are good because you always learn something new.
•  » » » 12 months ago, # ^ |   +14 But why learn things if it means losing juicy rating /s
•  » » » » 12 months ago, # ^ |   -6 Then what for are you there?? To solve easy problems and get nice colour or to learn new interesting algorithms?
•  » » » » » 12 months ago, # ^ |   +14 Both. I mean, getting nice color and to learn new interesting algorithm
•  » » » 12 months ago, # ^ |   +8 that's true. but even A only ~60% solved in his previous round. wasn't that pathetic?
 » 12 months ago, # |   -28 Is it rated, you know.
•  » » 12 months ago, # ^ |   +4 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 :/
•  » » » 12 months ago, # ^ |   -9 You don't, why should I kek XD lol memes
 » 12 months ago, # |   +38 It maybe the last round before retired,i hope this round quickly judged. Better rating! (:
•  » » 12 months ago, # ^ |   +4 why retired ?
•  » » 12 months ago, # ^ |   0 why 36 upvote?? :(
 » 12 months ago, # |   +4 I love this scoring distribution :)
 » 12 months ago, # |   0 God Bless Let's go...
 » 12 months ago, # |   +13 Queue already 45 pages long...
 » 12 months ago, # |   +4 queue :'(
 » 12 months ago, # |   +2 This queue can make round unrated
 » 12 months ago, # |   +6 Queue. :(
 » 12 months ago, # |   +5 I submit, get WA in like 10 mins and lose points. Do smth please.
 » 12 months ago, # |   +21 This queue made me lose 10-15 min, thinking that my solution is correct! :/
•  » » 12 months ago, # ^ |   +3 Yah, same happened with me
 » 12 months ago, # |   +5 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 ???
•  » » 12 months ago, # ^ |   0 same is happening with me too. Trying to submit the solution from past 40 mins. Not Working :(
 » 12 months ago, # |   0 What a delay...
 » 12 months ago, # |   -11 WHAT IS PRETEST 8 IN PROBLEM A ITS DEPRESSING...
•  » » 12 months ago, # ^ | ← Rev. 2 →   +3 bbb, ans=YES
 » 12 months ago, # |   +52 guys look at this Problem after Contest its really interesting Problem :) http://codeforces.com/problemset/problem/23/C
•  » » 12 months ago, # ^ |   +19 anyone who gave up and start reading comments and blogs!
•  » » 12 months ago, # ^ |   -9 They are not the same.
•  » » » 12 months ago, # ^ |   +14 I didnt say they are same
•  » » » » 12 months ago, # ^ |   -24 Who are 'they' ? ;)
•  » » » » » 12 months ago, # ^ |   0 me and earl and the dying girl
•  » » » 12 months ago, # ^ |   0 Why did you stop participating?
•  » » » » 12 months ago, # ^ |   0 To stay out of cyan :) That place is scary
•  » » » » » 12 months ago, # ^ |   +5 I was competing with you and always checked your score. Now I miss that =)
•  » » » » » » 12 months ago, # ^ |   0 Maybe one day when I can be more courageous, I will submit again :)
•  » » 12 months ago, # ^ |   +6 How do you find such problems? Did you do it before or did you make a google search?
•  » » » 12 months ago, # ^ |   0 Hint : He's actually in div 1.
•  » » » » 12 months ago, # ^ |   +20 I am div 1 but I didnt find it. So I am a fake div 1 ????
•  » » » » » 12 months ago, # ^ |   0 I didn't say that.
•  » » » » » » 12 months ago, # ^ |   +3 Then what is the relation between being in div 1 and finding the problem ? As you gave it as a hint.
•  » » » » » » » 12 months ago, # ^ |   0 Chances of having solved it previously is higher.
•  » » » » » » » » 12 months ago, # ^ | ← Rev. 2 →   0 Well you are saying it in certainty but not "higher chance".
•  » » » » » » » » 12 months ago, # ^ |   0 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.
 » 12 months ago, # | ← Rev. 2 →   +2 A pretest 8 Damnnnn
 » 12 months ago, # |   -19 Interesting round! First time I solved all the problems (mentally) :D
 » 12 months ago, # |   +8 How do I do C?
•  » » 12 months ago, # ^ |   +2 You can make them all multiples of 2.
•  » » » 12 months ago, # ^ |   0 But this is always minimal?
•  » » » » 12 months ago, # ^ |   0 Yesclick
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   +3 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
•  » » » 12 months ago, # ^ |   0 I tried to do this but it gave me WA, though maybe my code is just wrong.
•  » » » » 12 months ago, # ^ | ← Rev. 3 →   +3 check the following test: 6 1 2 1 1 1 2 Edit: Answer should be 5
•  » » » » » 12 months ago, # ^ |   0 The answer given by my code is "YES 5"
•  » » » » » » 12 months ago, # ^ |   +5 Okay I found my mistake, thanks :)
•  » » » 12 months ago, # ^ |   0 I wrote something like this, but it failed in pretest #4, did I just fail to implement properly?
•  » » 12 months ago, # ^ |   +5 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.
•  » » 12 months ago, # ^ |   0 This is what I did: NO is never an answer because you can make all of them multiples of 2. So check the gcd of all the numbers. If it is >1 we are done. Else for every odd number try to find an adjacent odd number. Now you can do the given operation to get multiples of two. If an odd number does not have an adjacent odd number then choose an adjacent even number and apply the operation 2 times.
 » 12 months ago, # |   +4 How to solve D?
•  » » 12 months ago, # ^ |   0 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 ....
•  » » » 12 months ago, # ^ |   0 I did that and got AC :) maybe your random-sequence generation is too slow
•  » » 12 months ago, # ^ | ← Rev. 6 →   +19 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: if sum of b(all of the index we chosed) is also fit the condition, print answer if not, then (2, 4, 6, ...) + (one optimize the two sum) must fit the condition I almost solve it in time and submit in the last minute, but i forget to output k.....TT
•  » » » 12 months ago, # ^ |   0 I feel so stupid now :)Thank you for the solution :)
 » 12 months ago, # |   +9 How the hell do you solve C ???
•  » » 12 months ago, # ^ |   +3 if gcd is 1, make all the numbers even.
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 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*k2b[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.
•  » » » 12 months ago, # ^ |   0 There's no case where the answer is NO, right?
•  » » » » 12 months ago, # ^ |   -40 1 1 This case is where ans is NO.
•  » » » » » 12 months ago, # ^ |   +21 n >= 2
•  » » » » » 12 months ago, # ^ | ← Rev. 2 →   +7 Your testcase isn't valid. The first line contains a single integer n (2 ≤ n ≤ 100 000) — length of sequence A. 
•  » » » » » 12 months ago, # ^ |   0 nope. answer is 1. after 1 operation- it turns 0 2 gcd(0,2)=2
•  » » » » 12 months ago, # ^ |   0 0 0
•  » » » » » 12 months ago, # ^ |   0 Two elements. Both 0
•  » » » » » » 12 months ago, # ^ |   0 all elements >=1
•  » » » » » » 12 months ago, # ^ |   0 "1 ≤ a_i ≤ 10^9"
•  » » » » 12 months ago, # ^ |   0 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.
•  » » » » » 12 months ago, # ^ |   0 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
•  » » » 12 months ago, # ^ |   0 less than twodo you mean <= or < 2? <= right?
•  » » » » 12 months ago, # ^ |   +3 You can't make in less than 2, which means you CAN make in >= 2 moves by simply adding them together twice.
•  » » » » » 12 months ago, # ^ | ← Rev. 2 →   0 Yes, sry I misread :DSo 2 is always possible, interesting
 » 12 months ago, # |   +6 I wrote something stupid for C and it worked. But still, could someone tell me the actual solution?
 » 12 months ago, # |   +41 sequences sequences everywhere
 » 12 months ago, # | ← Rev. 2 →   -6 How to solve C?I can get gcd using Euclidean Algorithm(if you know any better idea, can I ask you to tell any idea).
 » 12 months ago, # |   0 What's the hack case for C?
•  » » 12 months ago, # ^ |   0 2 7 14
•  » » 12 months ago, # ^ |   0 Maybe n=2, a={3, 3}. Case of gcd(a1, a2,..., an) > 1, the answer is 0.
•  » » 12 months ago, # ^ | ← Rev. 3 →   +1 n = 3 1 1 1 => 3 1 1 2 => 1 1 2 1 => 4 1 2 2 => 2 2 1 1 => 1 2 1 2 => 2 2 2 1 => 2 2 2 2 => 0 
 » 12 months ago, # | ← Rev. 2 →   +9 How to solve D? I think it is too hard for D problems in div 2 :((
 » 12 months ago, # |   +6 How to solve A ?
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 remember that we must change a character. first compare s[0.. n/2-1] and s[n-1.. n-1-(n/2-1)]YES : only one difference || ( n % 2 == 1 && every character is equal )NO : (Actually using 'else') ( n % 2 == 0 && every character is equal ) || more than 1 differences
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 Go from 0 to string.size /2, check how many pair char is different, let's call it n. if n == 1 => YESelse if n == 0 && string.size % 2 == 1 ==> YES // most failed here, included me.else => NO.
 » 12 months ago, # | ← Rev. 2 →   0 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 : HereEDITED : I change my solution with random shuffle and get accepted. Looks like Luck beats hard work this time
•  » » 12 months ago, # ^ | ← Rev. 2 →   +8 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.
•  » » 12 months ago, # ^ |   0 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.
 » 12 months ago, # |   +3 is there a "NO" case in C?
•  » » 12 months ago, # ^ |   -30 1 1
•  » » » 12 months ago, # ^ |   +11 That's an invalid input. The first line contains a single integer n (2 ≤ n ≤ 100 000) — length of sequence A.
•  » » » 12 months ago, # ^ |   +3 n >= 2
•  » » » 12 months ago, # ^ |   0 ans is 1 right? 1 1 -> 0 2. So 1 step?
•  » » » 12 months ago, # ^ |   +25 length of sequence >=2 pls dont give me a heartattack
•  » » » 12 months ago, # ^ |   0 I think it's YES (only one operation)0 2
•  » » » 12 months ago, # ^ |   0 n > 1 dude
•  » » 12 months ago, # ^ |   0 NO
•  » » » 12 months ago, # ^ |   0 hope that's true
 » 12 months ago, # | ← Rev. 9 →   +7 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 > 1Then 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.
 » 12 months ago, # |   +7 What was test-case 5 for problem A?
•  » » 12 months ago, # ^ |   +11 Something like abccba. Answer is NO.
•  » » 12 months ago, # ^ |   +6 I guess it like this: abcbaAnswer is YES.
•  » » 12 months ago, # ^ |   0 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 :(
•  » » » 12 months ago, # ^ |   +6 OH No! I spend 2 hours debugging my code
•  » » » 12 months ago, # ^ |   +1 Not if the string is of odd length, one can change the centre character
•  » » » » 12 months ago, # ^ |   +3 True that. Luckily my code is brute force, so I don't have that as a bug ;)
 » 12 months ago, # |   +1 My solution of C:1) find gcd of the sequence2) 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
•  » » 12 months ago, # ^ |   +3 omg that thing worked
•  » » 12 months ago, # ^ |   +1 so full explaination:check if the gcd of the seq is > 1 than ans is: YES 0else: go through the seq and do the operation once on pairs where both nums are oddgo through the seq again and do the operation twice on pairs where one num is even and one num is oddanswer is: YES
 » 12 months ago, # |   +14 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.
 » 12 months ago, # |   0 Is E just a simple topological sort?
 » 12 months ago, # |   +5 how to approach D?
 » 12 months ago, # |   0 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 :(
•  » » 12 months ago, # ^ |   0 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.
•  » » 12 months ago, # ^ | ← Rev. 2 →   0
 » 12 months ago, # |   +10 Question B, WA at test 94 :)
•  » » 12 months ago, # ^ |   0 What are you so happy about? Is 94 some lucky number? :)
•  » » » 12 months ago, # ^ |   0 No. Just because am speechless. So why not just smile :)
•  » » » » 12 months ago, # ^ |   -8 Yeah...a smile coupled with learning something new sounds like a good idea to me. :)
 » 12 months ago, # |   +3 How to solve D? Any hints?
•  » » 12 months ago, # ^ | ← Rev. 4 →   0 I used random_shuffle to solve it. In the example:1000001 1 1 1 ... 1 1 1 22 1 1 1 ... 1 1 1 1We 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:)
 » 12 months ago, # |   0 What a weak acmer I am!! I got 4 WA at the first problem.
 » 12 months ago, # |   0 Very cool problems!
 » 12 months ago, # |   0 Any deterministic solution for D?
•  » » 12 months ago, # ^ | ← Rev. 2 →   -8 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).
 » 12 months ago, # |   +15 LOL, are u serious about D tests ? 26562304
 » 12 months ago, # |   +8 I passed D using randomized algorithm.Just random k elements from A and B with equal indexes until correct answer got.http://codeforces.com/contest/798/submission/26561705
•  » » 12 months ago, # ^ | ← Rev. 2 →   +8 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?
•  » » » 12 months ago, # ^ | ← Rev. 5 →   +6 There is another similar problem using randomized algorithm in CodeforcesWait a minute, I'm seaching this problem.I will post this problem later.http://codeforces.com/problemset/problem/364/DFinally， 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.
•  » » » 12 months ago, # ^ |   +6 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 .
•  » » 12 months ago, # ^ |   0 Here is another randomized solution!!! http://codeforces.com/contest/798/submission/26560973look at it :p . I found this pretty cool!
•  » » 12 months ago, # ^ |   0 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% :) )
 » 12 months ago, # |   +5 WTF!! I didn't submit my solution for problem C because I didn't find the case for "NO".
 » 12 months ago, # |   -15 So easy E, why only 3 ACs?
•  » » 12 months ago, # ^ |   +5 Because it's not easy.
•  » » » 12 months ago, # ^ |   +1 Maybe
•  » » » 12 months ago, # ^ |   0 From the editorial, it looks like it was just a topological sort. People were stuck on D for long time, plus long queues.
•  » » » » 12 months ago, # ^ |   0 toposort + avoiding quadratic time
 » 12 months ago, # |   +11 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 probabilitythanks :)
 » 12 months ago, # |   +6 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 :(
 » 12 months ago, # |   +7 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.
 » 12 months ago, # |   0 I lost 1 hour to implement DFS in java for B but I got TLE on case 9... Anyone know why? https://pastebin.com/B42rBZgQ