codeforces-scrape

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

1170.md (15057B)


      1 Source: https://codeforces.com/blog/entry/67280
      2 
      3 [1170A - Three Integers Again](/contest/1170/problem/A "Kotlin Heroes: Episode 1")
      4 
      5 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh")
      6 
      7 Solution: [elizarov](/profile/elizarov "Candidate Master elizarov")
      8 
      9 **Tutorial**
     10 
     11 Tutorial is loading...
     12 
     13 **Solution**
     14 
     15 ```
     16 fun main() {
     17     val q = readLine()!!.toInt()
     18     repeat(q) {
     19         val (x, y) = readLine()!!.split(" ").map { it.toInt() }.sorted()
     20         println("1 ${x - 1} ${y - x + 1}")
     21     }
     22 }
     23 ```
     24 
     25 [1170B - Bad Days](/contest/1170/problem/B "Kotlin Heroes: Episode 1")
     26 
     27 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     28 
     29 Solution: [elizarov](/profile/elizarov "Candidate Master elizarov")
     30 
     31 **Tutorial**
     32 
     33 Tutorial is loading...
     34 
     35 **Solution**
     36 
     37 ```
     38 fun main() {
     39     val n = readLine()!!.toInt()
     40     val a = readLine()!!.split(" ").map { it.toInt() }
     41     var m1 = 0
     42     var m2 = 0
     43     var c = 0
     44     for (x in a) {
     45         if (m2 > x) {
     46             c++
     47         }
     48         when {
     49             x > m1 -> {
     50                 m2 = m1
     51                 m1 = x
     52             }
     53             x > m2 -> {
     54                 m2 = x
     55             }
     56         }
     57     }
     58     println(c)
     59 }
     60 ```
     61 
     62 [1170C - Minus and Minus Give Plus](/contest/1170/problem/C "Kotlin Heroes: Episode 1")
     63 
     64 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     65 
     66 Solution: [elizarov](/profile/elizarov "Candidate Master elizarov")
     67 
     68 **Tutorial**
     69 
     70 Tutorial is loading...
     71 
     72 **Solution**
     73 
     74 ```
     75 fun main() {
     76     val k = readLine()!!.toInt()
     77     repeat(k) {
     78         val s = readLine()!!
     79         val t = readLine()!!
     80         println(if (solve(s, t)) "YES" else "NO")
     81     }
     82 }
     83 
     84 private fun solve(s: String, t: String): Boolean {
     85     var i = 0
     86     var j = 0
     87     while (i < s.length && j < t.length) {
     88         when (s[i]) {
     89             t[j] -> {}
     90             '+' -> return false
     91             else -> { // '-' -> '+'
     92                 i++
     93                 if (i >= s.length || s[i] != '-') return false
     94             }
     95         }
     96         i++
     97         j++
     98     }
     99     return i == s.length && j == t.length
    100 }
    101 ```
    102 
    103 [1170D - Decoding of Integer Sequences](/contest/1170/problem/D "Kotlin Heroes: Episode 1")
    104 
    105 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    106 
    107 Solution: [elizarov](/profile/elizarov "Candidate Master elizarov")
    108 
    109 **Tutorial**
    110 
    111 Tutorial is loading...
    112 
    113 **Solution**
    114 
    115 ```
    116 import java.util.*
    117 
    118 fun main() {
    119     val m = readLine()!!.toInt()
    120     val b = readLine()!!.split(" ").map { it.toInt() }
    121     val n = b.count { it == -1 }
    122     val a = Array(n) { ArrayList<Int>() }
    123     val ix = LinkedList<Int>((0 until n).toList())
    124     var iter = ix.iterator()
    125     for (x in b) {
    126         if (!iter.hasNext()) iter = ix.iterator()
    127         val i = iter.next()
    128         if (x == -1) {
    129             iter.remove()
    130         } else {
    131             a[i].add(x)
    132         }
    133     }
    134     println(n)
    135     println(a.joinToString("\n") {
    136         "${it.size} ${it.joinToString(" ")}"
    137     })
    138 }
    139 ```
    140 
    141 [1170E - Sliding Doors](/contest/1170/problem/E "Kotlin Heroes: Episode 1")
    142 
    143 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    144 
    145 Solution: [elizarov](/profile/elizarov "Candidate Master elizarov")
    146 
    147 **Tutorial**
    148 
    149 Tutorial is loading...
    150 
    151 **Solution**
    152 
    153 ```
    154 fun main() {
    155     val (n, m) = readInts()
    156     val a = readInts().toIntArray()
    157     val q = readInt()
    158     val b = IntArray(4 * a.size)
    159 
    160     fun buildTree(il: Int, ir: Int, p: Int): Int {
    161         val s = if (il == ir) {
    162             a[il]
    163         } else {
    164             val im = (il + ir) / 2
    165             buildTree(il, im, 2 * p + 1) + buildTree(im + 1, ir, 2 * p + 2)
    166         }
    167         b[p] = s
    168         return s
    169     }
    170 
    171     buildTree(0, n - 1, 0)
    172     val ans = List(q) {
    173         val w = readInts().drop(1) + (m + 1) // sentinel
    174         if (solveDoors(n, m, b, w)) "YES" else "NO"
    175     }.joinToString("\n")
    176     println(ans)
    177 }
    178 
    179 private fun solveDoors(n: Int, m: Int, b: IntArray, w: List<Int>): Boolean {
    180     var pp = 0
    181     var i = 0
    182     var rem = 0
    183 
    184     fun queryTree(il: Int, ir: Int, p: Int, i: Int): Int {
    185         if (il == i && rem >= b[p]) {
    186             rem -= b[p]
    187             return ir + 1
    188         }
    189         if (il == ir) return i
    190         val im = (il + ir) / 2
    191         if (i > im) return queryTree(im + 1, ir, 2 * p + 2, i)
    192         val j = queryTree(il, im,2 * p + 1, i)
    193         if (j <= im) return j
    194         return queryTree(im + 1, ir,2 * p + 2, im + 1)
    195     }
    196 
    197     for (cp in w) {
    198         rem = cp - pp - 1
    199         i = queryTree(0, n - 1, 0, i)
    200         if (i >= n) return true
    201         pp = cp
    202     }
    203     return false
    204 }
    205 
    206 private fun readInt() = readLine()!!.toInt()
    207 private fun readInts() = readLine()!!.split(" ").map { it.toInt() }
    208 ```
    209 
    210 [1170F - Wheels](/contest/1170/problem/F "Kotlin Heroes: Episode 1")
    211 
    212 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), [vovuh](/profile/vovuh "Candidate Master vovuh"), [pashka](/profile/pashka "Grandmaster pashka")
    213 
    214 Solution: [Benq](/profile/Benq "Legendary Grandmaster Benq")
    215 
    216 **Tutorial**
    217 
    218 Tutorial is loading...
    219 
    220 **Solution**
    221 
    222 ```
    223 import java.util.*
    224 
    225 fun next() = readLine()!!
    226 fun nextInt() = next().toInt()
    227 fun nextInts() = next().split(" ").map { it.toInt() }
    228 fun nextLongs() = next().split(" ").map { it.toLong() }
    229 
    230 fun solve() {
    231     val (n,m,k) = nextInts()
    232     var A = nextLongs()
    233     var a = arrayListOf<Long>()
    234     a.addAll(A)
    235     a.sort()
    236     var ans = (1e18).toLong()
    237     var ind = 0
    238     var above:Long = 0
    239     var below:Long = 0
    240     for (i in 0..m-1) above += a[i]-a[0]
    241     for (i in 0..n-m) {
    242         val des = i+(m-1)/2
    243         while (ind < des) { // try to get closer to median if possible
    244             if (below+(a[ind+1]-a[ind])*(ind+1-i) <= k) {
    245                 below += (a[ind+1]-a[ind])*(ind+1-i)
    246                 above -= (a[ind+1]-a[ind])*(i+m-1-ind) // ind+1 to i+m-1
    247                 ind ++
    248             } else break
    249         }
    250         assert (k >= below)
    251         if (ind < des) {
    252             var oops: Long = (k-below)/(ind+1-i)
    253             ans = minOf(ans,below+above-(i+m-1-ind)*oops+(ind+1-i)*oops)
    254             assert(i+m-1-ind >= ind+1-i)
    255         } else ans = minOf(ans,above+below)
    256         if (i < n-m) {
    257             below -= a[ind]-a[i]
    258             above += a[i+m]-a[ind]
    259         }
    260     }
    261     print(ans)
    262 }
    263 
    264 fun main(args: Array<String>) {
    265     val t = 1
    266     for (i in 0..t-1) solve()
    267 }
    268 ```
    269 
    270 [1170G - Graph Decomposition](/contest/1170/problem/G "Kotlin Heroes: Episode 1")
    271 
    272 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    273 
    274 Solution: [elizarov](/profile/elizarov "Candidate Master elizarov")
    275 
    276 **Tutorial**
    277 
    278 Tutorial is loading...
    279 
    280 **Solution**
    281 
    282 ```
    283 fun main() {
    284     solveEuler()
    285 }
    286 
    287 class E(
    288     val y: Int,
    289     var c: Int = 0
    290 )
    291 
    292 class Edges {
    293     private val e = HashMap<Int, E>(2)
    294     private val c = ArrayList<E>(2)
    295     private var first = 0
    296 
    297     fun degree() = c.sumBy { it.c }
    298 
    299     fun add(y: Int) {
    300         val cur = e.getOrPut(y) { E(y) }
    301         if (cur.c == 0) c.add(cur)
    302         cur.c++
    303     }
    304 
    305     fun first() = c[first].y
    306 
    307     fun hasNext() = first < c.size
    308 
    309     fun rem(y: Int) {
    310         val cur = e.getValue(y)
    311         if (--cur.c == 0) {
    312             while (first < c.size && c[first].c == 0) first++
    313         }
    314     }
    315 }
    316 
    317 private fun solveEuler() {
    318     val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    319     val g = Array(n) { Edges() }
    320     repeat(m) {
    321         val (x, y) = readLine()!!.split(" ").map { it.toInt() - 1 }
    322         g[x].add(y)
    323         g[y].add(x)
    324     }
    325     if (!g.all { it.degree() % 2 == 0 }) {
    326         println("NO")
    327     } else {
    328         val c = ArrayList<List<Int>>()
    329         var start = 0
    330         val v = IntArray(n) { -1 }
    331         while (true) {
    332             while (start < n && !g[start].hasNext()) start++
    333             if (start >= n) break
    334             val list = ArrayList<Int>()
    335             var x = start
    336             while (true) {
    337                 v[x] = list.size
    338                 list.add(x)
    339                 val y = g[x].first()
    340                 g[x].rem(y)
    341                 g[y].rem(x)
    342                 if (y == start) break
    343                 if (v[y] >= 0) {
    344                     val d = list.subList(v[y], list.size)
    345                     c.add(d.toList())
    346                     for (z in d) v[z] = -1
    347                     d.clear()
    348                 }
    349                 x = y
    350             }
    351             c.add(list)
    352             for (z in list) v[z] = -1
    353         }
    354         println("YES")
    355         println(c.size)
    356         val ans = c.joinToString("\n") { list ->
    357             "${list.size + 1} ${list.joinToString(" ") { (it + 1).toString() }} ${list[0] + 1}"
    358         }
    359         println(ans)
    360     }
    361 }
    362 ```
    363 
    364 [1170H - Longest Saw](/contest/1170/problem/H "Kotlin Heroes: Episode 1")
    365 
    366 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    367 
    368 Solution: [pashka](/profile/pashka "Grandmaster pashka")
    369 
    370 **Tutorial**
    371 
    372 Tutorial is loading...
    373 
    374 **Solution**
    375 
    376 ```
    377 import java.io.BufferedReader
    378 import java.io.IOException
    379 import java.io.InputStreamReader
    380 import java.io.PrintWriter
    381 import java.util.*
    382 
    383 /**
    384  * @author: pashka
    385  */
    386 
    387 fun solve(a: IntArray): IntArray {
    388     val n = a.size
    389     var l = 0
    390     var r = a.size + 1
    391     var best = IntArray(0)
    392     while (r > l + 1) {
    393         var m = (l + r) / 2
    394         val c = IntArray(m)
    395         for (i in 0 until m) {
    396             if (i % 2 == 0) {
    397                 c[i] = a[i / 2]
    398             } else {
    399                 c[i] = a[n - m / 2 + i / 2]
    400             }
    401         }
    402         var ok = true
    403         for (i in 0 until m - 1) {
    404             if (c[i] == c[i + 1]) {
    405                 ok = false
    406             }
    407         }
    408         if (!ok && m % 2 == 0) {
    409             for (i in 0 until m step 2) {
    410                 val t = c[i]
    411                 c[i] = c[i + 1]
    412                 c[i + 1] = t
    413             }
    414             ok = true
    415             for (i in 0 until m - 1) {
    416                 if (c[i] == c[i + 1]) {
    417                     ok = false
    418                 }
    419             }
    420         }
    421         if (ok) {
    422             l = m
    423             best = c
    424         } else {
    425             r = m
    426         }
    427     }
    428     return best
    429 }
    430 
    431 private fun solveTest() {
    432     val n = readLine()!!.toInt()
    433     val a = readLine()!!.split(" ").map { it.toInt() }.toIntArray()
    434     a.sort()
    435     val best1 = solve(a)
    436     a.reverse()
    437     val best2 = solve(a)
    438     val best = if (best1.size > best2.size) best1 else best2
    439     println(best.size)
    440     println(best.joinToString(" "))
    441 }
    442 
    443 fun main() {
    444     val n = readLine()!!.toInt()
    445     for (i in 0 until n) {
    446         solveTest()
    447     }
    448 }
    449 ```
    450 
    451 [1170I - Good Subsets](/contest/1170/problem/I "Kotlin Heroes: Episode 1")
    452 
    453 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    454 
    455 Solution: [pashka](/profile/pashka "Grandmaster pashka")
    456 
    457 **Tutorial**
    458 
    459 Tutorial is loading...
    460 
    461 **Solution**
    462 
    463 ```
    464 import java.io.BufferedReader
    465 import java.io.IOException
    466 import java.io.InputStreamReader
    467 import java.io.PrintWriter
    468 import java.util.*
    469 
    470 /**
    471  * @author: pashka
    472  */
    473 
    474 val MOD = 998244353L
    475 
    476 internal class SegmentTree(private val size: Int) {
    477 
    478     private val sum = LongArray(4 * size)
    479     private val add = LongArray(4 * size)
    480     private val mult = LongArray(4 * size)
    481 
    482     public fun add(l: Int, r: Int, c: Long) {
    483         add(0, 0, size, l, r, c)
    484     }
    485 
    486     private fun add(n: Int, ll: Int, rr: Int, l: Int, r: Int, c: Long) {
    487         push(n, ll, rr)
    488         if (ll >= l && rr <= r) {
    489             add[n] += c
    490             sum[n] += c * (rr - ll)
    491             add[n] %= MOD
    492             sum[n] %= MOD
    493         } else if (ll >= r || l >= rr) {
    494             return
    495         } else {
    496             val m = (ll + rr) / 2
    497             add(n * 2 + 1, ll, m, l, r, c)
    498             add(n * 2 + 2, m, rr, l, r, c)
    499             sum[n] = (sum[2 * n + 1] + sum[2 * n + 2]) % MOD
    500         }
    501     }
    502 
    503     public fun mult(l: Int, r: Int, c: Long) {
    504         mult(0, 0, size, l, r, c)
    505     }
    506 
    507     private fun mult(n: Int, ll: Int, rr: Int, l: Int, r: Int, c: Long) {
    508         push(n, ll, rr)
    509         if (ll >= l && rr <= r) {
    510             mult[n] *= c
    511             add[n] *= c
    512             sum[n] *= c
    513             mult[n] %= MOD
    514             add[n] %= MOD
    515             sum[n] %= MOD
    516         } else if (ll >= r || l >= rr) {
    517             return
    518         } else {
    519             val m = (ll + rr) / 2
    520             mult(n * 2 + 1, ll, m, l, r, c)
    521             mult(n * 2 + 2, m, rr, l, r, c)
    522             sum[n] = (sum[2 * n + 1] + sum[2 * n + 2]) % MOD
    523         }
    524     }
    525 
    526     private fun push(n: Int, ll: Int, rr: Int) {
    527         if (rr - ll > 1) {
    528             val m = ll + rr shr 1
    529             for (i in 1..2) {
    530                 mult[2 * n + i] *= mult[n]
    531                 add[2 * n + i] *= mult[n]
    532                 sum[2 * n + i] *= mult[n]
    533                 add[2 * n + i] += add[n]
    534                 sum[2 * n + i] += add[n] * (if (i == 1) (m - ll) else (rr - m))
    535                 mult[2 * n + i] %= MOD
    536                 add[2 * n + i] %= MOD
    537                 sum[2 * n + i] %= MOD
    538             }
    539         }
    540         add[n] = 0
    541         mult[n] = 1
    542     }
    543 
    544     public fun sum(l: Int, r: Int): Long {
    545         return sum(0, 0, size, l, r)
    546     }
    547 
    548     private fun sum(n: Int, ll: Int, rr: Int, l: Int, r: Int): Long {
    549         push(n, ll, rr)
    550         if (ll >= l && rr <= r) {
    551             return sum[n]
    552         } else if (ll >= r || l >= rr) {
    553             return 0
    554         } else {
    555             val m = (ll + rr) / 2
    556             return (sum(n * 2 + 1, ll, m, l, r) + sum(n * 2 + 2, m, rr, l, r)) % MOD
    557         }
    558     }
    559 }
    560 
    561 private fun solve() {
    562     val n = nextInt()
    563     val l = IntArray(n)
    564     val r = IntArray(n)
    565     for (i in 0 until n) {
    566         l[i] = nextInt()
    567         r[i] = nextInt()
    568     }
    569     var all = l + r
    570     all.sort()
    571     var m = 1
    572     for (i in 1 until all.size) {
    573         if (all[i] != all[m - 1]) {
    574             all[m] = all[i]
    575             m++
    576         }
    577     }
    578     all = all.copyOf(m)
    579     for (i in 0 until n) {
    580         l[i] = all.binarySearch(l[i])
    581         r[i] = all.binarySearch(r[i])
    582     }
    583     val c = IntArray(2 * m)
    584     for (i in 0 until n) {
    585         c[l[i] * 2]++
    586         c[r[i] * 2 + 1]--
    587     }
    588     for (i in 1 until 2 * m) {
    589         c[i] += c[i - 1]
    590     }
    591     val q = IntArray(2 * m)
    592     var mm = 0
    593     for (i in 0 until 2 * m) {
    594         if (c[i] > 0) {
    595             q[i] = mm
    596             mm++
    597         }
    598     }
    599     m = mm
    600     for (i in 0 until n) {
    601         l[i] = q[2 * l[i]]
    602         r[i] = q[2 * r[i]]
    603     }
    604     var p = List(n) { x: Int -> x }.sortedBy { x: Int -> r[x] }
    605     val st = SegmentTree(m + 1)
    606     st.add(0, 1, 1)
    607     for (i in p) {
    608         st.mult(0, l[i], 2)
    609         val x = st.sum(l[i], r[i] + 2)
    610         st.add(r[i] + 1, r[i] + 2, x)
    611     }
    612     out.println(st.sum(m, m + 1))
    613 }
    614 
    615 fun main() {
    616     solve()
    617     out.close()
    618 }
    619 
    620 private var br = BufferedReader(InputStreamReader(System.`in`))
    621 private var st: StringTokenizer? = null
    622 private var out = PrintWriter(System.out)
    623 
    624 @Throws(IOException::class)
    625 private fun next(): String {
    626     while (st == null || !st!!.hasMoreTokens()) {
    627         st = StringTokenizer(br.readLine())
    628     }
    629     return st!!.nextToken()
    630 }
    631 
    632 @Throws(IOException::class)
    633 private fun nextInt(): Int {
    634     return Integer.parseInt(next())
    635 }
    636 ```