ditoly's blog

By ditoly, history, 6 years ago, In English

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
About the Constraints

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
Something else about this problem

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, nikanqilaizhenhaoxiao and consecutivelimit 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!

  • Vote: I like it
  • +191
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Worth the wait

»
6 years ago, # |
  Vote: I like it +29 Vote: I do not like it

All of the solution codes are amazingly short

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not the best thing though, sometimes it's so compressed that it can be barely understood

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Soooo worth waiting !!!

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

can someone elaborate the explanation of div2 C !

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Why we have to check only the divisibility of a number with a prime in question Div2 C>

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
6 years ago, # |
Rev. 3   Vote: I like it -9 Vote: I do not like it

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)

»
6 years ago, # |
  Vote: I like it -9 Vote: I do not like it

I keep wondering why people upvoted to the jokes about "Chinese guy preparing contest". What's up with that?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I can not feel Div2 C problem.Can anyone help me??

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ??????

  • »
    »
    6 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Bruh, put the parantheses inside (2 * 2).

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        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).

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 )

»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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).

»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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.

»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

No problem tags still ! :(

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why I am getting runtime error in question number 3 on test case 8.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    6 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.....

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How can you prove it's always an integer? Div 2B (theoretically)

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody explain a little bit more about Div2 D second approach given in editorial?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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???

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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"?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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;}

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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); }

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I think all occurrences of in the tutorial of 1E should be replaced by i&2x ditoly

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    The tutorial has been updated. Thank you very much!

»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because there exists O(n*sqrt(max(ai))) solution, which is much slower than O(n*log(ai)).

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/contest/1047/submission/54857708 runtime error used exactly what is written in tutorial problem 1 A

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please give me the prove of Div.2 B . I can't understand how it minimum distant count by the solve.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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).

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)$$$.