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

If you dont believe me scroll and check.

Orz

Manchester is RED , alireza_kaviani :) orz

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

how you became expert in your first contest itself??

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

Yes you are noob

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 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

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.

I also had the same idea, but here is the problem: It might be better to take the right maximum and then the left maximum afterwards.

test case:

5

4 3 5 1 2

The min for 4, 3, 1, 2 is clearly 1. But the min for the 5 would be 3. However, we can take right maximum and then left: 5 -> 2 -> 0. So answer is actually 1+1+2+1+1 = 6 instead of 7.

Disagree, C was standard imo, for example 102341H - Hypno is very similar, but a bit harder.

D, E and F were rather nice, a bit of AtCoderForces spirit, but still way better than most AGCs.

you run a djikstra-like algorithm on the reversed graph. In each iteration, my solution has an invariant that the nodes that have been popped from the set have the smallest values of $$$dp[u]$$$, where $$$dp[u]$$$ is the minimal cost required if one starts from node $$$u$$$ and goes to node $$$n$$$. We remove edges only when we are at the node from which the edge emanates (goes out). Then you can see how a djikstra-like algorithm always maintains this invariant, and hence answer is $$$dp[1]$$$.

details: 160892338

chadboy

I think I did the same thing, guessing that it would work (somehow it did). I would also like to see a proof of why this type of memoization runs in linear time.

Glad to see your persistence, try our best to prepare for the next round!

It's 2 different types of problems: "jury" thingy appears where you have to calculate a minimum or maximum answer for example and at some point there is a possibility to have a better answer than yours, but "expected" simply stands for a wrong answer.

I solved this problem using RBS (Regular Bracket Sequence) pattern. If you consider the positive numbers as the number of open brackets and the negative numbers as the number of closing brackets, you will see "If the total sequence is regular and it's closed then the answer is yes".

So you will get Yes for ( ()()() ) or ((())) or ( ( () ((())) ) ). But if the bracket is like this ()()() then it's no because in this case you can't get back to the first index.