This is an editorial blog for HCW 19 Team Round (ICPC format). Any further question can be asked in the comments, I'll try to answer all the questions. Please, do not private message or email me, your question could be the same as others', and I really hate to answer one question multiple times. >:(
102279A - Amsopoly Simple Version
Author: low_.
To solve the problem, you'll only need to note that in $$$(N+1)$$$-th turn: Seo moved through exactly $$$(N+1)*V_s$$$ property, that is exactly $$$V_s$$$ full round of the board, so that he end up in $$$1$$$ afterwards. The same happens with B21 and Lowie. After that, the game keeps repeating itself.
We can conclude that: if there isn't any event of one paying other in the first $$$3*(N+1)$$$ turns, it will never happen, so we can output $$$3000000000$$$. Otherwise, we can find the first event of it by brute force in $$$O(3*(N+1))$$$ time complexity.
Maximum time complexity: $$$O(3*(N+1))$$$.
102279D - Dahlia The Champion
Author: low_.
Dahlia can only reach targets in the circle of radius $$$R$$$ around her. But the trick here is she only pull one target in each direction she throw her arm to.
Here is the test that some may failed:
Maximum time complexity: $$$(O(N))$$$
102279E - Elevate To Dominate
It’s not very difficult to recognize the solution of this problem is to complete the $$$n$$$-th set of attack as soon as possible. Now we can solve this problem by computing $$$DP[i] = max(DP[j] + b[j] * a[i])$$$ , $$$1 \le j < i$$$ , which can be computed naively in $$$O(n^2)$$$. To optimize it to $$$O(n)$$$, you must use Convex Hull Trick.
Maximum time complexity: $$$O(n)$$$
102279G - Get Higher and Higher
The statement can be simplified to: comparing the tree in B21's best root possible and the tree in Lowie's worst root.
Call $$$d$$$ as the diameter of a tree, which can be calculated by two times DFS, we can prove that:
-- Maximum height of a tree by changing the node of root: $$$d$$$.
-- Minimum height of a tree by changing the node of root: $$$\lceil \frac{d}{2} \rceil$$$.
By simple DFS's we can find the answer easily.
Maximum time complexity: $$$O(2(N+M))$$$.
102279H - Houston, Are You There?
Author: low_
This problem requires no brainstorming at all. You can just brute force to find every combination possible.
Maximum time complexity: $$$O(N!*2^N)$$$.
102279I - Imitater The Potato
Author: low_. Editorial by NamSPro, wrote it after the contest ends.
We will divide this problem into two cases, odd $$$N$$$ and even $$$N$$$.
Firstly, let's call the total number of cards $$$sum$$$ and the number of cards in the pile with the least cards $$$min$$$.
If $$$N$$$ is odd, then we can prove that the answer is solely based on $$$sum$$$.
We can observe that the parity of sum would change no matter the moves players use (since $$$1$$$ and $$$N$$$ are odd). From this observation, we can conclude that the winner is the one to make sum even after his turn, since $$$0$$$ is an even number. If sum is odd, that would be Lowie, otherwise Imitater wins.
If $$$N$$$ is even, then we'll check the parity of both sum and min. There are 4 cases:
-- $$$sum$$$ and $$$min$$$ are both even (we'll call this the 'base case'): Let's prove that Imitater wins this case. Since sum is even, there must be an even number of piles with their amount of cards odd (call this number $$$k$$$). Consider all moves Lowie can make:
If he takes one card from all piles, Imitater will do the same move. Imitater can do this since min is even and nonzero (all piles must be nonempty, so $$$min \le 2$$$, remember that min is even).
If he takes one card from one of the $$$k$$$ piles, Imitater takes one card from one of the remaining $$$(k-1)$$$ piles.
If he takes one card from a pile different from the k piles, Imitater takes another card from the same pile. Imitater can do this since the amount of cards in that piles is even and greater than zero (players' moves must be from a nonempty pile, so the pile lowie picked must have at least $$$2$$$ cards).
After the Imitater's move, the parity of everything we are considering $$$(sum, min, k)$$$ stays the same. and because sum is initially even, Imitater will eventually win. And since Imitater goes second, we can imply that the player who goes second in this case wins.
-- $$$sum$$$ is even and $$$min$$$ is odd: Lowie can draw one card from all piles. Since $$$N$$$ is even, $$$sum$$$ would still be even. But $$$min$$$ is now one less, so it'll be even.
-- $$$sum$$$ is odd and $$$min$$$ is even: Lowie can draw one card from any pile that is not min. After that, min stays even, but sum is no longer odd.
-- $$$sum$$$ and $$$min$$$ are both odd: Lowie can draw one card from the 'min' pile. After that, sum and min are now both even. In the above 3 cases, Lowie can change this into the base case with the Imitater's turn, and as proven above, he'll win the game.
Overall complexity: $$$O(n)$$$ for input and $$$O(1)$$$ for computing and output.
Kudos to NamSPro for contributing such a complete solution.
102279J - Jumpity Digits
Author: b21quocbao.
Read the input as a string, then just use simple brute force to assess on all swaps possible.
Maximum time complexity: $$$O(N^3/2)$$$.
102279K - Kostly Cueries
Author: low_.
Obviously, you cannot ask for a single element in the array, because that would cost you $$$1$$$ burles, while you only have $$$0.45$$$!
Notice that the prime array is sorted and each element is smaller than $$$10^4$$$. So, you can ask for a subsegment of length $$$2$$$ and find out both element 100% correctly (because the product of two element is smaller than $$$10^9+9$$$, so it won't be deformed by $$$MOD$$$ operations). This will cost you $$$0.25$$$ burles.
From that, you can ask for another subsegment of $$$2$$$ next to it to "save money". For example, if you want to ask for subsegment $$$[r+1, r+2]$$$ and you've already got $$$[l, r]$$$, you should ask for $$$[l, r+2]$$$ and use modulo inversion to get the answer you wanted. That way, you could save a lot of money.
By two observations above, you can ask for a fixed set of queries for every tests: $$$[1, 2]$$$, $$$[1, 4]$$$,...,$$$[1, N-N\%2]$$$, $$$[1, N]$$$.
Some of the worst cases:
$$$N=3$$$: $$$0.25+0.(1) = 0.36(1)$$$ burles.
$$$N=499$$$ and $$$N=500$$$: about $$$0.410236$$$ burles.
Maximum time complexity: $$$O(N*log2(10^9+9))$$$.
