First of all, I would like to thank all of the testers: elizarov, darnley, IlyaLos, _overrated_, SergeyMelnikov, winger, FieryPhoenix, infinitepro, Sho, GrandDaddy, bfs.07, spookywooky. Also huge thanks to co-authors of the contest: MikeMirzayanov, Neon, Roms, adedalic, vovuh and awoo.
I hope you enjoyed participating in the round!
Okay, now for the editorial itself:
Idea: BledDest, preparation: awoo
Tutorial
Tutorial is loading...
Solution (elizarov)
fun main() {
repeat(readLine()!!.toInt()) {
val (n, k) = readLine()!!.split(" ").map { it.toInt() }
val n1 = n / (1 + k + k * k + k * k * k)
val n2 = n1 * k
val n3 = n2 * k
val n4 = n3 * k
println("$n1 $n2 $n3 $n4")
}
}
Idea: BledDest, preparation: Neon
Tutorial
Tutorial is loading...
Solution (elizarov)
fun main() {
repeat(readLine()!!.toInt()) {
val (n, k1, k2) = readLine()!!.split(" ").map { it.toInt() }
val s = readLine()!!
var m = 0
var prev = 0
for (c in s) {
if (c == '1') {
prev = minOf(k2 - prev, k1)
m += prev
} else {
prev = 0
}
}
println(m)
}
}
Idea: vovuh, preparation: vovuh
Tutorial
Tutorial is loading...
Solution (elizarov)
fun main() {
repeat(readLine()!!.toInt()) {
val (n, k, x, y) = readLine()!!.split(" ").map { it.toInt() }
val a = readLine()!!.split(" ").map { it.toInt() }.sorted()
val maxSum = k * n.toLong()
var sum = 0L
var ans = 0
var ok = true
var i = 0
while (i < n && sum + a[i] <= maxSum) {
sum += a[i]
if (ok && a[i] > k) {
ok = false
ans = (n - i) * x // can simply drop the rest
}
i++
}
ans = if (ok) (n - i) * x // drop the rest
else minOf(ans, (n - i) * x + y) // drop the rest & rearrange
println(ans)
}
}
1346D - Constructing the Dungeon
Idea: MikeMirzayanov, preparation: Neon
Tutorial
Tutorial is loading...
Solution (elizarov)
fun main() {
repeat(readLine()!!.toInt()) {
val (n, m) = readLine()!!.split(" ").map { it.toInt() }
val e = List(m) {
val (u, v, w) = readLine()!!.split(" ").map { it.toInt() }
Tun(u - 1, v - 1, w)
}
val a = solveDungeon(n, e)
if (a != null) {
println("YES")
println(a.joinToString(" "))
} else {
println("NO")
}
}
}
private class Tun(val u: Int, val v: Int, val w: Int)
private fun solveDungeon(n: Int, e: List<Tun>): IntArray? {
val a = IntArray(n)
for (t in e.sortedByDescending { it.w }) {
if (a[t.u] == 0) a[t.u] = t.w
if (a[t.v] == 0) a[t.v] = t.w
if (t.w != minOf(a[t.u], a[t.v])) return null
}
return a
}
Idea: BledDest, preparation: Neon
Tutorial
Tutorial is loading...
Solution (elizarov)
fun main() {
val (n, m, k) = readLine()!!.split(" ").map { it.toInt() }
val inf = Int.MAX_VALUE - 1
val s = IntArray(n) { inf }
s[k - 1] = 0
repeat(m) {
val (x, y) = readLine()!!.split(" ").map { it.toInt() - 1 }
val sx = s[x]
val sy = s[y]
s[x] = minOf(sx + 1, sy)
s[y] = minOf(sy + 1, sx)
}
println(s.joinToString(" ") { (if (it == inf) -1 else it).toString() })
}
1346F - Dune II: Battle For Arrakis
Idea: vovuh, preparation: vovuh
Tutorial
Tutorial is loading...
Solution (elizarov)
import kotlin.math.*
fun main() {
val (n, m, q) = readLine()!!.split(" ").map { it.toInt() }
val a = Array(n) { readLine()!!.split(" ").map { it.toInt() }.toIntArray() }
val rs = LongArray(n) { i -> (0 until m).map { j -> a[i][j].toLong() }.sum() }.toDistSum()
val cs = LongArray(m) { j -> (0 until n).map { i -> a[i][j].toLong() }.sum() }.toDistSum()
fun ans() = rs.min()!! + cs.min()!!
print(ans())
repeat(q) {
val (x1, y1, z) = readLine()!!.split(" ").map { it.toInt() }
val (x, y) = (x1 - 1) to (y1 - 1)
val d = (z - a[x][y]).toLong()
for (i in 0 until n) rs[i] += abs(x - i) * d
for (j in 0 until m) cs[j] += abs(y - j) * d
a[x][y] = z
print(" ${ans()}")
}
}
private fun LongArray.toDistSum(): LongArray {
val s = LongArray(size)
var su = 0L
var wsu = 0L
var sd = 0L
var wsd = 0L
for (i in 0 until size) {
sd += get(i)
wsd += (i + 1) * get(i)
}
for (i in 0 until size) {
wsd -= sd
sd -= get(i)
s[i] = wsu + wsd
su += get(i)
wsu += su
}
return s
}
Idea: adedalic, preparation: adedalic
Tutorial
Tutorial is loading...
Solution (elizarov)
fun main() {
val (k, n) = readLine()!!.split(" ").map { it.toInt() }
val p = readLine()!!.split(" ").map { it.toInt() }
val x = readLine()!!.split(" ").map { it.toInt() }
val c = solveCams(n, p, x)
if (c == null) {
println("NO")
} else {
println("YES")
println("$$${c.s1} $$${c.p1}")
println("$$${c.s2} $$${c.p2}")
}
}
private class Cams(val s1: Int, val p1: Int, val s2: Int, val p2: Int)
private tailrec fun gcd(x: Int, y: Int): Int = if (y == 0) x else gcd(y, x % y)
private fun solveCams(n: Int, p: List<Int>, x: List<Int>): Cams? {
fun place2(s1: Int, p1: Int): Cams? {
val f = BooleanArray(n) { j -> (x[j] - s1) % p1 == 0 }
val i = f.indexOf(false)
if (i < 0) return Cams(s1, p1, s1, p1)
val s2 = x[i]
var j = i + 1
while (j < n && f[j]) j++
if (j >= n) return Cams(s1, p1, s2, p[0])
var p2m = x[j] - s2
while (++j < n) {
if (!f[j]) p2m = gcd(p2m, x[j] - s2)
}
for (p2 in p) if (p2m % p2 == 0) {
return Cams(s1, p1, s2, p2)
}
return null
}
fun tryPlace2(s1: Int, p1m: Int): Cams? {
for (p1 in p) if (p1m % p1 == 0) {
place2(s1, p1)?.let { return it }
}
return null
}
if (n == 2) return Cams(x[0], p[0], x[1], p[0])
for (t1 in 1..2) {
tryPlace2(x[0], x[t1] - x[0])?.let { return it }
}
return tryPlace2(x[1], x[2] - x[1])
}
Tutorial
Tutorial is loading...
Solution (tourist)
import java.lang.AssertionError
private fun readLn() = readLine()!! // string line
private fun readInt() = readLn().toInt() // single int
private fun readLong() = readLn().toLong() // single long
private fun readDouble() = readLn().toDouble() // single double
private fun readStrings() = readLn().split(" ") // list of strings
private fun readInts() = readStrings().map { it.toInt() } // list of ints
private fun readLongs() = readStrings().map { it.toLong() } // list of longs
private fun readDoubles() = readStrings().map { it.toDouble() } // list of doubles
private fun myAssert(x: Boolean) {
if (!x) {
throw AssertionError()
}
}
fun main(args: Array<String>) {
var (tt, n) = readInts()
var lstart = IntArray(tt)
var rstart = IntArray(tt)
for (i in 0 until tt) {
var (x, y) = readInts()
lstart[i] = x
rstart[i] = y
}
var l = ArrayList<Int>()
var r = ArrayList<Int>()
for (i in 0 until n) {
var (x, y) = readInts()
l.add(x)
r.add(y)
}
var order = ArrayList<Int>()
for (i in 0 until n) {
order.add(i)
}
order.sortWith(compareBy({l[it] + r[it]}, {l[it]}))
val inf = 787788789
fun getDistance(L: Int, R: Int) : Int {
var low = 0
var high = n
while (low < high) {
var mid = (low + high) / 2
if (l[order[mid]] + r[order[mid]] < L + R ||
(l[order[mid]] + r[order[mid]] == L + R && l[order[mid]] < L)) {
low = mid + 1
} else {
high = mid
}
}
if (low < n && l[order[low]] + r[order[low]] == L + R) {
return l[order[low]] - L
}
return inf
}
var res = IntArray(tt) {-1}
for (qq in 0 until tt) {
var L = lstart[qq]
var R = rstart[qq]
var a = getDistance(L, R - 2) + 1
var b = getDistance(L, R)
var c = getDistance(L + 2, R) + 1
res[qq] = maxOf(minOf(a, b), minOf(b, c))
if (res[qq] >= inf) {
res[qq] = -1
}
}
println(res.joinToString(" "))
}
Idea: Neon and BledDest, preparation: Neon
Tutorial
Tutorial is loading...
Solution (Ne0n25)
import kotlin.math.abs
fun main() {
val INF = 1e9.toInt()
val INF64 = 1e18.toLong()
val LOG = 60
var (n, m, q, s) = readLine()!!.split(' ').map { it.toInt() }
s--
val a = readLine()!!.split(' ').map { it.toInt() }
val summask = LongArray(1 shl n) { 0 }
for (mask in 0 until (1 shl n)) {
for (i in 0 until n) {
if ((mask and (1 shl i)) > 0)
summask[mask] += a[i].toLong()
}
}
val d = Array(n) { IntArray(n) { INF } }
for (i in 0 until m) {
val (x, y) = readLine()!!.split(' ').map { it.toInt() }
d[x - 1][y - 1] = 1
}
val C = readLine()!!.split(' ').map { it.toLong() }
for (k in 0 until n) {
for (i in 0 until n) {
for (j in 0 until n)
d[i][j] = minOf(d[i][j], d[i][k] + d[k][j])
}
}
val dp = Array(n) { Array(n) { IntArray(1 shl n) { INF } } }
for (st in 0 until n) {
dp[st][st][1 shl st] = 0
for (mask in 0 until (1 shl n)) {
for (i in 0 until n) {
if ((mask and (1 shl i)) == 0)
continue
for (j in 0 until n) {
if ((mask and (1 shl j)) > 0)
continue
dp[st][j][mask or (1 shl j)] =
minOf(dp[st][j][mask or (1 shl j)], dp[st][i][mask] + d[i][j])
}
}
}
}
val bst = Array(n) { LongArray(n * n) { 0 } }
for (i in 0 until n) {
for (mask in 0 until (1 shl n)) {
if ((mask and (1 shl i)) > 0) {
for (j in 0 until n) {
if (dp[i][j][mask] != INF)
bst[i][dp[i][j][mask]] = maxOf(bst[i][dp[i][j][mask]], summask[mask])
}
}
}
}
val steps = Array(LOG) { Array(n) { LongArray(n) { INF64 } } }
for (i in 0 until n) {
for (j in 0 until n)
steps[0][i][j] = dp[i][j][(1 shl n) - 1].toLong()
}
for (t in 1 until LOG) {
for (i in 0 until n) {
for (j in 0 until n) {
for (k in 0 until n)
steps[t][i][j] = minOf(steps[t][i][j], steps[t - 1][i][k] + steps[t - 1][k][j])
}
}
}
for (qr in 0 until q) {
val sum = summask[(1 shl n) - 1]
val need = C[qr] / sum
var cur = LongArray(n) { INF64 }
cur[s] = 0
for (t in 0 until LOG - 1) {
if ((need and (1L shl t)) > 0) {
val ncur = LongArray(n) { INF64 }
for (i in 0 until n) {
for (j in 0 until n)
ncur[i] = minOf(ncur[i], steps[t][j][i] + cur[j])
}
cur = ncur
}
}
var ans = INF64
for(i in 0 until n) {
val lft = C[qr] % sum
for (j in 0 until n * n) {
if (bst[i][j] >= lft)
ans = minOf(ans, cur[i] + j);
}
}
println(ans)
}
}
As I don't know kotlin, can I solve these problems in other languages and submit?
Turns out that you can (in a sense)! Go to Gym → Create Mashup Contest and add the problems to a mashup contest; submissions would then be available in all the usual languages.
It's also a pretty handy tool for benchmarking solutions that are just over the time or memory limits.
Thank you for the problems! 2:30 seemed like a perfect duration for me.
My screencast
NICE TIME TO CHECK FOR MULTIPLE ACCOUNT , JUST MATCH WITH THE IP ADDRESS OF EACH DIFFERENT PROFILE SUBMISSION. :)
My (weird, and probably counterintuitive) solution to G: 81912387
Create a segment tree that supports the querying of two pieces of information: the GCD of all distances between all points on a range, and a single point on that range. Then try all possible periods for the first camera, assuming it starts at the time of the first point of interest. For each range in between the points covered by the first camera, query the range on the segment tree, GCD its total GCD value with a global GCD, and also GCD the global GCD with the distance between the returned point and any other previous point (It's probably provable that this is enough) If this overall GCD is a multiple of any valid period, then it'll work for the second camera.
Let $$$C = 10^6$$$ (really $$$\dfrac{10^6}{3}$$$ because a period of $$$1$$$ or $$$2$$$ is an automatic win), then because of the harmonic series, at most $$$O(C\log{C})$$$ queries are made, and each segment tree query is amortized $$$O(\log{C})$$$ because of how GCD works (this can also be optimized to $$$O(n\log{C})$$$ queries, but there's still $$$O(C\log{C})$$$ overhead).
Did anyone else solve it this way, or similar?
I had similar idea using the same "harmonic series" observation, but ran out of time while implementing it :(
For F, $$$\sum_{i=1}^{n}{|x - i| xs_i}$$$ for the fixed $$$x$$$ can be computed as sum of two parts:
Using two arrays of prefix sums for $$$xs_i$$$ and $$$i \cdot xs_i$$$ we can compute the given sum in $$$O(1)$$$ for the fixed $$$x$$$.
This approach doesn't improve the time complexity: we still need $$$O(n + m)$$$ to compute the answer for each query. But not we have two arrays $$$cost_{row}[i], i=1..n$$$ — cost of moving everything to row $$$i$$$, $$$cost_{col}[j], i=1..m$$$ — same for columns. The cost of moving everything to cell $$$i, j$$$ is just $$$cost_{row}[i] + cost_{col}[j]$$$ .
So we can just find minimum element in each array and don't worry about off-by-one bugs when computing the center of mass.
In problem D can I consider the minimum number of coins for node i among all the connected tunnels to i? Will this work?