Kotlin Heroes Episode 9 Editorial

#	User	Rating
1	jiangly	3976
2	tourist	3815
3	jqdai0815	3682
4	ksun48	3614
5	orzdevinwang	3526
6	ecnerwala	3514
7	Benq	3482
8	hos.lyric	3382
9	gamegame	3374
10	heuristica	3357

#	User	Contrib.
1	cry	169
2	-is-this-fft-	166
3	Um_nik	161
3	atcoder_official	161
5	djm03178	157
6	Dominater069	156
7	adamant	154
8	luogu_official	152
9	awoo	151
10	TheScrasse	147

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

Tutorial

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

Tutorial

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

Tutorial

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

Tutorial

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

Tutorial

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

Tutorial

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

Tutorial

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

Tutorial

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

Tutorial

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

Tutorial

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() }

BledDest's blog