Meta Hacker Cup Round 2 Editorial

Can anyone explain how to handle the equal weights in problem C, the Balance Scale? I couldn't grasp the editorial clearly. Thanks in advance.

More people than I expected apparently disliked A1/A2. If you're one of them, what didn't you like about it?

Problems were actually quite balanced.

Great work to the team :)

Editorial of B sais, that it's too long to solve it as general "find K longest paths in DAG" problem, but it isn't. We can construct a graph with N vertices and 2N edges, not N^2 edges. We don't need to add an edge to all possible buyers. Only to the smallest cost. But to compensate for it, we need to add an additional edge "resell immediately to next cost buyer".

private fun solve(debug: Boolean) {
    val (n, k) = readInts()
    val data = List(n) { readInts() }
    val clients = data.flatMapIndexed { index, it ->
        listOf(
            Client(index, it[0], it[2], 1),
            Client(index, it[1], it[3], 0)
        )
    }.sortedWith(compareBy(
        { it.day },
        { -it.cost },
        { it.isBuy },
        { it.id }
    ))

    data class Edge(val cost:Long, val to:Int)

    val next = Array(2) { arrayOfNulls<Edge>(n) }
    var prevBuy : Client? = null
    for (client in clients) {
        if (prevBuy != null && prevBuy.day == client.day) {
            next[client.isBuy][client.id] = Edge((prevBuy.cost - client.cost).toLong(), prevBuy.id)
        }
        if (client.isBuy == 1) {
            prevBuy = client
        }
    }

    require(next[0].filterNotNull().all { it.cost > 0 })


    val order = (0 until n).sortedWith(compareBy(
        { data[it][0] },
        { data[it][2] },
        { -it }
    )).reversed().toIntArray()


    val best = LongArray(n) { -1 }

    val fin = PriorityQueue(compareByDescending<Long> { it })
    val path = PriorityQueue(compareByDescending(Pair<Long,Int>::first))
    fin.add(-1)
    path.add(-1L to -1)

    for (i in order) {
        best[i] = 0
        for (e in 0..1) {
            next[e][i]?.let {
                require(best[it.to] != -1L) { "$$$i $$${it}"}
                best[i] = maxOf(best[i], best[it.to] + it.cost)
            }
        }
    }
    for (i in 0 until n) {
        next[0][i]?.let {
            path.add(it.cost + best[it.to] to it.to)
        }
    }

    var ans = 0L
    var prev = Long.MAX_VALUE
    var done = 0
    val res = mutableListOf<Long>()
    while (done < k) {
        val topF = fin.peek()!!
        val topP = path.peek()!!
        if (topF < 0 && topP.first < 0) break
        require(topP.first <= prev)
        require(topF <= prev)
        if (topF > topP.first) {
            prev = topF
            done += 1
            ans = (ans + topF) % MOD
            res.add(topF)
            fin.poll()
        } else {
            path.poll()
            var s = topP.second
            var add = topP.first - best[s]
            while (true) {
                val n1 = next[0][s]
                val n2 = next[1][s]
                fin.add(add)
                if (n1 == null || n2 == null) {
                    val nxt = n1 ?: n2 ?: break
                    require(best[s] == best[nxt.to] + nxt.cost)
                    add += nxt.cost
                    s = nxt.to
                    continue
                }
                if (best[s] == best[n1.to] + n1.cost) {
                    path.add(add + n2.cost + best[n2.to] to n2.to)
                    add += n1.cost
                    s = n1.to
                } else {
                    require(best[s] == best[n2.to] + n2.cost)
                    path.add(add + n1.cost + best[n1.to] to n1.to)
                    add += n2.cost
                    s = n2.to
                }
            }
            require(add == topP.first)
        }
    }
    println(ans)
}

Code is kinda messy and definitely not easier than the intended solution.

Also, the editorial of D2 seems to solve the subtask of type "find the smallest index $$$i$$$ in a nondecreasing Fenwick tree so that the $$$i$$$-th prefix sum is at least $$$x$$$" in $$$O(\log^2{n})$$$, while it is possible to do so in $$$O(\log{n})$$$, restoring the answer bit by bit

For A2 I used the classic 1e9 + 7 as big prime for hashing and got FST for 1 test case...

saddest person on earth right now

any good cf blogs to understand stuff going with problem A2.?

Immediately after reading A, I thought about Manacher's algorithm. Can we modify Manacher's algorithm to fit this problem?

EDIT: Thanks for clarifying. This is clearly about hashing then :3

How do we claim our t-shirt, and when will it be shipped out?

I really enjoyed the round tho I can only solve A1.Learnt a lot of new stuffs. Thank you for such a great round

Btw B can be solved in $$$O((N + K) \log N)$$$. You can find the potential with DP on DAG, and use Eppstein's K-th shortest path algorithm. (I got systest fail because of my lack of braveness to #define int long long.)

I like problem A2, D1, D2. Overall contest taught me a lot.

I did exactly the intended solution for A1, and it took 6.30 minutes to run on my computer.

Got an approach to Problem C that seems simpler than the editorial:

We model the process as arrangements of length $$$k+1$$$ of the cookies in which the first object is the one placed on the left pan and the cookies thereafter it are in the order in which they are taken and compared with the current cookie on the weighing balance.

The total number of arrangements is $$$sum\choose k+1$$$($$$k+1$$$)! where $$$sum$$$ is the total number of cookies. If there is any cookie in this arrangement that has a weight strictly greater than $$$w_1$$$, then a cookie of batch $$$1$$$ can never be the final remaining cookie. So the favorable arrangements have all cookies having weights atmost $$$w_1$$$.

Now declare two variables $$$small$$$ and $$$equal$$$ where $$$small$$$ is the number of cookies having a weight less than $$$w_1$$$ and $$$equal$$$ is the number of cookies having weight $$$w_1$$$ and not from batch $$$1$$$. Also we precompute the factorials and inverse factorials upto $$$MAX=9*10^6$$$ in $$$O(MAX)$$$ time.

Now any favorable arrangement can be divided into 3 cases: -

1: It contains exactly one cookie of weight $$$w_1$$$.

The cookie of weight $$$w_1$$$ must be from batch $$$1$$$.Hence number of such outcomes is $$$c_1\times$$$$$$small\choose k$$$$$$\times$$$($$$k+1$$$)! which can be calculated in $$$O(1)$$$ time

-

2: It contains more than one cookie of weight $$$= w_1$$$ with the first two cookies of this type in the arrangement satisfying the condition that exactly one of them is from batch $$$1$$$ and the other isn't.

Why such a weird case? Well because in this case lies the key argument that helps us in solving this problem...

Let $$$C_1$$$ and $$$C_2$$$ be those two cookies mentioned above in that order. Now consider another arrangement $$$A'$$$ of the $$$k+1$$$ cookies in this arrangement $$$A$$$ in which only the positions of $$$C_1$$$ and $$$C_2$$$ swapped. Then the claim is that $$$A'$$$ is unfavorable.

To prove it, suppose $$$C_1$$$ was the cookie from batch $$$1$$$. So it must have been on the right pan before comparing it with $$$C_2$$$ as if it was on the left pan then it must have been thrown away by bringing in $$$C_2$$$ which would then be on the right pan implying that in the end $$$C_2$$$ would remain. But this is a contradiction as $$$C_2$$$ is not from batch $$$1$$$. So in the arrangement $$$A'$$$, $$$C_2$$$ must have been in the right pan before comparing it with $$$C_1$$$. Since it is in the right pan, $$$C_1$$$ would have been thrown and for all other cookies after $$$C_2$$$ in $$$A'$$$, $$$C_2$$$ would still remain. Hence $$$A'$$$ is unfavorable.

Now suppose $$$C_1$$$ was not from batch $$$1$$$. So it must have been on the left pan before comparing it with $$$C_2$$$ as if it was on the right pan then it would have remained till end which is not possible. So in the arrangement $$$A'$$$, $$$C_2$$$ must have been on the left pan before comparing it with $$$C_1$$$ after which $$$C_1$$$ would be on the right pan and hence it would be the one left in the end making $$$A'$$$ unfavorable.

Thus if total arrangements satisfying 2 is $$$x$$$ then exactly $$$\frac{x}{2}$$$ of them are favorable!.

In order to compute $$$x$$$ we iterate over positions of $$$C_2$$$. If it is in the $$$j$$$th position then there are ($$$j-1$$$) choices for placing $$$C_1$$$. Also by the definition of $$$C_1$$$ and $$$C_2$$$ all cookies before $$$j$$$th position except $$$C_1$$$ have smaller weight than $$$w_1$$$ while the cookies after $$$C_2$$$ can have weight which is not greater than $$$w_1$$$. So the total ways are $$$(2\times c_1\times equal\times (j-1)\times$$$$$$small\choose j-2$$$$$$\times(j-2)!\times$$$$$$small-(j-2)+(equal-1)+(c_1-1)\choose k+1-j$$$$$$\times (k+1-j)!)$$$. Summing over these for all $$$2\leq j\leq k+1$$$ would give the value of $$$x$$$ above, whose half is what we want. These computations require $$$O(k)$$$ time.

-

3: It contains more than one cookie of weight $$$= w_1$$$ with the first two cookies of this type in the arrangement satisfying the condition that both of them are from batch $$$1$$$.

Let $$$C_1$$$ and $$$C_2$$$ be those two cookies mentioned above in that order. If $$$C_1$$$ was on the left pan before comparison with $$$C_2$$$ then $$$C_2$$$ would be on the right pan after comparison and hence it would be the remaining cookie in the end. If $$$C_1$$$ was on the right pan then it itself would remain in the end. In either case a cookie from batch $$$1$$$ is remaining in the end.

So the number of arrangements satisfying 3 would be obtained by again iterating over the position of $$$C_2$$$, i.e it is the summation of ($$$c_1\times (c_1-1)\times (j-1)\times$$$$$$small\choose j-2$$$$$$\times (j-2)!\times$$$$$$small-(j-2)+equal+(c_1-2)\choose k+1-j$$$$$$\times (k+1-j)!$$$) for $$$2\leq j\leq k+1$$$. These computations again require $$$O(k)$$$ time.

So summing up the favorable outcomes for all $$$3$$$ cases and dividing it by the total arrangements would give us the desired probability.

The complexity of this algorithm is $$$O$$$(max($$$MAX$$$,summation of $$$k$$$ over all testcases)) $$$\blacksquare$$$