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 TemplateI have a template.kt file, I copy-paste this file for each problem. It gives me a quick-start.
private fun nextInt() = readLine()!!.toInt()
private fun nextInts() = readLine()!!.split(" ").map { it.toInt() }
private fun nextLong() = readLine()!!.toLong()
private fun nextLongs() = readLine()!!.split(" ").map { it.toLong() }
fun main() {
for (t in 1..nextInt()) {}
}
Moreover, I have this function in my .zshrc. I just call korun a.kt and it automatically compiles and runs that kotlin file quickly.
function korun() {
local file="$1"
local output_dir="bin"
local base_name
local executable
# Check if the file exists
if [[ ! -f "$file" ]]; then
echo "Error: File '$file' does not exist."
return 1
fi
# Create the bin directory if it doesn't exist
mkdir -p "$output_dir"
# Extract the base name (filename without extension)
base_name=$(basename "$file" .kt)
executable="$output_dir/$base_name"
# Compile the Kotlin file into a JAR
kotlinc "$file" -include-runtime -d "$output_dir/$base_name.jar"
if [[ $? -ne 0 ]]; then
echo "Compilation failed."
return 1
fi
# Create the executable wrapper script
cat <<EOF > "$executable"
#!/bin/bash
exec java -jar "\<p>Unable to parse markup [type=CF_MATHJAX]</p>@"
EOF
# Make the wrapper executable
chmod +x "$executable"
echo "Executable created: $executable"
# Shift arguments and run the executable with them
shift
"$$$executable" "$$$@"
}
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
private fun nextInt() = readLine()!!.toInt()
private fun nextInts() = readLine()!!.split(" ").map { it.toInt() }
private fun nextLong() = readLine()!!.toLong()
private fun nextLongs() = readLine()!!.split(" ").map { it.toLong() }
fun main() {
for (t in 1..nextInt()) {
val (a, b, c) = nextInts()
val digits = listOf('0', '1', '2', '3', '4', '5', '6', '7', '8', '9')
val lowerCase = listOf('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k')
val upperCase = lowerCase.map { it.uppercase() }
for (i in 0..a - 1) {
print(digits[i])
}
for (i in 0..b - 1) {
print(upperCase[i])
}
for (i in 0..c - 1) {
print(lowerCase[i])
}
println()
}
}
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.
Solutionprivate fun nextInt() = readLine()!!.toInt()
private fun nextInts() = readLine()!!.split(" ").map { it.toInt() }
private fun nextLong() = readLine()!!.toLong()
private fun nextLongs() = readLine()!!.split(" ").map { it.toLong() }
fun main() {
for (t in 1..nextInt()) {
val n = nextInt()
val a = nextInts()
val aSorted = a.sorted()
var result = true
// 3 5 7 12
for (i in 0..n - 1) {
if (i < n - 1) {
if (aSorted[2 * i + 1] - aSorted[2 * i] > aSorted[2 * i + 2] - aSorted[2 * i + 1]) {
result = false
break
}
}
if (i > 0) {
if (aSorted[2 * i + 1] - aSorted[2 * i] > aSorted[2 * i] - aSorted[2 * i - 1]) {
result = false
break
}
}
}
if (result) {
println("YES")
} else {
println("NO")
}
}
}
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.
Solutionprivate fun nextInt() = readLine()!!.toInt()
private fun nextInts() = readLine()!!.split(" ").map { it.toInt() }
private fun nextLong() = readLine()!!.toLong()
private fun nextLongs() = readLine()!!.split(" ").map { it.toLong() }
fun main() {
val s = readLine()!!
val q = nextInt()
val goldSum = (listOf(0) + s.map { 0 }.toList()).toMutableList()
val silverSum = (listOf(0) + s.map { 0 }.toList()).toMutableList()
val bronzSum = (listOf(0) + s.map { 0 }.toList()).toMutableList()
for (i in 0..s.length - 1) {
when (s[i]) {
'G' -> {
goldSum[i + 1] = goldSum[i] + 1
silverSum[i + 1] = silverSum[i]
bronzSum[i + 1] = bronzSum[i]
}
'S' -> {
goldSum[i + 1] = goldSum[i]
silverSum[i + 1] = silverSum[i] + 1
bronzSum[i + 1] = bronzSum[i]
}
'B' -> {
goldSum[i + 1] = goldSum[i]
silverSum[i + 1] = silverSum[i]
bronzSum[i + 1] = bronzSum[i] + 1
}
}
}
for (t in 0..q - 1) {
val (l, r) = nextInts()
val gs = goldSum[r] - goldSum[l - 1]
val ss = silverSum[r] - silverSum[l - 1]
val bs = bronzSum[r] - bronzSum[l - 1]
val sums = listOf(gs, ss, bs).sorted()
println(sums[2] + sums[0])
}
}
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.
Solutionprivate fun nextInt() = readLine()!!.toInt()
private fun nextInts() = readLine()!!.split(" ").map { it.toInt() }
private fun nextLong() = readLine()!!.toLong()
private fun nextLongs() = readLine()!!.split(" ").map { it.toLong() }
fun main() {
val h = readLine()!!
val n = h.split(" ")[0].toInt()
fun String.invertCase(): String {
return (if (this[0].isUpperCase()) this[0].lowercase() else this[0].uppercase()) +
this.substring(1)
}
var searchTarget = h.split(" ")[1]
println("? 1")
var isInverted = false
val fr = readLine()!!
if (fr == searchTarget) {
println("! 1")
return
}
if (fr[0].isLowerCase()) {
isInverted = true
searchTarget = searchTarget.invertCase()
}
var l = 0
var r = n
var found = false
for (i in 0..7) {
val curr = (r + l) / 2
println("? " + (curr + 1))
val result = readLine()!!
val toCompare = if (isInverted) result.invertCase() else result
val cmp = toCompare.compareTo(searchTarget)
if (cmp == 0) {
found = true
println("! " + (curr + 1))
break
}
if (cmp < 0) {
l = curr
}
if (cmp > 0) {
r = curr
}
}
if (!found) {
println("! " + (r))
}
}
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,
- Only take all arrows that point to the right that has $$$c_i \gt 0$$$.
- Only take all arrows that point to the left that has $$$c_i \gt 0$$$.
- 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$$$.
- 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]$$$.
Solutionprivate fun nextInt() = readLine()!!.toInt()
private fun nextInts() = readLine()!!.split(" ").map { it.toInt() }
private fun nextLong() = readLine()!!.toLong()
private fun nextLongs() = readLine()!!.split(" ").map { it.toLong() }
fun main() {
for (t in 1..nextInt()) {
val n = nextInt()
val arrows = readLine()!!
val ci = nextLongs()
val lsum = (listOf(0L) + arrows.map { 0L }).toMutableList()
val rsum = (listOf(0L) + arrows.map { 0L }).toMutableList()
for (i in 0..n - 1) {
if (arrows[i] == '>') {
lsum[i + 1] = lsum[i] + maxOf(0L, ci[i])
rsum[i + 1] = rsum[i]
} else {
lsum[i + 1] = lsum[i]
rsum[i + 1] = rsum[i] + maxOf(0L, ci[i])
}
}
var best = maxOf(lsum.last(), rsum.last())
for (i in 0..n - 1) {
if (arrows[i] != '<') {
continue
}
val ls = lsum[i + 1]
val cost = ci[i]
val rs = rsum[i]
val total = ls + cost + rs
best = maxOf(total, best)
}
for (inv in 0..n - 1) {
val i = n - 1 - inv
if (arrows[i] != '>') {
continue
}
val rs = rsum[n] - rsum[i]
val cost = ci[i]
val ls = lsum[n] - lsum[i + 1]
val total = ls + cost + rs
best = maxOf(total, best)
}
println(best)
}
}
Auto comment: topic has been updated by Dogacel (previous revision, new revision, compare).
Auto comment: topic has been updated by Dogacel (previous revision, new revision, compare).
I think your solution to E is overcomplicated. We can fix the rigthmost < or the leftmost > that will be taken. For example, for the < with index r answer will be c[r] + max(0,c[0]) + max(0,c[1]) + ... + max(0,c[r-1]).
I did not understand what you mean by "fix". I have visualized my approach as a "sweep". If you combine number 3 and 4 in my solution, the sum might be equal to what you said. However I believe it is easier to visualize in your head by thinking it as making a U-turn. I don't think less steps is necessarily less complicated.
I mean let's assume that certain i is the last or the first index, that we will take. Let's consider the case that i is the first index we take, case that i is the last can be handled symmetrically. if i-th character is <, then we can take only i, because of our assumption, if it is >, we can take anything on the right of it, so simple greedy will work.
I understand now, thanks. It makes sense.