Author: MikeMirzayanov
Editorial
Tutorial is loading...
Solution (elizarov)
fun main() {
repeat(readLine()!!.toInt()) {
when (val n = readLine()!!.toInt()) {
in 0..999 -> println(n)
in 1000..999_499 -> println("${(n + 500) / 1000}K")
else -> println("${(n + 500_000) / 1_000_000}M")
}
}
}
Author: MikeMirzayanov
Editorial
Tutorial is loading...
Solution (elizarov)
fun main() {
class M(val a: Int, val b: Int)
repeat(readLine()!!.toInt()) {
val n = readLine()!!.toInt()
val ms = Array(n) {
readLine()!!.split(" ").map { it.toInt() }.let { (a, b) -> M(a, b) }
}
var ans = -1
fun check(x: Int) {
if (ms.count { m -> x in m.a..m.b } == 1) ans = x
}
for (m in ms) {
for (d in -1..1) {
check(m.a + d)
check(m.b + d)
}
}
println(ans)
}
}
Author: MikeMirzayanov
Editorial
Tutorial is loading...
Solution (elizarov)
fun main() {
repeat(readLine()!!.toInt()) {
val n = readLine()!!.toInt()
val a = readLine()!!.split(" ").map { it.toInt() }
val s = a.withIndex().sortedByDescending { it.value }
val i = s.indexOfLast { it.value > 0 }
val j = s.indexOfFirst { it.value < 0 }
val c = CharArray(n) { '0' }
for (k in 0 until i) c[s[k].index] = '1'
if (j >= 0 && -s[j].value < s[i].value) {
c[s[i].index] = '1'
c[s[j].index] = '1'
}
val sum = s.sumBy { if (c[it.index] == '1') it.value else 0 }
println(sum)
println(c.joinToString(""))
}
}
Author: MikeMirzayanov
Editorial
Tutorial is loading...
Solution (elizarov)
fun main() {
repeat(readLine()!!.toInt()) {
val (n, k) = readLine()!!.split(" ").map { it.toInt() }
val a = readLine()!!.split(" ").map { it.toInt() }
val s = a.withIndex().sortedByDescending { it.value }
val d = IntArray(n)
var rem = k
for (p in 1 until n) {
val i = s[p - 1].index
val j = s[p].index
d[j] = minOf(a[i] + d[i] - a[j] - 1, rem)
rem -= d[j]
}
val add = rem / n
val ext = rem % n
for (p in 0 until n) d[s[p].index] += add + if (p < ext) 1 else 0
println(d.joinToString(" "))
}
}
1297E - Modernization of Treeland
Author: MikeMirzayanov
Editorial
Tutorial is loading...
Solution (elizarov)
fun main() {
repeat(readLine()!!.toInt()) {
// readLine() // skip empty line
solveCase()
}
}
private fun solveCase() {
val (n, k) = readLine()!!.split(" ").map { it.toInt() }
val gf = IntArray(n) { -1 }
val gy = IntArray(2 * n)
val gn = IntArray(2 * n)
var ec = 0
fun edge(x: Int, y: Int) {
gy[ec] = y
gn[ec] = gf[x]
gf[x] = ec++
}
repeat(n - 1) {
val (x, y) = readLine()!!.split(" ").map { it.toInt() - 1 }
edge(x, y)
edge(y, x)
}
val v = BooleanArray(n)
val q = IntArray(n)
var h = 0
var t = 0
fun enqueue(x: Int) {
q[t++] = x
v[x] = true
}
enqueue(0)
var lc = 1
while (lc < k && h < t) {
val x = q[h++]
var i = gf[x]
var cc = 0
while (i >= 0 && lc < k) {
val y = gy[i]
if (!v[y]) {
enqueue(y)
if (cc++ > 0) lc++
}
i = gn[i]
}
if (x == 0 && cc == 1) lc++
}
if (lc < k) {
println("No")
return
}
println("Yes")
println(v.count { it })
println(v.withIndex().filter { it.value }.joinToString(" ") { (it.index + 1).toString() })
}
Author: MikeMirzayanov
Editorial
Tutorial is loading...
Solution (elizarov)
import java.util.*
fun main() {
repeat(readLine()!!.toInt()) {
// readLine() // skip empty line
solveCase()
}
}
private data class Mv(val i: Int, val a: Int, val b: Int, var t: Int = 0) : Comparable<Mv> {
override fun compareTo(other: Mv): Int = if (b != other.b) b.compareTo(other.b) else i.compareTo(other.i)
}
private fun solveCase() {
val (n, m) = readLine()!!.split(" ").map { it.toInt() }
val d = Array(n) { i ->
readLine()!!.split(" ").map { it.toInt() }.let { (a, b) -> Mv(i, a, b) }
}
d.sortBy { it.a }
var t = 0
val w = TreeSet<Mv>()
fun advance(to: Int) {
while (t < to && !w.isEmpty()) {
repeat(minOf(w.size, m)) {
val v = w.first()
v.t = t
w -= v
}
t++
}
t = to
}
for (v in d) {
advance(v.a)
w += v
}
advance(Int.MAX_VALUE)
d.sortBy { it.i }
println(maxOf(0, d.map { it.t - it.b }.max()!!))
println(d.joinToString(" ") { it.t.toString() })
}
Authors: MikeMirzayanov, Stepavly
Editorial
Tutorial is loading...
Solution (elizarov)
fun main() {
val (m, k) = readLine()!!.split(" ").map { it.toInt() }
val f = factor(m) ?: run {
println(-1)
return
}
val dp = HashMap<Long,Long>()
val dig = IntArray(100_000)
fun count(nd: Int, p: Long = -1): Long {
val e = f[0] + (f[1] shl 5) + (f[2] shl 10) + (f[3] shl 15) + (nd.toLong() shl 20)
if (nd == 0) return if (e == 0L) 1 else 0
if (p == -1L) dp[e]?.let { return it }
var cnt = 0L
for (d in 1..9) {
dig[nd - 1] = d
val df = factors[d]
for (i in 0..3) f[i] -= df[i]
if (f.all { it >= 0 }) {
val nc = count(nd - 1)
if (p >= 0 && cnt + nc > p) return count(nd - 1, p - cnt)
cnt += nc
}
for (i in 0..3) f[i] += df[i]
}
dp[e] = cnt
return cnt
}
var num = 1L
var nd = 1
while (count(nd) <= k - num) num += count(nd++)
check(count(nd, k - num) == 1L)
println(dig.take(nd).reversed().joinToString(""))
}
private val pr = listOf(2, 3, 5, 7)
private val factors = Array(10) { factor(it)!! }
private fun factor(m: Int): IntArray? {
val f = IntArray(4)
if (m <= 1) return f
var rem = m
for ((i, p) in pr.withIndex()) {
while (rem % p == 0) {
rem /= p
f[i]++
}
}
return f.takeIf { rem == 1 }
}
Authors: MikeMirzayanov, antontrygubO_o
Editorial
Tutorial is loading...
Solution (elizarov)
fun main() {
class Ans(val a: String, val m: String)
repeat(readLine()!!.toInt()) {
val s = readLine()!!
val n = s.length
val dp = Array(n) { i -> arrayOfNulls<Ans>(i + 1) }
dp[0][0] = Ans(s.substring(0, 1), "R")
var best = Ans(s, "")
fun updateBest(p: Ans) {
if (p.a <= best.a) best = p
}
fun updateDP(i: Int, j: Int, p: Ans) {
val cur = dp[i][j]
if (cur == null || p.a < cur.a) dp[i][j] = p
}
for (i in 1 until n) {
for (j in 0 until i) {
val p = dp[i - 1][j] ?: continue
updateDP(i, j, Ans(p.a + s[i], p.m + "R"))
if (j >= i - j) continue
if (s[i] == p.a[j]) updateDP(i, j + 1, Ans(p.a, p.m + "B"))
if (s[i] < p.a[j]) updateBest(Ans(p.a, p.m + "B".repeat(n - i)))
}
}
for (p in dp[n - 1]) if (p != null) updateBest(p)
println(best.m)
}
}
Authors: FieryPhoenix, dragonslayerintraining
Editorial
Tutorial is loading...
Solution (elizarov)
import java.util.*
private class Block(val l: Int, val r: Int) : Comparable<Block> {
fun cover(c: Block) = l <= c.l && r >= c.r
override fun compareTo(other: Block): Int = l.compareTo(other.l)
}
fun main() {
val (n, d) = readLine()!!.split(" ").map { it.toInt() }
val bh = arrayOfNulls<TreeSet<Block>>(n + 1) // blocks by height
// Segment tree
val tt = BooleanArray(4 * d) // terminal(leaf) node in segment tree
val th = IntArray(4 * d) // max height in this segment
tt[0] = true
// Segment tree functions
fun findMax(b: Block, i: Int, tl: Int, tr: Int): Int {
if (tt[i] || b.l <= tl && b.r >= tr) return th[i]
val tm = (tl + tr) / 2
return maxOf(
if (b.l <= tm) findMax(b, 2 * i + 1, tl, tm) else 0,
if (b.r > tm) findMax(b, 2 * i + 2, tm + 1, tr) else 0
)
}
fun setLeaf(i: Int, h: Int) {
tt[i] = true
th[i] = h
}
fun place(b: Block, h: Int, i: Int, tl: Int, tr: Int) {
if (b.l <= tl && b.r >= tr) return setLeaf(i, h)
val tm = (tl + tr) / 2
val j1 = 2 * i + 1
val j2 = 2 * i + 2
if (tt[i]) { // split node
tt[i] = false
setLeaf(j1, th[i])
setLeaf(j2, th[i])
}
if (b.l <= tm) place(b, h, j1, tl, tm)
if (b.r > tm) place(b, h, j2, tm + 1, tr)
th[i] = maxOf(th[j1], th[j2])
}
// Simulate each incoming block & print answer
var bc = 0
repeat(n) {
val b = readLine()!!.split(" ").map { it.toInt() }.let{ (l, r) -> Block(l, r) }
var maxH = findMax(b, 0, 1, d)
while (true) {
val bs = bh[maxH] ?: break
var floor = bs.floor(b)
if (floor != null && floor.r < b.l) floor = bs.higher(floor)
if (floor == null) floor = bs.first()
check(floor.l <= b.r)
val list = bs.tailSet(floor).takeWhile { it.l <= b.r }
if (!b.cover(list.first()) || !b.cover(list.last())) break
for (c in list) bs -= c // don't use bs.removeAll(list)
bc -= list.size
maxH--
}
val h = maxH + 1
place(b, h, 0, 1, d)
val bs = bh[h] ?: run { TreeSet<Block>().also { bh[h] = it } }
bs += b
println(++bc)
}
}
Auto comment: topic has been updated by adedalic (previous revision, new revision, compare).
BFS solution for E is nice and probably much more optimizable. The solution I went with in contest time was:
This is $$$O(n)$$$, but the constant factor is significant due to being easiest to implement with
LinkedHashSet
s. (data structure requirements are "get first element" and "delete arbitrary element"). Should still easily fit within the generous 5 sec time limit though.Edit: The potentially-ugly casework required to handle vertex $$$1$$$ in the BFS solution could be bypassed by starting the BFS from an arbitrary leaf node instead