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))$$$.
102279B - Beggin' For A Node
Author: lantrungseo.
This problems could be solved in multiple ways: Heavy-light decomposition, Centroid decomposition,.... However, this solution only used a little knowledge of LCA, DFS and binary search.
Basic knowledges:
First, we take a little research into the characteristics of a rooted tree (let its root be node $$$1$$$): The distance between two nodes is the number of edges on the simple path between two nodes.
Height of a node $$$u$$$, denoted as $$$h_u$$$ is the distance from that node to the root:
Least Common Ancestor (LCA) of node $$$u$$$ and $$$v$$$ is the node $$$X$$$ such that:
-- $$$X$$$ lies both in the path from $$$1-u$$$ and from $$$1-v$$$.
-- $$$h_X$$$ is as large as possible.
- The distance between node $$$u$$$ and node $$$v$$$, denoted as $$$d_{u, v}$$$ equals to the sum of distance from $$$u$$$ to $$$LCA(u,v)$$$ and distance from $$$LCA(u, v)$$$ to $$$v$$$.
Especially, if $$$h_u$$$ $$$=$$$ $$$h_v$$$ then $$$d_{u, v}$$$ $$$=$$$ $$$2*d_{u, LCA(u, v)}$$$.
Solution: Let $$$x$$$ be the node we are looking for:
Given the tree, we could define the set $$$S_d$$$ contains all nodes $$$u$$$ such that $$$h_u = d$$$. All nodes in the set is sorted based on DFS order.
This could be done by vector in C++ and one DFS.
The first query is "$$$?$$$ $$$1$$$ $$$1$$$" => $$$h_x$$$, so we know that $$$x$$$ must be in the set $$$S_{h_x}$$$.
Because nodes in a set is sorted in increasing order, thus if in the set $$$S_{h_x}$$$ we have nodes ordered like this
$$$...,u_3, u_2, u_1, x, v_1, v_2, v_3, ...$$$
then:
$$$...d_{u_2, x}, d_{u_1, x}, d_{x, x}=0, d_{v_1,x}, d_{v_2,x}...$$$
Here we could apply binary search in the set to find the index of node $$$x$$$ in the set
Suppose we have to binary search in the range $$$[l,r]$$$ and we have to check the index $$$m = (l+r)/2$$$, which means we are checking node $$$S_m$$$.
Query "$$$?$$$ $$$1$$$ $$$S_m$$$" => $$$d_{S_m,x}= 2d$$$, so we could find in the path from $$$S_m$$$ to $$$1$$$:
- The $$$(d-1)$$$-th node, let it be node $$$u$$$.
- The $$$d$$$-th node, which is also the $$$LCA(S_m, x)$$$, let it be node $$$L$$$.
- Or if $$$d = 0$$$ then $$$S_m = x$$$. Output $$$S_m$$$. In binary search, we can prove that we at least once access to node $$$x$$$.
Query "$$$?$$$ $$$2$$$ $$$L$$$" => $$$v$$$ is the second node in the path from $$$L$$$ to $$$x$$$.
- If $$$v$$$ is before $$$u$$$ in dfs order, then $$$S_m$$$ is definitely before $$$x$$$ in dfs order, thus we move to the range $$$[l, m-1]$$$, or else we move to the range $$$[m+1,r]$$$.
Maximum time complexity: $$$O(n*log(n))$$$.
Maximum queries possible: $$$2*log(n)+1$$$ $$$<$$$ $$$36$$$.
102279C - Countering Terrorists
Author: lantrungseo.
Firstly, sort the locations of the bombs in increasing order.
- Let $$$jump1_i$$$ is the index of the farthest bomb that could be destroyed if we destroy the $$$i$$$-th bomb using the a type-1 tool.
- Let $$$jump2_i$$$ is the index of the farthest bomb that could be destroyed if we destroy the $$$i$$$-th bomb using the a type-2 tool.
Because if $$$w_0$$$ satisfies then all $$$w>w_0$$$ satisfy, we could use binary search in the range $$$[1,10^9]$$$ to find satisfactory $$$w_0$$$.
So how could we check whether a particular value w is satisfactory?
If $$$n \le P+Q$$$ then every $$$w_1$$$ is satisfactory. If $$$P+Q < n \le 2000$$$:
Naively, we could define a dynamic programming function as this: Let $$$f[i][j][k]$$$ true if we could destroy $$$i$$$ to $$$n$$$-th bombs from using $$$j$$$ type-1 tools and $$$k$$$ type-2 tools, or else false. Thus $$$f[i][j][k]$$$ $$$=$$$ $$$f[jump1_i][j-1][k]$$$ or $$$f[jump2_i][j][k-1]$$$.
Optimally, we could define our DP function as this: $$$f[i][j]$$$ is the minimal amount of type-2 tools we have to use to destroy all bombs $$$i$$$ to $$$n$$$ while using at most $$$j$$$ type-1 tools.
So $$$f[i][j]=min(f[jump1_i][j-1], 1+f[jump2_i][j])$$$
After that, we have to check if $$$f[1][P] \le Q$$$.
Overall complexity is $$$O(n^2, log_2(10^9))$$$.
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)$$$
102279F - Flood Season
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))$$$.
