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.
- Kattis contest on Sun, Dec 15th
- Onsite contest — do not look unless you want to see scoreboard
- Problems — if you want to create your own contest using these problems
Problems were prepared by:
- ngfam_kongu
- chemthan
- I_love_Hoang_Yen
- I_love_tigersugar
- laoriu
- ll931110
- khuebeo
- and some professors from Vietnam.
The problems are so interesting, I love them. Can you evaluate the problems' difficulty in Codeforces scale?
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 :)
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).
E and J were standard and boring with additional annoying stuff.
I 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.
Some 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):
Solution: https://drive.google.com/file/d/1ar_O2vlcGWf2-1cZWdKxo8YrQJ8J65fD/view?usp=sharing Implementation: https://ideone.com/RLUOCS
Thank you :D that was a really nice problem.
The same solution can be done in a much simpler way:
Let $$$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. Code
But your explanation was really clear and helpful. Thank you for your effort.
Notice that when $$$gcd(p, 10) = 1$$$, $$$10^{p-1} = 1 \bmod p$$$.
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.
How to Solve A (Abstract Painting)?
Is there any editorial for this contest?
Let's fix the painting of the top horizontal $$$C$$$ edges arbitrary.
In 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?
$$$3^{C}*(3 * 2 ^ {C})^{R} = 3^{R+C}* 2^{RC}$$$
Great explanation. I guess Problem A could be solved by more teams if...
...the constraint was like $$$10^9$$$ or something. $$$1 \leq R \leq 14$$$ was a witty misguiding trick.
With 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. :)
You 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.
To avoid people from guessing instead of solving.
Wow I’m evenharder fan!
How to solve I and L. For problem I, I couldn't do better than n/2 queries.
L is a duplicate problem
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?
Can I see the system tests data file?