Hello, Codeforces!
Finally, the season of square869120Contest comes. I am filled with deep emotion when I think of the dawn of this contest :)
On April 14th, 20:00 JST, an innovative contest, square869120Contest #6 will be held. As usual, I'll invite everyone includes non-Japanese participants, and in previous contest, 20 non-Japanese participants joined in the contest. Hope in this year, much more will join :)
square869120Contest is a competition which is held by a twins: E869120 and square1001. This round is our sixth voluntary contest, counting from from our first round when we were 7-th grader. Now we are 11-th grader, but we are making much efforts to achieve continuous-growing of the contest, including some experience of writing problems of AtCoder Beginner Contests and others.
About square869120Contest (s8pc)
- This contest is unrated and unofficial, and AtCoder doesn't have responsibility about the contents of the problems.
- square869120Contest had been held 5 times before, and this is the 6th contest.
- From 3rd contest, Both English and Japanese problem statements are prepared.
- This contest is an IOI-style contest, and there are many partial scoring. It means even if you don't came up with a full-solution, to solve easier problem (e.g. lower constraints), you can get partial score. You can see previous square869120contests to know more about partial scorings.
Contest Information
- Time: April 14th, 2019, 20:00 JST
- Duration: 240 minutes
- Number of tasks: 9 (Consists of 8 algorithm tasks and 1 marathon task)
- Writer: E869120, square1001
- Rated: No (unrated)
- The first problem is as easy as (or possibly easier than) Codeforces Div2 A, and the last problem is as hard as Codeforces Div1-E. In addition, there are many partial scores. I think all participants can enjoy the contest.
Scoring
| Problem | A | B | C | D | E | F | G | H | I |
|---|---|---|---|---|---|---|---|---|---|
| Max. Score | 200 | 300 | 400 | 600 | 800 | 1000 | 1200 | 1500 | 1500 |
- Note: The last problem is a marathon-match-like optimization task.
- Note: The max score of problem D has changed.
Past Problems
- square869120Contest #5 (English / Japanese)
- square869120Contest #4 (English / Japanese)
- square869120Contest #3 (English / Japanese)
- square869120Contest #2 (Japanese)
- square869120Contest #1 (Japanese)
Feedbacks from participants of past s8pc participants
There 5 s8pc contests before. In cumulative total number of people, 1500 people registered in s8pc, and 876 people got 1 point or more, including 99 international participants. To some participants, I asked some impressions of s8pc, and some advice for newcomers.
yosupo (The winner in s8pc #5)
- Since there are many kind of problems though the writers are same, s8pc is very fun contest!
- But this contest is very consistent. For example, the last problem is always marathon-match like task.
- Participate more!
WA_TLE (17th place in s8pc #4, runner-up in s8pc #5)
- It was s8pc #4 when I first solved some problems by twins. At first, I wondered why they can make very good problems.
- Actually, I am in good relationship with twins, as if I could think "we are triplets". s8pc problems are interesting!
- Let's participate and enjoy!
zscoder (4th place in s8pc #4)
- I think s8pc is a fun contest! The problems are interesting and also challenging. Some problems require interesting ideas to solve.
- Also, there's the marathon problem every contest which looks interesting, though the time is probably too short for me to be able to work on it much considering that there are other hard problems to solve.
- For newcomers, the problems also have many subtasks, and first half of problems are not so difficult. Thus you don't have to worry that you can't solve anything ;)
kotamanegi (13th place in s8pc #5)
- In s8pc #5, because of proper difficulty and kind editorial, I learned very much in the contest!
- I am very good at marathon-match like problem. For the problem "Collecting Gems in Fun" (the last problem of s8pc #5), as much as you think, as many point as you can get. This problem is very good for introducion of marathon-match.
- Overall, s8pc is a high-level contest but enjoyable through many rating-clusters and many generations.
- Let's participate in this contest!
Let's participate and have fun!
E869120, square1001
UPDATE
- The max score of problem D has changed.
- Finally, now, the contest will starts less than 24 hours. Participate more!
- After the contest, let's discuss about the problems.
- The contest is over. Unofficial Ranking and Statistics is now open!
Reminder: The contest starts in 1 day and 2 hours.
Registeration Link of square869120Contest #6
The contest has just started! Let's participate and enjoy!!!
Thank you for participation! Let's discuss about problems :)
how to solve problem D — Snowball and E — 90-degree Rotations ?
D : Optimal solution is to fix one snowball and have roll snowballs from the left to it and roll snowballs from the right to it
E : Construct a graph where each row and each column is a vertex, and a cell with a token corresponds to an edge between the corresponding row and column. The condition is equivalent to the graph having an Eulerian Path.
is there a proof that in D it's always optimal to fix a snowball and have roll snowballs towards it ? , won't be more optimal if we made made a point in middle of two(or more) snowballs ?
Sure. For example for two snowballs you could think about it this way:
Consider two snowballs where $$$r_1, r_2$$$ — are their sizes, first one is located at $$$x = 0$$$, second one is located at $$$x = c$$$.
Let's first cover the case when $$$r_1 \ge c$$$ and $$$r_2 \ge c$$$
You are tasked to choose such $$$x$$$ that maximizes the function from statements. (the place where you roll both snowballs towards)
$$$x \in [0..c]$$$
Then you are to find maximum value of a function $$$f(x) = ((r_1 - x)^{3} + (r_2 - c + x)^{3})^\frac{1}{3}$$$. To do this, you should use the fact that the extreme values of a continuous function is either on the ends of an interval or where $$$f'(x) = 0$$$
$$$f'(x) = \frac{1}{3}((r_1 - x)^{3} + (r_2 - c + x)^{3})^{-\frac{2}{3}} \cdot (-3(r_1 - x) ^ 2 + 3(r_2 - c + x) ^ 2)$$$
From the function you can observe that it is actually equal to 0, in case ($$$r_1 - x = r_2 - c + x$$$) (which is a shame, but you could actually prove that this is actually a minimum of such function) This is done either by computing $$$f"(x)$$$, which will have positive denominator and numerator of sorts $$$2(c - r_1 - r_2) (-c + r_1 + r_2) (r_1 - x) (c - r_2 - x)$$$ which is always positive because of the assumtion of $$$r_1 \ge c, r_2 \ge c$$$ and $$$x \le c$$$.
Or perhaps easier: by a simple observation that $$$f'(x)$$$ is obviously monotonically increasing (on this interval) since the first clause is always positive, whereas in the second clause as $$$x$$$ increases, you add more and subtract less.
That means either $$$x = 0$$$ or $$$x = c$$$.
The case when $$$r_1 \le c$$$ was harder for me to prove (since you need to consider $$$x = c - r_2$$$ and $$$x = r_1$$$ as extreme points), but the intuition behind is that it is not reasonable to move such small snowball towards the bigger one, because total distance travelled by two snowballs is bigger than the size of smaller one
Thanks for your explanation.
Will an English editorial be posted?
Sorry but we did not made yet. That's because we are having pretty tough life of beginning of new grade in school (in Japan, school starts from April) and get used to new class is stamina-consuming.
So, I can say that we maybe (think 60 percent) make them. If we make, it will be published after few days.
But maybe you can add hints to solve problems in English like the ones zscoder wrote for D and E in the comment above.
Yeah, of course. If you want hint I can reply.