Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### ditoly's blog

By ditoly, history, 3 months ago, ,

Hi, here is the editorial. Sorry for a long waiting.

Have you enjoyed this round? I hope so. I know there are many things not so good and making some people unhappy :( I'm very sorry about that. Since this is my first round, I have many things not taken into consideration or done badly. I will try to improve them if I have my next round (I hope).

Let's talk about the problems. The problems are mainly prepared by me, ditoly, which can be seen in D1D as "Little D". Also, my friends ACMLCZH ("Little C") and FallDream ("Mr. F", I don't know whether this name can explain Chinese word "F大爷" well, maybe "Master F" is better?) provided great helps. The statements are mainly written by me (with the help of 300iq and cyand1317 and some others, thanks!). My English is not so good, so it's frequent that I just understand the problem but other people get AC :( So I try to explain the problems in short statements. Are you not the same with me in this round :p? By the way, why Little C loves "3" so much? He said, it's because C is the 3rd letter in alphabet :D

Div. 2 A — Little C loves 3 I

Problem Author: ditoly

This problem is set by Little C at first, and it's a problem about "Tic-Tac-Toe" for D2B. But after discussion with the coordinator, we thought it's just a implement problem and not so interesting. So I came up with a new problem as you saw.

Solution
My Code

Div. 2 B — Cover Points

Problem Author: ditoly and ACMLCZH

This is the former D2A :) After discussion with the coordinator, we thought this problem is too difficult for beginners so it became D2B. What do you think of it?

Solution
My Code

Div. 1 A — Enlarge GCD

Problem Author: FallDream

In the initial version, it's satisfied that the GCD of all the given integers is 1. So maybe it will be easier to find the standard solution?

Solution
My Code

Div. 1 B — Little C Loves 3 II

Problem Author: ACMLCZH

When ACMLCZH first told me this problem and the solution, I hacked him because of his mistake :p

Solution
My Code
How to solve this problem quickly and safely without complex proof?

Div. 1 C — Region Separation

Problem Author: ditoly

This problem seems to be a little difficult for its position. In fact, D1C is an easier problem with dp on a tree. For some reasons, it was replaced by this problem. But I think the new problem is very interesting, isn't it?

Solution
My Code

Div. 1 D — Intervals of Intervals

Problem Author: ditoly and FallDream

A data structure problem! With a very interesting (I think) solution! But in the beginning, this problem is just asking you for the values of several intervals of intervals :( I try to improve it and come up with this new problem :) This problem seems to be a little difficult so that only scott_wu solved it, congratulations! In fact, I would like to set the scoring contribution to 2250 (so scott_wu may take the 1st place?) before the contest. But for some reasons I finally did not :(

Great thanks to cyand1317 for the revision of the tutorial.

Solution
My Code

Div. 1 E — Little C Loves 3 III

Problem Author: ditoly

A common, artful, interesting solution for subset convolutions! Even though it can solve with modulo p which p is a small integer now, I can solve with modulo 109 + 7 using 1024-bit computers! :p

There seems to be many solutions with hard optimizations can pass this problem. I worried about whether I should allow these solutions before the contest and finally get the answer yes. Congratulations to people who solved this problem, L.A.C. and eds467 whose solutions are very close to the standard solution, and whzzt whose solution has an interesting optimization.

Solution
My Code

Hope it be useful to you!

•
• +191
•

 » 3 months ago, # |   +3 Worth the wait
 » 3 months ago, # |   +29 All of the solution codes are amazingly short
 » 3 months ago, # |   +5 Soooo worth waiting !!!
 » 3 months ago, # |   +3 can someone elaborate the explanation of div2 C !
 » 3 months ago, # |   +3 Why we have to check only the divisibility of a number with a prime in question Div2 C>
•  » » 3 months ago, # ^ |   +3 Whatever the final gcd is, it will be divided by at least one prime. So we just consider primes and can get the answer for any conditions.
•  » » 3 months ago, # ^ |   0 Because it's a fundamental fact that every number can be prime factorised. So, If any number can be prime factorised, it must be divisible by at least one prime number(including 1). We check for common prime divisors of the numbers to see if GCD > 1.
 » 3 months ago, # | ← Rev. 3 →   -9 The Editorial was good. It was really worth the wait. Please put the Editorial to the contest home page. (Came here via UPD in announcement section)
 » 3 months ago, # |   -9 I keep wondering why people upvoted to the jokes about "Chinese guy preparing contest". What's up with that?
 » 3 months ago, # |   0 I can not feel Div2 C problem.Can anyone help me??
•  » » 3 months ago, # ^ |   +1 https://www.geeksforgeeks.org/largest-subsequence-gcd-greater-1/ Divide the array with the gcd and then find largest-subsequence-gcd-greater-1
 » 3 months ago, # |   0 Nice editorial but could not you just extend these codes in a much readable way?
 » 3 months ago, # |   0 in solution div 1 A 1ll*n*m/2*2 i really didnt get that whats happening.Because when i run 1ll*3*3/2*2 it gives me 8 output but why i know that 1ll changes into 64 bits but when we divide with 2*2 output should be 2 instead of 8 i know i am wrong but tell me how. 1ll*3*3/2*2 = 8 ???? 1ll*3*3/4 = 2 ??????
•  » » 3 months ago, # ^ |   -8 Bruh, put the parantheses inside (2 * 2).
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 I think u didn't answer what I am asking bruh. My question is hohow the output comes out to be 8 even when I put into paranthesis.
•  » » » » 3 months ago, # ^ |   -8 I meant this:1ll*3*3/(2*2).This should result in 2.The multiplication and division has equal order, therefore, without any proper parantheses, the expression will be calculated from left to right.i.e. 1LL * 3 = 3LL -> 3LL * 3 = 9LL -> 9LL / 2 = 4LL -> 4LL * 2 = 8LL (since no parantheses were put in 2*2, so no way it'd be calculated beforehand).
 » 3 months ago, # |   0 This editorial should be appreciated with massive efforts and compassions given to it, compared to regular editorials :D(I don't mean normal eds were not passionate, just this one felt so right :D )
 » 3 months ago, # |   +10 I think the reason that many contestants get upset with this round came from the combination of the following three factors (from the Div1 side): The constraint on Div1-A is unsatisfying (since the constraint made it hard to predict whether O() solution can run under 1 seconds, without actually coding and run it in Codeforces' custom test). Div1B is a case-bashing problem. The issue with case-bashing problems are that, most of them are boring and frustrating to solve. Combined with the partial feedback on Codeforces, no one can be sured that they haven't forget any possible case until the systest. A lot of case-bashing problem on past Codeforces round also received negative feedback. At least, Div1-B have a maximum matching solution, which save contestants from having a migraine. The gap between Div1-B and the last three problems is way too large (not even 10% of Div1 contestants solved one of the last three problems).
 » 3 months ago, # |   +9 Problem D and E are all good problems.My first solution of problem D is: Use binary search to find the k-th maximum union of intervals L, when checking if there are k intervals of intervals with the union not less than L, use two-pointers and segment tree to maintain the union of intervals between pointers. Then we get ri that represents to the minimum r that the union of intrevals in [i, r] is not less than L. Use scanning line to calculate for each element segment, how many interval of intervals include it, and sum them up to get the answer.The complexity is , the bottleneck is the first-step, binary search, two-pointers and segment tree. I found it hard to optimize, because I can't do it without binary search, and when checking I can't do it without segment tree. I didn't know why it can be optimized.After hours of thinking I finally know how to optimize, same as the editorial. The solution is simple and tricky.My solution of problem E is using subset convolution simply, but O(2n·n2) will get TLE, so I compress a polynomial into a 64-bit integer and use a lot of complex operation to optimize it to O(2n·n). With the bless of Luck Fairy I passed it with the execution time 982ms.The solution in editorial is also simple and tricky. I want to know how to create this type of problems.
 » 3 months ago, # |   +8 For problem E, I first came up with the O(2n n2) fwt solution. Then I looked through my code, and found that it's possible to use long long to squeeze operation of polynomial.
 » 3 months ago, # |   0 No problem tags still ! :(
 » 3 months ago, # |   0 Why I am getting runtime error in question number 3 on test case 8.
 » 3 months ago, # |   0 Could anyone explain what does it mean when they say this in problem Div1.B?"This problem is a matching problem. And we found that two grids can be matched only if they have different parities of the sum of two coordinates. So it's actually a biparite graph matching problem :) So we can calculate the answer for all small n and m."Thanks.
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 I think it means the problem can change to bipartite graph matching problemWhen I first saw this question，I also thought about it, but I didn't have a good idea to build bipartite graph, so I gave up.
 » 3 months ago, # |   0 Can someone please explain the author's code for Div 2 C problem ?? I am not understanding how he is storing the divisors of a number and using them to find the new gcd.....
 » 3 months ago, # |   0 How can you prove it's always an integer? Div 2B (theoretically)
•  » » 5 weeks ago, # ^ |   0 since the equal sides are coordinate axis and since its a right angled triangle, the shortest sides are always on the coordinate axis. Now equation of the third side is y = -x + c => c = y + x hence to cover all points c = max(y+x)
 » 3 months ago, # |   0 Can anybody explain a little bit more about Div2 D second approach given in editorial?
 » 3 months ago, # |   0 div 2 C:if there is 2 element 1,7 i can remove 1 so i can get larger gcd 7 so result is 1 so when there is 4 element 3,6,15,30 i can remove all 3 elements except 30 so greatest gcd should be 30 , so the result should be 3.anyone, please help me with these problem???
•  » » 3 months ago, # ^ |   0 Print an integer — the minimum number of integers you need to remove so that the greatest common divisor of the remaining integers is bigger than that of all integers. I think the problem just wants a larger gcd than the initial gcd (not the biggest) and smallest number of moves
•  » » » 3 months ago, # ^ |   0 oh thanks . i didn't see it.
 » 3 months ago, # |   0 One question on E.The value of each A[i] and B[i] can be as large as 2^42，when processing "a[i]*=b[i]",it may overflow! Why it is right to used "long long" instead of "unsigned long long"?
 » 3 months ago, # |   0 Is u[i] the smallest prime factor of i?
 » 2 months ago, # | ← Rev. 2 →   0 Why the hell i am getting RTE fot test #8 in div2-c ditolyhttp://codeforces.com/contest/1047/submission/43594525
 » 2 months ago, # |   0 I haven't come across the question mark and :x things before, what's the deal with them? int gcd(int x,int y){return y?gcd(y,x%y):x;}
•  » » 2 months ago, # ^ |   0 it's operator ?:(condition) ? firstBLOCK : secondBLOCK it's similar to if (condition == true) { firstBLOCK; } else { secondBLOCK; }in your example we have if (y != 0) { return gcd(y, x%y); else { return x; ///if y == 0, then x is gcd(x, y); }
 » 2 months ago, # |   0 It's tricky tags for task D. There is much simpler solution for this problem, obviously. Besides i think that thanks to limit of N and M is impossible to use flow algorithm or something else (tags are wrong in russian version of task)
 » 2 months ago, # |   0 我我
 » 2 months ago, # |   +11 I think all occurrences of in the tutorial of 1E should be replaced by i&2x ditoly
•  » » 2 months ago, # ^ |   +3 The tutorial has been updated. Thank you very much!