That's sad! Don't Sleep ;)

23 minutes to the contest.. Time to wake up bro

Good morning!

Wholesome-forces

which can be a good thing for many (and a very bad thing for some)

vovuh, Neon and pikmike are participating officially in the contest this edu is based on.

Where do you live and what time will be in your country at the contest?

do you have classes on sundays?

Once the 2-hour problem solving round is over, participants have the option, to see the solutions submitted by other participants and try to generate possible inputs, upon which these solutions might end up giving incorrect outputs. This is what hacking means. All of this has to be done in a 12-hour hacking phase just after the contest. Once this 12-hour phase is over, solutions are re-judged based on all the hacks generated. Hope this helps!

Same here in Korea.
it's 18:05 (UTC+9)

For Japanese too. :) (start at 18:05)
Recently many contests were held at 23:35(UTC+9), in which is difficult for me to participate.

He has actually been conducting the last 79 edus.

please graphforces

C and D without educational worth.

C is just "try it, should work...somehow", D is kind of edgecase hunting.

all problems have equal weightage in educational round!

Counting Reverse pairs (Inversions)

Transform the string to an array of integers. Now traverse from left to right. When you meet one, you should delete some thing larger than 1 in the right. When you meet something that is not one, you just delete it.

111011 -> [3, 1, 2]

delete -> minus 1

remove prefix -> delete first number

Then try best to maximize the operation

two pointer concept.

Maintain an array of lengths of consecutive elements. If the first prefix length is greater than 1 (>1), then we can remove that prefix and increase the number of operations. Now if the prefix length is equal to 1 (==1), then search for the first length in the array that is greater than 1 and reduce it. If such length is not found, remove the last length from the array (maintain 2 pointers one left and one right and reduce the right pointer).

Example :- 1 5 10111

After 1st operation -> 011

After 2nd operation -> 1

Thus 3 operations are required.

A counter example as to why we should reduce from the first large prefix instead of the largest one is here

Have an vector of stack of size 26 where u push each character to respective bucket initially. Now we know that the first character has to reach the end. But the important thing to notice is that only the last occurence of the first character is required to reach end to save operations, that is why we maintain a stack to get last occurence.

Now if we know that the last occurence of ith character is at position j, we also need to know how many of the characters from j to n-1 have already been push to right and for that we use segment Tree/BIT.

So at each postion ans += n — 1 — (no. of char in [j,n-1] already pushed) — lastest position of that char

Heres my Submission

Ah, damn it... This is where most of us went wrong. Most of us did indeed solve a different version of this problem correctly.

wait, I missed that too... :(

precompute an array of sizes of chunks of 0s and 1s for [0, 0, 0, 1, 1, 0, 1, 0, 1, 1] -> [3, 2, 1, 1, 1, 2] now in each step first chunk would be removed anyway but we need to remove 1 other element before that, choose the chunk either after it or itself that has size > 1, if theres no such chunk remove the last element

Since we never delete a chunk of size 1 from middle, it is ensured that two chunks are never merged. Hence we will always get the optimal answer.

Exactly...Here is my approach.....

If prefix has more than 2 same characters then 1 operation consists of removing the first character and then the remaining prefix...this way we delete the minimum we can after every operation. Also if s[i]!=s[i+1] then we jump to s[i+2] after deleting si and s(i+1). This can be proved to be true by some casework...but I dont know why this greedy approach is failing.

1 7 0100010

You can try this case, my solution was giving wrong answer on this case. May be you might get your mistake. The correct answer is 4.

I figure what's wrong when my first submission

I maintain two index, the head and the index of number bigger than 1.

It's important to notice that the second index must >= the first index.

If you use O(n^2), you will surely get TLE. I also copied code from GFG though and get TLE on test cae 41 :P https://www.geeksforgeeks.org/minimum-number-of-adjacent-swaps-to-convert-a-string-into-its-given-anagram/

Getting TLE on test case 41 while simultaneoulsy on call with GF with she breaking up wid ya at the same exact moment or vice versa whatever minimizes your mood. My guess is you probably got lucky with both events not happening at the same time....If even luck did not favor you on that...then oh boy.... that oughta hurt (In Matthew Mccounaughey's voice)...good luck xD.

I think if n=1 then your a[n-2] will become a[-1]. Maybe that might be the mistake. You should only write a[n-1] as the answer because a[n-2] is already zero.