First of all, I would like to thank all testers of the round: pashka, FlakeLCR, peti1234, Akulyat, bugdone, pacha2880. Also huge thanks to co-authors of the contest: Neon, adedalic and awoo.
I hope you enjoyed participating in the round!
Okay, now for the editorial itself:
1571A - Sequence of Comparisons
Idea: BledDest, preparation: Neon
Tutorial
Tutorial is loading...
Solution (Neon)
fun main() = repeat(readLine()!!.toInt()) {
val s = readLine()!!
val l = s.count({ it == '<' })
val g = s.count({ it == '>' })
if (l > 0 && g > 0) println("?")
else if (l > 0) println("<");
else if (g > 0) println(">");
else println("=");
}
Idea: BledDest, preparation: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
fun main() {
repeat(readLine()!!.toInt()) {
val n = readLine()!!.toInt()
val (d1, v1) = readLine()!!.split(' ').map { it.toInt() }
val (d3, v3) = readLine()!!.split(' ').map { it.toInt() }
val d2 = readLine()!!.toInt()
fun isPossible(d1: Int, v1: Int, d2: Int, v2: Int) = (v2 - v1) <= (d2 - d1)
for (v2 in v1..v3) {
if (isPossible(d1, v1, d2, v1) && isPossible(d2, v2, d3, v3)) {
println(v2)
break
}
}
}
}
Idea: BledDest, preparation: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
fun main() {
repeat(readLine()!!.toInt()) {
val n = readLine()!!.toInt()
var l = 0
var r = 4e5.toInt()
for (i in 1..n) {
val pairs = readLine()!!.split(' ')
val limit = pairs[0].commonSuffixWith(pairs[1]).length
if (pairs[2] == "0")
l = maxOf(l, limit + 1)
else
r = minOf(r, limit)
}
println(maxOf(0, r - l + 1))
if (r - l + 1 > 0)
println((l..r).joinToString(" "))
}
}
Idea: BledDest, preparation: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
fun main() {
val (n, m) = readLine()!!.split(' ').map { it.toInt() }
val cntPairs = Array(n) { IntArray(n) { 0 } }
val cntFirst = IntArray(n) { 0 }
val cntLast = IntArray(n) { 0 }
val firstPair = readLine()!!.split(' ').map { it.toInt() - 1 }
for (i in 2..m) {
val (f, l) = readLine()!!.split(' ').map { it.toInt() - 1 }
cntPairs[f][l]++
cntFirst[f]++
cntLast[l]++
}
fun I(a: Boolean) = if (a) 1 else 0
var worstPlace = 0
for (w in 0 until n) {
for (l in 0 until n) {
if (w == l)
continue
val yourScore = I(w == firstPair[0]) + I(l == firstPair[1])
var place = 1
if (yourScore < 2)
place += cntPairs[w][l]
if (yourScore < 1)
place += cntFirst[w] + cntLast[l] - 2 * cntPairs[w][l]
worstPlace = maxOf(worstPlace, place)
}
}
println(worstPlace)
}
Idea: BledDest, preparation: Neon
Tutorial
Tutorial is loading...
Solution (pashka)
@file:Suppress("CanBeVal")
import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.io.PrintWriter
import java.util.*
private fun solve() {
var n = readInt()
var s = readLn()
var a = readLn()
var j = -1
for (i in a.indices) {
if (a[i] == '1') {
if (j >= 0 && ((i - j) == 1 || (i - j) == 3)) {
println(-1)
return
}
j = i
}
}
var i = 0
var res = 0
while (i < a.length) {
if (a[i] == '1') {
j = i
while (j < a.length && a[j] == '1') {
j += 2
}
if (j == i + 2) {
res += minOf(diff(s.substring(i, i + 4), "(())"),
diff(s.substring(i, i + 4), "()()"))
} else {
for (k in i .. j step 2) {
res += diff(s.substring(k, k + 2), "()")
}
}
i = j + 1
} else {
i++
}
}
println(res)
}
private fun diff(a: String, b: String): Int {
var res = 0
for (i in a.indices) {
if (a[i] != b[i]) res++
}
return res
}
// TEMPLATE
fun main(args: Array<String>) {
reader = BufferedReader(InputStreamReader(System.`in`))
out = PrintWriter(OutputStreamWriter(System.out))
repeat(readInt()) {
solve()
}
out.close()
}
private lateinit var out: PrintWriter
private lateinit var reader: BufferedReader
private var tokenizer: StringTokenizer? = null
private fun read(): String {
while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {
tokenizer = StringTokenizer(readLn())
}
return tokenizer!!.nextToken()
}
private fun readInt() = read().toInt()
private fun readLong() = read().toLong()
private fun readLn() = reader.readLine()!!
private fun readInts() = readLn().split(" ").map { it.toInt() }
private fun readInts(sz: Int) = Array(sz) { readInt() }
private fun readLongs() = readLn().split(" ").map { it.toLong() }
private fun readLongs(sz: Int) = Array(sz) { readLong() }
private fun print(b: Boolean) = out.print(b)
private fun print(i: Int) = out.print(i)
private fun print(d: Double) = out.print(d)
private fun print(l: Long) = out.print(l)
private fun print(s: String) = out.print(s)
private fun print(message: Any?) = out.print(message)
private fun print(a: Array<Int>) = a.forEach { print("$it ") }
private fun <T> print(a: Array<out T>) = a.forEach { print("$it ") }
private fun <T> print(a: Collection<T>) = a.forEach { print("$it ") }
private fun println(b: Boolean) = out.println(b)
private fun println(i: Int) = out.println(i)
private fun println(d: Double) = out.println(d)
private fun println(l: Long) = out.println(l)
private fun println(s: String) = out.println(s)
private fun println() = out.println()
private fun println(message: Any?) = out.println(message)
private fun <T> println(a: Array<out T>) {
a.forEach { print("$it ") }
println()
}
private fun println(a: IntArray) {
a.forEach { print("$it ") }
println()
}
private fun println(a: LongArray) {
a.forEach { print("$it ") }
println()
}
private fun <T> println(a: Collection<T>) {
a.forEach { print("$it ") }
println()
}
private fun intarr(sz: Int, v: Int = 0) = IntArray(sz) { v }
private fun longarr(sz: Int, v: Long = 0) = LongArray(sz) { v }
private fun intarr2d(n: Int, m: Int, v: Int = 0) = Array(n) { intarr(m, v) }
private fun <T> init(vararg elements: T) = elements
private fun VI(n: Int = 0, init: Int = 0) = MutableList(n) { init }
private fun VVI(n: Int = 0, m: Int = 0, init: Int = 0) = MutableList(n) { VI(m, init) }
private fun <T1 : Comparable<T1>, T2 : Comparable<T2>> pairCmp(): Comparator<Pair<T1, T2>> {
return Comparator { a, b ->
val res = a.first.compareTo(b.first)
if (res == 0) a.second.compareTo(b.second) else res
}
}
Idea: BledDest, preparation: BledDest
Tutorial
Tutorial is loading...
Solution (pashka)
@file:Suppress("CanBeVal")
import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.io.PrintWriter
import java.util.*
private fun solve() {
var (n, m) = readInts()
var k = intarr(n)
var t = intarr(n)
for (i in k.indices) {
var (kk, tt) = readInts()
k[i] = kk
t[i] = tt
}
var s1 = 0
var s2 = 0
var d = intarr(m + 1, -1)
d[0] = 0
for (i in k.indices) {
if (t[i] == 2) {
s1 += k[i]
for (j in m downTo 0) {
if (d[j] != -1 && j + k[i] <= m && d[j + k[i]] == -1) {
d[j + k[i]] = i
}
}
} else {
s2 += k[i]
}
}
for (i in 0..m) {
if (d[i] == -1) continue
if (maxOf(i * 2 - 1, (s1 - i) * 2) + s2 > m) continue
var c = BooleanArray(n)
var x = i
while (x > 0) {
c[d[x]] = true
x -= k[d[x]]
}
var res = intarr(n)
var kk = 1
for (i in 0 until n) {
if (t[i] == 2 && c[i]) {
res[i] = kk
kk += k[i] * 2
}
}
kk = 2
for (i in 0 until n) {
if (t[i] == 2 && !c[i]) {
res[i] = kk
kk += k[i] * 2
}
}
kk = m + 1
for (i in 0 until n) {
if (t[i] == 1) {
kk -= k[i]
res[i] = kk
}
}
println(res)
return
}
println(-1)
}
// TEMPLATE
fun main(args: Array<String>) {
reader = BufferedReader(InputStreamReader(System.`in`))
out = PrintWriter(OutputStreamWriter(System.out))
// repeat(readInt()) {
solve()
// }
out.close()
}
private lateinit var out: PrintWriter
private lateinit var reader: BufferedReader
private var tokenizer: StringTokenizer? = null
private fun read(): String {
while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {
tokenizer = StringTokenizer(readLn())
}
return tokenizer!!.nextToken()
}
private fun readInt() = read().toInt()
private fun readLong() = read().toLong()
private fun readLn() = reader.readLine()!!
private fun readInts() = readLn().split(" ").map { it.toInt() }
private fun readInts(sz: Int) = Array(sz) { readInt() }
private fun readLongs() = readLn().split(" ").map { it.toLong() }
private fun readLongs(sz: Int) = Array(sz) { readLong() }
private fun print(b: Boolean) = out.print(b)
private fun print(i: Int) = out.print(i)
private fun print(d: Double) = out.print(d)
private fun print(l: Long) = out.print(l)
private fun print(s: String) = out.print(s)
private fun print(message: Any?) = out.print(message)
private fun print(a: Array<Int>) = a.forEach { print("$it ") }
private fun <T> print(a: Array<out T>) = a.forEach { print("$it ") }
private fun <T> print(a: Collection<T>) = a.forEach { print("$it ") }
private fun println(b: Boolean) = out.println(b)
private fun println(i: Int) = out.println(i)
private fun println(d: Double) = out.println(d)
private fun println(l: Long) = out.println(l)
private fun println(s: String) = out.println(s)
private fun println() = out.println()
private fun println(message: Any?) = out.println(message)
private fun <T> println(a: Array<out T>) {
a.forEach { print("$it ") }
println()
}
private fun println(a: IntArray) {
a.forEach { print("$it ") }
println()
}
private fun println(a: LongArray) {
a.forEach { print("$it ") }
println()
}
private fun <T> println(a: Collection<T>) {
a.forEach { print("$it ") }
println()
}
private fun intarr(sz: Int, v: Int = 0) = IntArray(sz) { v }
private fun longarr(sz: Int, v: Long = 0) = LongArray(sz) { v }
private fun intarr2d(n: Int, m: Int, v: Int = 0) = Array(n) { intarr(m, v) }
private fun <T> init(vararg elements: T) = elements
private fun VI(n: Int = 0, init: Int = 0) = MutableList(n) { init }
private fun VVI(n: Int = 0, m: Int = 0, init: Int = 0) = MutableList(n) { VI(m, init) }
private fun <T1 : Comparable<T1>, T2 : Comparable<T2>> pairCmp(): Comparator<Pair<T1, T2>> {
return Comparator { a, b ->
val res = a.first.compareTo(b.first)
if (res == 0) a.second.compareTo(b.second) else res
}
}
1571G - A Battle Against a Dragon
Idea: BledDest, preparation: awoo
Tutorial
Tutorial is loading...
Solution (awoo)
class Attack(val a: Int, val b: Int, val i: Int)
fun main() {
val (n, m) = readLine()!!.split(" ").map { it.toInt() }
val ev = ArrayList<Attack>()
for (i in 0 until n) {
val k = readLine()!!.toInt()
val a = readLine()!!.split(" ").map { it.toInt() }
val b = readLine()!!.split(" ").map { it.toInt() }
for (j in 0 until k) {
ev.add(Attack(a[j], b[j], i))
}
}
ev.sortWith(compareBy({ -it.b }, { it.i }))
val INF = 1e18.toLong()
val mx = m + n + 1
val f = LongArray(mx) { -INF }
fun update(pos: Int, x: Long) {
var i = pos
while (i < mx) {
f[i] = maxOf(f[i], x)
i = i or (i + 1)
}
}
fun query(pos: Int) : Long {
var res = -INF
var i = pos
while (i >= 0) {
res = maxOf(res, f[i])
i = (i and (i + 1)) - 1
}
return res
}
update(m - 1, 0L)
for (it in ev) {
val dp = query(it.i + it.b - 1) + it.a
update(it.i + it.b, dp)
}
println(query(mx - 1))
}
Idea: BledDest, preparation: BledDest
Tutorial
Tutorial is loading...
Solution (pashka)
@file:Suppress("CanBeVal")
import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.io.PrintWriter
import java.util.*
private fun solveTest() {
var n = readInt()
var l = readInts()
var r = readInts()
var rr = r.toMutableList()
rr.sort()
var x = Integer.MAX_VALUE
for (i in 0 until n) {
x = minOf(x, rr[i] - i)
}
var a = (0 until n).toMutableList()
a.sortBy { i -> l[i] }
var j = 0
var pq = PriorityQueue<Int>(compareBy { i -> r[i] })
var res = intarr(n)
for (t in x until x + n) {
while (j < n && l[a[j]] <= t) {
pq.add(a[j])
j++
}
if (pq.isEmpty()) {
println(-1)
return
}
var q = pq.remove()
if (r[q] < t) {
println(-1)
return
}
res[t - x] = q + 1
}
println(x)
println(res)
}
private fun solve() {
var t = readInt()
while (t-- > 0) {
solveTest()
}
}
// TEMPLATE
fun main(args: Array<String>) {
reader = BufferedReader(InputStreamReader(System.`in`))
out = PrintWriter(OutputStreamWriter(System.out))
solve()
out.close()
}
private lateinit var out: PrintWriter
private lateinit var reader: BufferedReader
private var tokenizer: StringTokenizer? = null
private fun read(): String {
while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {
tokenizer = StringTokenizer(readLn())
}
return tokenizer!!.nextToken()
}
private fun readInt() = read().toInt()
private fun readLong() = read().toLong()
private fun readLn() = reader.readLine()!!
private fun readInts() = readLn().split(" ").map { it.toInt() }
private fun readInts(sz: Int) = Array(sz) { readInt() }
private fun readLongs() = readLn().split(" ").map { it.toLong() }
private fun readLongs(sz: Int) = Array(sz) { readLong() }
private fun print(b: Boolean) = out.print(b)
private fun print(i: Int) = out.print(i)
private fun print(d: Double) = out.print(d)
private fun print(l: Long) = out.print(l)
private fun print(s: String) = out.print(s)
private fun print(message: Any?) = out.print(message)
private fun print(a: Array<Int>) = a.forEach { print("$it ") }
private fun <T> print(a: Array<out T>) = a.forEach { print("$it ") }
private fun <T> print(a: Collection<T>) = a.forEach { print("$it ") }
private fun println(b: Boolean) = out.println(b)
private fun println(i: Int) = out.println(i)
private fun println(d: Double) = out.println(d)
private fun println(l: Long) = out.println(l)
private fun println(s: String) = out.println(s)
private fun println() = out.println()
private fun println(message: Any?) = out.println(message)
private fun <T> println(a: Array<out T>) {
a.forEach { print("$it ") }
println()
}
private fun println(a: IntArray) {
a.forEach { print("$it ") }
println()
}
private fun <T> println(a: Collection<T>) {
a.forEach { print("$it ") }
println()
}
private fun intarr(sz: Int, v: Int = 0) = IntArray(sz) { v }
private fun longarr(sz: Int, v: Long = 0) = LongArray(sz) { v }
private fun intarr2d(n: Int, m: Int, v: Int = 0) = Array(n) { intarr(m, v) }
private fun <T> init(vararg elements: T) = elements
private fun VI(n: Int = 0, init: Int = 0) = MutableList(n) { init }
private fun VVI(n: Int = 0, m: Int = 0, init: Int = 0) = MutableList(n) { VI(m, init) }
private fun <T1 : Comparable<T1>, T2 : Comparable<T2>> pairCmp(): Comparator<Pair<T1, T2>> {
return Comparator { a, b ->
val res = a.first.compareTo(b.first)
if (res == 0) a.second.compareTo(b.second) else res
}
}
Idea: BledDest, preparation: awoo
Tutorial
Tutorial is loading...
Solution (awoo)
import java.util.*
fun main() = repeat(readLine()!!.toInt()) {
val n = readLine()!!.toInt()
val L = readLine()!!.split(" ").map { it.toInt() }
val R = readLine()!!.split(" ").map { it.toInt() }
val ord = Array(n, { i -> i })
ord.sortWith({x : Int, y: Int -> L[x] - L[y]})
val ans = IntArray(n)
fun check(m: Int, fl: Boolean): Int {
val cur = PriorityQueue<Int>(compareBy { R[it] })
var j = 0
var res = 0
for (t in m until m + n) {
while (j < n && L[ord[j]] <= t) {
cur.add(ord[j])
++j;
}
if (cur.isEmpty()) {
res = 1
break
}
if (R[cur.peek()] < t) {
res = -1
break
}
if (fl) ans[t - m] = cur.peek() + 1
cur.poll()
}
return res;
}
var l = 1
var r = 1e9.toInt()
var res = -1
while (l <= r) {
val m = (l + r) / 2
val tmp = check(m, false)
if (tmp == 0) {
res = m
break
}
if (tmp == -1) {
r = m - 1
}
else {
l = m + 1
}
}
println(res)
if (res != -1) {
check(res, true)
println(ans.joinToString(" "))
}
}
Idea: BledDest, preparation: BledDest
Tutorial
Tutorial is loading...
Solution (pashka)
@file:Suppress("CanBeVal")
import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.io.PrintWriter
import java.util.*
private class SegmentTree(private val size: Int) {
class Item(val a: Long) {
fun add(item: Item): Item {
return if (a < item.a) this else item
}
}
val NEUTRAL = Item(Long.MAX_VALUE)
private val a: Array<Item>
operator fun set(i: Int, v: Item) {
set(0, 0, size, i, v)
}
private operator fun set(n: Int, l: Int, r: Int, i: Int, v: Item) {
if (r == l + 1) {
a[n] = a[n].add(v)
} else {
val m = (l + r) / 2
if (i < m) {
set(n * 2 + 1, l, m, i, v)
} else {
set(n * 2 + 2, m, r, i, v)
}
a[n] = a[n * 2 + 1].add(a[n * 2 + 2])
}
}
fun sum(l: Int, r: Int): Item {
return sum(0, 0, size, l, r)
}
private fun sum(n: Int, ll: Int, rr: Int, l: Int, r: Int): Item {
return if (ll >= l && rr <= r) {
a[n]
} else if (ll >= r || l >= rr) {
NEUTRAL
} else {
val m = (ll + rr) / 2
sum(n * 2 + 1, ll, m, l, r).add(sum(n * 2 + 2, m, rr, l, r))
}
}
init {
a = Array<Item>(4 * size) { NEUTRAL }
}
}
private fun solveTest() {
var n = readInt()
var a = readLongs(n - 1)
var b = readLongs(n - 1)
var c = readLongs(n)
var d = longarr(n - 1)
for (i in d.indices) {
d[i] = when (i) {
0 -> minOf(b[i], c[i])
n - 2 -> minOf(b[i], c[i + 1])
else -> b[i]
}
}
for (i in 1..n - 2) {
d[i] = minOf(d[i], c[i] + d[i - 1])
}
for (i in n - 3 downTo 0) {
d[i] = minOf(d[i], c[i + 1] + d[i + 1])
}
var st = SegmentTree(n - 1)
for (i in 0..n - 2) {
st[i] = SegmentTree.Item(d[i] + a[i])
}
var ul = longarr(n - 1)
var s = 0L
for (i in 0..n - 2) {
s += c[i]
ul[i] = s
}
var ur = longarr(n - 1)
s = 0L
for (i in n - 2 downTo 0) {
s += c[i + 1]
ur[i] = s
}
var stl = SegmentTree(n - 1)
for (i in 0..n - 2) {
stl[i] = SegmentTree.Item(a[i] + ul[i])
}
var str = SegmentTree(n - 1)
for (i in 0..n - 2) {
str[i] = SegmentTree.Item(a[i] + ur[i])
}
var q = readInt()
while (q-- > 0) {
var (l, r) = readInts(2)
l--; r--
var res = st.sum(l, r).a
if (l > 0) {
var s1 = stl.sum(l, r).a - ul[l - 1]
// var s2 = str.sum(0, l).a - ur[l - 1]
res = minOf(res, s1)
}
if (r < n - 1) {
var s1 = str.sum(l, r).a - ur[r]
// var s2 = stl.sum(r, n - 1).a - ul[r]
res = minOf(res, s1)
}
println(res)
}
}
private fun solve() {
// repeat(readInt()) {
solveTest()
// }
}
// TEMPLATE
fun main(args: Array<String>) {
reader = BufferedReader(InputStreamReader(System.`in`))
out = PrintWriter(OutputStreamWriter(System.out))
solve()
out.close()
}
private lateinit var out: PrintWriter
private lateinit var reader: BufferedReader
private var tokenizer: StringTokenizer? = null
private fun read(): String {
while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {
tokenizer = StringTokenizer(readLn())
}
return tokenizer!!.nextToken()
}
private fun readInt() = read().toInt()
private fun readLong() = read().toLong()
private fun readLn() = reader.readLine()!!
private fun readInts() = readLn().split(" ").map { it.toInt() }
private fun readInts(sz: Int) = Array(sz) { readInt() }
private fun readLongs() = readLn().split(" ").map { it.toLong() }
private fun readLongs(sz: Int) = Array(sz) { readLong() }
private fun print(b: Boolean) = out.print(b)
private fun print(i: Int) = out.print(i)
private fun print(d: Double) = out.print(d)
private fun print(l: Long) = out.print(l)
private fun print(s: String) = out.print(s)
private fun print(message: Any?) = out.print(message)
private fun print(a: Array<Int>) = a.forEach { print("$it ") }
private fun <T> print(a: Array<out T>) = a.forEach { print("$it ") }
private fun <T> print(a: Collection<T>) = a.forEach { print("$it ") }
private fun println(b: Boolean) = out.println(b)
private fun println(i: Int) = out.println(i)
private fun println(d: Double) = out.println(d)
private fun println(l: Long) = out.println(l)
private fun println(s: String) = out.println(s)
private fun println() = out.println()
private fun println(message: Any?) = out.println(message)
private fun <T> println(a: Array<out T>) {
a.forEach { print("$it ") }
println()
}
private fun println(a: IntArray) {
a.forEach { print("$it ") }
println()
}
private fun <T> println(a: Collection<T>) {
a.forEach { print("$it ") }
println()
}
private fun intarr(sz: Int, v: Int = 0) = IntArray(sz) { v }
private fun longarr(sz: Int, v: Long = 0) = LongArray(sz) { v }
private fun intarr2d(n: Int, m: Int, v: Int = 0) = Array(n) { intarr(m, v) }
private fun <T> init(vararg elements: T) = elements
private fun VI(n: Int = 0, init: Int = 0) = MutableList(n) { init }
private fun VVI(n: Int = 0, m: Int = 0, init: Int = 0) = MutableList(n) { VI(m, init) }
private fun <T1 : Comparable<T1>, T2 : Comparable<T2>> pairCmp(): Comparator<Pair<T1, T2>> {
return Comparator { a, b ->
val res = a.first.compareTo(b.first)
if (res == 0) a.second.compareTo(b.second) else res
}
}
Cant Submit These question. Put a lot of time on the E question but cant even submit it.Plz look into it