Problem — 1919D. My solution runs in 93 ms, and I don't understand why.

Here is what I came up with: let's try to find the split boundary for the root between the subtree of the $$$0$$$-weight edge and the $$$1$$$-weight edge. We can notice that if the $$$0$$$-edge goes left, the boundary is max(pos(0), pos(second_to_last_1)), because there is exactly $$$1$$$ one in the right subtree. And if the $$$0$$$-edge goes right, the boundary is min(pos(0), pos(second_1)).

The only problem is that we can't exactly determine which way the $$$0$$$-edge goes, so we will try both options. Obviously, this just turns into a recursion (I should add that we search for the boundaries in O(log n)).

What bothers me is that it seems there could be a lot of branching in the recursion, resulting in an exponential or quadratic time complexity. And I can't figure out: are the test cases just weak, or is there some smart observation here to prove that it runs fast?

388357320

Can someone prove why this works fast, or find a countertest?

As -is-this-fft- pointed out, the overall usefulness of blogs has been declining. Finding high-quality educational posts is almost impossible now unless you accidentally stumble upon them in a random comment.

I believe the best solution is to create a single, universal blog to serve as a community hub for the best educational materials.

However, it would probably be much better if a higher-rated user created this hub instead of me (rating bias definitely exists here). Would any high-rated user be willing to step up and start this thread (and farm contribution)?

In the meantime, I will get things started by sharing a few interesting blogs in the comments below(btw, you can too)

So, I came up with this problem:

You are given an array $$$a$$$ of length $$$N$$$. Additionally, you are given a set of $$$q$$$ operations, where each operation is defined by a pair $$$(s, p)$$$. You may perform any number of operations from this set in any order.

When you apply an operation $$$(s, p)$$$ to the current state of the array $$$a$$$, the following process occurs:

1. You accumulate the sum of elements at indices $$$s, s+p, s+2p, \dots, s+kp$$$, where $$$s+kp$$$ is the largest valid index such that $$$s+kp \le |a|$$$.
2. All elements at the visited indices are removed from the array.
3. The remaining elements are re-indexed consecutively, preserving their original relative order.

Your goal is to perform a sequence of operations such that the total accumulated sum of all chosen elements does not exceed $$$maxW$$$, and this sum is as large as possible

Right now, there is no better solution than exponential, but I'm wondering is there some polynomial solution?

Can anyone make an extension that will hide blogs from grey(and maybe green) users, pls

So, I was sleeping and this problem just came to me in a dream:

Given an array a and an array b, we need to split a into contiguous subsegments and for each subsegment assign 1/0 — whether we reverse it or not. The question: can we determine if it's possible to obtain b from a?

So far I only know how to solve it in O(n²), but there's clearly a better way, help pls

So the question of life the universe and everything: merch or CF rating?

more precisely, CF round or a local tournament with merch?