The contest was prepared by awoo, Neon, adedalic, Roms and me. We are very grateful to all of the testers of the contest: PavelKunyavskiy, ashmelev, vladmart, Vladosiya and mariibykova.
We hope you enjoyed both the problems and coding in Kotlin!
Okay, now let's talk about how these problems can be solved:
1910A - Username
Idea: BledDest, preparation: Neon
Solution (PavelKunyavskiy)fun main() {
repeat(readInt()) {
println(readln().dropLastWhile { it == '0' }.dropLast(1))
}
}
private fun readInt() = readln().toInt()
1910B - Security Guard
Idea: Roms, preparation: Roms
Solution (Neon)fun main() = repeat(readLine()!!.toInt()) {
val s = readLine()!!.toCharArray()
val x = s.indexOf('-').takeIf { it >= 0 } ?: 0
val y = s.lastIndexOf('+').takeIf { it >= x } ?: x
s[x] = s[y].also { s[y] = s[x] }
val bal = s.runningFold(0) { cur, c -> cur + if (c == '-') -1 else 1 }
println(if (bal.min() == 0) "$$${x + 1} $$${y + 1}" else "-1")
}
1910C - Poisonous Swamp
Idea: BledDest, preparation: awoo
Solution (PavelKunyavskiy)fun main() {
repeat(readInt()) {
readInt()
val s = readln() + '.' + readln()
println(s.split(".").sumOf { maxOf(0, it.length - 1) })
}
}
private fun readInt() = readln().toInt()
1910D - Remove and Add
Idea: BledDest, preparation: awoo
Solution (PavelKunyavskiy)private fun solve() : Boolean {
val n = readInt()
val a = readInts().toIntArray()
var dropped = false
for (i in 1 until n) {
if (a[i] == a[i-1]) {
a[i]++
} else if (a[i] < a[i-1]) {
if (dropped) return false
dropped = true
if (i != 1) {
when {
a[i-2] > a[i] -> a[i] = a[i-1]
a[i-2] == a[i] -> a[i]++
else -> {}
}
}
}
}
return true
}
fun main() {
repeat(readInt()) {
println(if (solve()) "YES" else "NO")
}
}
private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }
1910E - Maximum Sum Subarrays
Idea: BledDest, preparation: Neon
Solution 1 (Neon)fun main() = repeat(readLine()!!.toInt()) {
val n = readLine()!!.toInt()
val a = readLine()!!.split(" ").map { it.toLong() }
val b = readLine()!!.split(" ").map { it.toLong() }
val dp = Array(3) { LongArray(3) { 0 } }
for ((x, y) in a zip b) {
for (i in 0..2) for (j in 0..2) {
dp[i][j] += maxOf(
(if (i == 1) x else 0) + (if (j == 1) y else 0),
(if (i == 1) y else 0) + (if (j == 1) x else 0)
);
}
for (i in 0..2) for (j in 0..2) {
if (i < 2) dp[i + 1][j] = maxOf(dp[i + 1][j], dp[i][j]);
if (j < 2) dp[i][j + 1] = maxOf(dp[i][j + 1], dp[i][j]);
}
}
println(dp[2][2]);
}
Solution 2 (PavelKunyavskiy)fun best(a: List<Int>, k: Int): Long {
val r = LongArray(4)
var sum = 0L
for (v in a) {
sum += v
r[0] = maxOf(r[0], -sum)
r[1] = maxOf(r[1], r[0] + sum)
r[2] = maxOf(r[2], r[1] - sum)
r[3] = maxOf(r[3], r[2] + sum)
}
return r[2 * k - 1]
}
fun main() {
repeat(readInt()) {
readInt()
val a = readInts()
val b = readInts()
val mins = a.zip(b).map { minOf(it.first, it.second) }
val maxs = a.zip(b).map { maxOf(it.first, it.second) }
println(maxOf(best(mins, 1) + best(maxs, 1), best(maxs, 2)))
}
}
private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }
1910F - Build Railway Stations
Idea: BledDest, preparation: awoo
Solution (PavelKunyavskiy)fun main() {
repeat(readInt()) {
val (n, k) = readInts()
val g = List(n) { mutableListOf<Int>() }
repeat(n - 1) {
val (a, b) = readInts().map { it - 1 }
g[a].add(b)
g[b].add(a)
}
val size = IntArray(n)
fun dfs(v: Int, p:Int) : Int {
size[v] = 1 + g[v].sumOf { if (it == p) 0 else dfs(it, v) }
return size[v]
}
dfs(0, 0)
val ns = size.map { it.toLong() * (n - it) }.sortedDescending()
println(ns.subList(0, k - 1).sum() + ns.subList(k - 1, ns.size).sum() * 2)
}
}
private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }
1910G - Pool Records
Idea: adedalic, preparation: adedalic
Solution (adedalic)fun main() {
repeat(readln().toInt()) {
val n = readln().toInt()
val t = readln().split(' ').map { it.toLong() }
fun Long.genMoments() = List(n) { (it + 1) * this }
val sPeriod = t[0]
val lPeriod = t.firstOrNull { it % sPeriod != 0L }
val sMoments = sPeriod.genMoments()
val lMoments = lPeriod?.genMoments() ?: listOf()
val req = sMoments.union(lMoments).sorted().take(n)
println(if (req == t) "VALID" else "INVALID")
}
}
1910H - Sum of Digits of Sums
Idea: BledDest, preparation: BledDest
Solution (PavelKunyavskiy)private fun digitSum(a: Int) = a.toString().toCharArray().sumOf { it.digitToInt() }
private fun List<Int>.lowerBound(x: Int) = binarySearch { if (it < x) -1 else 1 }.inv()
fun main() {
val n = readInt()
val a = readInts()
val pw10 = buildList<Int> {
add(1)
repeat(9) { add(last() * 10) }
removeAt(0)
}
val d = pw10.map { p -> a.map { it % p }.sorted() }
val ds = a.sumOf { digitSum(it) }
println(a.map { x ->
ds + n * digitSum(x) - 9 * pw10.indices.sumOf {
n - d[it].lowerBound(pw10[it] - (x % pw10[it]))
}
}.joinToString(" "))
}
private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }
1910I - Inverse Problem
Idea: BledDest, preparation: awoo
Solution (awoo)val MOD = 998244353
fun main() {
val (n, k, c) = readLine()!!.split(' ').map { it.toInt() }
val t = readLine()!!
val cnt = n / k + 1
val dp = Array(2) { IntArray(cnt) {0} }
val pw = IntArray(cnt) {1}
dp[0][0] = 1
for (ii in 0 until n % k) {
val i = ii and 1
val ni = i xor 1
var sum = 0
val cur = c - (t[ii].toInt() - 'a'.toInt()) - 1
var pr = 1
for (j in 1 until cnt) {
pw[j] = (pw[j - 1] * (cur + 1).toLong() % MOD).toInt()
}
for (j in 0 until cnt) {
sum = ((sum * cur.toLong() + pr * dp[i][j].toLong()) % MOD).toInt()
pr = (pr * c.toLong() % MOD).toInt()
dp[ni][j] = (sum * pw[cnt - j - 1].toLong() % MOD).toInt()
}
}
var ans = 0
for (i in 0 until cnt) {
ans = (ans + dp[n % k % 2][i]) % MOD
}
for (i in 0 until n) {
if (i % k >= n % k) {
ans = (ans * c.toLong() % MOD).toInt()
}
}
println(ans)
}
1910J - Two Colors
Idea: BledDest, preparation: BledDest
Solution (PavelKunyavskiy)import kotlin.math.abs
fun main() {
val n = readInt()
val c = readInts()
val g = List(n) { mutableListOf<Pair<Int, Int>>() }
repeat(n - 1) {
val (a, b, w) = readInts()
g[a - 1].add(b - 1 to w)
g[b - 1].add(a - 1 to w)
}
val size = List(2) { IntArray(n) }
var ans = 0L
fun dfs(v: Int, p: Int) {
size[c[v]][v] = 1
for ((u, w) in g[v]) {
if (u != p) {
dfs(u, v)
size[0][v] += size[0][u]
size[1][v] += size[1][u]
ans += abs(size[0][u] - size[1][u]) * w.toLong()
}
}
}
dfs(0, 0)
println(ans)
}
private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }
Nicely curated problems orz in order of difficulty to slowly dive into the syntax and structure of Kotlin, took me time but enjoyed in solving and learning syntax on way.
For the problem H, there is actually an
O(nlogA)
solution. When i'm saying "b.s.", i'm refering to "binary search". TheO(nlognlogA)
complexity we need to "patch" comes in 2 parts: the sorting, and the b.s.. For the sorting, we can dolsd radix sort
(with base 10), and store every iteration of it. For the second part, we don't actually have to do b.s.. If we focus on the "queries" of the b.s. on an arbitrary array (one of thelogA
ones), the inputs of the b.s. arem-ar[i]
, wherem
is the current power of 10, andar[i]
is the value on the array. Becausear
is sorted (we don't care about order), the sequencem-ar[i]
is also sorted, in reverse order (becausem
is constant). Therefore, we can find all the positions of the sequence, with a basic 2-pointer method (see merge-sort), in linear time. So we haveO(n)
time for every array, and we havelogA
arrays, so the final time (and space) complexity isO(nlogA)
. I'm gonna upload c++ code in a while too.I just coded it up, the only test cases i've tested it on, are the 2 input examples from the problem statement (it works). 239141643 It obviously doesn't compile, its on c++. I sent the submission for you to see the code.
ALSO: The space complexity can be improved to
O(n)
, even tho i'm not gonna bother coding it: We need to store only the current iteration of the (base 10)lsd radix sort
, and calculate the values for the indeces, and then move on to the next iteration. From now on, we don't need the previous one, so we don't have to keep storing it.Final time complexity:
O(nlogA)
, where A is the max elementFinal space complexity:
O(n)
.Just did it, 239202554. I believe that this is the optimal time and space complexity