BitmaskForces ?

Good luck everyone...Hope everyone performs well :)

lol .. He said Huge thanks to testers for providing invaluable feedback.

If you dont believe me scroll and check.

Orz

Orz

Orz

Manchester is RED , alireza_kaviani :) orz

Orz

stO Orz

Don't worry, no surprises.

Haha certainly....but sometimes short ones are the real fire ones...looking forward for this round....

Have seen you somewhere ... anyways best of luck...

ok thx

Good luck

how you became expert in your first contest itself??

Rated range: (−∞,1899] for Div2, [1900, ∞) for Div1

That's the spirit! Wish you the most of luck! <3

Yes you are noob

Same TOT

orz

https://letmegooglethat.com/?q=what%27s+orz%3F

No, it's a twin contest.

no, it is rated.

I thought so too.

I hope so too.

infinity, quite literally. If you did not know, negative ratings exist and they are not rated in most rounds (most rounds' rated range begin from 0)

It should be [1900, tourist].

Orz to people that have actually seen his handle fully red

A Hieroglyph.

Why so many downvotes !? It's my personal opinion !

I agree with your opinion!

I respect the work of autors. Its very cool to do problems for codeforces round. I dont like this types problem. Thats what I meant.

I hated it for that reason, but problem was very good . They should'n have provided the 5th sample it was easy to guess then.

That's kinda funny tbf

Reverse the graph and then do something very similar to dijstrak starting from n-1. Notice that at some node, you have a bunch of nodes you can go to and if you know their distances, you can kill some in descending order(so like their effective distance is +0 +1, +2 +3....) and find the optimum of that. Thus, what you can do is to store the current estimates incoming (after reversing) for each node and pick the best (similar to dijstrak) after adding some weights. Then, we process the nodes by current estimate similar to dijstrak. But this may potentially force you to reupdate the whole set everytime you process a node. But, you realise that you only add numbers greater than numbers you add before (since you process nodes in ascending estimates). So, you can just store the best estimate.

Essentially its just do dijstrak with the following modification: dist[v] = min(dist[v], dist[u] + indeg[v]) indeg[v]--

I can write a bit more: assume that we've split the prefix into two sequences (decreasing and increasing) and the next two elements are $$$x$$$ and $$$y$$$, where $$$x$$$ can be appended both to increasing and to decreasing sequence. It turns out, that if $$$x<y$$$, it's optimal to append $$$x$$$ to increasing one. If $$$x>y$$$, it's optimal to append $$$x$$$ to decreasing one.

Beginning from last non-zero element, iterating backwards, keep adding arr[i], sum must never be >=0, except at Oth element. That was the opeartion about.

let j = position of last non-zero number (1-indexed)

There must be no prefix sum of length i(0<i<j) with sum <= 0

A[j] must be negative and total sum of array A = 0

maybe you are just paranoid

Yeah problem statement was not clear But prefix means abs(count(1s) — count(0s)) till that index eg: 0 1 0 0 1 pref 0 -> has 1 0s and 0 1s so its abs(1-0) — 0 Similarly till 1 to 4 i.e index 0 to 3 more formally 1's count = 1 and 0s count =3 so absdiff = (1-3) = 2 But since we need to minimize creepiness we need to do alternate 1s and 0s so they can cancel each other at certain prefix and abs diff = 0

for every prefix there will be a creepiness. out of all the creepiness of every prefix, we will have to take the maximum creepiness. now this maximum creepiness should be minimum.

form the testcase a=3 and b=7. this means there are 3 0's and 7 1's

there can be multiple answer to this, but lets take the testcase answer: 0001111

now the prefixes for there are: (beside them i will write the creepiness(c)) [c= abs(a-b)]

0 : a=1, b=0, c=1 00 : a=2, b=0, c=2 000 : a=3, b=0, c=3 0001 : a=3, b=1, c=2 00011 : a=3, b=2, c=1 000111 : a=3, b=3, c=0 0001111 : a=3, b=4, c=1

out of all the prefixes, the max creepiness is 3.

in this example, no matter how you arrange the 0's and 1's, you maximum creepiness will never be less than 3.

but this not how you should arrange your 0 and 1. You should first alternatively arrange them and then if there are some left from either just 1 or 0, just print all the remaining of them.

Post Traumatic String Disorder

Hey, Can I ask you, As a div 1 participant how was Div1B?

I don't know if i am eligible to explain something to CM, but this is how I solved.

• First I observed that if the first element = x, then we go right x times from first element.
• If we go x times right from first then we must go left x times from second element.
• since the second element = a[1] = ( number of rights from second — number of lefts from second). So we get right_times[1] = a[1] + x.
• Similary construct for all indices. If any of them is negative then its not possible since we cant go negative number of times in some direction.
• This is my code

PS: We also need to check if at some point right[i] becomes zero then all the array elements from that index must be zero, since we dont move towards right anymore.