### zscoder's blog

By zscoder, history, 7 months ago,

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)

Solution
Code (zscoder)

Solution
Code (zscoder)

Solution
Code (zscoder)

### Problem E — Valentine

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

Solution
Code (zscoder)

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

• +175

 » 7 months ago, # |   +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.
 » 7 months ago, # |   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 ?
 » 7 months ago, # |   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
 » 6 months ago, # |   +10 I like your problem statements!