Блог пользователя zscoder

Автор zscoder, история, 4 года назад, По-английски

I hope you enjoyed the contest!

Expected problem difficulty is F < A < (G ~ D) < (C ~ E) < B (though it might be different for different people).

I will mainly focus on explaining the full solution to the problems but I will briefly mention how to pass certain subtasks.

Problem A — Leakage

Solution
Code (zscoder)
Code (tmwilliamlin168)

Problem B — Confession

Solution
Code (zscoder)

Problem C — Isolation

Solution
Code (zscoder)

Problem D — Equality

Solution
Code (zscoder)

Problem E — Valentine

Solution
Code (zscoder)
Code, short version (tmwilliamlin168)

Problem F — Opposition

Solution
Code (zscoder)

Problem G — Honeymoon

Solution
Code (zscoder)

Bonus

The characters in the problem statements come from different anime/manga/light novels. Anime/Manga/LN fans of the romance genre (though some of them contain different elements) are recommended to check them out.

Problem A: School Days

Problem B: Tsurezure Children

Problem C: The Empty Box and Zeroth Maria (personal favourite, Light Novel only)

Problem D: Tsuki ga Kirei

Problem E: A Certain Magical Index (good luck watching/reading this series ^_^)

Problem F: Love, Chunibyo & Other Delusions (my favourite Kyoani anime)

Problem G: Yamada-kun and the Seven Witches

Разбор задач Valentines Day Contest 2020
  • Проголосовать: нравится
  • +175
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

For C, you can optimize the $$$O(N^3)$$$ approach to get 100 points.

$$$dp[n][x][y]$$$ will mean the number of ways to make a path of length $$$n$$$ from $$$(x,y)$$$.

First, notice that if $$$|$$$$$$x$$$$$$|$$$ $$$+$$$ $$$|$$$$$$y$$$$$$|$$$ $$$-$$$ $$$n$$$ $$$>$$$ $$$D$$$, we can never reach Kazuki, and the answer is $$$4^n$$$. Similarly if $$$|$$$$$$x$$$$$$|$$$ $$$+$$$ $$$|$$$$$$y$$$$$$|$$$ $$$\leq$$$ $$$D$$$, the answer is 0. Because of this we can reduce the number of states we need to calculate. For example, for $$$n=1$$$, we only need to calculate states where $$$|$$$$$$x$$$$$$|$$$ $$$+$$$ $$$|$$$$$$y$$$$$$|$$$ $$$=$$$ $$$D$$$ $$$+$$$ $$$1$$$, for $$$n=2$$$ we need to calculate states where $$$|$$$$$$x$$$$$$|$$$ $$$+$$$ $$$|$$$$$$y$$$$$$|$$$ $$$=$$$ $$$D$$$ $$$+$$$ $$$1$$$ or $$$|$$$$$$x$$$$$$|$$$ $$$+$$$ $$$|$$$$$$y$$$$$$|$$$ $$$=$$$ $$$D$$$ $$$+$$$ $$$2$$$, and so on.

Another optimization is to realize that the value of point $$$($$$$$$-$$$$$$5$$$$$$,$$$$$$-$$$$$$5$$$$$$)$$$ is the same as for point $$$($$$$$$5$$$$$$,$$$$$$5$$$$$$)$$$ as well as for point $$$($$$$$$5$$$$$$,$$$$$$-$$$$$$5$$$$$$)$$$. Which means that we can calculate the values for only one quadrant of the plane, but we can do better! Notice that the value for point $$$($$$$$$2$$$$$$,$$$$$$5$$$$$$)$$$ is the same as for point $$$($$$$$$5$$$$$$,$$$$$$2$$$$$$)$$$, so we need to calculate values for one eighth of the plane!

If we mark the values from the input as $$$X$$$, $$$Y$$$, and $$$N$$$, one final optimization is to see that when the following is true:
$$$|$$$$$$X$$$ $$$-$$$ $$$x$$$$$$|$$$ $$$+$$$ $$$|$$$$$$Y$$$ $$$-$$$ $$$y$$$$$$|$$$ $$$>$$$ $$$N$$$ $$$-$$$ $$$n$$$, we can skip calculating the value for this state. Just don't forget to move the values of $$$X$$$ and $$$Y$$$ into the section of the plane we are calculating for!

This approach works in around 3 seconds, but should be able to handle larger values of $$$D$$$. Here is the link to my submission, and also code.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For G I used the same idea as the O(NlogN+Qlog2N) mentioned in the editorial, but it exceeded the memory limit. Can anyone have a look and tell me which can be optimized ?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Maybe for the guys who don't know the block-cut tree.Task A is the hardest one. I solved F and G yesterday,then I think about task A for a long time without getting an idea. I don't know biconnected component either.TAT

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

I like your problem statements!