### I_love_Hoang_Yen's blog

By I_love_Hoang_Yen, history, 2 years 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:

• +115

 » 2 years ago, # | ← Rev. 2 →   0 The problems are so interesting, I love them. Can you evaluate the problems' difficulty in Codeforces scale?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +3 Spoiler warning: Click previous revision if you want to see spoilers about problem difficulties.
 » 2 years ago, # |   0 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).
•  » » 2 years ago, # ^ |   0 SpoilerE and J were standard and boring with additional annoying stuff.
•  » » » 2 years ago, # ^ |   0 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.
•  » » » 2 years ago, # ^ |   0 SpoilerSome contestants found a O(Q*log^2) solution for E, which was quite nice :D
•  » » » » 19 months ago, # ^ |   0 Amazing! Could you please tell me how to solve E in O(Q*log^2)? THX!
•  » » 22 months ago, # ^ |   +8 How do you solve J?
 » 2 years ago, # |   0 How to solve C and F?
•  » » 2 years ago, # ^ |   +16 Here's the solution for F (I'm the problem setter): Spoiler
•  » » » 2 years ago, # ^ |   +10 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.
•  » » 2 years ago, # ^ |   0 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$.
•  » » » 22 months ago, # ^ | ← Rev. 2 →   0 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)$!
•  » » » » 22 months ago, # ^ |   +8 $O(plogp)$ if you use FFT.
 » 2 years ago, # |   +26 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.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +3 How to Solve A (Abstract Painting)? Is there any editorial for this contest?
•  » » » 2 years ago, # ^ | ← Rev. 2 →   +11 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}$
•  » » » » 2 years ago, # ^ |   +3 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.
•  » » » » » 2 years ago, # ^ | ← Rev. 3 →   +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. :)
•  » » » » » » 2 years ago, # ^ |   +16 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.
•  » » » » » 2 years ago, # ^ |   +19 SpoilerTo avoid people from guessing instead of solving.
•  » » » » » 23 months ago, # ^ |   +8 Wow I’m evenharder fan!
 » 2 years ago, # | ← Rev. 2 →   0 How to solve I and L. For problem I, I couldn't do better than n/2 queries.
•  » » 2 years ago, # ^ |   +5
•  » » » 2 years ago, # ^ |   0 is it possible to see other people's submissions/ editorials in kattis.com?
•  » » » » 23 months ago, # ^ |   0 No. L is application of Hall's marriage theorem.
•  » » 23 months ago, # ^ |   0 I: Think about binary representation.
 » 23 months ago, # |   0 Hints for problem K?
 » 7 weeks ago, # |   0 Can I see the system tests data file?