Блог пользователя Dogacel

Solutions [A to E] for "Kotlin Heroes: Episode 12"
Автор Dogacel, история, 12 месяцев назад, По-английски

Kotlin Heroes: Episode 12

First of all, I would like to start with sharing my slim template for kotlin competitive programming environment. If you would like to learn more, read the spoiler below. I wish I could have solved all, but unfortunately I was only able to figure out the solutions to the first 5 problems.

Local Kotlin Template

Problem A — Password Generator

Considering $$$a$$$, $$$b$$$ and $$$c$$$ is less than 10 and "no two adjacent characters in the password should be the same", we can construct a string by appending $$$a$$$ unique digits, $$$b$$$ unique upper case characters and $$$c$$$ unique lower case characters. As their upper bound is 10, we don't need to worry about characters becoming adjacent as our character pool is large enough.

Solution

Problem B — Showmatch

Assume all players are sorted by their score, $$$a$$$. It is safe to assume it as we are only changing each player's index for the sake of this proof. For any given player $$$i$$$, their best opponent is either $$$i-1$$$ or $$$i+1$$$. Because the array is in the sorted order, $$$|a_i - a_{i+2}|$$$ is always greater than $$$|a_i - a_{i+1}|$$$ and vice versa.

Therefore we need to sort the array $$$a$$$, check each tuple and make sure every player is matched to their best opponent.

Iterate over each pair, $$$(a_i, a_{i+1})$$$ make sure $$$|a_i - a_{i-1}| \geq |a_{i+1} - a_i|$$$ and $$$|a_{i+2} - a_{i+1}| \geq |a_{i+1} - a_i|$$$. This ensures everyone is matched to their best opponent.

Note: Make sure you start at $$$i=0$$$ and increase $$$i$$$ by 2 because you want to iterate over each matchup.

Solution

Problem C — Coin Game

In this game, the optimal solution for each player is to take the type of coin that has the most amount. So the player 1 will always pick the coints with the type that has the most amount and least amount, as player 2 will pick the middle one.

We could have brute-forced this solution but we have $$$q \leq 10^5$$$ queries and $$$|s| \leq 10^5$$$. Thus total operations we should make would be $$$q \times |s| \leq 10^{10}$$$ and it is not feasible.

So we should do a dynamic-programming solution to make sure each of our queries run in $$$O(1)$$$ constant time. We can do this by memorizing the number of coins given in each interval $$$[l, r]$$$. Let's say $$$dp_{gold}[i]$$$ represents the number of gold coins inside the interval $$$[0, i)$$$. We can calculate the number of coins between $$$l$$$ and $$$r$$$ by $$$f(l, r) = dp_{gold}[r + 1] - dp_{gold}[l]$$$.

Using this memoization, we should only calculate $$$dp_{gold}$$$, $$$dp_{silver}$$$ and $$$dp_{bronze}$$$ once during initialization. Later on we can calculate the number of coins given inside the interval $$$[l, r]$$$ in $$$O(1)$$$ time using the equation above.

Solution

Problem D — Uppercase or Lowercase?

In this problem, we have at most $$$500$$$ entries in our DB. We are also given at most $$$10$$$ queries. We would like to do a binary search to efficiently query those entries and $$$8 \leq log_{2}{500} \leq 9$$$. This gives us an extra query chance to figure out if capital letters are ordered first or last.

We can learn about this by querying the first entry. If it starts with a capital letter, we can assume capital letters are ordered first. If not, lowercase letters are ordered first. To emulate this behavior in our binary search algorithm, we can invert the first character's capitalization of each word if lex order is inverted. By doing this, our database will be ordered correctly.

Solution

Problem E

The optimal solution to this problem contains at most 2 sweeps. While sweeping from one direction to another, we can take all arrows that point at the sweeping direction that has $$$c_i \gt 0$$$. At some point $$$j$$$, we should stop and start sweeping for the opposite direction. There is no better solution with a 3rd sweep, because we have already took all arrows that has $$$c_i \gt 0$$$. However the optimal solution might consider only 1 sweep as well.

So the solution can be either,

  1. Only take all arrows that point to the right that has $$$c_i \gt 0$$$.
  2. Only take all arrows that point to the left that has $$$c_i \gt 0$$$.
  3. Find the constant $$$j$$$ so that, take all arrows that point to the right that has $$$c_i \gt 0$$$ and $$$i \lt j$$$. At the point $$$j$$$, there must be an arrow pointing left. Make a U-turn and take all left arrows that has $$$c_i \gt 0$$$.
  4. Find the constant $$$j$$$ so that, take all arrows that point to the left that has $$$c_i \gt 0$$$ and $$$i \gt j$$$. At the point $$$j$$$, there must be an arrow pointing right. Make a U-turn and take all right arrows that has $$$c_i \gt 0$$$.

For number 1 and 2, the solution is a simple $$$O(n)$$$. However number 3 or 4 requires $$$O(n^2)$$$ iterations without any memoization.

So let's create a dynamic-programming solution. I will only explain number 3, but it's logic is applicable to number 4 as well. Define $$$dp_{left}[i]$$$ as the sum of all arrows, such that $$$c_i \gt 0$$$, that point left between the interval $$$[0, i)$$$. Also define $$$dp_{right}[i]$$$ as the sum of all arrows, such that $$$c_i \gt 0$$$, that point right between the interval $$$[0, i)$$$.

So to find the optimal result by doing a left to right sweep first and later doing a right to left sweep, we can iterate over all $$$j$$$ in $$$O(n)$$$ time.

$$$

= \begin{cases} dp_{right}[j] + c_j + dp_{left}[j], & \text{if jth arrow is a left arrow,} \\ 0, & \text{else}. \end{cases}

$$$

We have calculated the total amount gained in the right sweep with $$$dp_{right}[j]$$$, we have added the cost of making the U turn with $$$c_j$$$ and finally we added the amount gained in the left sweep with $$$dp_{left}[j]$$$.

Solution

Полный текст и комментарии »

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится