can you explain your construction of graph?

can you use dijkstra with you graph or not?

You have 2e5 queries so in total it will be TLE

Same, it is very unintuitive for me how you can just add the cumsums; This implementation makes a lot more sense to me: 276838911

It is actually causing Overflow, check your output. You can see negative value. When we add positive numbers, we can never get negative values, unless you got memory overflow.

You can actually find the failing test yourself.

Checker's output says "wrong answer 248th numbers differ — expected: '3', found: '-1'". That means you only need to add something like "if (test_id == 248) then print(all input)" to your code (and don't print anything else so that the output is not too large). The verdict will still be WA but at least you'll get to see the problematic test.

youre using maps and sets a bit too much probably

change auto st to auto& st

I said the same in original Contest post. and guess what, heavily downvoted. I would say it again. E was a nice problem.

ik this is off topic but wow dude how did you go from grey to purple in less than a year? as someone who's given about 5 contests it looks lowkey impossible for someone like me

i dont get this part aswell if u understand it please explain it below here

A rigorous proof would be something like that:

Consider the prefix sums of an array, and denote $$$s$$$ as the sum of all elements in it. An array of positive integers is palindromic if and only if its prefix sums are "symmetric" with $$$\frac{s}{2}$$$ as the center (i.e. if an integer $$$\frac{s}{2} + x$$$ exists in the array of prefix sums, then the integer $$$\frac{s}{2} - x$$$ should also exist, and vice versa). If there is a pair $$$(\frac{s}{2}-x, \frac{s}{2}+x)$$$ such that only one of these elements exists in prefix sums, this pair violates the condition, and we need to "fix" every such pair.

Now consider what our actions do to the array of prefix sums. When we merge two adjacent elements, we delete a prefix sum. When we split an element, we add a new prefix sum between the existing two. Every such action can "fix" one of the violating pairs $$$(\frac{s}{2}-x, \frac{s}{2}+x)$$$: merging two elements deletes one element from a pair, and splitting an element adds an element into the pair. So, if we have a pair that violates the condition, it doesn't matter whether we fix it by split operation or merge operation — we will still spend one operation to fix this pair.

I think a rigorous proof might also go like this:

Given the array $$$b[1\cdots n]$$$ after doing the minimum number of operations to make it a palindrome.
While possible, pick any element $$$b_i$$$ that was obtained by a split operation, and do the following:

$$$ \textbf{Case 1:} \text{ if } i \gt \left\lceil \frac{n}{2} \right\rceil \text{or } i \lt \left\lfloor \frac{n}{2} \right\rfloor \text{, undo the split operation in any possible direction, and fuse } b_{n - i + 1}$$$
$$$\text{in the opposite direction that } b_i \text{ got unsplit towards.This increases the number of operations by at most 0.} $$$

$$$ \textbf{Case 2:} \text{ if } i = \left\lceil \frac{n}{2} \right\rceil \text{or } i = \left\lfloor \frac{n}{2} \right\rfloor \text{, do the same as case 1 but if the direction of unsplit of } b_i \text{ is towards } b_{n - i + 1}$$$
$$$\text{don't do anything after the unsplitting step. This also increases the number of operations by at most 0.} $$$

$$$ \textbf{Case 3:} \text{ if } i = \frac{n}{2} \text{, unsplit } b_i \text{ and fuse the result in the opposite direction.} $$$

Note: when you fuse two elements $$$b_i$$$ and $$$b_j$$$, the state of the resulting element is the union of the split directions of $$$b_i$$$
minus the direction $$$b_i \rightarrow b_j$$$ and the split directions of $$$b_j$$$ minus the direction $$$b_j \rightarrow b_i$$$.

This process has to end because in each iteration you decrease the number of split elements by at least 1.

A similar argument can be constructed to convert all fuse operations to split operations.

Ok I see, issue was with 1., deep copying of vector. 2. Solves it. So dumb, it was going to be the first time I solved a D in div 2!!

1.vector<int> nodes = colorToNodes[all_colors[j]];

2. vector<int>& nodes = colorToNodes[all_colors[j]];

probably yeah

Yes. If you're checking every possible index, then time complexity will be approximately O(N*Q) because in the worst case, let's say, you will be getting the same x and y each query, and every other string will be suitable. Then, for each query you will be checking N-2 elements. Rounding up, it is N*Q

To be honest, I was also confused by this problem. I tried to solve it by math first, but decided to just write brute force.

In this line

set<int> temp=m[s];

you're copying a whole set which maximum size can be $$$2 \cdot 10^5$$$. Potentially this copy can be done for each query (again $$$2 \cdot 10^5$$$) and moreover a function solve() is called 8 times for every query.

If you really need this temporary variable, you can use a const reference:

const set<int>& temp=m[s];

I was thinking of it like that. If you are in a state with $$$c \gt 0$$$, you are always placing the next (the $$$i$$$-th) digit into an even block. And you always add $$$c$$$ to the answer with that. You can opt to go to $$$\mathit{dp}[i + 1][0]$$$, telling the $$$(i + 1)$$$-st digit to be in an odd block. With that, you'll know that digit when you are in that state.

Honestly, only your effort deserves accepted.

You can see the difference yourself using built-in "Compare" tool

In your code inside accumulate function you are declaring 0 as L i.e Long int but for large values you must declare it as 0LL i.e Long Long, rest everything is correct.

Link for corrected code: Solution

If S is not specifically determined to be odd, then S/2 will automatically be rounded down, which may cause some problems.

Use V<int> &ds = mp[temp[i]] instead of V<int> ds = mp[temp[i]] at Line 98 to avoid copy.

In Java 13 and earlier versions, Arrays.sort for primitive types doesn't guarantee $$$O(n\log n)$$$. You can refer to this and this.

It will TLE. There is no cutting corner around Floyd-Warshall that would help you, the algorithm is doing its best (sort of, this is excluding any research paper improving it to an extreme, but as far as I understand, this cannot have a better complexity than quadratic).

D is more of an exercise to practice implicit graph. That is, you know what you are solving is a graph, but it has special attributes that you should take advantages of instead of blindly jumping into a regular graph algorithm just because you deduce "shortest path" from the problem statements.

Avoid using custom comparator function, instead using inbuilt greater () function to sort the array in descending order, as:

The use of a custom comparator function introduces additional overhead due to function calls, which becomes significant when sorting large arrays. On the other hand, greater() is a highly optimized standard library component that avoids this overhead, leading to better performance and preventing TLE (Time Limit Exceeded) in competitive programming or performance-critical applications.

In most cases, prefer using standard library comparators like greater() for better performance unless you need custom behavior that can’t be achieved otherwise.

link for corrected solution: https://codeforces.me/contest/2004/submission/277758988