codeforces-scrape

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

1346.md (14156B)


      1 Source: https://codeforces.com/blog/entry/78124
      2 
      3 First of all, I would like to thank all of the testers: [elizarov](/profile/elizarov "Candidate Master elizarov"), [darnley](/profile/darnley "Grandmaster darnley"), [IlyaLos](/profile/IlyaLos "International Master IlyaLos"), [_overrated_](/profile/_overrated_ "Master _overrated_"), [SergeyMelnikov](/profile/SergeyMelnikov "Master SergeyMelnikov"), [winger](/profile/winger "International Grandmaster winger"), [FieryPhoenix](/profile/FieryPhoenix "Master FieryPhoenix"), [infinitepro](/profile/infinitepro "Expert infinitepro"), [Sho](/profile/Sho "Expert Sho"), [GrandDaddy](/profile/GrandDaddy "Expert GrandDaddy"), [bfs.07](/profile/bfs.07 "Expert bfs.07"), [spookywooky](/profile/spookywooky "Expert spookywooky"). Also huge thanks to co-authors of the contest: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), [Neon](/profile/Neon "Candidate Master Neon"), [Roms](/profile/Roms "Master Roms"), [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 [1346A - Color Revolution](/contest/1346/problem/A "Kotlin Heroes: Episode 4")
     10 
     11 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [awoo](/profile/awoo "Grandmaster awoo")
     12 
     13 **Tutorial**
     14 
     15 Tutorial is loading...
     16 
     17 **Solution (elizarov)**
     18 
     19 ```
     20 fun main() {
     21     repeat(readLine()!!.toInt()) {
     22         val (n, k) = readLine()!!.split(" ").map { it.toInt() }
     23         val n1 = n / (1 + k + k * k + k * k * k)
     24         val n2 = n1 * k
     25         val n3 = n2 * k
     26         val n4 = n3 * k
     27         println("$n1 $n2 $n3 $n4")
     28     }
     29 }
     30 ```
     31 
     32 [1346B - Boot Camp](/contest/1346/problem/B "Kotlin Heroes: Episode 4")
     33 
     34 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon")
     35 
     36 **Tutorial**
     37 
     38 Tutorial is loading...
     39 
     40 **Solution (elizarov)**
     41 
     42 ```
     43 fun main() {
     44     repeat(readLine()!!.toInt()) {
     45         val (n, k1, k2) = readLine()!!.split(" ").map { it.toInt() }
     46         val s = readLine()!!
     47         var m = 0
     48         var prev = 0
     49         for (c in s) {
     50             if (c == '1') {
     51                 prev = minOf(k2 - prev, k1)
     52                 m += prev
     53             } else {
     54                 prev = 0
     55             }
     56         }
     57         println(m)
     58     }
     59 }
     60 ```
     61 
     62 [1346C - Spring Cleaning](/contest/1346/problem/C "Kotlin Heroes: Episode 4")
     63 
     64 Idea: [vovuh](/profile/vovuh "Master vovuh"), preparation: [vovuh](/profile/vovuh "Master vovuh")
     65 
     66 **Tutorial**
     67 
     68 Tutorial is loading...
     69 
     70 **Solution (elizarov)**
     71 
     72 ```
     73 fun main() {
     74     repeat(readLine()!!.toInt()) {
     75         val (n, k, x, y) = readLine()!!.split(" ").map { it.toInt() }
     76         val a = readLine()!!.split(" ").map { it.toInt() }.sorted()
     77         val maxSum = k * n.toLong()
     78         var sum = 0L
     79         var ans = 0
     80         var ok = true
     81         var i = 0
     82         while (i < n && sum + a[i] <= maxSum) {
     83             sum += a[i]
     84             if (ok && a[i] > k) {
     85                 ok = false
     86                 ans = (n - i) * x // can simply drop the rest 
     87             }
     88             i++
     89         }
     90         ans = if (ok) (n - i) * x // drop the rest
     91             else minOf(ans, (n - i) * x + y) // drop the rest & rearrange
     92         println(ans)
     93     }
     94 }
     95 ```
     96 
     97 [1346D - Constructing the Dungeon](/contest/1346/problem/D "Kotlin Heroes: Episode 4")
     98 
     99 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), preparation: [Neon](/profile/Neon "Candidate Master Neon")
    100 
    101 **Tutorial**
    102 
    103 Tutorial is loading...
    104 
    105 **Solution (elizarov)**
    106 
    107 ```
    108 fun main() {
    109     repeat(readLine()!!.toInt()) {
    110         val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    111         val e = List(m) {
    112             val (u, v, w) = readLine()!!.split(" ").map { it.toInt() }
    113             Tun(u - 1, v - 1, w)
    114         }
    115         val a = solveDungeon(n, e)
    116         if (a != null) {
    117             println("YES")
    118             println(a.joinToString(" "))
    119         } else {
    120             println("NO")
    121         }
    122     }
    123 }
    124 
    125 private class Tun(val u: Int, val v: Int, val w: Int)
    126 
    127 private fun solveDungeon(n: Int, e: List<Tun>): IntArray? {
    128     val a = IntArray(n)
    129     for (t in e.sortedByDescending { it.w }) {
    130         if (a[t.u] == 0) a[t.u] = t.w
    131         if (a[t.v] == 0) a[t.v] = t.w
    132         if (t.w != minOf(a[t.u], a[t.v])) return null
    133     }
    134     return a
    135 }
    136 ```
    137 
    138 [1346E - Magic Tricks](/contest/1346/problem/E "Kotlin Heroes: Episode 4")
    139 
    140 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon")
    141 
    142 **Tutorial**
    143 
    144 Tutorial is loading...
    145 
    146 **Solution (elizarov)**
    147 
    148 ```
    149 fun main() {
    150     val (n, m, k) = readLine()!!.split(" ").map { it.toInt() }
    151     val inf = Int.MAX_VALUE - 1
    152     val s = IntArray(n) { inf }
    153     s[k - 1] = 0
    154     repeat(m) {
    155         val (x, y) = readLine()!!.split(" ").map { it.toInt() - 1 }
    156         val sx = s[x]
    157         val sy = s[y]
    158         s[x] = minOf(sx + 1, sy)
    159         s[y] = minOf(sy + 1, sx)
    160     }
    161     println(s.joinToString(" ") { (if (it == inf) -1 else it).toString() })
    162 }
    163 ```
    164 
    165 [1346F - Dune II: Battle For Arrakis](/contest/1346/problem/F "Kotlin Heroes: Episode 4")
    166 
    167 Idea: [vovuh](/profile/vovuh "Master vovuh"), preparation: [vovuh](/profile/vovuh "Master vovuh")
    168 
    169 **Tutorial**
    170 
    171 Tutorial is loading...
    172 
    173 **Solution (elizarov)**
    174 
    175 ```
    176 import kotlin.math.*
    177 
    178 fun main() {
    179     val (n, m, q) = readLine()!!.split(" ").map { it.toInt() }
    180     val a = Array(n) { readLine()!!.split(" ").map { it.toInt() }.toIntArray() }
    181     val rs = LongArray(n) { i -> (0 until m).map { j -> a[i][j].toLong() }.sum() }.toDistSum()
    182     val cs = LongArray(m) { j -> (0 until n).map { i -> a[i][j].toLong() }.sum() }.toDistSum()
    183     fun ans() = rs.min()!! + cs.min()!!
    184     print(ans())
    185     repeat(q) {
    186         val (x1, y1, z) = readLine()!!.split(" ").map { it.toInt() }
    187         val (x, y) = (x1 - 1) to (y1 - 1)
    188         val d = (z - a[x][y]).toLong()
    189         for (i in 0 until n) rs[i] += abs(x - i) * d
    190         for (j in 0 until m) cs[j] += abs(y - j) * d
    191         a[x][y] = z
    192         print(" ${ans()}")
    193     }
    194 }
    195 
    196 private fun LongArray.toDistSum(): LongArray {
    197     val s = LongArray(size)
    198     var su = 0L
    199     var wsu = 0L
    200     var sd = 0L
    201     var wsd = 0L
    202     for (i in 0 until size) {
    203         sd += get(i)
    204         wsd += (i + 1) * get(i)
    205     }
    206     for (i in 0 until size) {
    207         wsd -= sd
    208         sd -= get(i)
    209         s[i] = wsu + wsd
    210         su += get(i)
    211         wsu += su
    212     }
    213     return s
    214 }
    215 ```
    216 
    217 [1346G - Two IP Cameras](/contest/1346/problem/G "Kotlin Heroes: Episode 4")
    218 
    219 Idea: [adedalic](/profile/adedalic "International Master adedalic"), preparation: [adedalic](/profile/adedalic "International Master adedalic")
    220 
    221 **Tutorial**
    222 
    223 Tutorial is loading...
    224 
    225 **Solution (elizarov)**
    226 
    227 ```
    228 fun main() {
    229     val (k, n) = readLine()!!.split(" ").map { it.toInt() }
    230     val p = readLine()!!.split(" ").map { it.toInt() }
    231     val x = readLine()!!.split(" ").map { it.toInt() }
    232     val c = solveCams(n, p, x)
    233     if (c == null) {
    234         println("NO")
    235     } else {
    236         println("YES")
    237         println("${c.s1} ${c.p1}")
    238         println("${c.s2} ${c.p2}")
    239     }
    240 }
    241 
    242 private class Cams(val s1: Int, val p1: Int, val s2: Int, val p2: Int)
    243 
    244 private tailrec fun gcd(x: Int, y: Int): Int = if (y == 0) x else gcd(y, x % y)
    245 
    246 private fun solveCams(n: Int, p: List<Int>, x: List<Int>): Cams? {
    247     fun place2(s1: Int, p1: Int): Cams? {
    248         val f = BooleanArray(n) { j -> (x[j] - s1) % p1 == 0 }
    249         val i = f.indexOf(false)
    250         if (i < 0) return Cams(s1, p1, s1, p1)
    251         val s2 = x[i]
    252         var j = i + 1
    253         while (j < n && f[j]) j++
    254         if (j >= n) return Cams(s1, p1, s2, p[0])
    255         var p2m = x[j] - s2
    256         while (++j < n) {
    257             if (!f[j]) p2m = gcd(p2m, x[j] - s2)
    258         }
    259         for (p2 in p) if (p2m % p2 == 0) {
    260             return Cams(s1, p1, s2, p2)
    261         }
    262         return null
    263     }
    264     fun tryPlace2(s1: Int, p1m: Int): Cams? {
    265         for (p1 in p) if (p1m % p1 == 0) {
    266             place2(s1, p1)?.let { return it }
    267         }
    268         return null
    269     }
    270     if (n == 2) return Cams(x[0], p[0], x[1], p[0])
    271     for (t1 in 1..2) {
    272         tryPlace2(x[0], x[t1] - x[0])?.let { return it }
    273     }
    274     return tryPlace2(x[1], x[2] - x[1])
    275 }
    276 ```
    277 
    278 [1346H - Game with Segments](/contest/1346/problem/H "Kotlin Heroes: Episode 4")
    279 
    280 Idea: [Roms](/profile/Roms "Master Roms"), preparation: [Roms](/profile/Roms "Master Roms")
    281 
    282 **Tutorial**
    283 
    284 Tutorial is loading...
    285 
    286 **Solution (tourist)**
    287 
    288 ```
    289 import java.lang.AssertionError
    290  
    291 private fun readLn() = readLine()!! // string line
    292 private fun readInt() = readLn().toInt() // single int
    293 private fun readLong() = readLn().toLong() // single long
    294 private fun readDouble() = readLn().toDouble() // single double
    295 private fun readStrings() = readLn().split(" ") // list of strings
    296 private fun readInts() = readStrings().map { it.toInt() } // list of ints
    297 private fun readLongs() = readStrings().map { it.toLong() } // list of longs
    298 private fun readDoubles() = readStrings().map { it.toDouble() } // list of doubles
    299  
    300 private fun myAssert(x: Boolean) {
    301     if (!x) {
    302         throw AssertionError()
    303     }
    304 }
    305  
    306 fun main(args: Array<String>) {
    307     var (tt, n) = readInts()
    308     var lstart = IntArray(tt)
    309     var rstart = IntArray(tt)
    310     for (i in 0 until tt) {
    311         var (x, y) = readInts()
    312         lstart[i] = x
    313         rstart[i] = y
    314     }
    315     var l = ArrayList<Int>()
    316     var r = ArrayList<Int>()
    317     for (i in 0 until n) {
    318         var (x, y) = readInts()
    319         l.add(x)
    320         r.add(y)
    321     }
    322     var order = ArrayList<Int>()
    323     for (i in 0 until n) {
    324         order.add(i)
    325     }
    326     order.sortWith(compareBy({l[it] + r[it]}, {l[it]}))
    327     val inf = 787788789
    328     fun getDistance(L: Int, R: Int) : Int {
    329         var low = 0
    330         var high = n
    331         while (low < high) {
    332             var mid = (low + high) / 2
    333             if (l[order[mid]] + r[order[mid]] < L + R ||
    334                 (l[order[mid]] + r[order[mid]] == L + R && l[order[mid]] < L)) {
    335                 low = mid + 1
    336             } else {
    337                 high = mid
    338             }
    339         }
    340         if (low < n && l[order[low]] + r[order[low]] == L + R) {
    341             return l[order[low]] - L
    342         }
    343         return inf
    344     }
    345     var res = IntArray(tt) {-1}
    346     for (qq in 0 until tt) {
    347         var L = lstart[qq]
    348         var R = rstart[qq]
    349         var a = getDistance(L, R - 2) + 1
    350         var b = getDistance(L, R)
    351         var c = getDistance(L + 2, R) + 1
    352         res[qq] = maxOf(minOf(a, b), minOf(b, c))
    353         if (res[qq] >= inf) {
    354             res[qq] = -1
    355         }
    356     }
    357     println(res.joinToString(" "))
    358 }
    359 ```
    360 
    361 [1346I - Pac-Man 2.0](/contest/1346/problem/I "Kotlin Heroes: Episode 4")
    362 
    363 Idea: [Neon](/profile/Neon "Candidate Master Neon") and [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon")
    364 
    365 **Tutorial**
    366 
    367 Tutorial is loading...
    368 
    369 **Solution (Ne0n25)**
    370 
    371 ```
    372 import kotlin.math.abs
    373 
    374 fun main() {
    375     val INF = 1e9.toInt()
    376     val INF64 = 1e18.toLong()
    377     val LOG = 60
    378     var (n, m, q, s) = readLine()!!.split(' ').map { it.toInt() }
    379     s--
    380     val a = readLine()!!.split(' ').map { it.toInt() }
    381     
    382     val summask = LongArray(1 shl n) { 0 }
    383     for (mask in 0 until (1 shl n)) {
    384         for (i in 0 until n) {
    385             if ((mask and (1 shl i)) > 0)
    386                 summask[mask] += a[i].toLong()
    387         }
    388     }
    389 
    390     val d = Array(n) { IntArray(n) { INF } }
    391     for (i in 0 until m) {
    392         val (x, y) = readLine()!!.split(' ').map { it.toInt() }
    393         d[x - 1][y - 1] = 1
    394     }
    395     
    396     val C = readLine()!!.split(' ').map { it.toLong() }
    397 
    398     for (k in 0 until n) {
    399         for (i in 0 until n) {
    400             for (j in 0 until n)
    401                 d[i][j] = minOf(d[i][j], d[i][k] + d[k][j])
    402         }
    403     }
    404 
    405     val dp = Array(n) { Array(n) { IntArray(1 shl n) { INF } } }
    406     for (st in 0 until n) {
    407         dp[st][st][1 shl st] = 0
    408 
    409         for (mask in 0 until (1 shl n)) {
    410             for (i in 0 until n) {
    411                 if ((mask and (1 shl i)) == 0)
    412                     continue
    413                 for (j in 0 until n) {
    414                     if ((mask and (1 shl j)) > 0)
    415                         continue
    416                     dp[st][j][mask or (1 shl j)] =
    417                             minOf(dp[st][j][mask or (1 shl j)], dp[st][i][mask] + d[i][j])
    418                 }
    419             }
    420         }
    421     }
    422 
    423     val bst = Array(n) { LongArray(n * n) { 0 } }
    424     for (i in 0 until n) {
    425         for (mask in 0 until (1 shl n)) {
    426             if ((mask and (1 shl i)) > 0) {
    427                 for (j in 0 until n) {
    428                     if (dp[i][j][mask] != INF)
    429                         bst[i][dp[i][j][mask]] = maxOf(bst[i][dp[i][j][mask]], summask[mask])
    430                 }
    431             }
    432         }
    433     }
    434 
    435     val steps = Array(LOG) { Array(n) { LongArray(n) { INF64 } } }
    436     for (i in 0 until n) {
    437         for (j in 0 until n)
    438             steps[0][i][j] = dp[i][j][(1 shl n) - 1].toLong()
    439     }
    440 
    441     for (t in 1 until LOG) {
    442         for (i in 0 until n) {
    443             for (j in 0 until n) {
    444                 for (k in 0 until n)
    445                     steps[t][i][j] = minOf(steps[t][i][j], steps[t - 1][i][k] + steps[t - 1][k][j])
    446             }
    447         }
    448     }
    449 
    450     for (qr in 0 until q) {
    451         val sum = summask[(1 shl n) - 1]
    452         val need = C[qr] / sum
    453 
    454         var cur = LongArray(n) { INF64 }
    455         cur[s] = 0
    456 
    457         for (t in 0 until LOG - 1) {
    458             if ((need and (1L shl t)) > 0) {
    459                 val ncur = LongArray(n) { INF64 }
    460                 for (i in 0 until n) {
    461                     for (j in 0 until n)
    462                         ncur[i] = minOf(ncur[i], steps[t][j][i] + cur[j])
    463                 }
    464                 cur = ncur
    465             }
    466         }
    467 
    468         var ans = INF64
    469         for(i in 0 until n) {
    470             val lft = C[qr] % sum
    471             for (j in 0 until n * n) {
    472             	if (bst[i][j] >= lft)
    473             		ans = minOf(ans, cur[i] + j);
    474             }
    475         }
    476 
    477         println(ans)
    478     }
    479 }
    480 ```