Posting the announcement.

Now can you please tell me that what freak93 did ??

To Be Decided

To be determined

To be declared.

High quality, sophisticated.

Example: The recherché mustard in your profile picture is arguably the best you can get on the romanian market.

Best of luck. I hope to become master this round

hope to be pupil

https://codeforces.com/blog/entry/115895

Yes, we

are the same

TBD

wait till the God Comes...

Name starts with T, and ends with T.

Who the hell is win114514? T_T

What's exciting about this?

$$$MEX(a_1, \ldots, a_i) = min(a_{i+1}, \ldots, a_n)$$$ for permutations, therefore sum of prefix mexs == sum of suffix mins. After this observation problem is pretty standard, iterating over all cyclic shifts and recalculating cost in some way

The way I solved it was to look from the end rather than the beginning — then the sum of MEXs is related to the sum of suffix minimums.

Then I split the problem into two sub-problems: if you cut the array at a certain index and then swap the two parts obtained you get a cyclic shift. I solved the problem separately on those two parts. I did it in a very convoluted way with monotonic stack + binary search on a bunch of arrays but there is surely a better way.

Segment Trees worked for me. Basically, found all initial mexes, and then, did cyclic shift one element at a time, calculating the updated mexes. So what should happen when removing a[I] from the start of the array is considered. All mexes greater than a[I] will fall to a[I], also, adding a[I] to the end again simply adds n to the mexes. This is just done for all I from 0 to n-1

Another approach: compute mex values for the array, and encode them using run-length-encoding: RLE = [(mex1, cnt_mex1), (mex2, cnt_mex2), ...]. This array will have increasing sequence of mex values. Then you can implement left cycle operation: it will remove some of mex values from the end of RLE, and add two more values: [(x, removed_length), (n, 1)]. Doing so you can also keep total sum of mexes in the RLE. It is possible to show that such implementation gives linear complexity: https://codeforces.com/contest/1905/submission/237518768

It's working. I think you're just wrong in your estimate of the asymptotic

No.

A $$$O(n)$$$ solution would be simulating the whole segment tree process, adding $$$v \times (2^\text{No. of leaves in left subtree} - 1) \times (2^\text{No. of leaves in right subtree} - 1)$$$ to the answer each time.

By trying some smaller cases, you may observe that at each depth, the maximum difference of the range that the node represents are at most 1. So, for each depth, you can group the nodes into at most 2 sets, and then you can quickly calculate the contribution of each set of nodes to the answer (in $$$O(1)$$$ time complexity). The final time complexity would then be $$$O(log N)$$$.

great approach

Do we need to remove diameter leaves? I think it's ok to choose any pair of leaves, i might be wrong thou. I'm just asking

ceil(leaves/2)

Not really, you only needed to know what is a tree and adjacency list representation of the graph.

It is?

Edit: I can't view your submission at the moment. But maybe you're calculating the number of leaves by DFS, which will disregard the root.

if root has only one child you have to count it as a leaf.

not only leaves, all the nodes connected by only one edge, that means, if the root is have only 1 edge, it will be counted too.

that's the answer. You used "tree[v].size() == 0" to find leafs. it will be tree[v].size() == 1

I don't think my algorithm is good but here's how I did it.

First, I extracted the lexicographically greatest subsequence(lgs) from the given string. Then after reversing the lgs is it sorted or not? If it's sorted then the answer can be found. If there is an answer then, I've replaced the sorted string with the given string in the original position. Finally, I've checked if the given string is now sorted or not and printed the ans.

my submission

lets say the largest subsequence is zzba in the first iteration,then in the second iteration will be zzb, because after one right shift it becomes azzb,so now we cant take 'a' in the largest subsequence, this observation is very useful in solving this problem

You can see my submisson too

https://codeforces.com/contest/1905/submission/237535925

nodes are numbered from 1 to N but you are iterating from 0 to N — 1 either iterate from 1 to N or decrement u and v by 1

Sorry I don't think C is easy, it's hard.

You mean C is too simple? How? I do have no thought about it.

let $$$mx_i$$$ be the highest index $$$j$$$ (0 based) such that $$$p_j \leq p_i$$$.

Then the cost is $$$n^2 - \sum_{i=0}^{n-1} mx_i$$$.

We can simulate cyclic shifting using a sum-segment tree that supports adding a number and assigning a value to a segment.

See my code for more details: 237511939

C (40+min) is harder to debug than D(20+min).... Because I misread it as substring lol.

And I solve them using the same algorithm using the decreasing stack. For C it's to find a largest subseq, for D it's to find the min value on the right.

For D, you can start with x x x x x x x 0 and then start to put numbers from left to the right. The mex of the new moved number is the min(moved number). Using a decreasing stack can maintain the count simply.

Need a treat :)

notice that the largest lexicographical subsequence after all the moves will get reversed (because it will be non increasing so doing the operation until it gets reversed is optima)

so just reverse it and check if the string is sorted or no

and the answer is (size of the subsequence) — (the frequency of the first element in it)

you subtract the frequency of the first element because there's no need to shift the because the elements behind it will all come in front of it

here's my submission

Yes, I love you too;

same. Smh got WA on second pretest twice, wasted 2 hours on that problem

The characters not selected in the subsequence remains at its position and you cyclicly shift only the choosen elements among their own indices without effecting other indices

you make shifting to the right on the subsequence you pick which is the lexicographical maximum in each operation

been there... wish I didn't search for that bottle of water.

It seems they intentionally failed segment tree solutions.

Lazy Segment tree is too slow. You need to use stack to keep track of the sum of suffix minimums. It's possibly to remove element from this stack when sliding in O(log n) using binary search and some tricks (I did this, it passed as bin search is much faster than lazy segtree) but it turns out it isn't needed. Because the biggest suffix will always have 0 as minimum which doesn't contribute to the sum.

Convert it into another problem. We want the n + (maximum possible sum of (minimum suffix array) over all possible arrays from shifting)

Stuck at 3 problems as well. For me, if D is some math issue that I cannot solve even if I have 24h, then I will let it go. If it's something just related to the algorithm, I will spend more time to upsolve it after the contest. By shortening the solve time, I can sometimes finish D now.

You can take a path and compress it every move. Compressing a path removes 2 leaves.

we select 2 leaves every operation

initial thought was same but then realised problem won't be that tough for B.

I did: 237526207. A little bit tight on TL, but works

See codeforeces rule

It fails on this test:

1
8
aabbddcc

The answer should be 2.

Yes. I had the same thought during the contest! :p

Part 1 : Finding the lexicographically largest substring.

Hint : If you iterate end to start and maintain a char (largest so far), and if current char is largest, include it.

Part 2 : Note that only these characters (or a subset of them) are part of every move Hint : Every time the set reduces by exactly one character

Part 3 : You observe that the set of characters selected in 1 will eventually be reversed.

Part 4 : Can you construct a string where (step 3 is fulfilled)

Part 5 : check if string is sorted.

Nice Move ? : Intentionally left one edge case for you to solve.

Note — the answer depends on the last element, then the next smaller element left to it...and so on till it reaches 0.

Shift the array such that 0 occurs at the 1st position,

now ans[i] = ans[previous_smaller_position[i]] + array[i]*(i-previous_smaller_position[i]);

It says Accepted to me

during the contests there are certain tests which are not checked these are checked after the contest during system testing hence the tests during the contest are called pretests and on passing all the pretests you are shown pretest passed.

in every operation you can choose u and v as leave nodes and compress them. so in every operation you can decrease total no. of leaves by 2 so if no. of leaves is even it will take leaves / 2 operations. if no. of leaves is odd it will take leavs / 2 + 1 operations. ans = (leaves + 1) / 2.

That sometimes does happen man.

I think this has something to do with you using '+' operator to concatenate the strings, as it has higher time complexity. If you use push_back(), it will run smoothly. Submission