codeforces-scrape

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

2087.md (15058B)


      1 Source: https://codeforces.com/blog/entry/141608
      2 
      3 The contest was prepared by [adedalic](/profile/adedalic "Международный мастер adedalic"), [awoo](/profile/awoo "Мастер awoo"), [Neon](/profile/Neon "Кандидат в мастера Neon") and me. We had a great team of testers: [shnirelman](/profile/shnirelman "Международный гроссмейстер shnirelman"), [ashmelev](/profile/ashmelev "Гроссмейстер ashmelev"), [FelixArg](/profile/FelixArg "Международный мастер FelixArg"), [KIRIJIJI](/profile/KIRIJIJI "Мастер KIRIJIJI"), [Alenochka](/profile/Alenochka "Эксперт Alenochka"), [alyoks1](/profile/alyoks1 "Эксперт alyoks1"), [Vladosiya](/profile/Vladosiya "Кандидат в мастера Vladosiya"), [mariibykova](/profile/mariibykova "Специалист mariibykova") — huge thanks to all of you!
      4 
      5 **One insane moment from the testing phase**
      6 
      7 One day before the contest, [shnirelman](/profile/shnirelman "Международный гроссмейстер shnirelman") completely destroyed problem H in less than 15 minutes. Thankfully, I had an idea of a replacement problem.
      8 
      9 Thanks to all competitors for participation, I hope you enjoyed the problems we made!
     10 
     11 And last but not least, I would like to express my gratitude to [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov") for keeping Codeforces and Polygon running even under unprecedented pressure from the bots.
     12 
     13 Okay, now for the editorial itself:
     14 
     15 [2087A - Генератор паролей](/contest/2087/problem/A "Kotlin Heroes: Episode 12")
     16 
     17 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest")
     18 
     19 **Tutorial**
     20 
     21 Tutorial is loading...
     22 
     23 **Solution (Neon)**
     24 
     25 ```
     26 const val chars = "01ABab"
     27 
     28 fun main() = repeat(readln().toInt()) {
     29   val a = readln().split(" ").map { it.toInt() }
     30   println(a.mapIndexed { i, x -> 
     31     CharArray (x) { j -> chars[i * 2 + j % 2] }
     32   }.flatMap { it.asIterable() }.joinToString(""))
     33 }
     34 ```
     35 
     36 [2087B - Шоу-матч](/contest/2087/problem/B "Kotlin Heroes: Episode 12")
     37 
     38 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest")
     39 
     40 **Tutorial**
     41 
     42 Tutorial is loading...
     43 
     44 **Solution (Neon)**
     45 
     46 ```
     47 fun main() = repeat(readln().toInt()) {
     48   val n = readln().toInt() * 2
     49   val a = readln().split(" ").map { it.toInt() }.sorted()
     50   println(if ((1 until n - 1 step 2).any { i ->
     51     a[i + 1] - a[i] < maxOf(a[i] - a[i - 1], a[i + 2] - a[i + 1])
     52   }) "NO" else "YES")
     53 }
     54 ```
     55 
     56 [2087C - Игра с монетами](/contest/2087/problem/C "Kotlin Heroes: Episode 12")
     57 
     58 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [Neon](/profile/Neon "Кандидат в мастера Neon")
     59 
     60 **Tutorial**
     61 
     62 Tutorial is loading...
     63 
     64 **Solution (Neon)**
     65 
     66 ```
     67 const val coins = "BSG"
     68 
     69 fun main() {
     70   val s = readln()
     71   val sum = Array(3) { 
     72     s.map { c -> if (c == coins[it]) 1 else 0 }
     73      .scan(0) { x, y -> x + y }
     74   }
     75   
     76   val q = readln().toInt()
     77   println((0 until q).map {
     78     val (l, r) = readln().split(" ").map { it.toInt() }
     79     val cnt = sum.map { it[r] - it[l - 1] }
     80     cnt.max() + cnt.min()
     81   }.joinToString("\n"))
     82 }
     83 ```
     84 
     85 [2087D - Заглавные или строчные?](/contest/2087/problem/D "Kotlin Heroes: Episode 12")
     86 
     87 Idea: [adedalic](/profile/adedalic "Международный мастер adedalic"), preparation: [adedalic](/profile/adedalic "Международный мастер adedalic")
     88 
     89 **Tutorial**
     90 
     91 Tutorial is loading...
     92 
     93 **Solution (adedalic)**
     94 
     95 ```
     96 import kotlin.system.exitProcess
     97 
     98 fun main() {
     99     val (nString, h) = readln().split(" ")
    100 
    101     fun ask(pos: Int): String {
    102         println("? ${pos + 1}")
    103         System.out.flush()
    104         val resp = readln()
    105         if (resp == "-1")
    106             exitProcess(0)
    107         return resp
    108     }
    109 
    110     fun isLower(s: String) = s[0].isLowerCase()
    111 
    112     val lowerCaseFirst = isLower(ask(0))
    113     fun lowerOrEqual(a: String, b: String) : Boolean {
    114         if (isLower(a) == isLower(b))
    115             return a <= b;
    116         return isLower(a) == lowerCaseFirst
    117     }
    118     var l = 0
    119     var r = nString.toInt()
    120     while (r - l > 1) {
    121         val mid = (l + r) / 2
    122         if (lowerOrEqual(ask(mid), h))
    123             l = mid
    124         else
    125             r = mid
    126     }
    127     println("! ${l + 1}")
    128 }
    129 ```
    130 
    131 [2087E - Раскрась стрелки](/contest/2087/problem/E "Kotlin Heroes: Episode 12")
    132 
    133 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [awoo](/profile/awoo "Мастер awoo")
    134 
    135 **Tutorial**
    136 
    137 Tutorial is loading...
    138 
    139 **Solution (awoo)**
    140 
    141 ```
    142 fun main() = repeat(readLine()!!.toInt()) {
    143     val n = readLine()!!.toInt()
    144     var s = readLine()!!
    145     var a = readLine()!!.split(" ").map { it.toInt() }
    146     
    147     var ans = 0.toLong()
    148     
    149     repeat(2) {
    150         var sum = 0.toLong()
    151         for (i in 0 until n) {
    152             if (s[i] == '<')
    153                 ans = maxOf(ans, sum + a[i])
    154             sum += maxOf(a[i], 0)
    155         }
    156         a = a.reversed()
    157         s = s.reversed().replace('<', '.').replace('>', '<').replace('.', '>')
    158     }
    159     
    160     println(ans)
    161 }
    162 ```
    163 
    164 [2087F - Улучшение оружия](/contest/2087/problem/F "Kotlin Heroes: Episode 12")
    165 
    166 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [Neon](/profile/Neon "Кандидат в мастера Neon")
    167 
    168 **Tutorial**
    169 
    170 Tutorial is loading...
    171 
    172 **Solution (Neon)**
    173 
    174 ```
    175 const val N = 505
    176 const val INF = 1e9.toInt()
    177 
    178 fun main() {
    179   val n = readln().toInt()
    180   val a = readln().split(" ").map { it.toInt() - 1}
    181   val b = readln().split(" ").map { it.toInt() - 1}
    182   
    183   val cnt = Array(N) { IntArray(N) { 0 } }
    184   val dp = Array(2) { Array(N) { IntArray(N) { INF } } }
    185   dp[0][0][0] = 0
    186 
    187   for (t in 0 until 2 * n) {
    188     val ct = t and 1
    189     val nt = ct xor 1
    190     
    191     if (t < n) {
    192       for (i in 0 until N) for (j in 0 until N) {
    193         if (a[t] <= i || b[t] <= j) ++cnt[i][j];
    194       } 
    195     }
    196 
    197     dp[nt].forEach { it.fill(INF) }
    198     for (i in 0 until N) for (j in 0 until N) {
    199       if (dp[ct][i][j] != INF) {
    200         val lft = minOf(t + 1, n) - i - j
    201         if (cnt[i][j] > i + j) {
    202           dp[nt][i + 1][j] = minOf(dp[nt][i + 1][j], dp[ct][i][j] + lft - 1)
    203           dp[nt][i][j + 1] = minOf(dp[nt][i][j + 1], dp[ct][i][j] + lft - 1)
    204         } else {
    205           if (t < n || lft == 0) dp[nt][i][j] = minOf(dp[nt][i][j], dp[ct][i][j] + lft)
    206         }
    207       }
    208     }
    209   }
    210 
    211   var ans = INF
    212   for (i in 0 until N) for (j in 0 until N) ans = minOf(ans, dp[0][i][j])
    213   if (ans == INF) ans = -1
    214   println(ans)
    215 }
    216 ```
    217 
    218 [2087G - Киберспорт в Берляндии](/contest/2087/problem/G "Kotlin Heroes: Episode 12")
    219 
    220 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [adedalic](/profile/adedalic "Международный мастер adedalic")
    221 
    222 **Tutorial**
    223 
    224 Tutorial is loading...
    225 
    226 **Solution (adedalic)**
    227 
    228 ```
    229 fun main() {
    230     data class ModInt(val value : Int = 0) {
    231         val MOD = 998244353
    232         operator fun plus(oth : ModInt) : ModInt {
    233             val cur = (this.value + oth.value) % MOD
    234             return ModInt(cur)
    235         }
    236         operator fun times(oth : ModInt) : ModInt {
    237             val cur = value.toLong() * oth.value % MOD
    238             return ModInt(cur.toInt())
    239         }
    240         fun pow(k: Int) : ModInt {
    241             var ans = ModInt(1)
    242             var a = ModInt(value)
    243             var curPw = k
    244             while (curPw > 0) {
    245                 if (curPw % 2 == 1)
    246                     ans *= a
    247                 a *= a
    248                 curPw /= 2
    249             }
    250             return ans
    251         }
    252         fun inverse() = this.pow(MOD - 2)
    253         override fun toString() = this.value.toString()
    254     }
    255 
    256     val n = readln().toInt()
    257     val a = readln().split(" ").map { it.toInt() }
    258 
    259     val factorials = (1..n).runningFold(ModInt(1)) { acc, it -> acc * ModInt(it) }
    260     val invFact = factorials.map { it.inverse() }
    261 
    262     fun choose(n : Int, k : Int) : ModInt {
    263         if (k < 0 || n < k)
    264             return ModInt(0)
    265         return factorials[n] * invFact[k] * invFact[n - k]
    266     }
    267 
    268     val sum = a.sumOf { it.toLong() }
    269     val delta = List(n) { n - it - 1 - a[it] }.sortedDescending()
    270 
    271     var ansVal = sum
    272     var ansCnt = ModInt(1)
    273 
    274     var curSum = 0L
    275     var lf = 0
    276     var rg = 0
    277     for (k in 1..n) {
    278         curSum += delta[k - 1]
    279         while (delta[lf] > delta[k - 1])
    280             lf++
    281         while (rg < delta.size && delta[rg] >= delta[k - 1])
    282             rg++
    283         val curVal = sum + curSum - k.toLong() * (k - 1) / 2
    284         val curCnt = choose(rg - lf, k - lf)
    285         if (ansVal < curVal) {
    286             ansVal = curVal
    287             ansCnt = ModInt(0)
    288         }
    289         if (ansVal == curVal) {
    290             ansCnt += curCnt
    291         }
    292     }
    293     println("$ansVal $ansCnt")
    294 }
    295 ```
    296 
    297 [2087H - Ним со специальными числами](/contest/2087/problem/H "Kotlin Heroes: Episode 12")
    298 
    299 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest")
    300 
    301 **Tutorial**
    302 
    303 Tutorial is loading...
    304 
    305 **Solution (BledDest)**
    306 
    307 ```
    308 import java.util.*
    309 
    310 data class Node(var x: Int = 0, var a: Int = 0, var b: Int = 0)
    311 
    312 fun get(n: Node, x: Int): Int {
    313     return when {
    314         n.x == -1 -> x
    315         x < n.x -> n.a
    316         else -> n.b
    317     }
    318 }
    319 
    320 fun combine(a: Node, b: Node): Node {
    321     return when {
    322         a.x == -1 -> b
    323         b.x == -1 -> a
    324         else -> Node(a.x, get(b, a.a), get(b, a.b))
    325     }
    326 }
    327 
    328 fun emptyNode(): Node {
    329     return Node(-1, -1, -1)
    330 }
    331 
    332 fun fromLength(len: Int): Node {
    333     return if (len == -1) emptyNode() else Node(len, len, len - 1)
    334 }
    335 
    336 const val N = 300003
    337 const val M = 300001
    338 
    339 val S = sortedSetOf<Int>()
    340 val T = Array<Node>(4 * N) { emptyNode() }
    341 
    342 fun recalc(v: Int) {
    343     T[v] = combine(T[v * 2 + 1], T[v * 2 + 2])
    344 }
    345 
    346 fun build(v: Int, l: Int, r: Int) {
    347     if (l == r - 1) {
    348         T[v] = emptyNode()
    349     } else {
    350         val m = (l + r) / 2
    351         build(v * 2 + 1, l, m)
    352         build(v * 2 + 2, m, r)
    353         recalc(v)
    354     }
    355 }
    356 
    357 fun upd(v: Int, l: Int, r: Int, pos: Int, x: Int) {
    358     if (l == r - 1) {
    359         T[v] = fromLength(x)
    360     } else {
    361         val m = (l + r) / 2
    362         if (pos < m) upd(v * 2 + 1, l, m, pos, x)
    363         else upd(v * 2 + 2, m, r, pos, x)
    364         recalc(v)
    365     }
    366 }
    367 
    368 fun get(v: Int, l: Int, r: Int, L: Int, R: Int): Node {
    369     if (L >= R) return emptyNode()
    370     if (L == l && R == r) return T[v]
    371     val m = (l + r) / 2
    372     return combine(get(v * 2 + 1, l, m, L, minOf(m, R)), get(v * 2 + 2, m, r, maxOf(L, m), R))
    373 }
    374 
    375 fun prepare() {
    376     build(0, 0, M)
    377     upd(0, 0, M, 0, 0)
    378     S.add(0)
    379 }
    380 
    381 fun insertValue(x: Int) {
    382     val it = S.ceiling(x)
    383     if (it != null) {
    384         upd(0, 0, M, it, it - x)
    385     }
    386     S.lower(x)?.let { upd(0, 0, M, x, x - it) }
    387     S.add(x)
    388 }
    389 
    390 fun eraseValue(x: Int) {
    391     upd(0, 0, M, x, -1)
    392     S.remove(x)
    393     val it = S.ceiling(x)
    394     if (it != null) {
    395         val y = it
    396         S.lower(y)?.let { upd(0, 0, M, y, y - it) }
    397     }
    398 }
    399 
    400 fun getGrundy(x: Int): Int {
    401     val n = get(0, 0, M, 0, x)
    402     val it = S.lower(x)
    403     val y = it ?: return x
    404     val valY = get(n, 0)
    405     val dist = x - y
    406     return if (dist <= valY) dist - 1 else dist
    407 }
    408 
    409 fun main() {
    410     val q = readln().toInt()
    411     
    412     prepare()
    413     println((0 until q).map {
    414         val params = readln().split(" ").map { it.toInt() }
    415         val (t, x) = params.take(2)
    416         if (t == 1) {
    417             if (S.contains(x)) eraseValue(x) else insertValue(x)
    418             null
    419         } else {
    420             val res = params.drop(2).fold(0) { r, y -> r xor getGrundy(y) }
    421             if (res == 0) "Second" else "First"
    422         }
    423     }.filterNotNull().joinToString("\n"))
    424 }
    425 ```
    426 
    427 [2087I - Гамильтоново разбиение](/contest/2087/problem/I "Kotlin Heroes: Episode 12")
    428 
    429 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest")
    430 
    431 **Tutorial**
    432 
    433 Tutorial is loading...
    434 
    435 **Solution (BledDest)**
    436 
    437 ```
    438 fun main() {
    439     val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    440     val x = IntArray(m)
    441     val y = IntArray(m)
    442     val edgeId = mutableMapOf<Pair<Int, Int>, Int>()
    443     val inDeg = IntArray(n)
    444     val outDeg = IntArray(n)
    445 
    446     for (i in 0 until m) {
    447         val (xi, yi) = readLine()!!.split(" ").map { it.toInt() }
    448         x[i] = xi - 1
    449         y[i] = yi - 1
    450         edgeId[Pair(x[i], y[i])] = i
    451         inDeg[y[i]]++
    452         outDeg[x[i]]++
    453     }
    454 
    455     var c = 0
    456     for (i in 0 until n) {
    457         c = maxOf(c, inDeg[i], outDeg[i])
    458     }
    459 
    460     val color = Array(n * 2) { IntArray(c) { -1 } }
    461     for (i in 0 until m) {
    462         val a = x[i]
    463         val b = y[i] + n
    464         var ca = 0
    465         while (color[a][ca] != -1) ca++
    466         var cb = 0
    467         while (color[b][cb] != -1) cb++
    468         color[a][ca] = b
    469         color[b][cb] = a
    470         if (ca != cb) {
    471             var cur = b
    472             while (cur != -1) {
    473                 val temp = color[cur][cb]
    474                 color[cur][cb] = color[cur][ca]
    475                 color[cur][ca] = temp
    476                 cur = color[cur][cb]
    477                 val tempCa = ca
    478                 ca = cb
    479                 cb = tempCa
    480             }
    481         }
    482     }
    483 
    484     val ans = MutableList(m) { 0 }
    485     for (i in 0 until n) {
    486         for (j in 0 until c) {
    487             if (color[i][j] != -1) {
    488                 ans[edgeId[Pair(i, color[i][j] - n)]!!] = j
    489             }
    490         }
    491     }
    492 
    493     val xsAdd = mutableListOf<Int>()
    494     val ysAdd = mutableListOf<Int>()
    495     var k = 0
    496     for (i in 0 until c) {
    497         val nxt = IntArray(n) { -1 }
    498         val pre = IntArray(n) { -1 }
    499         for (j in 0 until m) {
    500             if (ans[j] == i) {
    501                 nxt[x[j]] = y[j]
    502                 pre[y[j]] = x[j]
    503             }
    504         }
    505         val parts = mutableListOf<Pair<Int, Int>>()
    506         for (j in 0 until n) {
    507             if (pre[j] == -1) {
    508                 var l = j
    509                 var r = j
    510                 while (nxt[r] != -1) r = nxt[r]
    511                 parts.add(Pair(l, r))
    512             }
    513         }
    514         val p = parts.size
    515         k += p
    516         for (j in 0 until p) {
    517             xsAdd.add(parts[j].second)
    518             ysAdd.add(parts[(j + 1) % p].first)
    519         }
    520         for (j in 0 until p) {
    521             ans += i
    522         }
    523     }
    524 
    525     println(k)
    526     for (i in 0 until k) {
    527         println("${xsAdd[i] + 1} ${ysAdd[i] + 1}")
    528     }
    529     println(c)
    530     for (x in ans) {
    531         print("${x + 1} ")
    532     }
    533     println()
    534 }
    535 ```