[Reposting] for anyone interested in video editorials for A, B, C and D: https://youtu.be/3gP74cSjhwg?si=bl1lMboWq4O2dPgg

A small correction for A: it has to be the negative of the sum of the present teams, not just the sum.

Good Editorial!

In div1-D, did anyone try directly calculating unequal part ?

It should be for these 3 cases: inequality at odd occurrence of value, at even occurrence, and inequality due to insufficient length

My submission I've added comments.. Answer differs by one, struggling to find the reason. Would highly appreciate if anyone can help

In problem 2E, is it neccessary to push the parent vertex immediately if the current vertex is white? If it is, can anyone explain it for me? I've tried to push the vertex only when it's indegree is 0 and get WA on test 4.

How to solve problem 2E/1C with 2-sat?I tried a lot of times but still wa on 4. And how to solve it with flow?

For problem A it should be negative of the sum.

For calculating the equal ways in 1D, if some $$$a_i$$$ occur odd times, impossible to equal, else we can think for each value x, $$$a_{i_1}=a_{i_2}=\dots=a_{i_{2k}}=x$$$, x have k segments $$$[a_{i_1},a_{i_2}]$$$, $$$[a_{i_3},a_{i_4}]$$$,$$$\dots $$$. For all segements, if one contains another, impossible to equal, if two segments for value x and y intersect, their order will be the same. Only need to use some easy data structure to search the segments.

Can Anyone share some problems similar to 2-D.

Can Someone Explain this part in more detail~ In order to calculate g(w) for all desired values of w , we need to iterate the elements of a from the biggest value to the smallest value. Each element we iterate, we iterate every index that is a factor of the index of the current element and mark those indices as group 1 while we keep track of the value of c .

Very good problems!

I really enjoyed the problems ! They felt beautiful and creative. Congrats to the authors !

I think there is a typo in 1877B — Helmets in Night Light tutorial.

residents with the smallest values of ai first. Using the fact that ai ≥ 1, we can deduce that we will always have a resident with an available share.

Should be

residents with the smallest values of bi first. Using the fact that ai ≥ 1, we can deduce that we will always have a resident with an available share.

Values of b represent the cost, and since all ai >= 1 we can always have that cheap person to tell atleast 1 other person.

Is Problem G a Geometry Dash reference? Lol.

UPD: Never mind

Alternative solution for div2-D:

For each element $$$a_i$$$, define the value $$$m_i$$$ — maximum in $$$a$$$ over all indices which are multiples of $$$i$$$.

Consider that some elements are colored black. If we suppose that the answer for such coloring is $$$m_i$$$, then the answer does not change while coloring black other indices $$$j$$$ such that $$$m_j \leq m_i$$$, so the answer to the problem is $$$\sum\limits_{i = 1}^n 2^{i-1} \cdot m_i$$$ over a sorted array $$$m$$$.

To calculate $$$m_i$$$, let's use the idea of sqrt decomposition:

1. If $$$i > \sqrt{n}$$$, then we can go over all multiples $$$i, 2i, ..., \lfloor\frac{n}{i}\rfloor i$$$ and find $$$m_i$$$ in $$$O(\sqrt{n})$$$.
2. If $$$i \leq \sqrt{n}$$$, then let's use dynamic programming. Define $$$dp_{i,j}$$$ as the maximum value over indices $$$i, i + j, i + 2j, ...$$$. To calculate this, the transition between states is quite simple: $$$dp_{i,j} = max(a_i, dp_{i + j,j})$$$. After that, the desired value for $$$m_i$$$ will be stored in $$$dp_{i,i}$$$. Since we only need $$$j \leq \sqrt{n}$$$ to calculate the answer, all the values can be obtained in $$$O(n\sqrt{n})$$$.

Therefore, the total complexity is $$$O(n\sqrt{n})$$$.

I have an alternative solution for G that runs in $$$O((n+q)(\log{n} + \log{\max{x}}))$$$.

Same as editorial, to answer a query $$$(l,r,x)$$$, we take $$$x$$$ and run through gates $$$r$$$ to $$$l$$$ sequentially, where gate $$$i$$$ is the function $$$f(x)=\min{(a_i,\lfloor \frac{x+a_i}{2} \rfloor)}$$$. We can retrieve the answer after computing the sum of results after running each gate.

Suppose all queries have $$$r=n$$$. Then we can get some solution sketch like this: gradually increment $$$x'$$$ from $$$0$$$ to $$$10^9$$$, while maintaining $$$ans_i$$$ for $$$1 \le i \le n$$$, where $$$ans_i$$$ is the result of $$$x'$$$ after running through gates $$$n$$$ to $$$i$$$. Then, to answer a query $$$(l,r,x)$$$, we just pick the moment we have $$$x'=x$$$, and we take the sum of $$$ans_i$$$ for $$$l \le i \le n$$$.

To maintain $$$ans_i$$$, we can store a set of active gates, which are gates $$$i$$$ that have $$$a_i \le ans_{i+1}$$$. Once a gate is activated, it will never be deactivated. Obviously, if gate $$$i$$$ is not active, then $$$ans_i = ans_{i+1}$$$. So by knowing positions active gates, we can divide the $$$ans$$$ array into continuous blocks of equal value. Now, when we increase $$$x$$$ by $$$1$$$, we update the $$$ans$$$ array in a similar fashion as how we would do $$$+1$$$ on a big integer represented in binary. This takes $$$O(1)$$$ amortized. We then check, for each changed value of $$$ans_i$$$, whether it would activate some gates. This can be detected by RMQ, and we can have a $$$O(\max{x}+n\log{n})$$$ idea.

To improve, we can compute the next value of $$$x'$$$ which either activates a gate or we need to answer a query of that value, instead of increasing $$$x'$$$ one by one. This improves the time complexity to $$$O((n+q)(\log{n} + \log{\max{x}}))$$$.

Finally, let's think of how to also handle queries with arbitrary $$$r$$$. Let's say we have a query $$$(l,r,x)$$$, If at any moment we manage to have $$$ans_{r+1}=x$$$, then we are very happy as we can get what we want by just computing sum of $$$ans_i$$$ for $$$l \le i \le r$$$. So we can just modify the previous solution to detect the next important $$$x$$$ that either activates a gate, or hits some $$$ans_{r+1}=x$$$.

But there might be some ugly situation where we have cooked $$$x'$$$ up to $$$10^9$$$, but $$$ans_{r+1}<x$$$ still holds. Now, the funny trick is that we realise at this moment, all queries with $$$r=n$$$ are already answered, and gate $$$n$$$ is already activated. So, we can simply pretend gate $$$n$$$ never exist, and repeat our process with the new $$$x'$$$ to be $$$ans_n$$$. By the time we removed all the gates, we would have already found out the answer for all queries.

The data structure details are not too ugly, but it took me a long time to implement...

In 2E/1C, "For each white element, there cannot be any white element with a value equal to the index of that black element.", should it be "For each white element, there cannot be any white element with a value equal to the index of that white element."

Could anyone please tell me the logical difference between these codes: 237306441 and 237304555? Both codes have the same logic.

can someone explain why I am getting TLE on this submission_A?