2141.md (26783B)
1 Source: https://codeforces.com/blog/entry/146347 2 3 I hope you liked the problems! Thank you for participation. I am sorry that the difference between H and I turned out to be that big, I didn't expect that so many people would solve H. 4 5 The contest was prepared by me, [Neon](/profile/Neon "Candidate Master Neon"), [adedalic](/profile/adedalic "International Master adedalic"), [FelixArg](/profile/FelixArg "Master FelixArg") and [Roms](/profile/Roms "Master Roms"). I would like to express my gratitude to the testers who helped us improve the contest: [pashka](/profile/pashka "International Grandmaster pashka"), [shnirelman](/profile/shnirelman "International Grandmaster shnirelman") and [awoo](/profile/awoo "Grandmaster awoo"). 6 7 See you in the next episode of Kotlin Heroes... sometime in the future (probably near the end of 2025). 8 9 [2141A - Furniture Store](/contest/2141/problem/A "Kotlin Heroes: Episode 13") 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 (Neon)** 18 19 ``` 20 fun main() = repeat(readln().toInt()) { 21 val n = readln().toInt() 22 val a = readln().split(" ").map { it.toInt() } 23 val p = a.runningReduce { x, y -> minOf(x, y) } 24 val ans = (1..n).filter { i -> a[i - 1] != p[i - 1] } 25 println(ans.size) 26 println(ans.joinToString(" ")) 27 } 28 ``` 29 30 [2141B - Games](/contest/2141/problem/B "Kotlin Heroes: Episode 13") 31 32 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon") 33 34 **Tutorial** 35 36 Tutorial is loading... 37 38 **Solution (Neon)** 39 40 ``` 41 fun main() = repeat(readln().toInt()) { 42 val (n, m) = readln().split(" ").map { it.toInt() } 43 val a = readln().split(" ").map { it.toInt() } 44 val b = readln().split(" ").map { it.toInt() } 45 val k = a.intersect(b).size 46 println(2 * minOf(n - k, m - k) + if (n > m) 2 else 1) 47 } 48 ``` 49 50 [2141C - Minimum on Subarrays](/contest/2141/problem/C "Kotlin Heroes: Episode 13") 51 52 Idea: [FelixArg](/profile/FelixArg "Master FelixArg"), preparation: [FelixArg](/profile/FelixArg "Master FelixArg") 53 54 **Tutorial** 55 56 Tutorial is loading... 57 58 **Solution (pashka)** 59 60 ``` 61 @file:Suppress("CanBeVal") 62 63 import java.io.BufferedReader 64 import java.io.InputStreamReader 65 import java.io.OutputStreamWriter 66 import java.io.PrintWriter 67 import java.util.* 68 import kotlin.math.max 69 import kotlin.math.min 70 71 private fun solveTest() { 72 val n = readInt() 73 val res = emptyList<String>().toMutableList() 74 for (i in 0..n - 1) { 75 if (i % 2 == 0) { 76 for (j in i..n - 1) { 77 res.add("pushfront a[" + j + "]") 78 res.add("min") 79 } 80 res.add("popback") 81 } else { 82 for (j in i..n - 1) { 83 res.add("min") 84 res.add("popfront") 85 } 86 } 87 } 88 println(res.size) 89 for (s in res) { 90 println(s) 91 } 92 } 93 94 private fun solve() { 95 // repeat(readInt()) { 96 solveTest() 97 // } 98 } 99 100 // TEMPLATE 101 fun main(args: Array<String>) { 102 reader = BufferedReader(InputStreamReader(System.`in`)) 103 out = PrintWriter(OutputStreamWriter(System.out)) 104 solve() 105 out.close() 106 } 107 108 private lateinit var out: PrintWriter 109 private lateinit var reader: BufferedReader 110 private var tokenizer: StringTokenizer? = null 111 private fun read(): String { 112 while (tokenizer == null || !tokenizer!!.hasMoreTokens()) { 113 tokenizer = StringTokenizer(readLn()) 114 } 115 return tokenizer!!.nextToken() 116 } 117 118 private fun readInt() = read().toInt() 119 private fun readLong() = read().toLong() 120 private fun readLn() = reader.readLine()!! 121 private fun readInts() = readLn().split(" ").map { it.toInt() } 122 private fun readInts(sz: Int) = Array(sz) { readInt() } 123 private fun readLongs() = readLn().split(" ").map { it.toLong() } 124 private fun readLongs(sz: Int) = Array(sz) { readLong() } 125 private fun print(b: Boolean) = out.print(b) 126 private fun print(i: Int) = out.print(i) 127 private fun print(d: Double) = out.print(d) 128 private fun print(l: Long) = out.print(l) 129 private fun print(s: String) = out.print(s) 130 private fun print(message: Any?) = out.print(message) 131 private fun print(a: Array<Int>) = a.forEach { print("$it ") } 132 private fun <T> print(a: Array<out T>) = a.forEach { print("$it ") } 133 private fun <T> print(a: Collection<T>) = a.forEach { print("$it ") } 134 private fun println(b: Boolean) = out.println(b) 135 private fun println(i: Int) = out.println(i) 136 private fun println(d: Double) = out.println(d) 137 private fun println(l: Long) = out.println(l) 138 private fun println(s: String) = out.println(s) 139 private fun println() = out.println() 140 private fun println(message: Any?) = out.println(message) 141 private fun <T> println(a: Array<out T>) { 142 a.forEach { print("$it ") } 143 println() 144 } 145 146 private fun println(a: IntArray) { 147 a.forEach { print("$it ") } 148 println() 149 } 150 151 private fun println(a: LongArray) { 152 a.forEach { print("$it ") } 153 println() 154 } 155 156 private fun <T> println(a: Collection<T>) { 157 a.forEach { print("$it ") } 158 println() 159 } 160 161 private fun intarr(sz: Int, v: Int = 0) = IntArray(sz) { v } 162 private fun longarr(sz: Int, v: Long = 0) = LongArray(sz) { v } 163 private fun intarr2d(n: Int, m: Int, v: Int = 0) = Array(n) { intarr(m, v) } 164 private fun longarr2d(n: Int, m: Int, v: Long = 0) = Array(n) { longarr(m, v) } 165 private fun <T> init(vararg elements: T) = elements 166 private fun VI(n: Int = 0, init: Int = 0) = MutableList(n) { init } 167 private fun VVI(n: Int = 0, m: Int = 0, init: Int = 0) = MutableList(n) { VI(m, init) } 168 private fun <T1 : Comparable<T1>, T2 : Comparable<T2>> pairCmp(): Comparator<Pair<T1, T2>> { 169 return Comparator { a, b -> 170 val res = a.first.compareTo(b.first) 171 if (res == 0) a.second.compareTo(b.second) else res 172 } 173 } 174 ``` 175 176 [2141D - Avoid Minimums](/contest/2141/problem/D "Kotlin Heroes: Episode 13") 177 178 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [adedalic](/profile/adedalic "International Master adedalic") 179 180 **Tutorial** 181 182 Tutorial is loading... 183 184 **Solution (adedalic)** 185 186 ``` 187 fun main() { 188 repeat(readln().toInt()) { 189 val (n, k) = readln().split(' ').map { it.toLong() } 190 val a = readln().split(' ').map { it.toLong() } 191 // n * resVal - a.sum() <= k 192 val resVal = (k + a.sum()) / n 193 if (resVal < a.maxOrNull()!!) { 194 println(-1) 195 return@repeat 196 } 197 val minEl = a.minOrNull()!! 198 var ans = a.sumOf { resVal - it } - (resVal - minEl) 199 if (minEl < resVal) 200 ans -= a.count { it == minEl } - 1 201 println(ans) 202 } 203 } 204 ``` 205 206 [2141E - Perfect Cut](/contest/2141/problem/E "Kotlin Heroes: Episode 13") 207 208 Idea: [FelixArg](/profile/FelixArg "Master FelixArg"), preparation: [Neon](/profile/Neon "Candidate Master Neon") 209 210 **Tutorial** 211 212 Tutorial is loading... 213 214 **Solution (Neon)** 215 216 ``` 217 const val MOD = 998244353; 218 219 fun main() = repeat(readln().toInt()) { 220 val s = readln() 221 var pw = 1 222 repeat(s.drop(1).count { it == '?' }) { 223 pw = pw * 2 % MOD 224 } 225 var ans = 0 226 if (s[0] == '1' || s[0] == '?') { 227 ans = (ans + pw) % MOD 228 } 229 if (s[0] == '0' || s[0] == '?') { 230 val x = if (s.indexOf('0', 1) == -1) 1 else 0 231 ans = (ans + pw - x) % MOD 232 } 233 println(ans) 234 } 235 ``` 236 237 [2141F - Array Reduction](/contest/2141/problem/F "Kotlin Heroes: Episode 13") 238 239 Idea: [Roms](/profile/Roms "Master Roms"), preparation: [Roms](/profile/Roms "Master Roms") 240 241 **Tutorial** 242 243 Tutorial is loading... 244 245 **Solution (pashka)** 246 247 ``` 248 @file:Suppress("CanBeVal") 249 250 import java.io.BufferedReader 251 import java.io.InputStreamReader 252 import java.io.OutputStreamWriter 253 import java.io.PrintWriter 254 import java.util.* 255 import kotlin.math.max 256 import kotlin.math.min 257 258 private fun solveTest() { 259 val n = readInt() 260 val a = readInts(n) 261 val c = intarr(n) 262 for (x in a) { 263 c[x - 1]++ 264 } 265 val res = intarr(n, Int.MAX_VALUE) 266 c.sort() 267 var j = 0 268 for (k in 0..n) { 269 while (j < n && c[j] <= k) j++ 270 var s = 0 271 for (i in j..n) { 272 val d = k + (n - i) 273 if (s < n) 274 res[s] = min(res[s], d) 275 if (i < n) s += (c[i] - k) 276 } 277 } 278 for (i in 1 .. n - 1) { 279 res[i] = min(res[i], res[i - 1]) 280 } 281 println(res) 282 } 283 284 private fun solve() { 285 repeat(readInt()) { 286 solveTest() 287 } 288 } 289 290 // TEMPLATE 291 fun main(args: Array<String>) { 292 reader = BufferedReader(InputStreamReader(System.`in`)) 293 out = PrintWriter(OutputStreamWriter(System.out)) 294 solve() 295 out.close() 296 } 297 298 private lateinit var out: PrintWriter 299 private lateinit var reader: BufferedReader 300 private var tokenizer: StringTokenizer? = null 301 private fun read(): String { 302 while (tokenizer == null || !tokenizer!!.hasMoreTokens()) { 303 tokenizer = StringTokenizer(readLn()) 304 } 305 return tokenizer!!.nextToken() 306 } 307 308 private fun readInt() = read().toInt() 309 private fun readLong() = read().toLong() 310 private fun readLn() = reader.readLine()!! 311 private fun readInts() = readLn().split(" ").map { it.toInt() } 312 private fun readInts(sz: Int) = Array(sz) { readInt() } 313 private fun readLongs() = readLn().split(" ").map { it.toLong() } 314 private fun readLongs(sz: Int) = Array(sz) { readLong() } 315 private fun print(b: Boolean) = out.print(b) 316 private fun print(i: Int) = out.print(i) 317 private fun print(d: Double) = out.print(d) 318 private fun print(l: Long) = out.print(l) 319 private fun print(s: String) = out.print(s) 320 private fun print(message: Any?) = out.print(message) 321 private fun print(a: Array<Int>) = a.forEach { print("$it ") } 322 private fun <T> print(a: Array<out T>) = a.forEach { print("$it ") } 323 private fun <T> print(a: Collection<T>) = a.forEach { print("$it ") } 324 private fun println(b: Boolean) = out.println(b) 325 private fun println(i: Int) = out.println(i) 326 private fun println(d: Double) = out.println(d) 327 private fun println(l: Long) = out.println(l) 328 private fun println(s: String) = out.println(s) 329 private fun println() = out.println() 330 private fun println(message: Any?) = out.println(message) 331 private fun <T> println(a: Array<out T>) { 332 a.forEach { print("$it ") } 333 println() 334 } 335 336 private fun println(a: IntArray) { 337 a.forEach { print("$it ") } 338 println() 339 } 340 341 private fun println(a: LongArray) { 342 a.forEach { print("$it ") } 343 println() 344 } 345 346 private fun <T> println(a: Collection<T>) { 347 a.forEach { print("$it ") } 348 println() 349 } 350 351 private fun intarr(sz: Int, v: Int = 0) = IntArray(sz) { v } 352 private fun longarr(sz: Int, v: Long = 0) = LongArray(sz) { v } 353 private fun intarr2d(n: Int, m: Int, v: Int = 0) = Array(n) { intarr(m, v) } 354 private fun longarr2d(n: Int, m: Int, v: Long = 0) = Array(n) { longarr(m, v) } 355 private fun <T> init(vararg elements: T) = elements 356 private fun VI(n: Int = 0, init: Int = 0) = MutableList(n) { init } 357 private fun VVI(n: Int = 0, m: Int = 0, init: Int = 0) = MutableList(n) { VI(m, init) } 358 private fun <T1 : Comparable<T1>, T2 : Comparable<T2>> pairCmp(): Comparator<Pair<T1, T2>> { 359 return Comparator { a, b -> 360 val res = a.first.compareTo(b.first) 361 if (res == 0) a.second.compareTo(b.second) else res 362 } 363 } 364 ``` 365 366 [2141G - Good Robot Paths](/contest/2141/problem/G "Kotlin Heroes: Episode 13") 367 368 Idea: [FelixArg](/profile/FelixArg "Master FelixArg"), preparation: [FelixArg](/profile/FelixArg "Master FelixArg") 369 370 **Tutorial** 371 372 Tutorial is loading... 373 374 **Solution (pashka)** 375 376 ``` 377 @file:Suppress("CanBeVal") 378 379 import java.io.BufferedReader 380 import java.io.InputStreamReader 381 import java.io.OutputStreamWriter 382 import java.io.PrintWriter 383 import java.util.* 384 import kotlin.collections.HashMap 385 import kotlin.math.max 386 import kotlin.math.min 387 388 private fun solveTest() { 389 val n = readInt() 390 val p = TreeMap<Int, MutableList<Int>>() 391 repeat(n) { 392 val x = readInt() 393 val y = readInt() 394 if (!p.containsKey(y)) { 395 p[y] = mutableListOf() 396 } 397 p[y]!!.add(x) 398 } 399 var lastY = Int.MIN_VALUE 400 var lastD = mutableMapOf<Int, Int>() 401 var res = 0L 402 for (y in p.keys) { 403 if (y != lastY + 1) { 404 lastD.clear() 405 } 406 var d = mutableMapOf<Int, Int>() 407 408 val xx = p[y]!! 409 xx.sort() 410 411 var lastX = Int.MIN_VALUE 412 val st = mutableListOf<Pair<Int, Int>>() 413 var sum1 = 0L 414 var sum2 = 0L 415 for (x in xx) { 416 val dd = lastD.getOrDefault(x, 0) + 1 417 d[x] = dd 418 419 if (x != lastX + 1) { 420 st.clear() 421 sum1 = 0 422 sum2 = 0 423 } 424 425 var c = 1 426 while (st.isNotEmpty() && st.last().first > dd) { 427 c += st.last().second 428 sum1 -= st.last().first * st.last().second 429 st.removeLast() 430 } 431 sum1 += c * dd 432 st.add(dd to c) 433 sum2++ 434 435 res += (sum1 - sum2 - dd + 1) * 4 436 res += (sum2 - 1) * 2 437 res += (dd - 1) * 2 438 // println("" + y + " " + x + " " + dd + " " + sum1 + " " + sum2 + " " + res) 439 lastX = x 440 } 441 442 lastY = y 443 lastD = d 444 } 445 println(res) 446 } 447 448 private fun solve() { 449 repeat(readInt()) { 450 solveTest() 451 } 452 } 453 454 // TEMPLATE 455 fun main(args: Array<String>) { 456 reader = BufferedReader(InputStreamReader(System.`in`)) 457 out = PrintWriter(OutputStreamWriter(System.out)) 458 solve() 459 out.close() 460 } 461 462 private lateinit var out: PrintWriter 463 private lateinit var reader: BufferedReader 464 private var tokenizer: StringTokenizer? = null 465 private fun read(): String { 466 while (tokenizer == null || !tokenizer!!.hasMoreTokens()) { 467 tokenizer = StringTokenizer(readLn()) 468 } 469 return tokenizer!!.nextToken() 470 } 471 472 private fun readInt() = read().toInt() 473 private fun readLong() = read().toLong() 474 private fun readLn() = reader.readLine()!! 475 private fun readInts() = readLn().split(" ").map { it.toInt() } 476 private fun readInts(sz: Int) = Array(sz) { readInt() } 477 private fun readLongs() = readLn().split(" ").map { it.toLong() } 478 private fun readLongs(sz: Int) = Array(sz) { readLong() } 479 private fun print(b: Boolean) = out.print(b) 480 private fun print(i: Int) = out.print(i) 481 private fun print(d: Double) = out.print(d) 482 private fun print(l: Long) = out.print(l) 483 private fun print(s: String) = out.print(s) 484 private fun print(message: Any?) = out.print(message) 485 private fun print(a: Array<Int>) = a.forEach { print("$it ") } 486 private fun <T> print(a: Array<out T>) = a.forEach { print("$it ") } 487 private fun <T> print(a: Collection<T>) = a.forEach { print("$it ") } 488 private fun println(b: Boolean) = out.println(b) 489 private fun println(i: Int) = out.println(i) 490 private fun println(d: Double) = out.println(d) 491 private fun println(l: Long) = out.println(l) 492 private fun println(s: String) = out.println(s) 493 private fun println() = out.println() 494 private fun println(message: Any?) = out.println(message) 495 private fun <T> println(a: Array<out T>) { 496 a.forEach { print("$it ") } 497 println() 498 } 499 500 private fun println(a: IntArray) { 501 a.forEach { print("$it ") } 502 println() 503 } 504 505 private fun println(a: LongArray) { 506 a.forEach { print("$it ") } 507 println() 508 } 509 510 private fun <T> println(a: Collection<T>) { 511 a.forEach { print("$it ") } 512 println() 513 } 514 515 private fun intarr(sz: Int, v: Int = 0) = IntArray(sz) { v } 516 private fun longarr(sz: Int, v: Long = 0) = LongArray(sz) { v } 517 private fun intarr2d(n: Int, m: Int, v: Int = 0) = Array(n) { intarr(m, v) } 518 private fun longarr2d(n: Int, m: Int, v: Long = 0) = Array(n) { longarr(m, v) } 519 private fun <T> init(vararg elements: T) = elements 520 private fun VI(n: Int = 0, init: Int = 0) = MutableList(n) { init } 521 private fun VVI(n: Int = 0, m: Int = 0, init: Int = 0) = MutableList(n) { VI(m, init) } 522 private fun <T1 : Comparable<T1>, T2 : Comparable<T2>> pairCmp(): Comparator<Pair<T1, T2>> { 523 return Comparator { a, b -> 524 val res = a.first.compareTo(b.first) 525 if (res == 0) a.second.compareTo(b.second) else res 526 } 527 } 528 ``` 529 530 [2141H - Merging Vertices in a Graph](/contest/2141/problem/H "Kotlin Heroes: Episode 13") 531 532 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest") 533 534 **Tutorial** 535 536 Tutorial is loading... 537 538 **Solution (pashka)** 539 540 ``` 541 @file:Suppress("CanBeVal") 542 543 import java.io.BufferedReader 544 import java.io.InputStreamReader 545 import java.io.OutputStreamWriter 546 import java.io.PrintWriter 547 import java.util.* 548 import kotlin.collections.HashMap 549 import kotlin.math.max 550 import kotlin.math.min 551 552 private fun solveTest() { 553 val n = readInt() 554 val m = readInt() 555 val g = Array(n) { mutableListOf<Int>() } 556 repeat(m) { 557 val x = readInt() - 1 558 val y = readInt() - 1 559 g[x].add(y) 560 g[y].add(x) 561 } 562 val z = intarr(n, 0) 563 var a = (0..n - 1).toMutableSet() 564 var res = Int.MAX_VALUE 565 566 while (!a.isEmpty()) { 567 var v = a.iterator().next() 568 a.remove(v) 569 z[v] = 1 570 var s = mutableSetOf<Int>() 571 for (x in g[v]) { 572 if (z[x] == 0) s.add(x) 573 } 574 var k = 0 575 while (true) { 576 var ok = false 577 for (x in a) { 578 if (!s.contains(x) && z[x] == 0) { 579 z[x] = 1 580 a.remove(x) 581 var ss = mutableSetOf<Int>() 582 for (y in g[x]) { 583 if (z[y] == 0 && s.contains(y)) { 584 ss.add(y) 585 } 586 } 587 ok = true 588 s = ss 589 k++ 590 break 591 } 592 } 593 if (!ok) { 594 res = min(res, k) 595 break 596 } 597 } 598 } 599 600 if (res == 0) { 601 println("" + res + " " + 0) 602 } else { 603 println("" + res + " " + (n - 1)) 604 } 605 } 606 607 private fun solve() { 608 // repeat(readInt()) { 609 solveTest() 610 // } 611 } 612 613 // TEMPLATE 614 fun main(args: Array<String>) { 615 reader = BufferedReader(InputStreamReader(System.`in`)) 616 out = PrintWriter(OutputStreamWriter(System.out)) 617 solve() 618 out.close() 619 } 620 621 private lateinit var out: PrintWriter 622 private lateinit var reader: BufferedReader 623 private var tokenizer: StringTokenizer? = null 624 private fun read(): String { 625 while (tokenizer == null || !tokenizer!!.hasMoreTokens()) { 626 tokenizer = StringTokenizer(readLn()) 627 } 628 return tokenizer!!.nextToken() 629 } 630 631 private fun readInt() = read().toInt() 632 private fun readLong() = read().toLong() 633 private fun readLn() = reader.readLine()!! 634 private fun readInts() = readLn().split(" ").map { it.toInt() } 635 private fun readInts(sz: Int) = Array(sz) { readInt() } 636 private fun readLongs() = readLn().split(" ").map { it.toLong() } 637 private fun readLongs(sz: Int) = Array(sz) { readLong() } 638 private fun print(b: Boolean) = out.print(b) 639 private fun print(i: Int) = out.print(i) 640 private fun print(d: Double) = out.print(d) 641 private fun print(l: Long) = out.print(l) 642 private fun print(s: String) = out.print(s) 643 private fun print(message: Any?) = out.print(message) 644 private fun print(a: Array<Int>) = a.forEach { print("$it ") } 645 private fun <T> print(a: Array<out T>) = a.forEach { print("$it ") } 646 private fun <T> print(a: Collection<T>) = a.forEach { print("$it ") } 647 private fun println(b: Boolean) = out.println(b) 648 private fun println(i: Int) = out.println(i) 649 private fun println(d: Double) = out.println(d) 650 private fun println(l: Long) = out.println(l) 651 private fun println(s: String) = out.println(s) 652 private fun println() = out.println() 653 private fun println(message: Any?) = out.println(message) 654 private fun <T> println(a: Array<out T>) { 655 a.forEach { print("$it ") } 656 println() 657 } 658 659 private fun println(a: IntArray) { 660 a.forEach { print("$it ") } 661 println() 662 } 663 664 private fun println(a: LongArray) { 665 a.forEach { print("$it ") } 666 println() 667 } 668 669 private fun <T> println(a: Collection<T>) { 670 a.forEach { print("$it ") } 671 println() 672 } 673 674 private fun intarr(sz: Int, v: Int = 0) = IntArray(sz) { v } 675 private fun longarr(sz: Int, v: Long = 0) = LongArray(sz) { v } 676 private fun intarr2d(n: Int, m: Int, v: Int = 0) = Array(n) { intarr(m, v) } 677 private fun longarr2d(n: Int, m: Int, v: Long = 0) = Array(n) { longarr(m, v) } 678 private fun <T> init(vararg elements: T) = elements 679 private fun VI(n: Int = 0, init: Int = 0) = MutableList(n) { init } 680 private fun VVI(n: Int = 0, m: Int = 0, init: Int = 0) = MutableList(n) { VI(m, init) } 681 private fun <T1 : Comparable<T1>, T2 : Comparable<T2>> pairCmp(): Comparator<Pair<T1, T2>> { 682 return Comparator { a, b -> 683 val res = a.first.compareTo(b.first) 684 if (res == 0) a.second.compareTo(b.second) else res 685 } 686 } 687 ``` 688 689 [2141I - Color the Tree](/contest/2141/problem/I "Kotlin Heroes: Episode 13") 690 691 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest") 692 693 **Tutorial** 694 695 Tutorial is loading... 696 697 **Solution (BledDest)** 698 699 ``` 700 import kotlin.math.min 701 702 const val K = 17 703 const val N = K * 2 704 const val MOD = 998244353 705 706 fun add(x: Int, y: Int): Int { 707 return ((x + y) % MOD + MOD) % MOD 708 } 709 710 fun mul(x: Int, y: Int): Int { 711 return (x.toLong() * y % MOD).toInt() 712 } 713 714 fun binpow(x: Int, y: Int): Int { 715 var z = 1 716 var base = x 717 var exponent = y 718 while (exponent > 0) { 719 if (exponent % 2 == 1) z = mul(z, base) 720 base = mul(base, base) 721 exponent /= 2 722 } 723 return z 724 } 725 726 data class State( 727 var unpaired: Int = 0, 728 var unpairedLess: Int = 0, 729 var pairedLess: Int = 0, 730 var flag: Int = 0, 731 var ways: Int = 0 732 ) 733 734 fun comp(a: State, b: State): Boolean { 735 if (a.unpaired != b.unpaired) return a.unpaired < b.unpaired 736 if (a.unpairedLess != b.unpairedLess) return a.unpairedLess < b.unpairedLess 737 if (a.pairedLess != b.pairedLess) return a.pairedLess < b.pairedLess 738 return a.flag < b.flag 739 } 740 741 fun fix(v: MutableList<State>) { 742 v.sortWith(compareBy(State::unpaired).thenBy { it.unpairedLess }.thenBy { it.pairedLess }.thenBy { it.flag }) 743 val v2 = mutableListOf<State>() 744 for (s in v) { 745 if (s.ways == 0) continue 746 if (v2.isEmpty() || comp(v2.last(), s)) { 747 v2.add(s) 748 } else { 749 v2.last().ways = add(v2.last().ways, s.ways) 750 } 751 } 752 v.clear() 753 v.addAll(v2) 754 } 755 756 val fact = IntArray(N) 757 val rfact = IntArray(N) 758 val g = Array(N) { mutableListOf<Int>() } 759 val dp = Array(N) { mutableListOf<MutableList<State>>() } 760 var n = 0 761 762 fun choose(x: Int, y: Int): Int { 763 return mul(fact[x], mul(rfact[y], rfact[x - y])) 764 } 765 766 fun merge2(x: MutableList<State>, y: MutableList<State>): MutableList<State> { 767 val res = mutableListOf<State>() 768 for (a in x) { 769 for (b in y) { 770 for (pairLess in 0..min(a.unpairedLess, b.unpairedLess)) { 771 for (pairGreater in 0..min(a.unpaired - a.unpairedLess, b.unpaired - b.unpairedLess)) { 772 var numOfChoices = mul(fact[pairLess], fact[pairGreater]) 773 numOfChoices = mul(numOfChoices, choose(a.unpairedLess, pairLess)) 774 numOfChoices = mul(numOfChoices, choose(a.unpaired - a.unpairedLess, pairGreater)) 775 numOfChoices = mul(numOfChoices, choose(b.unpairedLess, pairLess)) 776 numOfChoices = mul(numOfChoices, choose(b.unpaired - b.unpairedLess, pairGreater)) 777 numOfChoices = mul(numOfChoices, a.ways) 778 numOfChoices = mul(numOfChoices, b.ways) 779 var flag = 0 780 if (a.unpairedLess > 0 || b.unpairedLess > 0) flag = 1 781 if (a.unpairedLess < a.unpaired || b.unpairedLess < b.unpaired) flag = 2 782 res.add(State(a.unpaired + b.unpaired - 2 * pairLess - 2 * pairGreater, a.unpairedLess + b.unpairedLess - pairLess * 2, a.pairedLess + b.pairedLess + pairLess, maxOf(flag, a.flag), numOfChoices)) 783 } 784 } 785 } 786 } 787 fix(res) 788 return res 789 } 790 791 fun merge(a: MutableList<MutableList<State>>, b: MutableList<MutableList<State>>): MutableList<MutableList<State>> { 792 val res = MutableList(2) { mutableListOf<State>() } 793 for (i in 0..1) { 794 for (j in 0..1) { 795 if (i == 1 && j == 1) continue 796 val cur = merge2(a[i], b[j]) 797 res[i + j].addAll(cur) 798 } 799 } 800 for (i in 0..1) fix(res[i]) 801 return res 802 } 803 804 fun getDp(s: MutableList<State>, cntLess: Int, flag: Int): Int { 805 for (x in s) { 806 if (x.unpaired == 0 && x.pairedLess == cntLess && x.flag == flag) return x.ways 807 } 808 return 0 809 } 810 811 fun forceSpecial(a: MutableList<MutableList<State>>): MutableList<MutableList<State>> { 812 val res = MutableList(2) { mutableListOf<State>() } 813 for (x in a[0]) { 814 when (x.flag) { 815 0 -> res[1].add(x) 816 1 -> { 817 res[0].add(x.copy()) 818 res[1].add(x.copy()) 819 } 820 else -> res[0].add(x) 821 } 822 } 823 for (x in a[1]) { 824 res[1].add(x) 825 } 826 fix(res[0]) 827 fix(res[1]) 828 return res 829 } 830 831 fun dfs(v: Int, p: Int) { 832 val children = mutableListOf<Int>() 833 for (x in g[v]) { 834 if (x != p) { 835 dfs(x, v) 836 children.add(x) 837 } 838 } 839 if (g[v].size == 1 && v != p) { 840 val s1 = State(1, 1, 0, 0, 1) 841 val s2 = State(1, 0, 0, 0, 1) 842 dp[v] = mutableListOf(mutableListOf(s1, s2), mutableListOf()) 843 fix(dp[v][0]) 844 return 845 } 846 var aux = MutableList(2) { mutableListOf<State>() } 847 aux[0].add(State(0, 0, 0, 0, 1)) 848 for (c in children) { 849 aux = merge(aux, dp[c]) 850 } 851 dp[v] = forceSpecial(aux) 852 } 853 854 fun main() { 855 val reader = System.`in`.bufferedReader() 856 n = reader.readLine().toInt() 857 for (i in 0 until n - 1) { 858 val (x, y) = reader.readLine().split(" ").map { it.toInt() } 859 g[x - 1].add(y - 1) 860 g[y - 1].add(x - 1) 861 } 862 val leaves = mutableListOf<Int>() 863 val nonLeaves = mutableListOf<Int>() 864 for (i in 0 until n) { 865 if (g[i].size == 1) leaves.add(i) else nonLeaves.add(i) 866 } 867 fact[0] = 1 868 for (i in 1..n) fact[i] = mul(fact[i - 1], i) 869 for (i in 0..n) rfact[i] = binpow(fact[i], MOD - 2) 870 var ans = 0 871 if (leaves.size % 2 == 0) { 872 val root = nonLeaves[0] 873 dfs(root, root) 874 ans = mul(fact[leaves.size / 2], getDp(dp[root][0], 0, 2)) 875 println("${leaves.size / 2} $ans") 876 } else { 877 print("${(leaves.size + 1) / 2} ") 878 for (x in leaves) { 879 dfs(x, x) 880 for (j in 0..leaves.size / 2) { 881 val cur = getDp(dp[x][1], j, 0) 882 ans = add(ans, mul(cur, mul(fact[j], fact[leaves.size / 2 - j]))) 883 } 884 } 885 println(ans) 886 } 887 } 888 ```