ditoly's blog

By ditoly, history, 4 weeks 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, 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!

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

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Worth the wait

»
4 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

All of the solution codes are amazingly short

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Soooo worth waiting !!!

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

can someone elaborate the explanation of div2 C !

»
4 weeks 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>

  • »
    »
    4 weeks 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.

  • »
    »
    4 weeks 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.

»
4 weeks 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)

»
4 weeks 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?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice editorial but could not you just extend these codes in a much readable way?

»
4 weeks 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 ??????

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

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

    • »
      »
      »
      4 weeks 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.

      • »
        »
        »
        »
        4 weeks 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).

»
4 weeks 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 )

»
4 weeks 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).

»
4 weeks 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.

»
4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

No problem tags still ! :(

»
4 weeks 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.

»
4 weeks 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.

  • »
    »
    4 weeks 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.

»
4 weeks 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.....

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks 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?

»
3 weeks 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???

  • »
    »
    3 weeks 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

»
3 weeks 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"?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is u[i] the smallest prime factor of i?

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Why the hell i am getting RTE fot test #8 in div2-c ditoly

http://codeforces.com/contest/1047/submission/43594525

»
3 weeks 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;}

  • »
    »
    2 weeks 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); }

»
2 weeks 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)

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

我我

»
8 days 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

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

    The tutorial has been updated. Thank you very much!