2011.md (15300B)
1 Source: https://codeforces.com/blog/entry/134624 2 3 This round was prepared by [Neon](/profile/Neon "Candidate Master Neon"), [adedalic](/profile/adedalic "International Master adedalic"), [awoo](/profile/awoo "Grandmaster awoo"), [shnirelman](/profile/shnirelman "International Grandmaster shnirelman") and me. 4 5 Huge thanks to all of the testers: [ashmelev](/profile/ashmelev "Grandmaster ashmelev"), [KIRIJIJI](/profile/KIRIJIJI "Master KIRIJIJI"), [PavelKunyavskiy](/profile/PavelKunyavskiy "Grandmaster PavelKunyavskiy"), [soup](/profile/soup "Expert soup") and [Fanarill](/profile/Fanarill "Expert Fanarill")! Your feedback helped us balance this contest (and find a very stupid overflow bug I'm too ashamed to mention). 6 7 Thanks for participation, we hope you enjoyed the contest! 8 9 [2011A - Problem Solving](/contest/2011/problem/A "Kotlin Heroes: Episode 11") 10 11 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest") 12 13 **Tutorial** 14 15 Tutorial is loading... 16 17 **Solution (Neon)** 18 19 ``` 20 fun main() = repeat(readln().toInt()) { 21 readln().toInt() 22 val a = readln().split(" ").map { it.toInt() } 23 println(if (a.dropLast(1).contains(a.last() - 1)) a.last() - 1 else "Ambiguous") 24 } 25 ``` 26 27 [2011B - Shuffle](/contest/2011/problem/B "Kotlin Heroes: Episode 11") 28 29 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest") 30 31 **Tutorial** 32 33 Tutorial is loading... 34 35 **Solution (Neon)** 36 37 ``` 38 fun main() = repeat(readln().toInt()) { 39 val n = readln().toInt() 40 println((listOf(1) + (n downTo 2)).joinToString(" ")) 41 } 42 ``` 43 44 [2011C - Split the Expression](/contest/2011/problem/C "Kotlin Heroes: Episode 11") 45 46 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest") 47 48 **Tutorial** 49 50 Tutorial is loading... 51 52 **Solution (Neon)** 53 54 ``` 55 fun main() = repeat(readln().toInt()) { 56 val a = readln().split("+") 57 val ans = a.foldIndexed(0L) { i, res, s -> 58 res + if (i == 0 || i == a.size - 1) 59 s.toLong() 60 else 61 (1 until s.length).maxOf { s.take(it).toLong() + s.drop(it).toLong() } 62 } 63 println(ans) 64 } 65 ``` 66 67 [2011D - Among Wolves](/contest/2011/problem/D "Kotlin Heroes: Episode 11") 68 69 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [adedalic](/profile/adedalic "International Master adedalic") 70 71 **Tutorial** 72 73 Tutorial is loading... 74 75 **Solution (adedalic)** 76 77 ``` 78 fun main() { 79 repeat(readln().toInt()) { 80 val (n, h, b) = readln().split(' ').map { it.toLong() } 81 val grid = Array(2) { readln() } 82 val sheepColumn = grid[0].indices.find { grid[0][it] == 'S' || grid[1][it] == 'S' }!! 83 val wolvesLeft = (0..1).sumOf { grid[it].take(sheepColumn).count { it == 'W' } } 84 val wolvesRight = (0..1).sumOf { grid[it].substring(sheepColumn).count { it == 'W' } } 85 86 val ans = minOf( 87 (wolvesLeft + wolvesRight) * h, 88 wolvesLeft * h + 2 * b, 89 wolvesRight * h + 2 * b, 90 3 * b 91 ) 92 println(ans) 93 } 94 } 95 ``` 96 97 [2011E - Rock-Paper-Scissors Bot](/contest/2011/problem/E "Kotlin Heroes: Episode 11") 98 99 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon") 100 101 **Tutorial** 102 103 Tutorial is loading... 104 105 **Solution (Neon)** 106 107 ``` 108 const val INF = 1e9.toInt() 109 const val vars = "RPS" 110 111 fun main() = repeat(readln().toInt()) { 112 val a = readln().map { vars.indexOf(it) } 113 114 fun calc(a : List<Int>) : Int { 115 if (a[0] != 0) return INF 116 val balance = a.zipWithNext().fold(0) { s, (x, y) -> 117 s + (if (x == y) 1 else 0) - (if ((x + 2) % 3 == y) 1 else 0) 118 } 119 return a.size + maxOf(balance, 0) 120 } 121 122 println(minOf( 123 calc(a), 124 calc(listOf(0) + a), 125 calc(listOf(0, 2) + a) 126 )) 127 } 128 ``` 129 130 [2011F - Good Subarray](/contest/2011/problem/F "Kotlin Heroes: Episode 11") 131 132 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon") 133 134 **Tutorial** 135 136 Tutorial is loading... 137 138 **Solution (Neon)** 139 140 ``` 141 fun main() = repeat(readln().toInt()) { 142 val n = readln().toInt() 143 val a = readln().split(" ").map { it.toInt() - 1 } 144 145 val prev = IntArray(n + 1) { -1 } 146 val pos = IntArray(n) { -1 } 147 148 for (i in 0 until n) { 149 for (j in a[i]-1..a[i]+1) { 150 if (0 <= j && j < n) { 151 prev[i] = maxOf(prev[i], pos[j]) 152 } 153 } 154 pos[a[i]] = i 155 } 156 157 val st = mutableListOf(n) 158 var ans = 0L 159 for (i in (n - 1) downTo 0) { 160 while (st.size > 0 && prev[st.last()] >= i) { 161 st.removeLast() 162 } 163 ans += st.last() - i 164 st.add(i) 165 } 166 167 println(ans) 168 } 169 ``` 170 171 [2011G - Removal of a Permutation](/contest/2011/problem/G "Kotlin Heroes: Episode 11") 172 173 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon") 174 175 **Tutorial** 176 177 Tutorial is loading... 178 179 **Solution (Neon)** 180 181 ``` 182 const val LOG = 19 183 184 fun main() = repeat(readln().toInt()) { 185 val n = readln().toInt() 186 val p = readln().split(" ").map { it.toInt() - 1 } 187 val ans = IntArray(n - 1) { n } 188 189 fun rec(step: Int, p: List<Int>) { 190 if (p.size == 1 || step == LOG) return 191 for (cur in listOf(p, p.reversed())) { 192 val (a, b) = cur.zipWithNext().partition { (x, y) -> x < y } 193 a.forEach { (x, _) -> ans[x] = minOf(ans[x], step) } 194 rec(step + 1, b.map { (x, _) -> x} + cur.last()) 195 } 196 } 197 198 rec(1, p) 199 200 println(ans.joinToString(" ")) 201 } 202 ``` 203 204 [2011H - Strange Matrix](/contest/2011/problem/H "Kotlin Heroes: Episode 11") 205 206 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon") 207 208 **Tutorial** 209 210 Tutorial is loading... 211 212 **Solution (Neon)** 213 214 ``` 215 const val INF = 1e9.toInt() 216 const val B = 5 217 218 fun main() = repeat(readln().toInt()) { 219 val (n, m, k) = readInts() 220 val a = Array(n) { readInts() } 221 222 var ans = 0 223 224 for (bit in 0 until B) { 225 val g = Array(n) { ArrayList<Pair<Int, Int>>() } 226 for (i in 0 until n) { 227 for (j in 0 until i) { 228 val cnt = IntArray(4) { 0 } 229 for (x in 0 until m) { 230 val f = (a[i][x] shr bit) and 1 231 val s = (a[j][x] shr bit) and 1 232 ++cnt[f * 2 + s]; 233 } 234 val f1 = (cnt[0] < k && cnt[3] < k) 235 val f2 = (cnt[1] < k && cnt[2] < k) 236 if (f1 != f2) { 237 g[i].add(j to if (f2) 1 else 0) 238 g[j].add(i to if (f2) 1 else 0) 239 } else if (!f1) { 240 return@repeat println("-1") 241 } 242 } 243 } 244 245 val color = IntArray(n) { -1 } 246 val cnt = IntArray(2) { 0 } 247 var ok = true 248 249 fun dfs(v: Int, c: Int) { 250 color[v] = c 251 ++cnt[c] 252 for ((u, d) in g[v]) { 253 if (color[u] != -1) { 254 if ((c xor d) != color[u]) { 255 ok = false 256 } 257 } else { 258 dfs(u, c xor d) 259 } 260 } 261 } 262 263 for (v in 0 until n) { 264 if (color[v] != -1) continue 265 cnt.fill(0) 266 dfs(v, 0) 267 if (!ok) return@repeat println("-1") 268 ans += cnt.min() shl bit 269 } 270 } 271 272 println(maxOf(0, ans)) 273 } 274 275 fun readInts() = readln().split(" ").map { it.toInt() } 276 ``` 277 278 [2011I - Stack and Queue](/contest/2011/problem/I "Kotlin Heroes: Episode 11") 279 280 Idea: [shnirelman](/profile/shnirelman "International Grandmaster shnirelman"), preparation: [awoo](/profile/awoo "Grandmaster awoo") 281 282 **Tutorial** 283 284 Tutorial is loading... 285 286 **Solution (awoo)** 287 288 ``` 289 class Query(val t: Int, val x: Int) 290 291 class BIT(val mx: Int) { 292 val f = LongArray(mx) { 0L } 293 294 fun upd_pr(pos: Int, x: Int) { 295 var i = pos 296 while (i < mx) { 297 f[i] = f[i] + x 298 i = i or (i + 1) 299 } 300 } 301 302 fun get_pr(pos: Int) : Long { 303 var res = 0L 304 var i = pos 305 while (i >= 0) { 306 res += f[i] 307 i = (i and (i + 1)) - 1 308 } 309 return res 310 } 311 312 fun upd_su(pos: Int, x: Int) { 313 var i = pos 314 while (i >= 0) { 315 f[i] = f[i] + x 316 i = (i and (i + 1)) - 1 317 } 318 } 319 320 fun get_su(pos: Int) : Long { 321 var res = 0L 322 var i = pos 323 while (i < mx) { 324 res += f[i] 325 i = i or (i + 1) 326 } 327 return res 328 } 329 } 330 331 fun main() { 332 val n = readLine()!!.toInt() 333 val a = readLine()!!.split(" ").map { it.toInt() } 334 val q = Array(n) { Query(-1, -1) } 335 for (i in 0 until n) { 336 val (t, x) = readLine()!!.split(" ").map { it.toInt() } 337 q[i] = Query(t, x - 1) 338 } 339 340 val d = IntArray(n + 1) { 0 } 341 342 fun apply(coef: Int) { 343 var qs = Array<ArrayList<Pair<Int, Int>>>(n + 1) { ArrayList<Pair<Int, Int>>() } 344 for (i in 0 until n) { 345 qs[0].add(Pair(i, n + 1)) 346 } 347 348 var len = n + 1 349 while (true) { 350 val posq = IntArray(n) { -1 } 351 val poss = IntArray(n) { -1 } 352 val sv = IntArray(n) { -1 } 353 val fq = BIT(n) 354 val fs = BIT(n) 355 356 var cntq = 0 357 var cnts = 0 358 val nqs = Array<ArrayList<Pair<Int, Int>>>(n + 1) { ArrayList<Pair<Int, Int>>() } 359 var j = 0 360 361 var last = true 362 for (l in 0 until n + 1) { 363 for (it in qs[l]) { 364 val i = it.first 365 val r = it.second 366 if (r - l == 1) { 367 d[l] += coef 368 continue 369 } 370 371 last = false 372 val m = (l + r) / 2 373 while (j < m) { 374 val x = q[j].x 375 if (q[j].t == 1) { 376 posq[x] = cntq 377 sv[x] = cnts 378 cntq += 1 379 cnts += 1 380 fq.upd_pr(posq[x], a[x]) 381 } 382 else if (q[j].t == 2){ 383 poss[x] = cnts 384 cnts += 1 385 fs.upd_su(poss[x], a[x]) 386 } 387 else{ 388 fq.upd_pr(posq[x], -a[x]) 389 posq[x] = -1 390 poss[x] = sv[x] 391 fs.upd_su(poss[x], a[x]) 392 } 393 j += 1 394 } 395 assert(j == m) 396 if (poss[i] == -1 || posq[i] == -1) { 397 nqs[m].add(Pair(i, r)) 398 continue 399 } 400 val tq = fq.get_pr(posq[i] - 1) 401 val ts = fs.get_su(poss[i] + 1) 402 var ok = true 403 if (coef == 1) { 404 ok = tq - a[i] >= ts 405 } 406 else { 407 ok = tq + a[i] > ts 408 } 409 if (ok) { 410 nqs[m].add(Pair(i, r)) 411 } 412 else { 413 nqs[l].add(Pair(i, m)) 414 } 415 } 416 } 417 qs = nqs 418 if (last) { 419 break 420 } 421 } 422 println("") 423 } 424 425 apply(1) 426 apply(-1) 427 for (i in 0 until n) { 428 d[i + 1] += d[i] 429 } 430 val res = d.map { x -> (if (x == 0) "Yes" else "No") } 431 println(res.take(res.size - 1).joinToString(separator = "\n")) 432 } 433 ``` 434 435 **Solution 2 (awoo)** 436 437 ``` 438 class Query(val t: Int, val x: Int) 439 440 class BIT(val mx: Int) { 441 val f = LongArray(mx) { 0L } 442 443 fun upd_pr(pos: Int, x: Int) { 444 var i = pos 445 while (i < mx) { 446 f[i] = f[i] + x 447 i = i or (i + 1) 448 } 449 } 450 451 fun get_pr(pos: Int) : Long { 452 var res = 0L 453 var i = pos 454 while (i >= 0) { 455 res += f[i] 456 i = (i and (i + 1)) - 1 457 } 458 return res 459 } 460 461 fun upd_su(pos: Int, x: Int) { 462 var i = pos 463 while (i >= 0) { 464 f[i] = f[i] + x 465 i = (i and (i + 1)) - 1 466 } 467 } 468 469 fun get_su(pos: Int) : Long { 470 var res = 0L 471 var i = pos 472 while (i < mx) { 473 res += f[i] 474 i = i or (i + 1) 475 } 476 return res 477 } 478 } 479 480 fun main() { 481 val n = readLine()!!.toInt() 482 val a = readLine()!!.split(" ").map { it.toInt() } 483 val q = Array(n) { Query(-1, -1) } 484 for (i in 0 until n) { 485 val (t, x) = readLine()!!.split(" ").map { it.toInt() } 486 q[i] = Query(t, x - 1) 487 } 488 val fq = BIT(n) 489 val fs = BIT(n) 490 491 val d = IntArray(n + 1) { 0 } 492 val posq = IntArray(n) { -1 } 493 val poss = IntArray(n) { -1 } 494 val sv = IntArray(n) { -1 } 495 var cntq = 0 496 var cnts = 0 497 498 fun calc(l: Int, r: Int, coef: Int, all: ArrayList<Int>) { 499 if (l == r - 1) { 500 d[l] += all.size * coef 501 return 502 } 503 504 val m = (l + r) / 2 505 506 val who_chg = ArrayList<Int>() 507 val idx_chg = ArrayList<Int>() 508 val val_chg = ArrayList<Int>() 509 val chq = ArrayList<Pair<Int, Int>>() 510 val chs = ArrayList<Pair<Int, Int>>() 511 512 for (i in l until m) { 513 val x = q[i].x 514 if (q[i].t == 1) { 515 who_chg.add(0) 516 idx_chg.add(x) 517 val_chg.add(posq[x]) 518 posq[x] = cntq 519 who_chg.add(2) 520 idx_chg.add(x) 521 val_chg.add(sv[x]) 522 sv[x] = cnts 523 cntq += 1 524 cnts += 1 525 chq.add(Pair(posq[x], -a[x])) 526 fq.upd_pr(posq[x], a[x]) 527 } 528 else if (q[i].t == 2){ 529 who_chg.add(1) 530 idx_chg.add(x) 531 val_chg.add(poss[x]) 532 poss[x] = cnts 533 cnts += 1 534 chs.add(Pair(poss[x], -a[x])) 535 fs.upd_su(poss[x], a[x]) 536 } 537 else{ 538 chq.add(Pair(posq[x], a[x])) 539 fq.upd_pr(posq[x], -a[x]) 540 who_chg.add(0) 541 idx_chg.add(x) 542 val_chg.add(posq[x]) 543 posq[x] = -1 544 who_chg.add(1) 545 idx_chg.add(x) 546 val_chg.add(poss[x]) 547 poss[x] = sv[x] 548 who_chg.add(2) 549 idx_chg.add(x) 550 val_chg.add(sv[x]) 551 sv[x] = -1 552 chs.add(Pair(poss[x], -a[x])) 553 fs.upd_su(poss[x], a[x]) 554 } 555 } 556 557 val tol = ArrayList<Int>() 558 val tor = ArrayList<Int>() 559 560 for (x in all) { 561 if (poss[x] == -1 || posq[x] == -1) { 562 tor.add(x) 563 continue 564 } 565 val tq = fq.get_pr(posq[x] - 1) 566 val ts = fs.get_su(poss[x] + 1) 567 var ok = true 568 if (coef == 1) { 569 ok = tq - a[x] >= ts 570 } 571 else { 572 ok = tq + a[x] > ts 573 } 574 if (ok) { 575 tor.add(x) 576 } 577 else { 578 tol.add(x) 579 } 580 } 581 582 calc(m, r, coef, tor) 583 584 who_chg.reverse() 585 idx_chg.reverse() 586 val_chg.reverse() 587 588 for (i in 0 until who_chg.size) { 589 if (who_chg[i] == 0) { 590 posq[idx_chg[i]] = val_chg[i] 591 } 592 else if (who_chg[i] == 1) { 593 poss[idx_chg[i]] = val_chg[i] 594 } 595 else { 596 sv[idx_chg[i]] = val_chg[i] 597 } 598 } 599 600 for (i in l until m) { 601 if (q[i].t == 1) { 602 cntq -= 1 603 cnts -= 1 604 } 605 else if (q[i].t == 2){ 606 cnts -= 1 607 } 608 } 609 610 for (it in chq) { 611 fq.upd_pr(it.first, it.second) 612 } 613 for (it in chs) { 614 fs.upd_su(it.first, it.second) 615 } 616 617 calc(l, m, coef, tol) 618 } 619 620 val all = ArrayList<Int>() 621 for (i in 0 until n) { 622 all.add(i) 623 } 624 calc(0, n + 1, 1, all) 625 calc(0, n + 1, -1, all) 626 for (i in 0 until n) { 627 d[i + 1] += d[i] 628 } 629 val res = d.map { x -> (if (x == 0) "Yes" else "No") } 630 println(res.take(res.size - 1).joinToString(separator = "\n")) 631 } 632 ```