We hope you enjoyed the problems! Thank you for participation.
The authors are the usual suspects: Neon, awoo, adedalic, Roms and me. Huge thanks to the testers: shnirelman, KIRIJIJI, soup, Optoed, le.mur, and the MVP tester PavelKunyavskiy. Without your insights, this round would be impossible!
Idea: BledDest, preparation: BledDest
Tutorial
Tutorial is loading...
Solution (PavelKunyavskiy)
fun main() {
val ans = IntArray(101) { Int.MAX_VALUE }
ans[0] = 0
for (i in ans.indices) {
for ((d, c) in listOf(1 to 1, 3 to 0, 5 to 0)) {
if (i + d in ans.indices) ans[i + d] = minOf(ans[i + d], ans[i] + c)
}
}
repeat(readInt()) {
println(ans[readInt()])
}
}
private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }
Idea: adedalic, preparation: adedalic
Tutorial
Tutorial is loading...
Solution (PavelKunyavskiy)
fun main() {
repeat(readInt()) {
val (k, m) = readInts()
println(maxOf(0, 2 * k - (m % (3 * k))))
}
}
private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }
Idea: BledDest, preparation: BledDest
Tutorial
Tutorial is loading...
Solution (PavelKunyavskiy)
fun main() {
repeat(readInt()) {
val (n, k) = readLongs()
println(n - k.countTrailingZeroBits())
}
}
private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }
Idea: BledDest, preparation: BledDest
Tutorial
Tutorial is loading...
Solution (PavelKunyavskiy)
fun main() {
repeat(readInt()) {
readInt()
val d = mutableListOf(mutableListOf<Long>())
for (i in readLongs()) {
if (i == 0L) {
d.add(mutableListOf())
} else {
d.last().add(i)
}
}
println(d.sumOf { l -> 2 * l.sum() - ((l.indices step 2).takeIf { l.size % 2 == 1 }?.maxOfOrNull { l[it] } ?: 0) })
}
}
private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }
1958E - Yet Another Permutation Constructive
Idea: BledDest, preparation: BledDest
Tutorial
Tutorial is loading...
Solution (PavelKunyavskiy)
private fun solve(): String {
val (n, k) = readInts()
var ans = listOf(n - 1, n)
repeat(k - 1) {
val min = ans.min()
val prevStart = min - ans.size + 1
if (prevStart <= 0) {
return "-1"
}
ans = ans.zip(prevStart .. min).flatMap { (a, b) -> listOf(a, b) }.dropLast(1)
}
ans = (1 until ans.min()) + ans
return ans.joinToString(" ")
}
fun main() {
repeat(readInt()) {
println(solve())
}
}
private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }
Idea: BledDest, preparation: awoo
Tutorial
Tutorial is loading...
Solution (PavelKunyavskiy)
private const val MOD = 1000000007
@JvmInline
@Suppress("NOTHING_TO_INLINE")
private value class ModInt(val x: Int) {
inline operator fun plus(other: ModInt) = ModInt((x + other.x).let { if (it >= MOD) it - MOD else it })
inline operator fun minus(other: ModInt) = ModInt((x - other.x).let { if (it < 0) it + MOD else it })
inline operator fun times(other: ModInt) = ModInt((x.toLong() * other.x % MOD).toInt())
fun power(p_: Int): ModInt {
var a = this
var res = ModInt(1)
var p = p_
while (p != 0) {
if ((p and 1) == 1) res *= a
a *= a
p = p shr 1
}
return res
}
inline operator fun div(other: ModInt) = this * other.inv()
inline fun inv() = power(MOD - 2)
companion object {
inline fun from(x: Int) = ModInt((x % MOD + MOD) % MOD)
inline fun from(x: Long) = ModInt(((x % MOD).toInt() + MOD) % MOD)
}
}
@JvmInline
private value class ModIntArray(val storage:IntArray) {
operator fun get(index: Int) = ModInt(storage[index])
operator fun set(index: Int, value: ModInt) { storage[index] = value.x }
val size get() = storage.size
}
private inline fun ModIntArray(n: Int, init: (Int) -> ModInt) = ModIntArray(IntArray(n) { init(it).x })
private const val COMB_MAX = 400_010
private val fs = ModIntArray(COMB_MAX) { ModInt(1) }.apply {
for (i in 1 until size) {
set(i, get(i - 1) * ModInt.from(i))
}
}
private val ifs = ModIntArray(COMB_MAX) { fs[it].inv() }
private fun cnk(n: Int, k: Int) = if (n >= k) fs[n] * ifs[k] * ifs[n - k] else ModInt(0)
fun main() {
val (n, k) = readInts()
val ans = ModIntArray(n + 1) { ModInt(0) }
for (diff in -n..n) {
val ways = maxOf(0, diff - 1)
val ll = maxOf(1, diff)
val rr = minOf(n, n - 1 + diff)
ans[ways] += ModInt(maxOf(0, rr - ll)) * cnk(n - diff - 1, k - 2)
}
for (i in 1 until n) {
ans[i] += cnk(n - i - 1, k - 1)
}
for (j in 0 until n - 1) {
ans[n - j - 1] += cnk(j, k - 1)
}
println(ans.storage.joinToString(" "))
}
private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }
Idea: BledDest, preparation: awoo
Tutorial
Tutorial is loading...
Solution (PavelKunyavskiy)
import kotlin.math.abs
import kotlin.math.sign
fun main() {
readInts()
val x = readInts()
val h = readInts()
val ord = buildList {
for (i in x.indices.sortedBy { x[it] }) {
while (isNotEmpty() && h[i] - h[last()] >= x[i] - x[last()]) {
removeLast()
}
if (isEmpty() || h[last()] - h[i] <= x[i] - x[last()]) {
add(i)
}
}
}.map { x[it] to h[it] }
fun nextAfter(pos: Int) = ord.binarySearch { (x, _) -> if (x >= pos) 1 else -1 }.inv()
fun coverBy(idx: Int, pos: Int) = ord.getOrNull(idx)?.let { (x, h) -> maxOf(0, abs(x - pos) - h) } ?: Int.MAX_VALUE
fun cover(pos: Int): Int {
val a = nextAfter(pos)
return minOf(coverBy(a - 1, pos), coverBy(a, pos))
}
fun cover2(l: Int, r: Int): Int {
val a = nextAfter((l + r) / 2)
return minOf(maxOf(coverBy(a, l), coverBy(a, r)), maxOf(coverBy(a - 1, l), coverBy(a - 1, r)))
}
val ans = List(readInt()) {
val (l, r) = readInts()
minOf(
cover(l) + cover(r),
cover2(l, r)
)
}
println(ans.joinToString(" "))
}
private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }
Tutorial
Tutorial is loading...
Solution (Neon)
import java.math.BigInteger
fun main() = repeat(readLine()!!.toInt()) {
val (n, hp) = readLine()!!.split(" ").let { (n, hp) -> n.toInt() to BigInteger(hp) }
val s = readLine()!!.split(" ").map { BigInteger(it) }
val m = readLine()!!.toInt()
val c = Array(m) { readLine()!!.split(" ").drop(1).map { it.toInt() - 1 } }
val delta = Array(m) { BigInteger.ZERO }
val minDelta = Array(m) { BigInteger.ZERO }
for (i in 0 until m) {
var curHP = BigInteger.ZERO
for (id in c[i]) {
if (id < n) {
curHP += s[id]
minDelta[i] = minOf(minDelta[i], curHP)
} else {
minDelta[i] = minOf(minDelta[i], curHP + minDelta[id - n])
curHP += delta[id - n]
}
}
delta[i] = curHP
}
fun rec(remHP : BigInteger, idCompSpell : Int) : Int {
var curHP = remHP
for (id in c[idCompSpell]) {
if (id < n) {
curHP += s[id]
if (curHP <= BigInteger.ZERO)
return id + 1
} else {
if (curHP + minDelta[id - n] <= BigInteger.ZERO)
return rec(curHP, id - n)
curHP += delta[id - n]
}
}
return -1
}
println(rec(hp, m - 1))
}
Idea: BledDest, preparation: Neon
Tutorial
Tutorial is loading...
Solution (PavelKunyavskiy)
fun readTree(n: Int) : List<BooleanArray> {
val p = listOf(null) + readInts().map { it - 1 }
return List(n) { a -> BooleanArray(n) { b -> a in generateSequence(b) { p[it] } } }
}
fun main() {
val n = readInt()
val t1 = readTree(n)
val t2 = readTree(n)
val masks = LongArray(n) { a ->
(0 until n).filter { b -> a != b && t1[a][b] == t2[a][b] && t1[b][a] == t2[b][a] }.sumOf { 1L shl it }
}
val data = mutableMapOf<Long, Int>()
data[0] = 0
fun compute(mask: Long) : Int = data.getOrPut(mask) {
val index = mask.countTrailingZeroBits()
maxOf(compute(mask xor (1L shl index)), compute(mask and masks[index]) + 1)
}
println(2 * (n - compute((1L shl n) - 1)))
}
private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }
Idea: BledDest, preparation: Neon
Tutorial
Tutorial is loading...
Solution (Neon)
const val M = 1000
const val K = 10
fun main() {
val (n, q) = readLine()!!.split(" ").map { it.toInt() }
val a = readLine()!!.split(" ").map { it.toInt() }
val b = readLine()!!.split(" ").map { it.toInt() }
val l = IntArray(q)
val r = IntArray(q)
for (i in 0 until q) {
val (x, y) = readLine()!!.split(" ").map { it.toInt() - 1}
l[i] = x
r[i] = y
}
val s = b.scan(0, Int::plus)
val ev = Array(n) { mutableListOf<Int>() }
for (i in 0 until n) {
for (j in 1 until K) {
val x = s[i] - (a[i] + j - 1) / j + 1
val pos = s.binarySearch { if (it < x) -1 else 1 }.inv()
if (pos < i) ev[pos].add(i)
}
}
val qr = Array(n) { mutableListOf<Int>() }
for (i in 0 until q) qr[l[i]].add(i)
val f = IntArray(n) { 0 }
fun inc(i : Int) = generateSequence(i) { (it or (it + 1)).takeIf { it < n } }.forEach { ++f[it] }
fun sum(i : Int) = generateSequence(i) { ((it and (it + 1)) - 1).takeIf { it >= 0 } }.sumOf { f[it] }
for (i in 0 until n) inc(i)
val ans = IntArray(q) { 0 }
for (i in 0 until n) {
for (j in ev[i]) inc(j)
for (j in qr[i]) {
var cur = b[l[j]]
for (x in 1 until M.coerceAtMost(r[j] - l[j] + 1)) {
ans[j] += (a[l[j] + x] + cur - 1) / cur
cur += b[l[j] + x]
}
if (l[j] + M <= r[j]) ans[j] += sum(r[j]) - sum(l[j] + M - 1)
}
}
println(ans.joinToString("\n"))
}
Can you add Editorial to the contest page
https://codeforces.net/contest/1958
The implementation of problem I is mind-blowing to me
I can't believe how clean it is, makes we wanna learn kotlin
Who has the solution in $$$O(n \sqrt A \log n)$$$ to the J problem