This round was prepared by Neon, adedalic, awoo, shnirelman and me.
Huge thanks to all of the testers: ashmelev, KIRIJIJI, PavelKunyavskiy, soup and Fanarill! Your feedback helped us balance this contest (and find a very stupid overflow bug I'm too ashamed to mention).
Thanks for participation, we hope you enjoyed the contest!
Idea: BledDest, preparation: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
fun main() = repeat(readln().toInt()) {
readln().toInt()
val a = readln().split(" ").map { it.toInt() }
println(if (a.dropLast(1).contains(a.last() - 1)) a.last() - 1 else "Ambiguous")
}
Idea: BledDest, preparation: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
fun main() = repeat(readln().toInt()) {
val n = readln().toInt()
println((listOf(1) + (n downTo 2)).joinToString(" "))
}
Idea: BledDest, preparation: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
fun main() = repeat(readln().toInt()) {
val a = readln().split("+")
val ans = a.foldIndexed(0L) { i, res, s ->
res + if (i == 0 || i == a.size - 1)
s.toLong()
else
(1 until s.length).maxOf { s.take(it).toLong() + s.drop(it).toLong() }
}
println(ans)
}
Idea: BledDest, preparation: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
fun main() {
repeat(readln().toInt()) {
val (n, h, b) = readln().split(' ').map { it.toLong() }
val grid = Array(2) { readln() }
val sheepColumn = grid[0].indices.find { grid[0][it] == 'S' || grid[1][it] == 'S' }!!
val wolvesLeft = (0..1).sumOf { grid[it].take(sheepColumn).count { it == 'W' } }
val wolvesRight = (0..1).sumOf { grid[it].substring(sheepColumn).count { it == 'W' } }
val ans = minOf(
(wolvesLeft + wolvesRight) * h,
wolvesLeft * h + 2 * b,
wolvesRight * h + 2 * b,
3 * b
)
println(ans)
}
}
2011E - Rock-Paper-Scissors Bot
Idea: BledDest, preparation: Neon
Tutorial
Tutorial is loading...
Solution (Neon)
const val INF = 1e9.toInt()
const val vars = "RPS"
fun main() = repeat(readln().toInt()) {
val a = readln().map { vars.indexOf(it) }
fun calc(a : List<Int>) : Int {
if (a[0] != 0) return INF
val balance = a.zipWithNext().fold(0) { s, (x, y) ->
s + (if (x == y) 1 else 0) - (if ((x + 2) % 3 == y) 1 else 0)
}
return a.size + maxOf(balance, 0)
}
println(minOf(
calc(a),
calc(listOf(0) + a),
calc(listOf(0, 2) + a)
))
}
Idea: BledDest, preparation: Neon
Tutorial
Tutorial is loading...
Solution (Neon)
fun main() = repeat(readln().toInt()) {
val n = readln().toInt()
val a = readln().split(" ").map { it.toInt() - 1 }
val prev = IntArray(n + 1) { -1 }
val pos = IntArray(n) { -1 }
for (i in 0 until n) {
for (j in a[i]-1..a[i]+1) {
if (0 <= j && j < n) {
prev[i] = maxOf(prev[i], pos[j])
}
}
pos[a[i]] = i
}
val st = mutableListOf(n)
var ans = 0L
for (i in (n - 1) downTo 0) {
while (st.size > 0 && prev[st.last()] >= i) {
st.removeLast()
}
ans += st.last() - i
st.add(i)
}
println(ans)
}
2011G - Removal of a Permutation
Idea: BledDest, preparation: Neon
Tutorial
Tutorial is loading...
Solution (Neon)
const val LOG = 19
fun main() = repeat(readln().toInt()) {
val n = readln().toInt()
val p = readln().split(" ").map { it.toInt() - 1 }
val ans = IntArray(n - 1) { n }
fun rec(step: Int, p: List<Int>) {
if (p.size == 1 || step == LOG) return
for (cur in listOf(p, p.reversed())) {
val (a, b) = cur.zipWithNext().partition { (x, y) -> x < y }
a.forEach { (x, _) -> ans[x] = minOf(ans[x], step) }
rec(step + 1, b.map { (x, _) -> x} + cur.last())
}
}
rec(1, p)
println(ans.joinToString(" "))
}
Idea: BledDest, preparation: Neon
Tutorial
Tutorial is loading...
Solution (Neon)
const val INF = 1e9.toInt()
const val B = 5
fun main() = repeat(readln().toInt()) {
val (n, m, k) = readInts()
val a = Array(n) { readInts() }
var ans = 0
for (bit in 0 until B) {
val g = Array(n) { ArrayList<Pair<Int, Int>>() }
for (i in 0 until n) {
for (j in 0 until i) {
val cnt = IntArray(4) { 0 }
for (x in 0 until m) {
val f = (a[i][x] shr bit) and 1
val s = (a[j][x] shr bit) and 1
++cnt[f * 2 + s];
}
val f1 = (cnt[0] < k && cnt[3] < k)
val f2 = (cnt[1] < k && cnt[2] < k)
if (f1 != f2) {
g[i].add(j to if (f2) 1 else 0)
g[j].add(i to if (f2) 1 else 0)
} else if (!f1) {
return@repeat println("-1")
}
}
}
val color = IntArray(n) { -1 }
val cnt = IntArray(2) { 0 }
var ok = true
fun dfs(v: Int, c: Int) {
color[v] = c
++cnt[c]
for ((u, d) in g[v]) {
if (color[u] != -1) {
if ((c xor d) != color[u]) {
ok = false
}
} else {
dfs(u, c xor d)
}
}
}
for (v in 0 until n) {
if (color[v] != -1) continue
cnt.fill(0)
dfs(v, 0)
if (!ok) return@repeat println("-1")
ans += cnt.min() shl bit
}
}
println(maxOf(0, ans))
}
fun readInts() = readln().split(" ").map { it.toInt() }
Idea: shnirelman, preparation: awoo
Tutorial
Tutorial is loading...
Solution (awoo)
class Query(val t: Int, val x: Int)
class BIT(val mx: Int) {
val f = LongArray(mx) { 0L }
fun upd_pr(pos: Int, x: Int) {
var i = pos
while (i < mx) {
f[i] = f[i] + x
i = i or (i + 1)
}
}
fun get_pr(pos: Int) : Long {
var res = 0L
var i = pos
while (i >= 0) {
res += f[i]
i = (i and (i + 1)) - 1
}
return res
}
fun upd_su(pos: Int, x: Int) {
var i = pos
while (i >= 0) {
f[i] = f[i] + x
i = (i and (i + 1)) - 1
}
}
fun get_su(pos: Int) : Long {
var res = 0L
var i = pos
while (i < mx) {
res += f[i]
i = i or (i + 1)
}
return res
}
}
fun main() {
val n = readLine()!!.toInt()
val a = readLine()!!.split(" ").map { it.toInt() }
val q = Array(n) { Query(-1, -1) }
for (i in 0 until n) {
val (t, x) = readLine()!!.split(" ").map { it.toInt() }
q[i] = Query(t, x - 1)
}
val d = IntArray(n + 1) { 0 }
fun apply(coef: Int) {
var qs = Array<ArrayList<Pair<Int, Int>>>(n + 1) { ArrayList<Pair<Int, Int>>() }
for (i in 0 until n) {
qs[0].add(Pair(i, n + 1))
}
var len = n + 1
while (true) {
val posq = IntArray(n) { -1 }
val poss = IntArray(n) { -1 }
val sv = IntArray(n) { -1 }
val fq = BIT(n)
val fs = BIT(n)
var cntq = 0
var cnts = 0
val nqs = Array<ArrayList<Pair<Int, Int>>>(n + 1) { ArrayList<Pair<Int, Int>>() }
var j = 0
var last = true
for (l in 0 until n + 1) {
for (it in qs[l]) {
val i = it.first
val r = it.second
if (r - l == 1) {
d[l] += coef
continue
}
last = false
val m = (l + r) / 2
while (j < m) {
val x = q[j].x
if (q[j].t == 1) {
posq[x] = cntq
sv[x] = cnts
cntq += 1
cnts += 1
fq.upd_pr(posq[x], a[x])
}
else if (q[j].t == 2){
poss[x] = cnts
cnts += 1
fs.upd_su(poss[x], a[x])
}
else{
fq.upd_pr(posq[x], -a[x])
posq[x] = -1
poss[x] = sv[x]
fs.upd_su(poss[x], a[x])
}
j += 1
}
assert(j == m)
if (poss[i] == -1 || posq[i] == -1) {
nqs[m].add(Pair(i, r))
continue
}
val tq = fq.get_pr(posq[i] - 1)
val ts = fs.get_su(poss[i] + 1)
var ok = true
if (coef == 1) {
ok = tq - a[i] >= ts
}
else {
ok = tq + a[i] > ts
}
if (ok) {
nqs[m].add(Pair(i, r))
}
else {
nqs[l].add(Pair(i, m))
}
}
}
qs = nqs
if (last) {
break
}
}
println("")
}
apply(1)
apply(-1)
for (i in 0 until n) {
d[i + 1] += d[i]
}
val res = d.map { x -> (if (x == 0) "Yes" else "No") }
println(res.take(res.size - 1).joinToString(separator = "\n"))
}
Solution 2 (awoo)
class Query(val t: Int, val x: Int)
class BIT(val mx: Int) {
val f = LongArray(mx) { 0L }
fun upd_pr(pos: Int, x: Int) {
var i = pos
while (i < mx) {
f[i] = f[i] + x
i = i or (i + 1)
}
}
fun get_pr(pos: Int) : Long {
var res = 0L
var i = pos
while (i >= 0) {
res += f[i]
i = (i and (i + 1)) - 1
}
return res
}
fun upd_su(pos: Int, x: Int) {
var i = pos
while (i >= 0) {
f[i] = f[i] + x
i = (i and (i + 1)) - 1
}
}
fun get_su(pos: Int) : Long {
var res = 0L
var i = pos
while (i < mx) {
res += f[i]
i = i or (i + 1)
}
return res
}
}
fun main() {
val n = readLine()!!.toInt()
val a = readLine()!!.split(" ").map { it.toInt() }
val q = Array(n) { Query(-1, -1) }
for (i in 0 until n) {
val (t, x) = readLine()!!.split(" ").map { it.toInt() }
q[i] = Query(t, x - 1)
}
val fq = BIT(n)
val fs = BIT(n)
val d = IntArray(n + 1) { 0 }
val posq = IntArray(n) { -1 }
val poss = IntArray(n) { -1 }
val sv = IntArray(n) { -1 }
var cntq = 0
var cnts = 0
fun calc(l: Int, r: Int, coef: Int, all: ArrayList<Int>) {
if (l == r - 1) {
d[l] += all.size * coef
return
}
val m = (l + r) / 2
val who_chg = ArrayList<Int>()
val idx_chg = ArrayList<Int>()
val val_chg = ArrayList<Int>()
val chq = ArrayList<Pair<Int, Int>>()
val chs = ArrayList<Pair<Int, Int>>()
for (i in l until m) {
val x = q[i].x
if (q[i].t == 1) {
who_chg.add(0)
idx_chg.add(x)
val_chg.add(posq[x])
posq[x] = cntq
who_chg.add(2)
idx_chg.add(x)
val_chg.add(sv[x])
sv[x] = cnts
cntq += 1
cnts += 1
chq.add(Pair(posq[x], -a[x]))
fq.upd_pr(posq[x], a[x])
}
else if (q[i].t == 2){
who_chg.add(1)
idx_chg.add(x)
val_chg.add(poss[x])
poss[x] = cnts
cnts += 1
chs.add(Pair(poss[x], -a[x]))
fs.upd_su(poss[x], a[x])
}
else{
chq.add(Pair(posq[x], a[x]))
fq.upd_pr(posq[x], -a[x])
who_chg.add(0)
idx_chg.add(x)
val_chg.add(posq[x])
posq[x] = -1
who_chg.add(1)
idx_chg.add(x)
val_chg.add(poss[x])
poss[x] = sv[x]
who_chg.add(2)
idx_chg.add(x)
val_chg.add(sv[x])
sv[x] = -1
chs.add(Pair(poss[x], -a[x]))
fs.upd_su(poss[x], a[x])
}
}
val tol = ArrayList<Int>()
val tor = ArrayList<Int>()
for (x in all) {
if (poss[x] == -1 || posq[x] == -1) {
tor.add(x)
continue
}
val tq = fq.get_pr(posq[x] - 1)
val ts = fs.get_su(poss[x] + 1)
var ok = true
if (coef == 1) {
ok = tq - a[x] >= ts
}
else {
ok = tq + a[x] > ts
}
if (ok) {
tor.add(x)
}
else {
tol.add(x)
}
}
calc(m, r, coef, tor)
who_chg.reverse()
idx_chg.reverse()
val_chg.reverse()
for (i in 0 until who_chg.size) {
if (who_chg[i] == 0) {
posq[idx_chg[i]] = val_chg[i]
}
else if (who_chg[i] == 1) {
poss[idx_chg[i]] = val_chg[i]
}
else {
sv[idx_chg[i]] = val_chg[i]
}
}
for (i in l until m) {
if (q[i].t == 1) {
cntq -= 1
cnts -= 1
}
else if (q[i].t == 2){
cnts -= 1
}
}
for (it in chq) {
fq.upd_pr(it.first, it.second)
}
for (it in chs) {
fs.upd_su(it.first, it.second)
}
calc(l, m, coef, tol)
}
val all = ArrayList<Int>()
for (i in 0 until n) {
all.add(i)
}
calc(0, n + 1, 1, all)
calc(0, n + 1, -1, all)
for (i in 0 until n) {
d[i + 1] += d[i]
}
val res = d.map { x -> (if (x == 0) "Yes" else "No") }
println(res.take(res.size - 1).joinToString(separator = "\n"))
}
For problem I, it is fast enough to directly binary search on the persistent segment tree, in same complexity $$$O(\log^2 n)$$$ but (a lot) worse constant factor. This option is easier to implement (less problem specific thinking, more general implementation) than either of the two, especially if a optimised (array based, not object based) persistent segment tree is available to you.
Usually I would not dare to persistent binary search even at 1e5 and 4 seconds. This time around I thought it is worth the risk to quickly get the solve on I. This is also a believe that Kotlin Heroes in general have more lenient TLs since people just trying out Kotlin will not know how to write the most optimised kotlin code. I also thought there is enough time left to change to D&C BIT if it turns out to TL -- I was wrong as I misread and caught two silly WAs. I am happy it ended up passing.