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
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.
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?
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?
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
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?
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.
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, nikanqilaizhenhaoxiao and consecutivelimit whose solutions are very close to the standard solution, and whzzt whose solution has an interesting optimization.
Hope it be useful to you!
Worth the wait
All of the solution codes are amazingly short
Not the best thing though, sometimes it's so compressed that it can be barely understood
Soooo worth waiting !!!
can someone elaborate the explanation of div2 C !
Why we have to check only the divisibility of a number with a prime in question Div2 C>
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.
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.
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)
I keep wondering why people upvoted to the jokes about "Chinese guy preparing contest". What's up with that?
I can not feel Div2 C problem.Can anyone help me??
https://www.geeksforgeeks.org/largest-subsequence-gcd-greater-1/ Divide the array with the gcd and then find largest-subsequence-gcd-greater-1
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 ??????
Bruh, put the parantheses inside (2 * 2).
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.
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).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 )
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).
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.
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.
No problem tags still ! :(
Why I am getting runtime error in question number 3 on test case 8.
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.
I think it means the problem can change to bipartite graph matching problem
When 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.
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.....
How can you prove it's always an integer? Div 2B (theoretically)
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)
Can anybody explain a little bit more about Div2 D second approach given in editorial?
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???
I think the problem just wants a larger gcd than the initial gcd (not the biggest) and smallest number of moves
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"?
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;}
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); }
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)
I think all occurrences of in the tutorial of 1E should be replaced by i&2x ditoly
The tutorial has been updated. Thank you very much!
Although I'm not a python programmer,I know that 3e5 integers to input may cause TLE. If the solution's running time is only about max(ai) and sum(ai),why to make n so big?
Because there exists O(n*sqrt(max(ai))) solution, which is much slower than O(n*log(ai)).
ditoly
. "Let the equation be si/S = x /k where x is a positive integer, so k should be a multiple of " S/gcd(si,S)"
Can you please explain where did that equation come from and how it means that k should be a multiple of S/gcd(si,S)?
got it np
https://codeforces.net/contest/1047/submission/54857708 runtime error used exactly what is written in tutorial problem 1 A
Please give me the prove of Div.2 B . I can't understand how it minimum distant count by the solve.
I think the trick is "the shorter side". I am not sure what it is, but I am fairly sure it is not the shortest side of the triangle.
Edit: Ok, got it. "isosceles triangle" means the two shorter sides have same size. Which means the points are (0,x+y),(x+y,0) of max(x+y).
Isosceles triangle actually refers to a triangle having at least two equal sides, but they don't always have to be the shorter ones. For example, both $$$(4,4,2)$$$ and $$$(4,4,6)$$$ are valid triangles, and they both are isosceles.
The trick of this problem is placing the two sides on the coordinate axis. When you try doing so, it will become a right angled isosceles triangle, of which the hypotenuse should be the larger side. Also note, all of it are bound on the first quadrant.
The hypotenuse meets the axes at $$$45^{\circ}$$$. So, every point on the hypotenuse has the property: $$$x+y=len$$$; where $$$len$$$ is the length of either of the shorter sides of the triangle. Obviously, The shorter sides will be minimized when the hypotenuse is minimized, and vice-versa. The hypotenuse will be minimized when the farthest point is on the hypotenuse.
Hence, the answer is $$$max(x_i+y_i)$$$.