Codeforces Round #511 Editorial

Revision en1, by ditoly, 2018-09-22 17:56:13

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!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English ditoly 2018-10-16 13:56:15 8
en3 English ditoly 2018-10-16 13:55:19 134 Reverted to en1
en2 English ditoly 2018-10-16 13:46:01 134
en1 English ditoly 2018-09-22 17:56:13 23826 Initial revision (published)