### I_love_Hoang_Yen's blog

By I_love_Hoang_Yen, history, 9 months ago, Hi,

We have added the problems from 2019 ICPC Asia Danang Regional on Kattis. I think the problems are very interesting and fun.

I have created a contest on Kattis on Sun, Dec 15th, 7pm GMT+7. But you can also create your own contests.

Problems were prepared by: Comments (28)
 » 9 months ago, # | ← Rev. 2 →   The problems are so interesting, I love them. Can you evaluate the problems' difficulty in Codeforces scale?
•  » » 9 months ago, # ^ | ← Rev. 2 →   Spoiler warning: Click previous revision if you want to see spoilers about problem difficulties.
 » Despite of having a terrible performance, I really enjoyed solving the problems this year. Therefore, it's highly recommended to try out at least 5 hardest problems :) My opinions about some problems.E and J were probably the best problems I have done this year, while it was absolutely amazing how the author came up with the idea for problem A. C was way interesting and fun to implement as a dp problem. F was a beautiful Math problem, and maybe the very first Math problem from Vietnam Regional Contest that a noob like me can actually understand the idea behind (not an insult tho lol).
•  » » SpoilerE and J were standard and boring with additional annoying stuff.
•  » » » SpoilerI admit that both of them could have been more interesting and less annoying (or at least I can do some edit to them), and even from the problem statement, anyone could tell. But what I am trying to say is that I learned more from E and J than from any problem I did this year, so they are still the best. By the way, I think E was way more annoying than J, considering the amount of time I spent for both.
•  » » » SpoilerSome contestants found a O(Q*log^2) solution for E, which was quite nice :D
•  » » » » Amazing! Could you please tell me how to solve E in O(Q*log^2)? THX!
•  » » How do you solve J?
 » How to solve C and F?
•  » » Here's the solution for F (I'm the problem setter): Spoiler
•  » » » Thank you :D that was a really nice problem. The same solution can be done in a much simpler way: SpoilerLet $x_i = c*d_i$ be the bandwidth allocated as denoted. We can do a binary search on $c$. For a fixed $c$, we can allocate bandwidth in the same manner as in the editorial (either $x_i$ itself or the closest valid value). Increase $c$ if we still have bandwidth to share, or decrease if we allocated too much bandwidth. CodeBut your explanation was really clear and helpful. Thank you for your effort.
•  » » C ideaNotice that when $gcd(p, 10) = 1$, $10^{p-1} = 1 \bmod p$. We handle the case $p = 2$ and $p = 5$ separately. Split the digits in blocks of $p-1$ digits. Now the problem becomes a standard DP problem: you need to concat some blocks of digits, to get a number equals $k \bmod p$.
•  » » » 7 months ago, # ^ | ← Rev. 2 →   a bit more?I have figured out it can be split in blocks. Using matrix exponential I can solve it with $O(p^3*logN)$, but I'm struggling with optimization.Can you share a bit more?Edit: My transfer used $O(p^3)$, which is unnecessary. I can simply merge two dp in $O(p^2)$!
•  » » » » $O(plogp)$ if you use FFT.
 » It was one of the most impressive and well-polished ICPC problemset I have ever done (including problem A). Thank you for preparing such a valuable contest.
•  » » 9 months ago, # ^ | ← Rev. 2 →   How to Solve A (Abstract Painting)? Is there any editorial for this contest?
•  » » » 9 months ago, # ^ | ← Rev. 2 →   Hint1Let's fix the painting of the top horizontal $C$ edges arbitrary. Hint2In addition to this, let's fix the painting of the top leftmost edge arbitrary. Then, how many different paintings are there to color the top remaining $C$ vertical edges? Answer for A$3^{C}*(3 * 2 ^ {C})^{R} = 3^{R+C}* 2^{RC}$
•  » » » » Great explanation. I guess Problem A could be solved by more teams if... Spoiler...the constraint was like $10^9$ or something. $1 \leq R \leq 14$ was a witty misguiding trick.
•  » » » » » 9 months ago, # ^ | ← Rev. 3 →   I have other suggestionsWith small $R$ suggest a kind of "profile DP" solution. Because any column only depends on the previous column, we can create a ternary "profile" based on the previous column. This should give $O(3^R*C)$ or somewhere close. It looks like a lot, but maybe it can pass. Here is another problem that uses this "profile DP" idea.But it looks like you're from the 3rd ranked team on the official standings right? Well done, I hope you qualify for WF. :)
•  » » » » » » That general idea should workYou can do DP with time complexity $O(3^{R+1} * C)$ (probably can be lower) and memory $O(3^{R+1})$.This would be too slow. So for $R \ge 9$, you need to pre-compute all answers and put a constant array in your code.
•  » » » » » SpoilerTo avoid people from guessing instead of solving.
•  » » » » » Wow I’m evenharder fan!
 » 9 months ago, # | ← Rev. 2 →   How to solve I and L. For problem I, I couldn't do better than n/2 queries.
•  » »
•  » » » is it possible to see other people's submissions/ editorials in kattis.com?
•  » » » » No. L is application of Hall's marriage theorem.
•  » » I: Think about binary representation.
 » Hints for problem K?