As someone who has a birthday, please give me a contribution.

Thank you, for your wishes for everyone who got it positive

Merry Christmas!

but a tester can't participate in the round

Mate you just missed by 2. Maybe in rechecking later it may increase.......

i often wonder what exactly does a tester do ? and how do even 1200-1300 rated people become tester

Both A,B,C accepted... Hope to see myself Expert.

maybe the best of things,

I read Kazekage

Had the same idea, how are you calculating the inversions for relative power shifts? My approach ended up double counting many things

You don't need to simplify this to anything else. You can calculate this directly

Can u plz explain me your submission for problem B, why it is working ?

was getting WA on pretest 3 :(

What's wrong with it, I think it is a really good problem for Div2 C?

beta detected opinion rejected

Sum of the first occurrence of each character is the answer. Suppose we have s = "abeakf". Then if we consider 'a' is the first character, we will have ["abeakf", "aeakf", "aakf", "akf", "af", "a"]. We only need to care about the first position of character 'a' in s, because if we tried to used the second 'a', the result string will be duplicated (these are "akf", "af", "a")

Essentially, the only difference between strings after "i" operations is the first letter. That's because you can't reach the other characters through these operations. However, that initial letter could be any letter present in the prefix of length "i" of the original string. So, you calculate the number of unique letters in each prefix and then sum them up. That's basically the answer.

Just add the left over length when ever you encounter a new character. for a string abcde the number of substring contributed by letter 'a' => $$$a, ab, abc, abcd, abcde = 5$$$, 'b' = 4... so on.

check the string from left to right, if i th character has not appeared before, answer += n-i

I thought of that in this way. Suppose you have a string "ayush",now if you want to find all the strings of size '4', "ush" will always be there so the string will be "_ush" now for the first character look at how many distinct characters we have encountered before we reach 'u' (2), so there are two possible choices for the first character. Do this starting from size 'n' to size '1'. Hope this makes sense to you!

i did min(3*n, d)

$$$n$$$ is not sufficient. You can raise the answer by $$$1$$$ in $$$2$$$ steps using operation 2 but operation 1 can add upto $$$n$$$, so you need to check for the first $$$2 \cdot n$$$ steps.

I can proof. You actually need to do not 5000, but 4001 (additions). Because if you do 4002 additions and get 2000 score as return, you could have also done 4001 for 2000 score with the strategy — do one addition — cash the score

It don't know understand why you need to do that , main thing is that only 1 such position is possible after 0-array , so brute force till k , then all will give 1

for(ll i = 0; i < k ; i++){
     ll cnt = 0;
     for(ll i = 0; i < n; i++){
       if(a[i] == (i+1)) cnt++;
     }
     ans = maxm(ans,cnt+((d-i-1)/2));
     for(ll j = 0 ; j < v[i] ; j++){
          a[j] += 1;
     }
  }

same bro.

I did it by dp First reverse string s, then we are considering removing from either last or the second last position. Our answer is f(n-2,s[n-1]) f(i,x) = No of unique strings that can be obtained from (s[0:i] + x ) by 0 or more operations f(i,x) = 1 + f(i-1,x) if s[i]==x f(i,x) = 1 + f(i-1,x) + f(i-1,s[i]) — f(i-2,s[i-1]) otherwise subtraction is to avoid double counting

I used recursion, but not DP. First submition failed as I tried to save all possible subsrings https://codeforces.com/contest/1917/submission/238697805. And the next attempt was successfull when I decided just to increment answer https://codeforces.com/contest/1917/submission/238704078

I tried that too I reversed the array and used a stack dp but when I calculated the space complexity I was kinda convinced it would give me MLE so I tried a different approach

you can observe something from enumrating the resulting substrings

for every suffix[i] from n-1 to 0 :

I erase second character until s[i] is the same as second char. (count += i - last occur of s[i])

I dont use fisrt type operation because the string will be the same as suffix[i+1].

so I just store the position of last occur s[i].

my submission here

Your second submission, and its submission time, is used. You are also penalized as if the first submission was rejected.

In the last 'for' loop, you are checking for the valid indices only till b[j]+1. You need to check the whole array.

i think when u added to the first b elements in the array, you checked if an element became "good" meaning that a[i] = i but not if an element is now no longer "good"

Recently all problems sets are very nice.

Oh I see, forget to take those power of 2 exceeding ±20 into consideration ...

You don't need to do so. Its just that after you do a reset operation then you can't get score greater than 1 after any number of operations. So its optimal to take a score of one from first element greedily after doing 1 reset operation

How many can you get from first reset op?

Here is my solution by the way, which didn't passed probably because of bug in implementation.

Fix an element in array $$$a$$$. I want to know, when it is good, i.e. $$$a[i] = i$$$. If $$$a[i] < i$$$, then after some movements on array $$$v$$$ it will become good, then it will become bad forever. Sounds like scanline. Let's calculate for all elements of $$$a$$$ the segment of numbers of operations of type 1 after which the element is good. Process them in decreasing order. Fix $$$i$$$. Then all $$$v[j] \ge i$$$ change element $$$a[i]$$$. I want to know the position in cyclic array $$$v$$$, after which $$$a[i] = i$$$, i.e. I want to know $$$(i-a[i])$$$-th element of array $$$v$$$ with only elements which $$$v[j] \ge i$$$. Assume, they are in some structure. Let there are $$$x$$$ satisfying elements in array $$$v$$$. Then I need to traverse the whole array some number of times, and them some prefix. So I need to be able to find $$$k$$$-th element. I can do it with Cartesian Tree (Декартово Дерево), or with "indexed set" (google "cses.fi Josephus Problem II").

not actually

My English is not good,in my opinion,the sequence is like stairs,because it can be added to ans when it equals to it position,so every time you do opreation [1,b[i]] +1,it will break the stairs,so if 1-n is 0,only 1 or 0 can be added to your ans after several +1 opreation. To be the best,you can do opration 1 once and do opration 2 once.In this way you can add 1 to ans for two oprations. after understand it,you can make a brute force on array 'a' to Calculate the best ans. it will be allowed on O(n*n) , you can according to my ans 238725053. I Hope i can help you.

I was supposed to be CM, but FST in C spoiled the mood :(

True A and B were speedforces couldn't say the same for rest of the problems

really? how do you know

Yes because if it doesn't get give better result in this range there's no way it will give better if it's more since you can increase the score by 1 in 2 steps. I didn't realise that and checked way more than this by throwing and got Ac

Here is a case where checking up to $$$n$$$ fails:

1
4 3 6
2 0 1 2 
1 4 1

Only optimal solution is doing op 1 five times then op 2.

more like max(n,k)

me too, I felt than C even easier than B.

d can be upto 1e9 which goes way above the constraint

If n + (d - 1 - u) / 2 <= ans then this and the future iterations are useless since they won't improve the answer. And since the initial ans is $$$\frac{d - 1}{2}$$$, any value of $$$u \ge 2n$$$ will be useless. Therefore, this cycle performs at most $$$2n + 1 = \mathcal O(n)$$$ iterations.

You don't get FST because $$$k$$$ is large, you get FST because checking the first $$$k$$$ days is not enough.

Yes, I didn't think a lot about odd $$$n$$$, but yes it's solvable (check Bonus in the editorial for the problem E)

Ohh What fresh hell is this !!

Really feels bad when you misread the problem.

couldnt make this work ( 238728699 ), wasted 2 hours