Kotlin Heroes Episode 9 Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

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

Comments (4)

Write comment?

silent_Joy

11 months ago, # |

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.

→ Reply

streidi

10 months ago, # |

← Rev. 2 →

For the problem H, there is actually an O(nlogA) solution. When i'm saying "b.s.", i'm refering to "binary search". The O(nlognlogA) complexity we need to "patch" comes in 2 parts: the sorting, and the b.s.. For the sorting, we can do lsd 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 the logA ones), the inputs of the b.s. are m-ar[i], where m is the current power of 10, and ar[i] is the value on the array. Because ar is sorted (we don't care about order), the sequence m-ar[i] is also sorted, in reverse order (because m 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 have O(n) time for every array, and we have logA arrays, so the final time (and space) complexity is O(nlogA). I'm gonna upload c++ code in a while too.

10 months ago, # ^ |

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 element

Final space complexity: O(n).

Just did it, 239202554. I believe that this is the optimal time and space complexity

BledDest's blog