codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1910.md (10261B)


      1 Source: https://codeforces.com/blog/entry/123261
      2 
      3 The contest was prepared by [awoo](/profile/awoo "Master awoo"), [Neon](/profile/Neon "Candidate Master Neon"), [adedalic](/profile/adedalic "International Master adedalic"), [Roms](/profile/Roms "Master Roms") and me. We are very grateful to all of the testers of the contest: [PavelKunyavskiy](/profile/PavelKunyavskiy "Grandmaster PavelKunyavskiy"), [ashmelev](/profile/ashmelev "Grandmaster ashmelev"), [vladmart](/profile/vladmart "Master vladmart"), [Vladosiya](/profile/Vladosiya "Expert Vladosiya") and [mariibykova](/profile/mariibykova "Newbie mariibykova").
      4 
      5 We hope you enjoyed both the problems and coding in Kotlin!
      6 
      7 Okay, now let's talk about how these problems can be solved:
      8 
      9 [1910A - Username](/contest/1910/problem/A)
     10 
     11 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon")
     12 
     13 **Tutorial**
     14 
     15 Tutorial is loading...
     16 
     17 **Solution (PavelKunyavskiy)**
     18 
     19 ```
     20 fun main() {
     21     repeat(readInt()) {
     22         println(readln().dropLastWhile { it == '0' }.dropLast(1))
     23     }
     24 }
     25 
     26 private fun readInt() = readln().toInt()
     27 ```
     28 
     29 [1910B - Security Guard](/contest/1910/problem/B)
     30 
     31 Idea: [Roms](/profile/Roms "Master Roms"), preparation: [Roms](/profile/Roms "Master Roms")
     32 
     33 **Tutorial**
     34 
     35 Tutorial is loading...
     36 
     37 **Solution (Neon)**
     38 
     39 ```
     40 fun main() = repeat(readLine()!!.toInt()) {
     41   val s = readLine()!!.toCharArray()
     42   val x = s.indexOf('-').takeIf { it >= 0 } ?: 0
     43   val y = s.lastIndexOf('+').takeIf { it >= x } ?: x
     44   s[x] = s[y].also { s[y] = s[x] }
     45   val bal = s.runningFold(0) { cur, c -> cur + if (c == '-') -1 else 1 }
     46   println(if (bal.min() == 0) "${x + 1} ${y + 1}" else "-1")
     47 }
     48 ```
     49 
     50 [1910C - Poisonous Swamp](/contest/1910/problem/C)
     51 
     52 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [awoo](/profile/awoo "Master awoo")
     53 
     54 **Tutorial**
     55 
     56 Tutorial is loading...
     57 
     58 **Solution (PavelKunyavskiy)**
     59 
     60 ```
     61 fun main() {
     62     repeat(readInt()) {
     63         readInt()
     64         val s = readln() + '.' + readln()
     65         println(s.split(".").sumOf { maxOf(0, it.length - 1) })
     66     }
     67 }
     68  
     69 private fun readInt() = readln().toInt()
     70 ```
     71 
     72 [1910D - Remove and Add](/contest/1910/problem/D)
     73 
     74 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [awoo](/profile/awoo "Master awoo")
     75 
     76 **Tutorial**
     77 
     78 Tutorial is loading...
     79 
     80 **Solution (PavelKunyavskiy)**
     81 
     82 ```
     83 private fun solve() : Boolean {
     84     val n = readInt()
     85     val a = readInts().toIntArray()
     86     var dropped = false
     87     for (i in 1 until n) {
     88         if (a[i] == a[i-1]) {
     89             a[i]++
     90         } else if (a[i] < a[i-1]) {
     91             if (dropped) return false
     92             dropped = true
     93             if (i != 1) {
     94                 when {
     95                     a[i-2] > a[i] -> a[i] = a[i-1]
     96                     a[i-2] == a[i] -> a[i]++
     97                     else -> {}
     98                 }
     99             }
    100         }
    101     }
    102     return true
    103 }
    104 fun main() {
    105     repeat(readInt()) {
    106         println(if (solve()) "YES" else "NO")
    107     }
    108 }
    109 
    110 private fun readInt() = readln().toInt()
    111 private fun readLongs() = readStrings().map { it.toLong() }
    112 private fun readStrings() = readln().split(" ")
    113 private fun readInts() = readStrings().map { it.toInt() }
    114 ```
    115 
    116 [1910E - Maximum Sum Subarrays](/contest/1910/problem/E)
    117 
    118 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon")
    119 
    120 **Tutorial**
    121 
    122 Tutorial is loading...
    123 
    124 **Solution 1 (Neon)**
    125 
    126 ```
    127 fun main() = repeat(readLine()!!.toInt()) {
    128   val n = readLine()!!.toInt()
    129   val a = readLine()!!.split(" ").map { it.toLong() }
    130   val b = readLine()!!.split(" ").map { it.toLong() }
    131   val dp = Array(3) { LongArray(3) { 0 } }
    132   for ((x, y) in a zip b) {
    133     for (i in 0..2) for (j in 0..2) {
    134       dp[i][j] += maxOf(
    135       	(if (i == 1) x else 0) + (if (j == 1) y else 0),
    136       	(if (i == 1) y else 0) + (if (j == 1) x else 0)
    137       );
    138     }
    139     for (i in 0..2) for (j in 0..2) {
    140       if (i < 2) dp[i + 1][j] = maxOf(dp[i + 1][j], dp[i][j]);
    141       if (j < 2) dp[i][j + 1] = maxOf(dp[i][j + 1], dp[i][j]);
    142     }
    143   }
    144   println(dp[2][2]);
    145 }
    146 ```
    147 
    148 **Solution 2 (PavelKunyavskiy)**
    149 
    150 ```
    151 fun best(a: List<Int>, k: Int): Long {
    152     val r = LongArray(4)
    153     var sum = 0L
    154     for (v in a) {
    155         sum += v
    156         r[0] = maxOf(r[0], -sum)
    157         r[1] = maxOf(r[1], r[0] + sum)
    158         r[2] = maxOf(r[2], r[1] - sum)
    159         r[3] = maxOf(r[3], r[2] + sum)
    160     }
    161     return r[2 * k - 1]
    162 }
    163 
    164 fun main() {
    165     repeat(readInt()) {
    166         readInt()
    167         val a = readInts()
    168         val b = readInts()
    169         val mins = a.zip(b).map { minOf(it.first, it.second) }
    170         val maxs = a.zip(b).map { maxOf(it.first, it.second) }
    171         println(maxOf(best(mins, 1) + best(maxs, 1), best(maxs, 2)))
    172     }
    173 }
    174 
    175 private fun readInt() = readln().toInt()
    176 private fun readLongs() = readStrings().map { it.toLong() }
    177 private fun readStrings() = readln().split(" ")
    178 private fun readInts() = readStrings().map { it.toInt() }
    179 ```
    180 
    181 [1910F - Build Railway Stations](/contest/1910/problem/F)
    182 
    183 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [awoo](/profile/awoo "Master awoo")
    184 
    185 **Tutorial**
    186 
    187 Tutorial is loading...
    188 
    189 **Solution (PavelKunyavskiy)**
    190 
    191 ```
    192 fun main() {
    193     repeat(readInt()) {
    194         val (n, k) = readInts()
    195         val g = List(n) { mutableListOf<Int>() }
    196         repeat(n - 1) {
    197             val (a, b) = readInts().map { it - 1 }
    198             g[a].add(b)
    199             g[b].add(a)
    200         }
    201         val size = IntArray(n)
    202         fun dfs(v: Int, p:Int) : Int {
    203             size[v] = 1 + g[v].sumOf { if (it == p) 0 else dfs(it, v) }
    204             return size[v]
    205         }
    206         dfs(0, 0)
    207         val ns = size.map { it.toLong() * (n - it) }.sortedDescending()
    208         println(ns.subList(0, k - 1).sum() + ns.subList(k - 1, ns.size).sum() * 2)
    209     }
    210 }
    211 
    212 private fun readInt() = readln().toInt()
    213 private fun readLongs() = readStrings().map { it.toLong() }
    214 private fun readStrings() = readln().split(" ")
    215 private fun readInts() = readStrings().map { it.toInt() }
    216 ```
    217 
    218 [1910G - Pool Records](/contest/1910/problem/G)
    219 
    220 Idea: [adedalic](/profile/adedalic "International Master adedalic"), preparation: [adedalic](/profile/adedalic "International Master adedalic")
    221 
    222 **Tutorial**
    223 
    224 Tutorial is loading...
    225 
    226 **Solution (adedalic)**
    227 
    228 ```
    229 fun main() {
    230     repeat(readln().toInt()) {
    231         val n = readln().toInt()
    232         val t = readln().split(' ').map { it.toLong() }
    233 
    234         fun Long.genMoments() = List(n) { (it + 1) * this }
    235 
    236         val sPeriod = t[0]
    237         val lPeriod = t.firstOrNull { it % sPeriod != 0L }
    238 
    239         val sMoments = sPeriod.genMoments()
    240         val lMoments = lPeriod?.genMoments() ?: listOf()
    241 
    242         val req = sMoments.union(lMoments).sorted().take(n)
    243         println(if (req == t) "VALID" else "INVALID")
    244     }
    245 }
    246 ```
    247 
    248 [1910H - Sum of Digits of Sums](/contest/1910/problem/H)
    249 
    250 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    251 
    252 **Tutorial**
    253 
    254 Tutorial is loading...
    255 
    256 **Solution (PavelKunyavskiy)**
    257 
    258 ```
    259 private fun digitSum(a: Int) = a.toString().toCharArray().sumOf { it.digitToInt() }
    260 private fun List<Int>.lowerBound(x: Int) = binarySearch { if (it < x) -1 else 1 }.inv()
    261 fun main() {
    262     val n = readInt()
    263     val a = readInts()
    264     val pw10 = buildList<Int> {
    265         add(1)
    266         repeat(9) { add(last() * 10) }
    267         removeAt(0)
    268     }
    269     val d = pw10.map { p -> a.map { it % p }.sorted() }
    270     val ds = a.sumOf { digitSum(it) }
    271     println(a.map { x ->
    272         ds + n * digitSum(x) - 9 * pw10.indices.sumOf {
    273             n - d[it].lowerBound(pw10[it] - (x % pw10[it]))
    274         }
    275     }.joinToString(" "))
    276 }
    277 
    278 private fun readInt() = readln().toInt()
    279 private fun readLongs() = readStrings().map { it.toLong() }
    280 private fun readStrings() = readln().split(" ")
    281 private fun readInts() = readStrings().map { it.toInt() }
    282 ```
    283 
    284 [1910I - Inverse Problem](/contest/1910/problem/I)
    285 
    286 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [awoo](/profile/awoo "Master awoo")
    287 
    288 **Tutorial**
    289 
    290 Tutorial is loading...
    291 
    292 **Solution (awoo)**
    293 
    294 ```
    295 val MOD = 998244353
    296 
    297 fun main() {
    298 	val (n, k, c) = readLine()!!.split(' ').map { it.toInt() }
    299 	val t = readLine()!!
    300 	val cnt = n / k + 1
    301 	val dp = Array(2) { IntArray(cnt) {0} }
    302 	val pw = IntArray(cnt) {1}
    303 	dp[0][0] = 1
    304 	for (ii in 0 until n % k) {
    305 		val i = ii and 1
    306 		val ni = i xor 1
    307 		var sum = 0
    308 		val cur = c - (t[ii].toInt() - 'a'.toInt()) - 1
    309 		var pr = 1
    310 		for (j in 1 until cnt) {
    311 			pw[j] = (pw[j - 1] * (cur + 1).toLong() % MOD).toInt()
    312 		}
    313 		for (j in 0 until cnt) {
    314 			sum = ((sum * cur.toLong() + pr * dp[i][j].toLong()) % MOD).toInt()
    315 			pr = (pr * c.toLong() % MOD).toInt()
    316 			dp[ni][j] = (sum * pw[cnt - j - 1].toLong() % MOD).toInt()
    317 		}
    318 	}
    319 	var ans = 0
    320 	for (i in 0 until cnt) {
    321 		ans = (ans + dp[n % k % 2][i]) % MOD
    322 	}
    323 	for (i in 0 until n) {
    324 		if (i % k >= n % k) {
    325 			ans = (ans * c.toLong() % MOD).toInt()
    326 		}
    327 	}
    328 	println(ans)
    329 }
    330 ```
    331 
    332 [1910J - Two Colors](/contest/1910/problem/J)
    333 
    334 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    335 
    336 **Tutorial**
    337 
    338 Tutorial is loading...
    339 
    340 **Solution (PavelKunyavskiy)**
    341 
    342 ```
    343 import kotlin.math.abs
    344 
    345 fun main() {
    346     val n = readInt()
    347     val c = readInts()
    348     val g = List(n) { mutableListOf<Pair<Int, Int>>() }
    349     repeat(n - 1) {
    350         val (a, b, w) = readInts()
    351         g[a - 1].add(b - 1 to w)
    352         g[b - 1].add(a - 1 to w)
    353     }
    354     val size = List(2) { IntArray(n) }
    355     var ans = 0L
    356     fun dfs(v: Int, p: Int) {
    357         size[c[v]][v] = 1
    358         for ((u, w) in g[v]) {
    359             if (u != p) {
    360                 dfs(u, v)
    361                 size[0][v] += size[0][u]
    362                 size[1][v] += size[1][u]
    363                 ans += abs(size[0][u] - size[1][u]) * w.toLong()
    364             }
    365         }
    366     }
    367     dfs(0, 0)
    368     println(ans)
    369 }
    370 
    371 private fun readInt() = readln().toInt()
    372 private fun readLongs() = readStrings().map { it.toLong() }
    373 private fun readStrings() = readln().split(" ")
    374 private fun readInts() = readStrings().map { it.toInt() }
    375 ```