Congratulations to the winners! ↵
↵
1. [user:spentplaying,2017-01-06]↵
↵
2. [user:0w1,2017-01-06]↵
↵
3. [user:lawfung,2017-01-06]↵
↵
Also special props to [user:biGinNer,2017-01-06] for solving the last 3 problems (and the only one to solve F during contest)↵
↵
Here are the editorials :↵
↵
Problem A.↵
----------↵
↵
This is a simple problem. First, we calculate the position Harry ends in after making the moves $1$ time. This can be done by directly simulating the moves Harry make. Now, suppose Harry is at $(x, y)$ after $1$ iteration. Note that after every iteration, Harry will move $x$ units to the right and $y$ units up, so after $n$ moves he will end up in $(nx, ny)$. The complexity of the solution is $O(|s|)$.↵
↵
Problem B.↵
----------↵
↵
This is a dp problem. Let $dp[i]$ be the maximum possible sum of the remaining numbers in the range $[1..i]$. For $1 \le i \le k - 1$ the value is just the sum of the numbers in the range. Let $dp[0] = 0$. For $i \ge k$, we may choose to keep the element $a_{i}$ or remove a subsegment of length $k$ which ends at $a_{i}$. Thus, we arrive at the recurrence $dp[i] = \max(dp[i - 1] + a_{i}, dp[i - k])$. We can calculate the dp values in $O(n)$.↵
↵
Problem C.↵
----------↵
↵
----------↵
Observe that we can consider each prime factor separately. For each prime $p$ that appears in $N$, let's see what prime power $p^{k_{i}}$ should we pick from each number $a_{i}$ so that the sum of $k_{i}$ is equal to the power of $p$ in the prime factorization of $N$. Firstly, we need to prime factorize all the numbers $a_{i}$. We can use Sieve to find the primes and the factorization can be done in $O(n\pi(\sqrt{a_{i}}))$. From now on, we'll focus on a specific prime $p$. Now, we know the maximum prime power $m_{i}$ we can take from each number $a_{i}$ (so $k_{i} \le m_{i}$). From here, we can use a greedy method to decide what to take from each number $a_{i}$. Note that $m_{i} \le 20$ because $2^{20} = 1048576 > 10^{6}$. So, for each number $a_{i}$, we know the cost needed if we take $1, 2, ..., m_{i}$ factors of $p$ from $a_{i}$. We can store a vector and for each $a_{i}$, we push $w_{i}p, w_{i}(p^{2} - p), w_{i}(p^{3} - p^{2}), ..., w_{i}(p^{m_{i}} - p^{m_{i} - 1})$ into the vector. Now, we sort the vector and take the first $x$ elements, where $x$ is the power of prime $p$ in the prime factorization of $N$. If we can't take $x$ elements, the answer is $-1$. We can repeat this for all primes and solve the problem in $O(nr\log a_{i})$ time.↵
↵
Problem D.↵
----------↵
↵
To solve this problem, you need to know a bit about permutations. First, we need to determine how to find the minimum number of swaps to sort a permutation. This is a well-known problem. Let the permutation be $P = p_{1}, p_{2}, ..., p_{n}$. Construct a graph by drawing edges from $i$ to $p_{i}$ for all $1 \le i \le n$. Note that the graph is formed by disjoint cycles. You can easily see swapping two elements can either split a cycle into two smaller cycles, or merge two cycles into one cycle. Since the identity permutation is formed by $n$ cycles, the optimal way is to keep splitting cycles into two and increase the total number of cycles by $1$ each step. Thus, if we denote $c$ as the number of cycles in the current permutation, the number of moves needed to sort the permutation is $n - c$. Harry wins if and only if $n - c$ is odd.↵
↵
The key observation is that whenever there are exactly two question marks left, the first player will always win. Why? Consider how the current graph of the permutation looks like. It will be a union of few cycles and $2$ chains (we consider the singleton, a component formed by a single vertex, as a chain). Now, the first player can either choose to close off one of the chains, or join the two chains together. The latter will leave exactly $1$ less number of cycles than the former. So, one of them will guarantee the value of $n - c$ to be odd. Thus, the first player only have to choose the correct move. This implies that if the number of question marks $m$ is at least $2$, then Harry wins if $m$ is even and loses otherwise.↵
↵
Now, the only case left is when there're only $1$ question mark in the beginning. This means that Harry only have $1$ possible move and we're left with the problem of deciding whether the final permutation have $n - c$ odd. Thus, it is enough to count the number of cycles in the formed graph. This can be done by dfs. The complexity of the solution is $O(n)$.↵
↵
Problem E.↵
----------↵
↵
First, we form a trie of the given words. Now, the game is equivalent to the following :↵
↵
1. Start from the root of the trie.↵
↵
2. Each player can either move to one of the children of the current node, or delete one edge connecting the current node to one of the children.↵
↵
The one who can't move loses. This reduced game can be solved with Tree DP. Let $dp[u]$ denote the winner of the game if the first player starts at node $u$. The leaves have $dp[u] = 2$. Our goal is to find $dp[0]$ (where $0$ is the root). The recurrence is simple. Suppose we're finding $dp[u]$ and the children of $u$ are $v_{1}, v_{2}, ..., v_{k}$. If one of the children has dp value of $2$, then Player 1 can just move to that children and win. Otherwise, all children have dp value of $1$. Thus, both players will try not to move down unless forced to. So, they'll keep deleting edges. If there are an even number of children, Player 2 will win, as he will either delete all edges or force Player 1 to move down. Otherwise, Player 1 wins. This gives a simple $O(n)$ tree dp solution.↵
↵
Problem F.↵
----------↵
↵
Firstly, we make the same observations as problem C. Swapping two elements will either split a cycle into two or merge two cycles. Note that if we swap two elements from the same cycle, the cycle will split into two. If we swap two elements from different cycles, the two cycles will combine. Also note that for a cycle of size $c$, we can always split it into two cycles $a$ and $b$ with $a, b > 0$ and $a + b = c$ by choosing the appropriate two elements to swap from the cycle. Now, the game reduces to choose $2$ possibly equal elements from one cycle, swap them, and delete one of the resulting cycles. So, for a given permutation, if the cycle sizes are $c_{1}, c_{2}, ..., c_{k}$, then each move we can choose one of the sizes and the operation is equivalent to changing the size into any nonnegative number strictly smaller than it. Thus, we have reduced the problem to playing a game of Nim on $c_{1}, c_{2}, ..., c_{k}$. Since Harry goes second, he wins if and only if the xor values of all the cycle sizes is $0$. (This is a well-known fact)↵
↵
Thus, we've reduced the problem into finding the number of permutations of length $n$ which have the xor of all cycle sizes equal to $0$. To do so, let $dp[i][j]$ denote the number of permutations with length $i$ and xor of all cycle sizes equal $j$. The dp transitions can be done by iterating through all possible sizes $s$ of the cycle containing $i$. For each $s$, there are $\binom{i - 1}{s - 1}$ ways to choose the remaining elements of the cycle containing $i$ and $(s - 1)!$ ways to permute them. Thus, we can sum up the values of $dp[i - s][j \otimes s] \cdot \binom{i - 1}{s - 1} \cdot (s - 1)!$ for all $1 \le s \le i$. The whole solution works in $O(n^{3})$ time.
↵
1. [user:spentplaying,2017-01-06]↵
↵
2. [user:0w1,2017-01-06]↵
↵
3. [user:lawfung,2017-01-06]↵
↵
Also special props to [user:biGinNer,2017-01-06] for solving the last 3 problems (and the only one to solve F during contest)↵
↵
Here are the editorials :↵
↵
Problem A.↵
----------↵
↵
This is a simple problem. First, we calculate the position Harry ends in after making the moves $1$ time. This can be done by directly simulating the moves Harry make. Now, suppose Harry is at $(x, y)$ after $1$ iteration. Note that after every iteration, Harry will move $x$ units to the right and $y$ units up, so after $n$ moves he will end up in $(nx, ny)$. The complexity of the solution is $O(|s|)$.↵
↵
Problem B.↵
----------↵
↵
This is a dp problem. Let $dp[i]$ be the maximum possible sum of the remaining numbers in the range $[1..i]$. For $1 \le i \le k - 1$ the value is just the sum of the numbers in the range. Let $dp[0] = 0$. For $i \ge k$, we may choose to keep the element $a_{i}$ or remove a subsegment of length $k$ which ends at $a_{i}$. Thus, we arrive at the recurrence $dp[i] = \max(dp[i - 1] + a_{i}, dp[i - k])$. We can calculate the dp values in $O(n)$.↵
↵
Problem C.↵
----------↵
----------↵
↵
Problem D.↵
----------↵
↵
To solve this problem, you need to know a bit about permutations. First, we need to determine how to find the minimum number of swaps to sort a permutation. This is a well-known problem. Let the permutation be $P = p_{1}, p_{2}, ..., p_{n}$. Construct a graph by drawing edges from $i$ to $p_{i}$ for all $1 \le i \le n$. Note that the graph is formed by disjoint cycles. You can easily see swapping two elements can either split a cycle into two smaller cycles, or merge two cycles into one cycle. Since the identity permutation is formed by $n$ cycles, the optimal way is to keep splitting cycles into two and increase the total number of cycles by $1$ each step. Thus, if we denote $c$ as the number of cycles in the current permutation, the number of moves needed to sort the permutation is $n - c$. Harry wins if and only if $n - c$ is odd.↵
↵
The key observation is that whenever there are exactly two question marks left, the first player will always win. Why? Consider how the current graph of the permutation looks like. It will be a union of few cycles and $2$ chains (we consider the singleton, a component formed by a single vertex, as a chain). Now, the first player can either choose to close off one of the chains, or join the two chains together. The latter will leave exactly $1$ less number of cycles than the former. So, one of them will guarantee the value of $n - c$ to be odd. Thus, the first player only have to choose the correct move. This implies that if the number of question marks $m$ is at least $2$, then Harry wins if $m$ is even and loses otherwise.↵
↵
Now, the only case left is when there're only $1$ question mark in the beginning. This means that Harry only have $1$ possible move and we're left with the problem of deciding whether the final permutation have $n - c$ odd. Thus, it is enough to count the number of cycles in the formed graph. This can be done by dfs. The complexity of the solution is $O(n)$.↵
↵
Problem E.↵
----------↵
↵
First, we form a trie of the given words. Now, the game is equivalent to the following :↵
↵
1. Start from the root of the trie.↵
↵
2. Each player can either move to one of the children of the current node, or delete one edge connecting the current node to one of the children.↵
↵
The one who can't move loses. This reduced game can be solved with Tree DP. Let $dp[u]$ denote the winner of the game if the first player starts at node $u$. The leaves have $dp[u] = 2$. Our goal is to find $dp[0]$ (where $0$ is the root). The recurrence is simple. Suppose we're finding $dp[u]$ and the children of $u$ are $v_{1}, v_{2}, ..., v_{k}$. If one of the children has dp value of $2$, then Player 1 can just move to that children and win. Otherwise, all children have dp value of $1$. Thus, both players will try not to move down unless forced to. So, they'll keep deleting edges. If there are an even number of children, Player 2 will win, as he will either delete all edges or force Player 1 to move down. Otherwise, Player 1 wins. This gives a simple $O(n)$ tree dp solution.↵
↵
Problem F.↵
----------↵
↵
Firstly, we make the same observations as problem C. Swapping two elements will either split a cycle into two or merge two cycles. Note that if we swap two elements from the same cycle, the cycle will split into two. If we swap two elements from different cycles, the two cycles will combine. Also note that for a cycle of size $c$, we can always split it into two cycles $a$ and $b$ with $a, b > 0$ and $a + b = c$ by choosing the appropriate two elements to swap from the cycle. Now, the game reduces to choose $2$ possibly equal elements from one cycle, swap them, and delete one of the resulting cycles. So, for a given permutation, if the cycle sizes are $c_{1}, c_{2}, ..., c_{k}$, then each move we can choose one of the sizes and the operation is equivalent to changing the size into any nonnegative number strictly smaller than it. Thus, we have reduced the problem to playing a game of Nim on $c_{1}, c_{2}, ..., c_{k}$. Since Harry goes second, he wins if and only if the xor values of all the cycle sizes is $0$. (This is a well-known fact)↵
↵
Thus, we've reduced the problem into finding the number of permutations of length $n$ which have the xor of all cycle sizes equal to $0$. To do so, let $dp[i][j]$ denote the number of permutations with length $i$ and xor of all cycle sizes equal $j$. The dp transitions can be done by iterating through all possible sizes $s$ of the cycle containing $i$. For each $s$, there are $\binom{i - 1}{s - 1}$ ways to choose the remaining elements of the cycle containing $i$ and $(s - 1)!$ ways to permute them. Thus, we can sum up the values of $dp[i - s][j \otimes s] \cdot \binom{i - 1}{s - 1} \cdot (s - 1)!$ for all $1 \le s \le i$. The whole solution works in $O(n^{3})$ time.
