Задача — 1919D. Мое решение работает за 93 мс, и я не понимаю почему.

Что я придумал: попытаемся найти для корня границу разделения между поддеревом ребра веса $$$0$$$ и веса $$$1$$$. Можно заметить, что если $$$0$$$-ребро ведет влево, то граница — это max(pos(0), pos(предпоследней_1)), потому что в правом поддереве ровно $$$1$$$ единица. А если $$$0$$$-ребро ведет вправо, то граница — это min(pos(0), pos(второй_1)).

Проблема лишь в том, что мы не можем точно определить, куда именно ведет $$$0$$$-ребро, так что будем пробовать оба варианта. Понятно, что это просто рекурсия (надо добавить, что границы за O(logn) ищем).

Меня смущает то, что, кажется, ветвлений у рекурсии может быть много и получится экспонента или квадрат. И я не могу понять: это тест-кейсы плохие, или тут можно заметить что-то умное и доказать, что работает за быстро.

388357320

Может кто-то доказать, почему это работает быстро, или найти контртест?

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)

Это правда, что эту задачу нельзя решить быстрее O(N^2)? Задача

Она тогда по ассимптотике явно не проходит, а на ВСОШ(хоть и муниципе) такого быть не должно вроде.

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?

I frequently see advice along the lines of, "Solve 1000 problems and you'll reach rating X." While this might work for some, I believe it's actively harmful to many others. It sets a false expectation. People think, "Once I hit that magical 1000th problem, I'll finally reach my target rating." But when that milestone passes and nothing happens — or worse, their rating actually drops after the next round — it becomes incredibly demotivating to keep practicing.

A prime example of this is Rabari_9999. He has solved over 1000 problems, including 400+ problems rated 200 points above his current rating, yet his rating hasn't increased. He reached out to me, and according to him, he spends over an hour trying to solve problems independently. He is doing exactly what the CP community recommends.

What I'm trying to say is: there is no magic formula. There is no upper bound on the number of problems you need to solve to reach a specific rating (and no lower bound, either).

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

What do you think about USACO contests?

I'm wondering whether I should prefer them over virtual contests from CF

AFTER MONTHS OF PAIN WITHOUT RATING PREDICTIONS, I CAN FINALLY LIVE WITH A BIT LESS PAIN

Like, I’ve never seen a blog/comment from >=blue guy exposing another bunch of cheaters

Значит я спал себе спокойно и вдруг эта задача мне приснилась:

Дан массив a и массив b, надо разбить a на подотрезки и для каждого подотрезка поставить 1/0 — разворачиваем мы его или нет. Вопрос: надо определить можем ли мы из a получить b?

Я пока умею решать только за O(n^2), но явно же можно лучше, помогите плиз

Добавьте тег для задач "НЕ КОНСТРУКТИВ" пжпжпж

P.S. Хотя, ладно, пользы маловаты от него будет, учитывая, что последнее время его практически нигде не применить

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

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