1533.md (11554B)
1 Source: https://codeforces.com/blog/entry/92357 2 3 First of all, I would like to thank all testers of the round: [PavelKunyavskiy](/profile/PavelKunyavskiy "International Grandmaster PavelKunyavskiy"), [IlyaLos](/profile/IlyaLos "International Master IlyaLos"), [Vladik](/profile/Vladik "Candidate Master Vladik"), [ashmelev](/profile/ashmelev "International Grandmaster ashmelev"), [nooinenoojno](/profile/nooinenoojno "Expert nooinenoojno"), [AlexFetisov](/profile/AlexFetisov "Master AlexFetisov"). Also huge thanks to co-authors of the contest: [Neon](/profile/Neon "Candidate Master Neon"), [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 [1533A - Travel to Bertown](/contest/1533/problem/A "Kotlin Heroes: Episode 7") 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(readLine()!!.toInt()) { 21 val (n, k) = readLine()!!.split(" ").map { it.toInt() } 22 var ans = 0 23 repeat(n) { 24 val (l, r) = readLine()!!.split(" ").map { it.toInt() } 25 if (l <= k) ans = maxOf(ans, r - k + 1) 26 } 27 println(ans) 28 } 29 ``` 30 31 [1533B - Nearest Point Function](/contest/1533/problem/B "Kotlin Heroes: Episode 7") 32 33 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [vovuh](/profile/vovuh "Master vovuh") 34 35 **Tutorial** 36 37 Tutorial is loading... 38 39 **Solution (vovuh)** 40 41 ``` 42 fun main() { 43 val t = readLine()!!.toInt() 44 repeat(t) { 45 val n = readLine()!!.toInt() 46 val x = readLine()!!.split(" ").map { it.toInt() } 47 var ans = false 48 for (i in 1 until n) { 49 if ((x[i] - x[i - 1]) % 2 == 0) { 50 ans = true 51 } 52 } 53 println(if (ans) "YES" else "NO") 54 } 55 } 56 ``` 57 58 [1533C - Sweets](/contest/1533/problem/C "Kotlin Heroes: Episode 7") 59 60 Idea: [Neon](/profile/Neon "Candidate Master Neon"), preparation: [Neon](/profile/Neon "Candidate Master Neon") 61 62 **Tutorial** 63 64 Tutorial is loading... 65 66 **Solution (Neon)** 67 68 ``` 69 fun main() = repeat(readLine()!!.toInt()) { 70 val (n, k) = readLine()!!.split(" ").map { it.toInt() } 71 val s = readLine()!! 72 val used = BooleanArray(n) { false } 73 var cnt = s.count({ it == '1'}) 74 var pos = 0 75 while (cnt > 0) { 76 used[pos] = true 77 if (s[pos] == '1') --cnt 78 if (cnt == 0) break 79 var lft = k 80 while (lft > 0) { 81 pos = (pos + 1) % n 82 if (!used[pos]) --lft; 83 } 84 } 85 println(used.count({ it })) 86 } 87 ``` 88 89 [1533D - String Searching](/contest/1533/problem/D "Kotlin Heroes: Episode 7") 90 91 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") and [Neon](/profile/Neon "Candidate Master Neon"), preparation: [Neon](/profile/Neon "Candidate Master Neon") 92 93 **Tutorial** 94 95 Tutorial is loading... 96 97 **Solution (Neon)** 98 99 ``` 100 fun main() { 101 val (n, m) = readLine()!!.split(" ").map { it.toInt() } 102 val used = Array(n) { readLine()!! }.toSet() 103 repeat(readLine()!!.toInt()) { 104 val t = readLine()!! 105 val s = (0..m).map { i -> t.removeRange(i..i) }.toSet() 106 println(s.count { used.contains(it) } ) 107 } 108 } 109 ``` 110 111 [1533E - Chess Team Forming](/contest/1533/problem/E "Kotlin Heroes: Episode 7") 112 113 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [awoo](/profile/awoo "Grandmaster awoo") 114 115 **Tutorial** 116 117 Tutorial is loading... 118 119 **Solution (awoo)** 120 121 ``` 122 fun main() { 123 val n = readLine()!!.toInt() 124 val a = readLine()!!.split(" ").map { it.toInt() }.toIntArray() 125 val b = readLine()!!.split(" ").map { it.toInt() }.toIntArray() 126 val m = readLine()!!.toInt() 127 val c = readLine()!!.split(" ").map { it.toInt() }.toIntArray() 128 a.sort() 129 b.sort() 130 val pr = IntArray(n + 1) { -2e9.toInt() } 131 for (i in 0 until n) { 132 pr[i + 1] = maxOf(pr[i], b[i] - a[i]) 133 } 134 val su = IntArray(n + 1) { -2e9.toInt() } 135 for (i in (n-1) downTo 0) { 136 su[i] = maxOf(su[i + 1], b[i + 1] - a[i]) 137 } 138 val ans = IntArray(m) 139 for (i in 0 until m) { 140 var pos = a.binarySearch(c[i]) 141 if (pos < 0) { 142 pos = -pos - 1 143 } 144 ans[i] = maxOf(pr[pos], su[pos], b[pos] - c[i]) 145 } 146 println(ans.joinToString(" ")) 147 } 148 ``` 149 150 [1533F - Binary String Partition](/contest/1533/problem/F "Kotlin Heroes: Episode 7") 151 152 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon") 153 154 **Tutorial** 155 156 Tutorial is loading... 157 158 **Solution (Neon)** 159 160 ``` 161 fun main() { 162 val s = readLine()!!.map { (it - '0').toInt() }.toIntArray() 163 val pos = Array(2) { c -> s.indices.filter { s[it] == c }.toIntArray() } 164 val sum = Array(2) { c -> s.runningFold(0) { cur, x -> cur + if (x == c) 1 else 0 }.toIntArray() } 165 println((1..s.size).map { k -> 166 generateSequence(0) { i -> 167 IntArray(2) { c -> pos[c].getOrElse(sum[c][i] + k) { s.size } }.maxOrNull()!! 168 }.indexOf(s.size) 169 }.joinToString(" ")) 170 } 171 ``` 172 173 [1533G - Biome Map](/contest/1533/problem/G "Kotlin Heroes: Episode 7") 174 175 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon") 176 177 **Tutorial** 178 179 Tutorial is loading... 180 181 **Solution (Neon)** 182 183 ``` 184 fun main() = repeat(readLine()!!.toInt()) { 185 val (n, m) = readLine()!!.split(" ").map { it.toInt() } 186 val a = Array(n) { readLine()!!.split(" ").map { it.toInt() } } 187 val used = BooleanArray(111) { false } 188 val ord = ArrayList<Int>() 189 190 val dx = intArrayOf(0, 1, 0, -1) 191 val dy = intArrayOf(1, 0, -1, 0) 192 193 fun dfs(x : Int, y : Int) { 194 ord.add(a[x][y]) 195 used[a[x][y]] = true 196 for (i in 0 until 4) { 197 val nx = x + dx[i] 198 val ny = y + dy[i] 199 if (0 <= nx && nx < n && 0 <= ny && ny < m && a[nx][ny] != 0 && !used[a[nx][ny]]) { 200 dfs(nx, ny) 201 ord.add(a[x][y]) 202 } 203 } 204 } 205 206 var k = 0 207 208 for (x in 0 until n) { 209 for (y in 0 until m) { 210 if (a[x][y] != 0) { 211 k += 1 212 if (ord.isEmpty()) dfs(x, y) 213 } 214 } 215 } 216 217 if (ord.count() != 2 * k - 1) { 218 return@repeat println(-1) 219 } 220 221 println("$k $k") 222 for (x in 0 until k) { 223 for (y in 0 until k) { 224 print("${ord[x + y]} ") 225 } 226 println() 227 } 228 } 229 ``` 230 231 [1533H - Submatrices](/contest/1533/problem/H "Kotlin Heroes: Episode 7") 232 233 Idea: [Neon](/profile/Neon "Candidate Master Neon"), preparation: [Neon](/profile/Neon "Candidate Master Neon") 234 235 **Tutorial** 236 237 Tutorial is loading... 238 239 **Solution (Neon)** 240 241 ``` 242 fun main() { 243 val AL = 5 244 val (n, m) = readLine()!!.split(" ").map { it.toInt() } 245 val s = Array(n) { readLine()!! } 246 val res = LongArray(1 shl AL) { mask -> 247 val d = IntArray(m) { 0 } 248 var sum = 0L 249 for (i in 0 until n) { 250 for (j in 0 until m) { 251 val cur = (mask shr (s[i][j] - 'A')) and 1 252 d[j] = if (cur == 1) d[j] + 1 else 0 253 } 254 val l = IntArray(m) { -1 } 255 val q = IntArray(m) { 0 } 256 var ptr = -1 257 for (j in 0 until m) { 258 while (ptr >= 0 && d[q[ptr]] >= d[j]) ptr -= 1 259 if (ptr >= 0) l[j] = q[ptr] 260 ptr += 1 261 q[ptr] = j 262 } 263 val r = IntArray(m) { m } 264 ptr = -1 265 for (j in m - 1 downTo 0) { 266 while (ptr >= 0 && d[q[ptr]] > d[j]) ptr -= 1 267 if (ptr >= 0) r[j] = q[ptr] 268 ptr += 1 269 q[ptr] = j 270 } 271 for (j in 0 until m) sum += (j - l[j]) * (r[j] - j) * d[j].toLong() 272 } 273 sum 274 } 275 276 for (i in 0 until AL) { 277 for (mask in 1 until (1 shl AL)) { 278 if (((mask shr i) and 1) == 0) res[mask or (1 shl i)] -= res[mask] 279 } 280 } 281 282 val ans = LongArray(AL + 1) { 0 } 283 for (mask in 1 until (1 shl AL)) ans[mask.countOneBits()] += res[mask] 284 285 println(ans.drop(1).joinToString(" ")) 286 } 287 ``` 288 289 [1533I - Excursions](/contest/1533/problem/I "Kotlin Heroes: Episode 7") 290 291 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest") 292 293 **Tutorial** 294 295 Tutorial is loading... 296 297 **Solution (Neon)** 298 299 ``` 300 import java.util.Queue 301 import java.util.LinkedList 302 303 fun main() { 304 val (n1, n2, m) = readLine()!!.split(" ").map { it.toInt() } 305 val S = n1 + n2 306 val T = S + 1 307 val V = T + 1 308 309 data class Edge(val y : Int, val c : Int, var f : Int, val cost : Int) 310 311 val e = ArrayList<Edge>() 312 val g = Array(V) { ArrayList<Int>() } 313 314 fun addEdge(x : Int, y : Int, c : Int, cost : Int) { 315 g[x].add(e.size) 316 e.add(Edge(y, c, 0, cost)) 317 g[y].add(e.size) 318 e.add(Edge(x, 0, 0, -cost)) 319 } 320 321 var sum = 0 322 readLine()!!.split(" ").mapIndexed { i, value -> 323 val k = value.toInt() 324 addEdge(i, T, 1, -k) 325 sum += k 326 } 327 328 val deg = IntArray(n2) { 0 } 329 repeat(m) { 330 val (x, y) = readLine()!!.split(" ").map { it.toInt() - 1 } 331 addEdge(y + n1, x, 1, 0) 332 deg[y] += 1 333 } 334 335 for (i in 0 until n2) { 336 addEdge(S, i + n1, deg[i] - 1, 0) 337 } 338 339 var mincost = 0 340 341 fun enlarge() : Boolean { 342 val q: Queue<Int> = LinkedList<Int>() 343 val inq = IntArray(V) { 0 } 344 val d = IntArray(V) { 1e9.toInt() } 345 val p = IntArray(V) { -1 } 346 val pe = IntArray(V) { -1 } 347 348 q.add(S) 349 inq[S] = 1 350 d[S] = 0 351 352 while (!q.isEmpty()) { 353 val k = q.poll() 354 g[k].forEach { a -> 355 val (to, c, f, w) = e[a] 356 if (c - f != 0 && d[to] > d[k] + w) { 357 d[to] = d[k] + w 358 p[to] = k 359 pe[to] = a 360 if (inq[to] == 0) { 361 q.add(to) 362 inq[to] = 1 363 } 364 } 365 } 366 } 367 368 if (p[T] == -1) return false 369 370 var cur = T 371 while (cur != S) { 372 mincost += e[pe[cur]].cost 373 e[pe[cur]].f += 1 374 e[pe[cur] xor 1].f -= 1 375 cur = p[cur] 376 } 377 378 return true 379 } 380 381 while (enlarge()); 382 383 println(sum + mincost) 384 385 } 386 ``` 387 388 [1533J - Pawns](/contest/1533/problem/J "Kotlin Heroes: Episode 7") 389 390 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest") 391 392 **Tutorial** 393 394 Tutorial is loading... 395 396 **Solution (Neon)** 397 398 ``` 399 fun main() { 400 val N = 500043 401 val n = readLine()!!.toInt() 402 val pts = Array(N) { ArrayList<Int>() } 403 repeat(n) { 404 val (x, y) = readLine()!!.split(" ").map { it.toInt() } 405 pts[y].add(x) 406 } 407 pts.forEach { it.sort() } 408 409 data class Event(val y : Int, val t : Int, val value : Int) 410 411 fun recalc(v1 : ArrayList<Pair<Int, Int>>, v2 : ArrayList<Int>, flag : Boolean) : ArrayList<Pair<Int, Int>> { 412 val events = ArrayList<Event>() 413 if (flag) { 414 v1.forEach { events.add(Event(it.first, 0, it.second)) } 415 v2.forEachIndexed { i, value -> events.add(Event(value, 1, i + 1)) } 416 events.add(Event(0, 1, 0)) 417 events.sortWith(compareBy({ -it.y }, { it.t }, { it.value })) 418 } else { 419 v1.forEach { events.add(Event(it.first, 0, it.second)) } 420 v2.forEachIndexed { i, value -> events.add(Event(value, 1, v2.size - i)) } 421 events.add(Event(N + 43, 1, 0)) 422 events.sortWith(compareBy({ it.y }, { it.t }, { it.value })) 423 } 424 var cur = 0 425 val res = ArrayList<Pair<Int, Int>>() 426 events.forEach { 427 if (it.t == 0) { 428 cur = maxOf(cur, it.value) 429 } else { 430 res.add(Pair(it.y, it.value + cur)) 431 } 432 } 433 return res 434 } 435 436 fun calc(flag : Int) : Int { 437 var cur = ArrayList<Pair<Int, Int>>() 438 pts.forEachIndexed { i, value -> cur = recalc(cur, value, flag != i % 2) } 439 var res = 0 440 cur.forEach { res = maxOf(res, it.second) } 441 return res 442 } 443 444 println(calc(0) + calc(1) - n) 445 } 446 ```