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.

try using long long instead of int, integer overflow takes place if you take int.

Used two pointer concept and it passed!

overflow may take place when int is used

are you using multiple accounts? because you do not have a submission using int, nor did you get a wrong answer on this problem.

use this #define int long long would be life saving

F is DP

$$$dp[i][j]$$$ = minimum cost (in bullets) to beat $$$i$$$ rounds (and start the next round) with $$$j$$$ bullets remaining in your magazine.

Note that since $$$j \leq 10^9$$$ you should use a map/associative array for that dimension.

The initial state is $$$dp[0][k] = 0$$$. Each state can be the parent of up to two states, one with $$$j < k$$$ (no reload after round) and one with $$$j = k$$$ (reload after round; only transition to this state if you have enough time). A state may also "dead-end" if it is impossible to beat the current round from it; if all states dead-end the answer is $$$-1$$$.

This fits in $$$O(n^2)$$$ or $$$O(n^2 \log)$$$ as the number of states increase by at most one each round (the $$$j = k$$$ state may create a new $$$j < k$$$ state, while the $$$j<k$$$ states only "move" about or merge into the $$$j=k$$$ state)

vector insert is O(n)

DEVIL indeed!

count inversions any other way (merge sort , set -order_of_key)

use pbds if you are using c++, 95257988

It can be done without segment/fenwick trees. Because its a character string, we can keep prefix/suffix frequency arrays for both initial and reverse strings and maintain the answer. You can look at my code for reference.

adderall Very easy solution: https://codeforces.net/contest/1430/submission/95314914

not in educational and div.3 rounds.

I would give u a better approach .. Just use the max 2 possible values each time and then work yourself on a case or two. You would get to know that you would always end up at 2

An example test case is -> 1 13 1010010101111

Your approach gives 6 while the answer should be 7

The problem is that we should not remove from the biggest chunk because we may exhaust it early. The ideal way is to remove from the first chunk which is greater than 1. That way we can optimally utilize the chunks. In the example, it exhausts (1111) which could have been used for 6th element while we could have reduced the (00) for the 1st element.

Dude I overcomplicated my C because I thought the solution to C should not be so obvious. Now I see that a brainless greedy works. -_-

I love the "Good morning everybody" you do at the beginning of your videos!

Sorry for asking, but what's FST?

ur solution for E was just awsome or maybe how u teach.

https://www.geeksforgeeks.org/number-swaps-sort-adjacent-swapping-allowed/

It is not wrong in a mathematical sense. It is just to slow.

when there's 1000 cases of n = 4, you will get TLE

The problem for loosing rating in this contest has huge role of your mindset saying that "I will loose rating from previous pattern ,making you feel pressure and under pressure u don't do well". Thinking it to be any normal contest and being cool , you might have performed better.

I thought about something like this initially. But decided that it is quicker and less error-prone to write brute-force that should converge quickly

My solutions got hacked in both. So sad.

So, here is my solution : First take the reverse of the given string and try to get all characters into position starting from the last.

Some sort of proof for this : It is always optimal to choose the rightmost matching character in the original string to swap and get to the final intended position. Assume it takes X moves for rightmost character to get into final position. Now any other character Y will take X + dist(rightmost character, Y).

Now, on why it is better to start fixing from the end of the string : When we try to fix some position before fixing the positions to the right of it, then this character might get displaced once again when some other to the left of the fixed character needs to go to the right of it.

Let's say there are various segments of same elements, so one thing that you can see clearly is that you don't want to merge two segments, right? Now if the segment at front has size 2 or greater you can simply delete one of its element and then delete this segment. But what if our segment at front has size 1. In the first operation you want to delete a number other than this segment, so you can do it by deleting from any segment after this and size greater than 1. It will basically create a suffix with ones only and you just want to find the size of this suffix. the answer will be number of segments initially — (suffix length/2).