1431.md (12480B)
1 Source: https://codeforces.com/blog/entry/84563 2 3 First of all, I would like to thank all testers of the round: [elizarov](/profile/elizarov "Candidate Master elizarov"), [IlyaLos](/profile/IlyaLos "International Master IlyaLos"), [nuipojaluista](/profile/nuipojaluista "Expert nuipojaluista"), [hg333](/profile/hg333 "Candidate Master hg333"), [nooinenoojno](/profile/nooinenoojno "Expert nooinenoojno"), [winger](/profile/winger "International Grandmaster winger"), [neko_nyaaaaaaaaaaaaaaaaa](/profile/neko_nyaaaaaaaaaaaaaaaaa "Grandmaster neko_nyaaaaaaaaaaaaaaaaa"), [kort0n](/profile/kort0n "Grandmaster kort0n"), [hos.lyric](/profile/hos.lyric "Legendary Grandmaster hos.lyric") and [Roms](/profile/Roms "Master Roms"). Also huge thanks to co-authors of the contest: [Neon](/profile/Neon "Candidate Master Neon"), [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 [1431A - Selling Hamburgers](/contest/1431/problem/A "Kotlin Heroes 5: ICPC Round") 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 (elizarov)** 18 19 ``` 20 fun main() { 21 repeat(readLine()!!.toInt()) { 22 val n = readLine()!!.toInt() 23 val a = readLine()!!.split(" ").map { it.toLong() } 24 val answer = a.sortedDescending().withIndex().maxOf { (it.index + 1) * it.value } 25 println(answer) 26 } 27 } 28 ``` 29 30 [1431B - Polycarp and the Language of Gods](/contest/1431/problem/B "Kotlin Heroes 5: ICPC Round") 31 32 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [awoo](/profile/awoo "Grandmaster awoo") 33 34 **Tutorial** 35 36 Tutorial is loading... 37 38 **Solution (elizarov)** 39 40 ``` 41 fun main() { 42 repeat(readLine()!!.toInt()) { 43 val s = readLine()!! 44 val answer = s.count { it == 'w' } + s.split("w").sumOf { it.length / 2 } 45 println(answer) 46 } 47 } 48 ``` 49 50 [1431C - Black Friday](/contest/1431/problem/C "Kotlin Heroes 5: ICPC Round") 51 52 Idea: [Neon](/profile/Neon "Candidate Master Neon"), preparation: [Neon](/profile/Neon "Candidate Master Neon") and [awoo](/profile/awoo "Grandmaster awoo") 53 54 **Tutorial** 55 56 Tutorial is loading... 57 58 **Solution (elizarov)** 59 60 ``` 61 fun main() { 62 repeat(readLine()!!.toInt()) { 63 val (n, k) = readLine()!!.split(" ").map { it.toInt() } 64 val p = readLine()!!.split(" ").map { it.toInt() } 65 val answer = (1..n / k).maxOf { d -> 66 val m = d * k 67 p.subList(n - m, n - m + d).sum() 68 } 69 println(answer) 70 } 71 } 72 ``` 73 74 [1431D - Used Markers](/contest/1431/problem/D "Kotlin Heroes 5: ICPC Round") 75 76 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [adedalic](/profile/adedalic "International Master adedalic") 77 78 **Tutorial** 79 80 Tutorial is loading... 81 82 **Solution (elizarov)** 83 84 ``` 85 fun main() { 86 repeat(readLine()!!.toInt()) { 87 val n = readLine()!!.toInt() 88 val a = readLine()!!.split(" ").map { it.toInt() } 89 .withIndex().sortedBy { it.value } 90 var i = 0 91 var j = n - 1 92 val answer = ArrayList<Int>(n) 93 var bc = 0 94 while (i <= j) { 95 if (bc >= a[i].value) { 96 answer += a[i++].index 97 bc = 1 98 } else { 99 answer += a[j--].index 100 bc++ 101 } 102 } 103 println(answer.joinToString(" ") { (it + 1).toString() }) 104 } 105 } 106 ``` 107 108 [1431E - Chess Match](/contest/1431/problem/E "Kotlin Heroes 5: ICPC Round") 109 110 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest") 111 112 **Tutorial** 113 114 Tutorial is loading... 115 116 **Solution (Ne0n25)** 117 118 ``` 119 fun main() = repeat(readLine()!!.toInt()) { 120 val n = readLine()!!.toInt() 121 val a = readLine()!!.split(" ").map { it.toInt() } 122 val b = readLine()!!.split(" ").map { it.toInt() } 123 124 var ans = -1 125 var ans_shift = -1 126 for (shift in 0 until n) { 127 var res = 1e9.toInt() 128 for(i in 0 until n) 129 res = Math.min(res, Math.abs(a[i] - b[(i + shift) % n])) 130 if (res > ans) { 131 ans = res 132 ans_shift = shift 133 } 134 } 135 136 println(IntArray(n) { (it + ans_shift) % n + 1 }.joinToString(" ")) 137 } 138 ``` 139 140 [1431F - Neural Network Problem](/contest/1431/problem/F "Kotlin Heroes 5: ICPC Round") 141 142 Idea: [vovuh](/profile/vovuh "Master vovuh"), preparation: [vovuh](/profile/vovuh "Master vovuh") 143 144 **Tutorial** 145 146 Tutorial is loading... 147 148 **Solution (vovuh)** 149 150 ``` 151 import java.util.* 152 153 fun main() { 154 val (n, k, x) = readLine()!!.split(" ").map { it.toInt() } 155 val a = readLine()!!.split(" ").map { it.toInt() } 156 var l = 0L 157 var r = 10L * 1000 * 1000 * 1000 158 var res = -1L 159 160 fun can(sum : Long) : Boolean { 161 var cursum = 0L 162 var need = 0 163 var cur = PriorityQueue<Int>(compareBy<Int> { -it }) 164 for (i in 0 until n) { 165 cursum += a[i] 166 cur.add(a[i]) 167 while (cur.size > x || cursum > sum) { 168 cursum -= cur.first() 169 cur.remove() 170 need += 1 171 } 172 if (cur.size == x) { 173 cursum = 0L 174 cur.clear() 175 } 176 } 177 return need <= k 178 } 179 180 while (l <= r) { 181 val mid = (l + r) / 2 182 if (can(mid)) { 183 res = mid 184 r = mid - 1 185 } else { 186 l = mid + 1 187 } 188 } 189 println(res) 190 } 191 ``` 192 193 [1431G - Number Deletion Game](/contest/1431/problem/G "Kotlin Heroes 5: ICPC Round") 194 195 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest") 196 197 **Tutorial** 198 199 Tutorial is loading... 200 201 **Solution (Ne0n25)** 202 203 ``` 204 fun main() { 205 val (n, k) = readLine()!!.split(' ').map { it.toInt() } 206 val a = readLine()!!.split(" ").map { it.toInt() }.sorted() 207 208 val p = IntArray(n + 1) { 0 } 209 for (i in 0 until n) p[i + 1] = p[i] + a[i] 210 211 val dp = Array(n + 1) { IntArray(k + 1) { -1 } } 212 213 dp[0][0] = 0 214 for (i in 0 until n) { 215 for (j in 0 until k + 1) { 216 if (dp[i][j] < 0) 217 continue 218 dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j]) 219 val maxx = Math.min(k - j, (n - i) / 2) 220 for (x in 1..maxx) 221 dp[i + 2 * x][j + x] = Math.max(dp[i + 2 * x][j + x], dp[i][j] + p[i + 2 * x] - p[i + x] - p[i + x] + p[i]) 222 } 223 } 224 225 println(dp[n][k]) 226 } 227 ``` 228 229 [1431H - Rogue-like Game](/contest/1431/problem/H "Kotlin Heroes 5: ICPC Round") 230 231 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon") 232 233 **Tutorial** 234 235 Tutorial is loading... 236 237 **Solution (Ne0n25)** 238 239 ``` 240 fun main() { 241 val (n, m, k) = readLine()!!.split(" ").map { it.toInt() } 242 val a = readLine()!!.split(" ").map { it.toLong() } 243 val b = readLine()!!.split(" ").map { it.toLong() } 244 val c = Array(n) { readLine()!!.split(" ").map { it.toLong() } } 245 246 val ev = Array(n + m) { 247 if (it < n) 248 longArrayOf(a[it], 1L, it.toLong()) 249 else 250 longArrayOf(b[it - n], 0L, (it - n).toLong()) 251 } 252 253 ev.sortWith(compareBy({ it[0] })) 254 255 val vals = LongArray(n + m) { 0 } 256 257 for (e in 0 until n + m) { 258 if (ev[e][1] == 1L) { 259 val i = ev[e][2].toInt() 260 vals[e] = b.indices.filter { b[it] <= ev[e][0] }.map { c[i][it] }.max()!! 261 } else { 262 val j = ev[e][2].toInt() 263 vals[e] = a.indices.filter { a[it] <= ev[e][0] }.map { c[it][j] }.max()!! 264 } 265 } 266 267 var ans = 1e18.toLong() 268 269 for (bonus in 1 until n + m) { 270 vals[bonus] += k.toLong() 271 var (res, cur, mx) = LongArray(3) { 0 } 272 var i = 0 273 while (true) { 274 while (i < n + m && ev[i][0] <= cur) { 275 mx = Math.max(mx, vals[i]) 276 ++i; 277 } 278 if (i == n + m) break 279 val need = (ev[i][0] - cur + mx - 1) / mx 280 res += need 281 cur += need * mx 282 } 283 ans = Math.min(ans, res) 284 vals[bonus] -= k.toLong() 285 } 286 287 println(ans) 288 } 289 ``` 290 291 [1431I - Cyclic Shifts](/contest/1431/problem/I "Kotlin Heroes 5: ICPC Round") 292 293 Idea: [Neon](/profile/Neon "Candidate Master Neon"), preparation: [Neon](/profile/Neon "Candidate Master Neon") 294 295 **Tutorial** 296 297 Tutorial is loading... 298 299 **Solution (Ne0n25)** 300 301 ``` 302 import java.io.PrintWriter 303 304 fun main() { 305 val (n, m, q) = readLine()!!.split(' ').map { it.toInt() } 306 val s = Array(n) { readLine()!! } 307 val c = Array(m + 1) { IntArray(n) { 0 } } 308 val rc = Array(m + 1) { IntArray(n) { 0 } } 309 310 for (j in m - 1 downTo 0) { 311 val cur = Array(n) { intArrayOf(s[it][j].toInt(), c[j + 1][it], it) } 312 cur.sortWith(compareBy({it[0]}, {it[1]})) 313 for (i in 0 until n) rc[j][i] = cur[i][2] 314 c[j][cur[0][2]] = 0 315 for (i in 1 until n) { 316 val add = if (cur[i][0] == cur[i - 1][0] && cur[i][1] == cur[i - 1][1]) 0 else 1 317 c[j][cur[i][2]] = c[j][cur[i - 1][2]] + add 318 } 319 } 320 321 val writer = PrintWriter(System.out) 322 323 repeat(q) { 324 val t = readLine()!! 325 var ans = 0 326 var j = 0 327 while (j < m) { 328 var (nj, L, R) = intArrayOf(j, 0, n - 1) 329 while (nj < m) { 330 var (l1, r1, nL) = intArrayOf(L, R, R + 1) 331 while (l1 <= r1) { 332 val mid = (l1 + r1) / 2 333 if (s[rc[j][mid]][nj] >= t[nj]) { 334 nL = mid 335 r1 = mid - 1 336 } else { 337 l1 = mid + 1 338 } 339 } 340 341 var (l2, r2, nR) = intArrayOf(nL, R, nL - 1) 342 while (l2 <= r2) { 343 val mid = (l2 + r2) / 2 344 if (s[rc[j][mid]][nj] <= t[nj]) { 345 nR = mid 346 l2 = mid + 1 347 } else { 348 r2 = mid - 1 349 } 350 } 351 352 if (nL > nR) 353 break 354 355 L = nL 356 R = nR 357 ++nj 358 } 359 360 if (j == nj) { 361 ans = 0 362 break 363 } 364 365 ans += 1 366 j = nj 367 } 368 369 writer.println(ans - 1) 370 } 371 372 writer.close() 373 } 374 ``` 375 376 [1431J - Zero-XOR Array](/contest/1431/problem/J "Kotlin Heroes 5: ICPC Round") 377 378 Idea: [Neon](/profile/Neon "Candidate Master Neon"), preparation: [Neon](/profile/Neon "Candidate Master Neon") and [adedalic](/profile/adedalic "International Master adedalic") 379 380 **Tutorial** 381 382 Tutorial is loading... 383 384 **Solution (Ne0n25)** 385 386 ``` 387 fun main() { 388 val MOD = 998244353 389 390 fun add(x : Int, y : Int) : Int { 391 return x + y - if (x + y < MOD) 0 else MOD 392 } 393 394 fun mul(x : Int, y : Int) : Int { 395 return (1L * x * y % MOD).toInt() 396 } 397 398 val inv = IntArray(60) { 0 }.also { it[0] = 1; it[1] = (MOD + 1) / 2 } 399 for (i in 2 until 60) { 400 inv[i] = mul(inv[i - 1], inv[1]) 401 } 402 403 val n = readLine()!!.toInt() 404 val a = readLine()!!.split(" ").map { it.toLong() } 405 val target = a.fold(0.toLong()) { res, it -> res xor it } 406 val dp = Array(n) { Array(2) { IntArray(2) { 0 } } } 407 408 var ans = 0 409 410 val m = 1 shl (n - 1) 411 for (mask in 0 until m) { 412 val cur = Array(n - 1) { longArrayOf(a[it], a[it + 1]) } 413 val used = BooleanArray(n - 1) { false } 414 415 for (pw in 59 downTo 0) { 416 for (i in 0 until n) 417 for (cnt in 0 until 2) 418 for (fl in 0 until 2) 419 dp[i][cnt][fl] = 0 420 dp[0][0][0] = 1 421 for (i in 0 until n - 1) { 422 for (cnt in 0 until 2) { 423 for (fl in 0 until 2) { 424 if (dp[i][cnt][fl] == 0) 425 continue 426 val (l, r) = cur[i] 427 if ((l shr pw) == (r shr pw)) { 428 if (!used[i] && ((mask shr i) and 1) == 1) 429 continue 430 val c = (l shr pw).toInt() 431 val len = (cur[i][1] - cur[i][0] + 1) 432 dp[i + 1][cnt xor c][fl] = add(dp[i + 1][cnt xor c][fl], mul((len % MOD).toInt(), dp[i][cnt][fl])) 433 } else for (c in 0 until 2) { 434 if (!used[i] && (c != (mask shr i) and 1)) 435 continue 436 val nl = if (c == 1) 0L else l 437 var nr = if (c == 1) r - (1L shl pw) else (1L shl pw) - 1 438 val len = nr - nl + 1 439 val nfl = if (len == (1L shl pw) && (c != ((mask shr i) and 1))) 1 else 0 440 dp[i + 1][cnt xor c][fl or nfl] = add(dp[i + 1][cnt xor c][fl or nfl], mul((len % MOD).toInt(), dp[i][cnt][fl])) 441 } 442 } 443 } 444 } 445 446 var cnt = ((target shr pw) and 1).toInt() 447 ans = add(ans, mul(dp[n - 1][cnt][1], inv[pw])) 448 if (pw == 0) 449 ans = add(ans, dp[n - 1][cnt][0]) 450 451 for (i in 0 until n - 1) { 452 val (l, r) = cur[i] 453 if ((l shr pw) == (r shr pw)) { 454 val c = (l shr pw) 455 cnt = cnt xor c.toInt() 456 cur[i][0] -= c shl pw 457 cur[i][1] -= c shl pw 458 } else { 459 used[i] = true 460 val c = (mask shr i) and 1 461 cnt = cnt xor c.toInt() 462 cur[i][0] = if (c == 1) 0 else cur[i][0] 463 cur[i][1] = if (c == 1) cur[i][1] - (1L shl pw) else (1L shl pw) - 1 464 } 465 } 466 467 if (cnt != 0) 468 break 469 } 470 } 471 472 println(ans) 473 } 474 ```