codeforces-scrape

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

1431.md (12480B)


      1 Source: https://codeforces.com/blog/entry/84563
      2 
      3 First of all, I would like to thank all testers of the round: [elizarov](/profile/elizarov "Candidate Master elizarov"), [IlyaLos](/profile/IlyaLos "International Master IlyaLos"), [nuipojaluista](/profile/nuipojaluista "Expert nuipojaluista"), [hg333](/profile/hg333 "Candidate Master hg333"), [nooinenoojno](/profile/nooinenoojno "Expert nooinenoojno"), [winger](/profile/winger "International Grandmaster winger"), [neko_nyaaaaaaaaaaaaaaaaa](/profile/neko_nyaaaaaaaaaaaaaaaaa "Grandmaster neko_nyaaaaaaaaaaaaaaaaa"), [kort0n](/profile/kort0n "Grandmaster kort0n"), [hos.lyric](/profile/hos.lyric "Legendary Grandmaster hos.lyric") and [Roms](/profile/Roms "Master Roms"). Also huge thanks to co-authors of the contest: [Neon](/profile/Neon "Candidate Master Neon"), [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 [1431A - Selling Hamburgers](/contest/1431/problem/A "Kotlin Heroes 5: ICPC Round")
     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 (elizarov)**
     18 
     19 ```
     20 fun main() {
     21     repeat(readLine()!!.toInt()) {
     22         val n = readLine()!!.toInt()
     23         val a = readLine()!!.split(" ").map { it.toLong() }
     24         val answer = a.sortedDescending().withIndex().maxOf { (it.index + 1) * it.value }
     25         println(answer)
     26     }
     27 }
     28 ```
     29 
     30 [1431B - Polycarp and the Language of Gods](/contest/1431/problem/B "Kotlin Heroes 5: ICPC Round")
     31 
     32 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [awoo](/profile/awoo "Grandmaster awoo")
     33 
     34 **Tutorial**
     35 
     36 Tutorial is loading...
     37 
     38 **Solution (elizarov)**
     39 
     40 ```
     41 fun main() {
     42     repeat(readLine()!!.toInt()) {
     43         val s = readLine()!!
     44         val answer = s.count { it == 'w' } + s.split("w").sumOf { it.length / 2 }
     45         println(answer)
     46     }
     47 }
     48 ```
     49 
     50 [1431C - Black Friday](/contest/1431/problem/C "Kotlin Heroes 5: ICPC Round")
     51 
     52 Idea: [Neon](/profile/Neon "Candidate Master Neon"), preparation: [Neon](/profile/Neon "Candidate Master Neon") and [awoo](/profile/awoo "Grandmaster awoo")
     53 
     54 **Tutorial**
     55 
     56 Tutorial is loading...
     57 
     58 **Solution (elizarov)**
     59 
     60 ```
     61 fun main() {
     62     repeat(readLine()!!.toInt()) {
     63         val (n, k) = readLine()!!.split(" ").map { it.toInt() }
     64         val p = readLine()!!.split(" ").map { it.toInt() }
     65         val answer = (1..n / k).maxOf { d ->
     66             val m = d * k
     67             p.subList(n - m, n - m + d).sum()
     68         }
     69         println(answer)
     70     }
     71 }
     72 ```
     73 
     74 [1431D - Used Markers](/contest/1431/problem/D "Kotlin Heroes 5: ICPC Round")
     75 
     76 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [adedalic](/profile/adedalic "International Master adedalic")
     77 
     78 **Tutorial**
     79 
     80 Tutorial is loading...
     81 
     82 **Solution (elizarov)**
     83 
     84 ```
     85 fun main() {
     86     repeat(readLine()!!.toInt()) {
     87         val n = readLine()!!.toInt()
     88         val a = readLine()!!.split(" ").map { it.toInt() }
     89             .withIndex().sortedBy { it.value }
     90         var i = 0
     91         var j = n - 1
     92         val answer = ArrayList<Int>(n)
     93         var bc = 0
     94         while (i <= j) {
     95             if (bc >= a[i].value) {
     96                 answer += a[i++].index
     97                 bc = 1
     98             } else {
     99                 answer += a[j--].index
    100                 bc++
    101             }
    102         }
    103         println(answer.joinToString(" ") { (it + 1).toString() })
    104     }
    105 }
    106 ```
    107 
    108 [1431E - Chess Match](/contest/1431/problem/E "Kotlin Heroes 5: ICPC Round")
    109 
    110 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    111 
    112 **Tutorial**
    113 
    114 Tutorial is loading...
    115 
    116 **Solution (Ne0n25)**
    117 
    118 ```
    119 fun main() = repeat(readLine()!!.toInt()) {
    120 	val n = readLine()!!.toInt()
    121 	val a = readLine()!!.split(" ").map { it.toInt() }
    122 	val b = readLine()!!.split(" ").map { it.toInt() }
    123 	
    124 	var ans = -1
    125 	var ans_shift = -1
    126 	for (shift in 0 until n) {
    127 		var res = 1e9.toInt()
    128 		for(i in 0 until n)
    129 			res = Math.min(res, Math.abs(a[i] - b[(i + shift) % n]))
    130 		if (res > ans) {
    131 			ans = res
    132 			ans_shift = shift
    133 		}
    134 	}	
    135 
    136 	println(IntArray(n) { (it + ans_shift) % n + 1 }.joinToString(" ")) 
    137 }
    138 ```
    139 
    140 [1431F - Neural Network Problem](/contest/1431/problem/F "Kotlin Heroes 5: ICPC Round")
    141 
    142 Idea: [vovuh](/profile/vovuh "Master vovuh"), preparation: [vovuh](/profile/vovuh "Master vovuh")
    143 
    144 **Tutorial**
    145 
    146 Tutorial is loading...
    147 
    148 **Solution (vovuh)**
    149 
    150 ```
    151 import java.util.*
    152 
    153 fun main() {
    154     val (n, k, x) = readLine()!!.split(" ").map { it.toInt() }
    155     val a = readLine()!!.split(" ").map { it.toInt() }
    156     var l = 0L
    157     var r = 10L * 1000 * 1000 * 1000
    158     var res = -1L
    159 
    160     fun can(sum : Long) : Boolean {
    161         var cursum = 0L
    162         var need = 0
    163         var cur = PriorityQueue<Int>(compareBy<Int> { -it })
    164         for (i in 0 until n) {
    165             cursum += a[i]
    166             cur.add(a[i])
    167             while (cur.size > x || cursum > sum) {
    168                 cursum -= cur.first()
    169                 cur.remove()
    170                 need += 1
    171             }
    172             if (cur.size == x) {
    173                 cursum = 0L
    174                 cur.clear()
    175             }
    176         }
    177         return need <= k
    178     }
    179 
    180     while (l <= r) {
    181         val mid = (l + r) / 2
    182         if (can(mid)) {
    183             res = mid
    184             r = mid - 1
    185         } else {
    186             l = mid + 1
    187         }
    188     }
    189     println(res)
    190 }
    191 ```
    192 
    193 [1431G - Number Deletion Game](/contest/1431/problem/G "Kotlin Heroes 5: ICPC Round")
    194 
    195 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    196 
    197 **Tutorial**
    198 
    199 Tutorial is loading...
    200 
    201 **Solution (Ne0n25)**
    202 
    203 ```
    204 fun main() {
    205 	val (n, k) = readLine()!!.split(' ').map { it.toInt() }
    206 	val a =	readLine()!!.split(" ").map { it.toInt() }.sorted()
    207 	
    208 	val p = IntArray(n + 1) { 0 }
    209 	for (i in 0 until n) p[i + 1] = p[i] + a[i]
    210 	
    211 	val dp = Array(n + 1) { IntArray(k + 1) { -1 } }
    212 
    213  	dp[0][0] = 0
    214  	for (i in 0 until n) {
    215  		for (j in 0 until k + 1) {
    216  			if (dp[i][j] < 0)
    217  				continue
    218  			dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j])
    219  			val maxx = Math.min(k - j, (n - i) / 2)
    220  			for (x in 1..maxx)
    221  				dp[i + 2 * x][j + x] = Math.max(dp[i + 2 * x][j + x], dp[i][j] + p[i + 2 * x] - p[i + x] - p[i + x] + p[i])	
    222  		}
    223  	}
    224  	
    225  	println(dp[n][k])
    226 }
    227 ```
    228 
    229 [1431H - Rogue-like Game](/contest/1431/problem/H "Kotlin Heroes 5: ICPC Round")
    230 
    231 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon")
    232 
    233 **Tutorial**
    234 
    235 Tutorial is loading...
    236 
    237 **Solution (Ne0n25)**
    238 
    239 ```
    240 fun main() {
    241 	val (n, m, k) = readLine()!!.split(" ").map { it.toInt() }	
    242 	val a = readLine()!!.split(" ").map { it.toLong() }
    243 	val b = readLine()!!.split(" ").map { it.toLong() }
    244 	val c = Array(n) { readLine()!!.split(" ").map { it.toLong() } }
    245 	
    246 	val ev = Array(n + m) {
    247 		if (it < n)
    248 			longArrayOf(a[it], 1L, it.toLong())
    249 		else
    250 			longArrayOf(b[it - n], 0L, (it - n).toLong())
    251 	}
    252 	
    253 	ev.sortWith(compareBy({ it[0] }))
    254 	
    255 	val vals = LongArray(n + m) { 0 }
    256 	
    257 	for (e in 0 until n + m) {
    258 		if (ev[e][1] == 1L) {
    259 			val i = ev[e][2].toInt()
    260 			vals[e] = b.indices.filter { b[it] <= ev[e][0] }.map { c[i][it] }.max()!!
    261 		} else {
    262 			val j = ev[e][2].toInt()
    263 			vals[e] = a.indices.filter { a[it] <= ev[e][0] }.map { c[it][j] }.max()!!
    264 		}
    265 	}
    266 	
    267 	var ans = 1e18.toLong()
    268 	
    269 	for (bonus in 1 until n + m) {
    270 		vals[bonus] += k.toLong()
    271 		var (res, cur, mx) = LongArray(3) { 0 }
    272 		var i = 0
    273 		while (true) {
    274 			while (i < n + m && ev[i][0] <= cur) {
    275 				mx = Math.max(mx, vals[i])
    276 				++i;
    277 			}
    278 			if (i == n + m) break
    279 			val need = (ev[i][0] - cur + mx - 1) / mx
    280 			res += need
    281 			cur += need * mx
    282 		}
    283 		ans = Math.min(ans, res)
    284 		vals[bonus] -= k.toLong()
    285 	}
    286 
    287 	println(ans)
    288 }
    289 ```
    290 
    291 [1431I - Cyclic Shifts](/contest/1431/problem/I "Kotlin Heroes 5: ICPC Round")
    292 
    293 Idea: [Neon](/profile/Neon "Candidate Master Neon"), preparation: [Neon](/profile/Neon "Candidate Master Neon")
    294 
    295 **Tutorial**
    296 
    297 Tutorial is loading...
    298 
    299 **Solution (Ne0n25)**
    300 
    301 ```
    302 import java.io.PrintWriter
    303 
    304 fun main() {
    305 	val (n, m, q) = readLine()!!.split(' ').map { it.toInt() }
    306 	val s = Array(n) { readLine()!! }
    307 	val c = Array(m + 1) { IntArray(n) { 0 } }
    308 	val rc = Array(m + 1) { IntArray(n) { 0 } }
    309 	
    310 	for (j in m - 1 downTo 0) {
    311 		val cur = Array(n) { intArrayOf(s[it][j].toInt(), c[j + 1][it], it) }
    312 		cur.sortWith(compareBy({it[0]}, {it[1]}))
    313 		for (i in 0 until n) rc[j][i] = cur[i][2]
    314 		c[j][cur[0][2]] = 0
    315 		for (i in 1 until n) {
    316 			val add = if (cur[i][0] == cur[i - 1][0] && cur[i][1] == cur[i - 1][1]) 0 else 1
    317 			c[j][cur[i][2]] = c[j][cur[i - 1][2]] + add
    318 		}
    319 	}
    320 	
    321 	val writer = PrintWriter(System.out)
    322 	
    323 	repeat(q) {
    324 		val t = readLine()!!
    325 		var ans = 0
    326 		var j = 0
    327 		while (j < m) {
    328 			var (nj, L, R) = intArrayOf(j, 0, n - 1)
    329 			while (nj < m) {
    330 				var (l1, r1, nL) = intArrayOf(L, R, R + 1)
    331 				while (l1 <= r1) {
    332 					val mid = (l1 + r1) / 2
    333 					if (s[rc[j][mid]][nj] >= t[nj]) {
    334 						nL = mid
    335 						r1 = mid - 1
    336 					} else {
    337 						l1 = mid + 1
    338 					}
    339 				}
    340 				
    341 				var (l2, r2, nR) = intArrayOf(nL, R, nL - 1)
    342 				while (l2 <= r2) {
    343 					val mid = (l2 + r2) / 2
    344 					if (s[rc[j][mid]][nj] <= t[nj]) {
    345 						nR = mid
    346 						l2 = mid + 1
    347 					} else {
    348 						r2 = mid - 1
    349 					}
    350 				}
    351 				
    352 				if (nL > nR)
    353 					break
    354 					
    355 				L = nL
    356 				R = nR
    357 				++nj
    358 			}
    359 			
    360 			if (j == nj) {
    361 				ans = 0
    362 				break
    363 			}
    364 			
    365 			ans += 1
    366 			j = nj
    367 		}
    368 		
    369 		writer.println(ans - 1)
    370 	}
    371 	
    372 	writer.close()
    373 }
    374 ```
    375 
    376 [1431J - Zero-XOR Array](/contest/1431/problem/J "Kotlin Heroes 5: ICPC Round")
    377 
    378 Idea: [Neon](/profile/Neon "Candidate Master Neon"), preparation: [Neon](/profile/Neon "Candidate Master Neon") and [adedalic](/profile/adedalic "International Master adedalic")
    379 
    380 **Tutorial**
    381 
    382 Tutorial is loading...
    383 
    384 **Solution (Ne0n25)**
    385 
    386 ```
    387 fun main() {
    388 	val MOD = 998244353
    389 	
    390 	fun add(x : Int, y : Int) : Int {
    391 		return x + y - if (x + y < MOD) 0 else MOD	
    392 	}
    393 	
    394 	fun mul(x : Int, y : Int) : Int {
    395 		return (1L * x * y % MOD).toInt()
    396 	}
    397 	
    398 	val inv = IntArray(60) { 0 }.also { it[0] = 1; it[1] = (MOD + 1) / 2 }
    399 	for (i in 2 until 60) {
    400 		inv[i] = mul(inv[i - 1], inv[1])
    401 	}
    402 	
    403 	val n = readLine()!!.toInt()
    404 	val a =	readLine()!!.split(" ").map { it.toLong() }
    405 	val target = a.fold(0.toLong()) { res, it -> res xor it }
    406 	val dp = Array(n) { Array(2) { IntArray(2) { 0 } } }
    407 	
    408 	var ans = 0
    409 	
    410 	val m = 1 shl (n - 1)
    411 	for (mask in 0 until m) {
    412 		val cur = Array(n - 1) { longArrayOf(a[it], a[it + 1]) }
    413 		val used = BooleanArray(n - 1) { false }
    414 		
    415 		for (pw in 59 downTo 0) {
    416 			for (i in 0 until n)
    417 				for (cnt in 0 until 2)
    418 					for (fl in 0 until 2)
    419 						dp[i][cnt][fl] = 0
    420 			dp[0][0][0] = 1
    421 			for (i in 0 until n - 1) {
    422 				for (cnt in 0 until 2) {
    423 					for (fl in 0 until 2) {
    424 						if (dp[i][cnt][fl] == 0)
    425 							continue
    426 						val (l, r) = cur[i]
    427 						if ((l shr pw) == (r shr pw)) {
    428 							if (!used[i] && ((mask shr i) and 1) == 1)
    429 								continue
    430 							val c = (l shr pw).toInt()
    431 							val len = (cur[i][1] - cur[i][0] + 1)
    432 							dp[i + 1][cnt xor c][fl] = add(dp[i + 1][cnt xor c][fl], mul((len % MOD).toInt(), dp[i][cnt][fl]))
    433 						} else for (c in 0 until 2) {
    434 							if (!used[i] && (c != (mask shr i) and 1))
    435 								continue
    436 							val nl = if (c == 1) 0L else l
    437 							var nr = if (c == 1) r - (1L shl pw) else (1L shl pw) - 1
    438 							val len = nr - nl + 1
    439 							val nfl = if (len == (1L shl pw) && (c != ((mask shr i) and 1))) 1 else 0
    440 							dp[i + 1][cnt xor c][fl or nfl] = add(dp[i + 1][cnt xor c][fl or nfl], mul((len % MOD).toInt(), dp[i][cnt][fl]))
    441 						}
    442 					}
    443 				}
    444 			}
    445 			
    446 			var cnt = ((target shr pw) and 1).toInt()
    447 			ans = add(ans, mul(dp[n - 1][cnt][1], inv[pw]))
    448 			if (pw == 0) 
    449 				ans = add(ans, dp[n - 1][cnt][0])
    450 			
    451 			for (i in 0 until n - 1) {
    452 				val (l, r) = cur[i]
    453 				if ((l shr pw) == (r shr pw)) {
    454 					val c = (l shr pw)
    455 					cnt = cnt xor c.toInt()
    456 					cur[i][0] -= c shl pw
    457 					cur[i][1] -= c shl pw
    458 				} else {
    459 					used[i] = true
    460 					val c = (mask shr i) and 1
    461 					cnt = cnt xor c.toInt()
    462 					cur[i][0] = if (c == 1) 0 else cur[i][0]
    463 					cur[i][1] = if (c == 1) cur[i][1] - (1L shl pw) else (1L shl pw) - 1
    464 				}
    465 			}
    466 			
    467 			if (cnt != 0)
    468 				break
    469 		}
    470 	}
    471 	
    472 	println(ans)
    473 }
    474 ```