codeforces-scrape

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

2011.md (15300B)


      1 Source: https://codeforces.com/blog/entry/134624
      2 
      3 This round was prepared by [Neon](/profile/Neon "Candidate Master Neon"), [adedalic](/profile/adedalic "International Master adedalic"), [awoo](/profile/awoo "Grandmaster awoo"), [shnirelman](/profile/shnirelman "International Grandmaster shnirelman") and me.
      4 
      5 Huge thanks to all of the testers: [ashmelev](/profile/ashmelev "Grandmaster ashmelev"), [KIRIJIJI](/profile/KIRIJIJI "Master KIRIJIJI"), [PavelKunyavskiy](/profile/PavelKunyavskiy "Grandmaster PavelKunyavskiy"), [soup](/profile/soup "Expert soup") and [Fanarill](/profile/Fanarill "Expert Fanarill")! Your feedback helped us balance this contest (and find a very stupid overflow bug I'm too ashamed to mention).
      6 
      7 Thanks for participation, we hope you enjoyed the contest!
      8 
      9 [2011A - Problem Solving](/contest/2011/problem/A "Kotlin Heroes: Episode 11")
     10 
     11 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     12 
     13 **Tutorial**
     14 
     15 Tutorial is loading...
     16 
     17 **Solution (Neon)**
     18 
     19 ```
     20 fun main() = repeat(readln().toInt()) {
     21   readln().toInt()
     22   val a = readln().split(" ").map { it.toInt() }
     23   println(if (a.dropLast(1).contains(a.last() - 1)) a.last() - 1 else "Ambiguous")
     24 }
     25 ```
     26 
     27 [2011B - Shuffle](/contest/2011/problem/B "Kotlin Heroes: Episode 11")
     28 
     29 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     30 
     31 **Tutorial**
     32 
     33 Tutorial is loading...
     34 
     35 **Solution (Neon)**
     36 
     37 ```
     38 fun main() = repeat(readln().toInt()) {
     39   val n = readln().toInt()
     40   println((listOf(1) + (n downTo 2)).joinToString(" "))
     41 }
     42 ```
     43 
     44 [2011C - Split the Expression](/contest/2011/problem/C "Kotlin Heroes: Episode 11")
     45 
     46 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     47 
     48 **Tutorial**
     49 
     50 Tutorial is loading...
     51 
     52 **Solution (Neon)**
     53 
     54 ```
     55 fun main() = repeat(readln().toInt()) {
     56   val a = readln().split("+")
     57   val ans = a.foldIndexed(0L) { i, res, s ->
     58     res + if (i == 0 || i == a.size - 1)
     59       s.toLong()
     60     else 
     61       (1 until s.length).maxOf { s.take(it).toLong() + s.drop(it).toLong() }
     62   }
     63   println(ans)
     64 }
     65 ```
     66 
     67 [2011D - Among Wolves](/contest/2011/problem/D "Kotlin Heroes: Episode 11")
     68 
     69 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [adedalic](/profile/adedalic "International Master adedalic")
     70 
     71 **Tutorial**
     72 
     73 Tutorial is loading...
     74 
     75 **Solution (adedalic)**
     76 
     77 ```
     78 fun main() {
     79     repeat(readln().toInt()) {
     80         val (n, h, b) = readln().split(' ').map { it.toLong() }
     81         val grid = Array(2) { readln() }
     82         val sheepColumn = grid[0].indices.find { grid[0][it] == 'S' || grid[1][it] == 'S' }!!
     83         val wolvesLeft = (0..1).sumOf { grid[it].take(sheepColumn).count { it == 'W' } }
     84         val wolvesRight = (0..1).sumOf { grid[it].substring(sheepColumn).count { it == 'W' } }
     85 
     86         val ans = minOf(
     87             (wolvesLeft + wolvesRight) * h,
     88             wolvesLeft * h + 2 * b,
     89             wolvesRight * h + 2 * b,
     90             3 * b
     91         )
     92         println(ans)
     93     }
     94 }
     95 ```
     96 
     97 [2011E - Rock-Paper-Scissors Bot](/contest/2011/problem/E "Kotlin Heroes: Episode 11")
     98 
     99 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon")
    100 
    101 **Tutorial**
    102 
    103 Tutorial is loading...
    104 
    105 **Solution (Neon)**
    106 
    107 ```
    108 const val INF = 1e9.toInt()
    109 const val vars = "RPS"
    110 
    111 fun main() = repeat(readln().toInt()) {  
    112   val a = readln().map { vars.indexOf(it) }
    113   
    114   fun calc(a : List<Int>) : Int {
    115     if (a[0] != 0) return INF
    116     val balance = a.zipWithNext().fold(0) { s, (x, y) ->
    117       s + (if (x == y) 1 else 0) - (if ((x + 2) % 3 == y) 1 else 0)
    118     }
    119     return a.size + maxOf(balance, 0)
    120   }
    121   
    122   println(minOf(
    123     calc(a),
    124     calc(listOf(0) + a),
    125     calc(listOf(0, 2) + a)
    126    ))
    127 }
    128 ```
    129 
    130 [2011F - Good Subarray](/contest/2011/problem/F "Kotlin Heroes: Episode 11")
    131 
    132 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon")
    133 
    134 **Tutorial**
    135 
    136 Tutorial is loading...
    137 
    138 **Solution (Neon)**
    139 
    140 ```
    141 fun main() = repeat(readln().toInt()) {  
    142   val n = readln().toInt()
    143   val a = readln().split(" ").map { it.toInt() - 1 }
    144   
    145   val prev = IntArray(n + 1) { -1 }
    146   val pos = IntArray(n) { -1 } 
    147   
    148   for (i in 0 until n) {
    149     for (j in a[i]-1..a[i]+1) {
    150       if (0 <= j && j < n) {
    151         prev[i] = maxOf(prev[i], pos[j])
    152       }
    153     }
    154     pos[a[i]] = i
    155   }
    156   
    157   val st = mutableListOf(n)
    158   var ans = 0L
    159   for (i in (n - 1) downTo 0) {
    160     while (st.size > 0 && prev[st.last()] >= i) {
    161       st.removeLast()
    162     }
    163     ans += st.last() - i
    164     st.add(i)
    165   }
    166   
    167   println(ans)
    168 }
    169 ```
    170 
    171 [2011G - Removal of a Permutation](/contest/2011/problem/G "Kotlin Heroes: Episode 11")
    172 
    173 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon")
    174 
    175 **Tutorial**
    176 
    177 Tutorial is loading...
    178 
    179 **Solution (Neon)**
    180 
    181 ```
    182 const val LOG = 19
    183 
    184 fun main() = repeat(readln().toInt()) {  
    185   val n = readln().toInt()
    186   val p = readln().split(" ").map { it.toInt() - 1 }
    187   val ans = IntArray(n - 1) { n }
    188   
    189   fun rec(step: Int, p: List<Int>) {
    190     if (p.size == 1 || step == LOG) return
    191     for (cur in listOf(p, p.reversed())) {
    192       val (a, b) = cur.zipWithNext().partition { (x, y) -> x < y }
    193       a.forEach { (x, _) -> ans[x] = minOf(ans[x], step) }
    194       rec(step + 1, b.map { (x, _) -> x} + cur.last())
    195     }
    196   }
    197   
    198   rec(1, p)
    199   
    200   println(ans.joinToString(" "))
    201 }
    202 ```
    203 
    204 [2011H - Strange Matrix](/contest/2011/problem/H "Kotlin Heroes: Episode 11")
    205 
    206 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon")
    207 
    208 **Tutorial**
    209 
    210 Tutorial is loading...
    211 
    212 **Solution (Neon)**
    213 
    214 ```
    215 const val INF = 1e9.toInt()
    216 const val B = 5
    217 
    218 fun main() = repeat(readln().toInt()) {
    219   val (n, m, k) = readInts()
    220   val a = Array(n) { readInts() }
    221   
    222   var ans = 0
    223   
    224   for (bit in 0 until B) {
    225     val g = Array(n) { ArrayList<Pair<Int, Int>>() }
    226     for (i in 0 until n) {
    227       for (j in 0 until i) {
    228         val cnt = IntArray(4) { 0 }
    229         for (x in 0 until m) {
    230           val f = (a[i][x] shr bit) and 1
    231           val s = (a[j][x] shr bit) and 1
    232           ++cnt[f * 2 + s];
    233         }
    234         val f1 = (cnt[0] < k && cnt[3] < k)
    235         val f2 = (cnt[1] < k && cnt[2] < k)
    236         if (f1 != f2) {
    237           g[i].add(j to if (f2) 1 else 0)
    238           g[j].add(i to if (f2) 1 else 0)
    239         } else if (!f1) {
    240           return@repeat println("-1")
    241         }
    242       }
    243     }
    244     
    245     val color = IntArray(n) { -1 }
    246     val cnt = IntArray(2) { 0 }
    247     var ok = true
    248     
    249     fun dfs(v: Int, c: Int) {
    250       color[v] = c
    251       ++cnt[c]
    252       for ((u, d) in g[v]) {
    253         if (color[u] != -1) {
    254           if ((c xor d) != color[u]) {
    255             ok = false
    256           }
    257         } else {
    258           dfs(u, c xor d)
    259         }
    260       }
    261     }
    262     
    263     for (v in 0 until n) {
    264       if (color[v] != -1) continue
    265       cnt.fill(0)
    266       dfs(v, 0)
    267       if (!ok) return@repeat println("-1")
    268       ans += cnt.min() shl bit
    269     }
    270   }
    271   
    272   println(maxOf(0, ans))
    273 }
    274 
    275 fun readInts() = readln().split(" ").map { it.toInt() }
    276 ```
    277 
    278 [2011I - Stack and Queue](/contest/2011/problem/I "Kotlin Heroes: Episode 11")
    279 
    280 Idea: [shnirelman](/profile/shnirelman "International Grandmaster shnirelman"), preparation: [awoo](/profile/awoo "Grandmaster awoo")
    281 
    282 **Tutorial**
    283 
    284 Tutorial is loading...
    285 
    286 **Solution (awoo)**
    287 
    288 ```
    289 class Query(val t: Int, val x: Int)
    290 
    291 class BIT(val mx: Int) {
    292 	val f = LongArray(mx) { 0L }
    293 	
    294 	fun upd_pr(pos: Int, x: Int) {
    295 		var i = pos
    296 		while (i < mx) {
    297 			f[i] = f[i] + x
    298 			i = i or (i + 1)
    299 		}
    300 	}
    301 
    302 	fun get_pr(pos: Int) : Long {
    303 		var res = 0L
    304 		var i = pos
    305 		while (i >= 0) {
    306 			res += f[i]
    307 			i = (i and (i + 1)) - 1
    308 		}
    309 		return res
    310 	}
    311 
    312 	fun upd_su(pos: Int, x: Int) {
    313 		var i = pos
    314 		while (i >= 0) {
    315 			f[i] = f[i] + x
    316 			i = (i and (i + 1)) - 1
    317 		}
    318 	}
    319 
    320 	fun get_su(pos: Int) : Long {
    321 		var res = 0L
    322 		var i = pos
    323 		while (i < mx) {
    324 			res += f[i]
    325 			i = i or (i + 1)
    326 		}
    327 		return res
    328 	}
    329 }
    330 
    331 fun main() {
    332 	val n = readLine()!!.toInt()
    333 	val a = readLine()!!.split(" ").map { it.toInt() }
    334 	val q = Array(n) { Query(-1, -1) }
    335 	for (i in 0 until n) {
    336 		val (t, x) = readLine()!!.split(" ").map { it.toInt() }
    337 		q[i] = Query(t, x - 1)
    338 	}
    339 	
    340 	val d = IntArray(n + 1) { 0 }
    341 	
    342 	fun apply(coef: Int) {	
    343 		var qs = Array<ArrayList<Pair<Int, Int>>>(n + 1) { ArrayList<Pair<Int, Int>>() }
    344 		for (i in 0 until n) {
    345 			qs[0].add(Pair(i, n + 1))
    346 		}
    347 		
    348 		var len = n + 1
    349 		while (true) {
    350 			val posq = IntArray(n) { -1 }
    351 			val poss = IntArray(n) { -1 }
    352 			val sv = IntArray(n) { -1 }
    353 			val fq = BIT(n)
    354 			val fs = BIT(n)
    355 			
    356 			var cntq = 0
    357 			var cnts = 0
    358 			val nqs = Array<ArrayList<Pair<Int, Int>>>(n + 1) { ArrayList<Pair<Int, Int>>() }
    359 			var j = 0
    360 			
    361 			var last = true
    362 			for (l in 0 until n + 1) {
    363 				for (it in qs[l]) {
    364 					val i = it.first
    365 					val r = it.second
    366 					if (r - l == 1) {
    367 						d[l] += coef
    368 						continue
    369 					}
    370 					
    371 					last = false
    372 					val m = (l + r) / 2
    373 					while (j < m) {
    374 						val x = q[j].x
    375 						if (q[j].t == 1) {
    376 							posq[x] = cntq
    377 							sv[x] = cnts
    378 							cntq += 1
    379 							cnts += 1
    380 							fq.upd_pr(posq[x], a[x])
    381 						}
    382 						else if (q[j].t == 2){
    383 							poss[x] = cnts
    384 							cnts += 1
    385 							fs.upd_su(poss[x], a[x])
    386 						}
    387 						else{
    388 							fq.upd_pr(posq[x], -a[x])
    389 							posq[x] = -1
    390 							poss[x] = sv[x]
    391 							fs.upd_su(poss[x], a[x])
    392 						}
    393 						j += 1
    394 					}
    395 					assert(j == m)
    396 					if (poss[i] == -1 || posq[i] == -1) {
    397 						nqs[m].add(Pair(i, r))
    398 						continue
    399 					}
    400 					val tq = fq.get_pr(posq[i] - 1)
    401 					val ts = fs.get_su(poss[i] + 1)
    402 					var ok = true
    403 					if (coef == 1) {
    404 						ok = tq - a[i] >= ts
    405 					}
    406 					else {
    407 						ok = tq + a[i] > ts
    408 					}
    409 					if (ok) {
    410 						nqs[m].add(Pair(i, r))
    411 					}
    412 					else {
    413 						nqs[l].add(Pair(i, m))
    414 					}
    415 				}
    416 			}
    417 			qs = nqs
    418 			if (last) {
    419 				break
    420 			}
    421 		}
    422 		println("")
    423 	}
    424 	
    425 	apply(1)
    426 	apply(-1)
    427 	for (i in 0 until n) {
    428 		d[i + 1] += d[i]
    429 	}
    430 	val res = d.map { x -> (if (x == 0) "Yes" else "No") }
    431 	println(res.take(res.size - 1).joinToString(separator = "\n"))
    432 }
    433 ```
    434 
    435 **Solution 2 (awoo)**
    436 
    437 ```
    438 class Query(val t: Int, val x: Int)
    439 
    440 class BIT(val mx: Int) {
    441     val f = LongArray(mx) { 0L }
    442     
    443     fun upd_pr(pos: Int, x: Int) {
    444         var i = pos
    445         while (i < mx) {
    446             f[i] = f[i] + x
    447             i = i or (i + 1)
    448         }
    449     }
    450 
    451     fun get_pr(pos: Int) : Long {
    452         var res = 0L
    453         var i = pos
    454         while (i >= 0) {
    455             res += f[i]
    456             i = (i and (i + 1)) - 1
    457         }
    458         return res
    459     }
    460 
    461     fun upd_su(pos: Int, x: Int) {
    462         var i = pos
    463         while (i >= 0) {
    464             f[i] = f[i] + x
    465             i = (i and (i + 1)) - 1
    466         }
    467     }
    468 
    469     fun get_su(pos: Int) : Long {
    470         var res = 0L
    471         var i = pos
    472         while (i < mx) {
    473             res += f[i]
    474             i = i or (i + 1)
    475         }
    476         return res
    477     }
    478 }
    479 
    480 fun main() {
    481     val n = readLine()!!.toInt()
    482     val a = readLine()!!.split(" ").map { it.toInt() }
    483     val q = Array(n) { Query(-1, -1) }
    484     for (i in 0 until n) {
    485         val (t, x) = readLine()!!.split(" ").map { it.toInt() }
    486         q[i] = Query(t, x - 1)
    487     }
    488     val fq = BIT(n)
    489     val fs = BIT(n)
    490     
    491     val d = IntArray(n + 1) { 0 }
    492     val posq = IntArray(n) { -1 }
    493     val poss = IntArray(n) { -1 }
    494     val sv = IntArray(n) { -1 }
    495     var cntq = 0
    496     var cnts = 0
    497     
    498     fun calc(l: Int, r: Int, coef: Int, all: ArrayList<Int>) {
    499         if (l == r - 1) {
    500             d[l] += all.size * coef
    501             return
    502         }
    503         
    504         val m = (l + r) / 2
    505         
    506         val who_chg = ArrayList<Int>()
    507         val idx_chg = ArrayList<Int>()
    508         val val_chg = ArrayList<Int>()
    509         val chq = ArrayList<Pair<Int, Int>>()
    510         val chs = ArrayList<Pair<Int, Int>>()
    511         
    512         for (i in l until m) {
    513             val x = q[i].x
    514             if (q[i].t == 1) {
    515                 who_chg.add(0)
    516                 idx_chg.add(x)
    517                 val_chg.add(posq[x])
    518                 posq[x] = cntq
    519                 who_chg.add(2)
    520                 idx_chg.add(x)
    521                 val_chg.add(sv[x])
    522                 sv[x] = cnts
    523                 cntq += 1
    524                 cnts += 1
    525                 chq.add(Pair(posq[x], -a[x]))
    526                 fq.upd_pr(posq[x], a[x])
    527             }
    528             else if (q[i].t == 2){
    529                 who_chg.add(1)
    530                 idx_chg.add(x)
    531                 val_chg.add(poss[x])
    532                 poss[x] = cnts
    533                 cnts += 1
    534                 chs.add(Pair(poss[x], -a[x]))
    535                 fs.upd_su(poss[x], a[x])
    536             }
    537             else{
    538                 chq.add(Pair(posq[x], a[x]))
    539                 fq.upd_pr(posq[x], -a[x])
    540                 who_chg.add(0)
    541                 idx_chg.add(x)
    542                 val_chg.add(posq[x])
    543                 posq[x] = -1
    544                 who_chg.add(1)
    545                 idx_chg.add(x)
    546                 val_chg.add(poss[x])
    547                 poss[x] = sv[x]
    548                 who_chg.add(2)
    549                 idx_chg.add(x)
    550                 val_chg.add(sv[x])
    551                 sv[x] = -1
    552                 chs.add(Pair(poss[x], -a[x]))
    553                 fs.upd_su(poss[x], a[x])
    554             }
    555         }
    556     
    557         val tol = ArrayList<Int>()
    558         val tor = ArrayList<Int>()
    559         
    560         for (x in all) {
    561             if (poss[x] == -1 || posq[x] == -1) {
    562                 tor.add(x)
    563                 continue
    564             }
    565             val tq = fq.get_pr(posq[x] - 1)
    566             val ts = fs.get_su(poss[x] + 1)
    567             var ok = true
    568             if (coef == 1) {
    569                 ok = tq - a[x] >= ts
    570             }
    571             else {
    572                 ok = tq + a[x] > ts
    573             }
    574             if (ok) {
    575                 tor.add(x)
    576             }
    577             else {
    578                 tol.add(x)
    579             }
    580         }
    581     
    582         calc(m, r, coef, tor)
    583         
    584         who_chg.reverse()
    585         idx_chg.reverse()
    586         val_chg.reverse()
    587         
    588         for (i in 0 until who_chg.size) {
    589             if (who_chg[i] == 0) {
    590                 posq[idx_chg[i]] = val_chg[i]
    591             }
    592             else if (who_chg[i] == 1) {
    593                 poss[idx_chg[i]] = val_chg[i]
    594             }
    595             else {
    596                 sv[idx_chg[i]] = val_chg[i]
    597             }
    598         }
    599         
    600         for (i in l until m) {
    601             if (q[i].t == 1) {
    602                 cntq -= 1
    603                 cnts -= 1
    604             }
    605             else if (q[i].t == 2){
    606                 cnts -= 1
    607             }
    608         }
    609 
    610         for (it in chq) {
    611             fq.upd_pr(it.first, it.second)
    612         }
    613         for (it in chs) {
    614             fs.upd_su(it.first, it.second)
    615         }
    616         
    617         calc(l, m, coef, tol)
    618     }
    619     
    620     val all = ArrayList<Int>()
    621     for (i in 0 until n) {
    622         all.add(i)
    623     }
    624     calc(0, n + 1, 1, all)
    625     calc(0, n + 1, -1, all)
    626     for (i in 0 until n) {
    627         d[i + 1] += d[i]
    628     }
    629     val res = d.map { x -> (if (x == 0) "Yes" else "No") }
    630     println(res.take(res.size - 1).joinToString(separator = "\n"))
    631 }
    632 ```