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 ```