## 2A. Goals of Victory

Author: nandonathaniel

Developer: nandonathaniel

**Tutorial**

## 2B/1A. Helmets in Night Light

Author: ArvinCiu

Developer: gansixeneh

**Tutorial**

## 2C. Joyboard

Author: Pyqe

Developer: gansixeneh

**Tutorial**

## 2D/1B. Effects of Anti Pimples

**Tutorial**

## 2E/1C. Autosynthesis

**Tutorial**

## 2F/1D. Lexichromatography

**Tutorial**

## 2G/1E. Ball-Stackable

**Tutorial**

## 1F. Indefinite Clownfish

**Tutorial**

## 1G. Clubstep

**Tutorial**

[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.

Whoops, sorry about that! It's fixed now

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 case it gives any clue..

I had checked for this particular test-case, execution doesn't get to 3rd case.. gets to first & second

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.

I have the same issue as yours and I am also confused. Why would this change the answer? Does the order in which the vertices are pushed change the answer? I thought we were doing a BFS except that we stop when we encounter a cycle.

Actually, I now do understand why my solution didn't work. Try this test case:

A possible solution is

The problems with pushing the vertex into the queue only if it's indegree is 0 is that some of the vertices in the cycles have to be assigned "black" before we iterate through the cycles.

It's not really necessary to handle it like that. But I chose to do it like that in order to easily handle the case where the colours in the cycle is forced (it happens when at least one child of a vertex in the cycle is white).

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.

In first question sum must be negative of n-1 other teams score not same

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 .`

first we will sort the given array(but keeping track of the indices, so use pair<int,int> or something to store the input).

From biggest to smallest: I hope you understood the group 1 and group 2 idea. We are going from bigger values in the sorted array to smaller ones because we want to incrementally build group 1 (actually we need just the count of group 1, i.e. c).

For each element we iterate, lets say curr1 (curr1.first -> value and curr1.second -> index), we are going to mark each element of group1 which are the divisor of my curr.second, which will represent the indices, if chosen in next iteration of curr2 element, will yield the value from group 1 (i.e. curr1->value), which we want to avoid for curr2. I hope it makes sense.

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.

Should be

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

That's right! It was a mistake. It should be fixed now

Is Problem G a Geometry Dash reference? Lol.

Yes, it is! Glad you noticed :D

Yeah, I actually came up with the idea of that problem when playing an insane demon level in the game lol

You guys should make more problems like this lol, would be interesting to see

UPD: Never mind

Can anyone help me to understand effects of Anti Pimples problem. I am not able to get the logic behind the tutorial.

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

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

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

This takes $$$O(n/i)$$$, so $$$O(n\log n)$$$ in total

Oh, you're right, thank you!

So there's no need for dp, and the solution is even simpler and more efficient.

i came up with this solution too, tbh i find this much more intuitive/simpler than the solution in the editorial

Bro u made it more difficult:P

Why is this wrong for B? I spent 15mins writing it then another 1hr debugging it :skull:

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...

Can anyone help me with this code of problem D . Ive been trying this problem since tommorow and i dont know why this code doesnt works; 228466533

Can anyone tell the flaw in the logic for the problem 2e/1c. First we pool that values in array for which freq is more than one , then we can see that the index corresponding to that value should be circled . Then for the remaining array values apart from ones which will be circled and other which has freq more than one we can make an undirected graph with index --> array value . This graph should be bipartite and if not the ans is -1 , else we can alternate between the nodes to circle them.

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

blackelement.", should it be "For each white element, there cannot be any white element with a value equal to the index of thatwhiteelement."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?