Probably among a handful at best. Pretty sure the blog would be lambasted otherwise.

yes I am also the handful one

It was constantly showing an error on Brave browser. The issue was resolved when I switched to chrome for some reason.

but.. you didn't even give the contest?

Let $$$b$$$ be array of string balance. Then, if you do operation on $$$(l,r)$$$ you change all $$$b_i$$$ $$$(l \le i \le r)$$$ to $$$2 \cdot b_{l-1} - b_i$$$.

Hint — 0

We can only reverse EVEN length segments. We can only reverse segments, where number of '(' is equal to number of ')'.

Hint — 1.

Lets take one sample string -> (((( )))) . Figure out, how many possible reversals are there.

Hint — 2.

We are allowed to reverse till last two '('. We can not reverse last three '(' . Why ?

To get an answer to above question, try this on pen-paper...

1. Keep one counter. Initial value of the counter = 0;

2. Travel the string from left to right. When you encounter '(' , counter++, else counter--, Store above values into some array.

For each segment start l we want to count number of correct segments' ends r, such that sequence remains balanced, and that means:

1. $$$ count_{opened-to-l} - count_{closed-to-l} == count_{opened-to-r} - count_{closed-to-r}$$$, otherwise we will change the balance of whole sequence and it will become irregular.
2. Suppose balance of l-th place is $$$k$$$. Then between l and r there can't be a position with balance $$$\geq 2*k + 1$$$, otherwise there will be a position, where we open (after operation we close) more than k brackets, meaning our balance goes below zero, then sequence is also incorrect.

Counting suitable ends can be done with grouping positions by balance and binary search

Here is my solution.

1. diff_cnt -- counter the different between the number of '(' and the number of ')'
2. Since the diff_cnt will decrease later, we just do diff_map[(diff_cnt[i]-1)/2] = 0; The different from 0 to diff_cnt[i]-1)/2 is invalid. But other value will be set later.

3. For each position the answer will be all position of current diff_cnt. ( ans += diff_map[diff_cnt[i]]; ) Because the difference between these position is 0.

   map<int, int> diff_map; for(int i=1;i<=s.size();i++) { ans += diff_map[diff_cnt[i]]; diff_map[diff_cnt[i]]++; diff_map[(diff_cnt[i]-1)/2] = 0; // cout << "diff cnt: " << diff_cnt[i] << " map: " << diff_map[diff_cnt[i]] << endl; } cout << ans << endl;

263353060

since first candidate is having higher testing skil, he must be consider as the tester.

When you're skipping 3rd one,the tester shouldn't be the 2nd one rather 1st one because according to the statement until programmer or tester slot is not filled, you should always take the one with greater skill value.As the first one's testing skill is more than programming skill and tester slot is not filled yet(initially 0),you should take the first one as tester and rest as programmers.

you have to assign in order, so the first candidate will be assigned as a tester since his bi (5) > ai (4), then the second candidate will be assigned as programmer

you always need to do the copy operation once so the answer can never be zero

The minimum answer for this problem is one because when we move any element of A to last it will cost us 1, So we won't get 0 as output

your code is wrong because if lastIncluded is false at the end of the iteration you just add one but more than that many operations might be needed

simple solution for A, if string is sorted YES else NO

Don't leave. Keep trying you will do better. I saw, you solved both A and B which is great! You shouldn't be demotivated by few WAs.

Calculate the answer for answer[n+m+1], call it sum. Store the job given to each indices in this arrangement(You can use a set for example). Also, store the first instance where someone's job flipped(i.e. they were more skilled in testing but only programming is left, or vice versa). Notice that after that, there are no more flips of the opposite manner, since after a flip, every job is the same. Finally, just run through from 1 to n+m, and pretend to remove this persons job. It would go to either a) the first person flipped infront of this index(in which case their job goes to the last person) or to the last person. For a more formal look, you can checkout my sol here 263338267

Simplest is bruteforce with memoization, because taking/skipping 1 element will affect very few elements.

But of course there much more clever solutions

no

What mistake?

how

i don't want comments like this get normalized

Why? I enjoyed it.

Why? Because it forces you to think in a different way?

You are damn right

For example:

1

2 2

1 2 3 4 2

3 4 5 6 1

Your code outputs 14 13 13 12 14

For the second person, the answer should be: 3+5+4+2=14 (he would've been a tester, so the third guy becomes a tester instead of him, and the last guy becomes a programmer).

Remove last one and choose everyone to progers or testers by naive. What will happen if you remove $$$i$$$-th person? $$$(1 \le i \textbf{<} n+m+1)$$$?

yes, my submission is n log n

You can do binary search + sparse table or segment tree to solve in $$$O(n \log{n})$$$

D can be solved in O(n): 263368704

I too was not able to find why I got WA for 30 minutes. I am Too slow at implementation and debugging.

Hello Master DuongForeverAlone! hru? do u remember me?

I cant see you last reply LOL so i just replied myself XD

I too thought the same. But the shortest way to solve the problem A is to just check whether given is sorted or not. it is so elegant.

consider each element as potential candidate which can be use to perform 3'rd operation
if you choose a_i for 3'rd operation
think about how you can minimize cost for i'th element because for all other j (j != i) cost is fixed that is abs(a_i — b_i)

Dp, If don't understand then ask.

I use sparse table + binary search to find "the index of the first item after pos that is greater than x"

263354202

My solution is the same and runs in O(n * logn * logn). But I just copied segtree's code from GFG and it runs in less than 1000ms.

263329045

damn

1) Do your operation on whole string. 2) Then look what operation does on segment

Where did you get such information? I still find it hard to comprehend an 8yr old CM :(.

input:

1
16 16
41 30 6 18 12 7 38 7 28 27 16 41 31 15 1 34 46 11 5 41 47 16 11 16 14 11 29 14 27 37 25 14 8 
32 6 40 47 33 30 11 41 1 20 1 1 1 29 9 13 45 43 46 19 20 20 43 12 36 20 40 5 30 49 34 17 37

correct output:

1012 1023 1022 1015 1029 1032 1015 1021 1025 1026 1037 1012 1022 1033 1053 1019 1007 1019 1016 1012 1006 1042 1019 1037 1026 1042 1022 1039 1032 1013 1028 1039 1045

Try to write cleaner code! it helps while debugging your solution.

How is a problem bad just because it is lengthy? Most real-life problems are way longer than this tbh I enjoyed C it had so many factors to consider before arriving at the solution instead of one single crazy trick ¯_(ツ)_/¯

I didn't find the implementation that lengthy, 263365416

Assume all the candidates come to interview. Solve the problem twice, once for N+1 coders and M testers, and once for N coders and M+1 testers. In both solutions track whether each candidate is appointed as a coder or as a tester. This takes O(N+M+1) steps.

If the candidate i does not come to interview, then check whether i is appointed a coder or tester in the two solutions. If a coder in the first solution, then answer is (first solution score — candidate i score as a coder). If a tester in the second solution, then answer is (second solution score — candidate i score as a tester).

You will never have candidate i appointed as tester in first solution and as coder in second solution.

line 124: cout<<ans1-t[i]; There is no space before the next output.

Nevermind, resolved.

You need to check if $$$b[n]$$$ is between $$$min(a[i], b[i])$$$ and $$$max(a[i], b[i])$$$ for any $$$i$$$ in loop instead of just at the end using bottom and top variables. If this condition holds, just add 1, otherwise handle the case as you're doing it right now.

The mirror was fine the whole time for me.

I wasted about 30min because of 502 and cloudflare.

m1,m2 and m3 didn't work well, too.

A lengthy problem in 2-hour contest is a bad problem.If it's in a 5-hour or 14-day contest, it's not really bad.

can you provide an AC link ?