1346.md (14156B)
1 Source: https://codeforces.com/blog/entry/78124 2 3 First of all, I would like to thank all of the testers: [elizarov](/profile/elizarov "Candidate Master elizarov"), [darnley](/profile/darnley "Grandmaster darnley"), [IlyaLos](/profile/IlyaLos "International Master IlyaLos"), [_overrated_](/profile/_overrated_ "Master _overrated_"), [SergeyMelnikov](/profile/SergeyMelnikov "Master SergeyMelnikov"), [winger](/profile/winger "International Grandmaster winger"), [FieryPhoenix](/profile/FieryPhoenix "Master FieryPhoenix"), [infinitepro](/profile/infinitepro "Expert infinitepro"), [Sho](/profile/Sho "Expert Sho"), [GrandDaddy](/profile/GrandDaddy "Expert GrandDaddy"), [bfs.07](/profile/bfs.07 "Expert bfs.07"), [spookywooky](/profile/spookywooky "Expert spookywooky"). Also huge thanks to co-authors of the contest: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), [Neon](/profile/Neon "Candidate Master Neon"), [Roms](/profile/Roms "Master Roms"), [adedalic](/profile/adedalic "International Master adedalic"), [vovuh](/profile/vovuh "Master vovuh") and [awoo](/profile/awoo "Grandmaster awoo"). 4 5 I hope you enjoyed participating in the round! 6 7 Okay, now for the editorial itself: 8 9 [1346A - Color Revolution](/contest/1346/problem/A "Kotlin Heroes: Episode 4") 10 11 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [awoo](/profile/awoo "Grandmaster awoo") 12 13 **Tutorial** 14 15 Tutorial is loading... 16 17 **Solution (elizarov)** 18 19 ``` 20 fun main() { 21 repeat(readLine()!!.toInt()) { 22 val (n, k) = readLine()!!.split(" ").map { it.toInt() } 23 val n1 = n / (1 + k + k * k + k * k * k) 24 val n2 = n1 * k 25 val n3 = n2 * k 26 val n4 = n3 * k 27 println("$n1 $n2 $n3 $n4") 28 } 29 } 30 ``` 31 32 [1346B - Boot Camp](/contest/1346/problem/B "Kotlin Heroes: Episode 4") 33 34 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon") 35 36 **Tutorial** 37 38 Tutorial is loading... 39 40 **Solution (elizarov)** 41 42 ``` 43 fun main() { 44 repeat(readLine()!!.toInt()) { 45 val (n, k1, k2) = readLine()!!.split(" ").map { it.toInt() } 46 val s = readLine()!! 47 var m = 0 48 var prev = 0 49 for (c in s) { 50 if (c == '1') { 51 prev = minOf(k2 - prev, k1) 52 m += prev 53 } else { 54 prev = 0 55 } 56 } 57 println(m) 58 } 59 } 60 ``` 61 62 [1346C - Spring Cleaning](/contest/1346/problem/C "Kotlin Heroes: Episode 4") 63 64 Idea: [vovuh](/profile/vovuh "Master vovuh"), preparation: [vovuh](/profile/vovuh "Master vovuh") 65 66 **Tutorial** 67 68 Tutorial is loading... 69 70 **Solution (elizarov)** 71 72 ``` 73 fun main() { 74 repeat(readLine()!!.toInt()) { 75 val (n, k, x, y) = readLine()!!.split(" ").map { it.toInt() } 76 val a = readLine()!!.split(" ").map { it.toInt() }.sorted() 77 val maxSum = k * n.toLong() 78 var sum = 0L 79 var ans = 0 80 var ok = true 81 var i = 0 82 while (i < n && sum + a[i] <= maxSum) { 83 sum += a[i] 84 if (ok && a[i] > k) { 85 ok = false 86 ans = (n - i) * x // can simply drop the rest 87 } 88 i++ 89 } 90 ans = if (ok) (n - i) * x // drop the rest 91 else minOf(ans, (n - i) * x + y) // drop the rest & rearrange 92 println(ans) 93 } 94 } 95 ``` 96 97 [1346D - Constructing the Dungeon](/contest/1346/problem/D "Kotlin Heroes: Episode 4") 98 99 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), preparation: [Neon](/profile/Neon "Candidate Master Neon") 100 101 **Tutorial** 102 103 Tutorial is loading... 104 105 **Solution (elizarov)** 106 107 ``` 108 fun main() { 109 repeat(readLine()!!.toInt()) { 110 val (n, m) = readLine()!!.split(" ").map { it.toInt() } 111 val e = List(m) { 112 val (u, v, w) = readLine()!!.split(" ").map { it.toInt() } 113 Tun(u - 1, v - 1, w) 114 } 115 val a = solveDungeon(n, e) 116 if (a != null) { 117 println("YES") 118 println(a.joinToString(" ")) 119 } else { 120 println("NO") 121 } 122 } 123 } 124 125 private class Tun(val u: Int, val v: Int, val w: Int) 126 127 private fun solveDungeon(n: Int, e: List<Tun>): IntArray? { 128 val a = IntArray(n) 129 for (t in e.sortedByDescending { it.w }) { 130 if (a[t.u] == 0) a[t.u] = t.w 131 if (a[t.v] == 0) a[t.v] = t.w 132 if (t.w != minOf(a[t.u], a[t.v])) return null 133 } 134 return a 135 } 136 ``` 137 138 [1346E - Magic Tricks](/contest/1346/problem/E "Kotlin Heroes: Episode 4") 139 140 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon") 141 142 **Tutorial** 143 144 Tutorial is loading... 145 146 **Solution (elizarov)** 147 148 ``` 149 fun main() { 150 val (n, m, k) = readLine()!!.split(" ").map { it.toInt() } 151 val inf = Int.MAX_VALUE - 1 152 val s = IntArray(n) { inf } 153 s[k - 1] = 0 154 repeat(m) { 155 val (x, y) = readLine()!!.split(" ").map { it.toInt() - 1 } 156 val sx = s[x] 157 val sy = s[y] 158 s[x] = minOf(sx + 1, sy) 159 s[y] = minOf(sy + 1, sx) 160 } 161 println(s.joinToString(" ") { (if (it == inf) -1 else it).toString() }) 162 } 163 ``` 164 165 [1346F - Dune II: Battle For Arrakis](/contest/1346/problem/F "Kotlin Heroes: Episode 4") 166 167 Idea: [vovuh](/profile/vovuh "Master vovuh"), preparation: [vovuh](/profile/vovuh "Master vovuh") 168 169 **Tutorial** 170 171 Tutorial is loading... 172 173 **Solution (elizarov)** 174 175 ``` 176 import kotlin.math.* 177 178 fun main() { 179 val (n, m, q) = readLine()!!.split(" ").map { it.toInt() } 180 val a = Array(n) { readLine()!!.split(" ").map { it.toInt() }.toIntArray() } 181 val rs = LongArray(n) { i -> (0 until m).map { j -> a[i][j].toLong() }.sum() }.toDistSum() 182 val cs = LongArray(m) { j -> (0 until n).map { i -> a[i][j].toLong() }.sum() }.toDistSum() 183 fun ans() = rs.min()!! + cs.min()!! 184 print(ans()) 185 repeat(q) { 186 val (x1, y1, z) = readLine()!!.split(" ").map { it.toInt() } 187 val (x, y) = (x1 - 1) to (y1 - 1) 188 val d = (z - a[x][y]).toLong() 189 for (i in 0 until n) rs[i] += abs(x - i) * d 190 for (j in 0 until m) cs[j] += abs(y - j) * d 191 a[x][y] = z 192 print(" ${ans()}") 193 } 194 } 195 196 private fun LongArray.toDistSum(): LongArray { 197 val s = LongArray(size) 198 var su = 0L 199 var wsu = 0L 200 var sd = 0L 201 var wsd = 0L 202 for (i in 0 until size) { 203 sd += get(i) 204 wsd += (i + 1) * get(i) 205 } 206 for (i in 0 until size) { 207 wsd -= sd 208 sd -= get(i) 209 s[i] = wsu + wsd 210 su += get(i) 211 wsu += su 212 } 213 return s 214 } 215 ``` 216 217 [1346G - Two IP Cameras](/contest/1346/problem/G "Kotlin Heroes: Episode 4") 218 219 Idea: [adedalic](/profile/adedalic "International Master adedalic"), preparation: [adedalic](/profile/adedalic "International Master adedalic") 220 221 **Tutorial** 222 223 Tutorial is loading... 224 225 **Solution (elizarov)** 226 227 ``` 228 fun main() { 229 val (k, n) = readLine()!!.split(" ").map { it.toInt() } 230 val p = readLine()!!.split(" ").map { it.toInt() } 231 val x = readLine()!!.split(" ").map { it.toInt() } 232 val c = solveCams(n, p, x) 233 if (c == null) { 234 println("NO") 235 } else { 236 println("YES") 237 println("${c.s1} ${c.p1}") 238 println("${c.s2} ${c.p2}") 239 } 240 } 241 242 private class Cams(val s1: Int, val p1: Int, val s2: Int, val p2: Int) 243 244 private tailrec fun gcd(x: Int, y: Int): Int = if (y == 0) x else gcd(y, x % y) 245 246 private fun solveCams(n: Int, p: List<Int>, x: List<Int>): Cams? { 247 fun place2(s1: Int, p1: Int): Cams? { 248 val f = BooleanArray(n) { j -> (x[j] - s1) % p1 == 0 } 249 val i = f.indexOf(false) 250 if (i < 0) return Cams(s1, p1, s1, p1) 251 val s2 = x[i] 252 var j = i + 1 253 while (j < n && f[j]) j++ 254 if (j >= n) return Cams(s1, p1, s2, p[0]) 255 var p2m = x[j] - s2 256 while (++j < n) { 257 if (!f[j]) p2m = gcd(p2m, x[j] - s2) 258 } 259 for (p2 in p) if (p2m % p2 == 0) { 260 return Cams(s1, p1, s2, p2) 261 } 262 return null 263 } 264 fun tryPlace2(s1: Int, p1m: Int): Cams? { 265 for (p1 in p) if (p1m % p1 == 0) { 266 place2(s1, p1)?.let { return it } 267 } 268 return null 269 } 270 if (n == 2) return Cams(x[0], p[0], x[1], p[0]) 271 for (t1 in 1..2) { 272 tryPlace2(x[0], x[t1] - x[0])?.let { return it } 273 } 274 return tryPlace2(x[1], x[2] - x[1]) 275 } 276 ``` 277 278 [1346H - Game with Segments](/contest/1346/problem/H "Kotlin Heroes: Episode 4") 279 280 Idea: [Roms](/profile/Roms "Master Roms"), preparation: [Roms](/profile/Roms "Master Roms") 281 282 **Tutorial** 283 284 Tutorial is loading... 285 286 **Solution (tourist)** 287 288 ``` 289 import java.lang.AssertionError 290 291 private fun readLn() = readLine()!! // string line 292 private fun readInt() = readLn().toInt() // single int 293 private fun readLong() = readLn().toLong() // single long 294 private fun readDouble() = readLn().toDouble() // single double 295 private fun readStrings() = readLn().split(" ") // list of strings 296 private fun readInts() = readStrings().map { it.toInt() } // list of ints 297 private fun readLongs() = readStrings().map { it.toLong() } // list of longs 298 private fun readDoubles() = readStrings().map { it.toDouble() } // list of doubles 299 300 private fun myAssert(x: Boolean) { 301 if (!x) { 302 throw AssertionError() 303 } 304 } 305 306 fun main(args: Array<String>) { 307 var (tt, n) = readInts() 308 var lstart = IntArray(tt) 309 var rstart = IntArray(tt) 310 for (i in 0 until tt) { 311 var (x, y) = readInts() 312 lstart[i] = x 313 rstart[i] = y 314 } 315 var l = ArrayList<Int>() 316 var r = ArrayList<Int>() 317 for (i in 0 until n) { 318 var (x, y) = readInts() 319 l.add(x) 320 r.add(y) 321 } 322 var order = ArrayList<Int>() 323 for (i in 0 until n) { 324 order.add(i) 325 } 326 order.sortWith(compareBy({l[it] + r[it]}, {l[it]})) 327 val inf = 787788789 328 fun getDistance(L: Int, R: Int) : Int { 329 var low = 0 330 var high = n 331 while (low < high) { 332 var mid = (low + high) / 2 333 if (l[order[mid]] + r[order[mid]] < L + R || 334 (l[order[mid]] + r[order[mid]] == L + R && l[order[mid]] < L)) { 335 low = mid + 1 336 } else { 337 high = mid 338 } 339 } 340 if (low < n && l[order[low]] + r[order[low]] == L + R) { 341 return l[order[low]] - L 342 } 343 return inf 344 } 345 var res = IntArray(tt) {-1} 346 for (qq in 0 until tt) { 347 var L = lstart[qq] 348 var R = rstart[qq] 349 var a = getDistance(L, R - 2) + 1 350 var b = getDistance(L, R) 351 var c = getDistance(L + 2, R) + 1 352 res[qq] = maxOf(minOf(a, b), minOf(b, c)) 353 if (res[qq] >= inf) { 354 res[qq] = -1 355 } 356 } 357 println(res.joinToString(" ")) 358 } 359 ``` 360 361 [1346I - Pac-Man 2.0](/contest/1346/problem/I "Kotlin Heroes: Episode 4") 362 363 Idea: [Neon](/profile/Neon "Candidate Master Neon") and [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon") 364 365 **Tutorial** 366 367 Tutorial is loading... 368 369 **Solution (Ne0n25)** 370 371 ``` 372 import kotlin.math.abs 373 374 fun main() { 375 val INF = 1e9.toInt() 376 val INF64 = 1e18.toLong() 377 val LOG = 60 378 var (n, m, q, s) = readLine()!!.split(' ').map { it.toInt() } 379 s-- 380 val a = readLine()!!.split(' ').map { it.toInt() } 381 382 val summask = LongArray(1 shl n) { 0 } 383 for (mask in 0 until (1 shl n)) { 384 for (i in 0 until n) { 385 if ((mask and (1 shl i)) > 0) 386 summask[mask] += a[i].toLong() 387 } 388 } 389 390 val d = Array(n) { IntArray(n) { INF } } 391 for (i in 0 until m) { 392 val (x, y) = readLine()!!.split(' ').map { it.toInt() } 393 d[x - 1][y - 1] = 1 394 } 395 396 val C = readLine()!!.split(' ').map { it.toLong() } 397 398 for (k in 0 until n) { 399 for (i in 0 until n) { 400 for (j in 0 until n) 401 d[i][j] = minOf(d[i][j], d[i][k] + d[k][j]) 402 } 403 } 404 405 val dp = Array(n) { Array(n) { IntArray(1 shl n) { INF } } } 406 for (st in 0 until n) { 407 dp[st][st][1 shl st] = 0 408 409 for (mask in 0 until (1 shl n)) { 410 for (i in 0 until n) { 411 if ((mask and (1 shl i)) == 0) 412 continue 413 for (j in 0 until n) { 414 if ((mask and (1 shl j)) > 0) 415 continue 416 dp[st][j][mask or (1 shl j)] = 417 minOf(dp[st][j][mask or (1 shl j)], dp[st][i][mask] + d[i][j]) 418 } 419 } 420 } 421 } 422 423 val bst = Array(n) { LongArray(n * n) { 0 } } 424 for (i in 0 until n) { 425 for (mask in 0 until (1 shl n)) { 426 if ((mask and (1 shl i)) > 0) { 427 for (j in 0 until n) { 428 if (dp[i][j][mask] != INF) 429 bst[i][dp[i][j][mask]] = maxOf(bst[i][dp[i][j][mask]], summask[mask]) 430 } 431 } 432 } 433 } 434 435 val steps = Array(LOG) { Array(n) { LongArray(n) { INF64 } } } 436 for (i in 0 until n) { 437 for (j in 0 until n) 438 steps[0][i][j] = dp[i][j][(1 shl n) - 1].toLong() 439 } 440 441 for (t in 1 until LOG) { 442 for (i in 0 until n) { 443 for (j in 0 until n) { 444 for (k in 0 until n) 445 steps[t][i][j] = minOf(steps[t][i][j], steps[t - 1][i][k] + steps[t - 1][k][j]) 446 } 447 } 448 } 449 450 for (qr in 0 until q) { 451 val sum = summask[(1 shl n) - 1] 452 val need = C[qr] / sum 453 454 var cur = LongArray(n) { INF64 } 455 cur[s] = 0 456 457 for (t in 0 until LOG - 1) { 458 if ((need and (1L shl t)) > 0) { 459 val ncur = LongArray(n) { INF64 } 460 for (i in 0 until n) { 461 for (j in 0 until n) 462 ncur[i] = minOf(ncur[i], steps[t][j][i] + cur[j]) 463 } 464 cur = ncur 465 } 466 } 467 468 var ans = INF64 469 for(i in 0 until n) { 470 val lft = C[qr] % sum 471 for (j in 0 until n * n) { 472 if (bst[i][j] >= lft) 473 ans = minOf(ans, cur[i] + j); 474 } 475 } 476 477 println(ans) 478 } 479 } 480 ```