codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```