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