does it matter?

So is it rated?

Each division will have 6 problems.

Usually Div.2 C is the same as Div.1 A, so I think there will be four.

Wow, we have the same rating! Hope for the best results :)

Yes!

Relatable :(

Joining the club :|

And Really you become pupil..

They are different people.
vintage_Vlad_Makeev and team never won ICPC.
vintage_Vlad_Makeev and team won ICPC 18.
vintage_Vlad_Makeev and team won ICPC 19.

Updated.

Huh..are people openly allowed to create multiple accounts?

Sure

You'll find out in a minute, why so impatient?

wth is pretest 4

I felt this way about div1 B. Not sure if my solution or implementation was wrong but having to reconstruct made it much more work.

what is the idea of C ?

how to solve easy version of it with n <= 500.

OMG ! Div1 C = English test :/

In case too many passengers will go for boiled water simultaneously, they will form a queue
Ok, so there is a queue.

Nobody likes to stand in a queue.
Oh, so no queues?

There is an unspoken rule, that in case at some moment several people can go to the tank, than only the leftmost of them will go to the tank, while all others will wait for the next moment.
Alright, no queues it is.

This is what I was thinking.

I'm not sure if it's that hard as a solution, but it's easy to get lost looking for it. The quantity we're maximising is the number of minimum prefix sums. If we swap parentheses $$$i$$$ and $$$j$$$, prefix sums $$$i+1$$$ through $$$j$$$ change — either they increase by 2 or decrease by 2, depending on parenthesis $$$i$$$.

Obviously, if we don't select all occurrences of the current minimum, the resulting minimum of all prefix sums can only decrease, by at most 2. If we select it, then the resulting minimum can only increase or decrease by at most 2 as well. We can now try all possibilities for the resulting minimum and "increase/decrease", since there are $$$O(1)$$$ of them.

If we want minimum $$$m$$$ with "decrease", all prefix sums in the range $$$[i+1, j]$$$ must be at least $$$m+2$$$, at least one must be exactly $$$m+2$$$ and all prefix sums outside this range must be at least $$$m$$$. For a fixed $$$i$$$, we can choose the maximum $$$j$$$ such that the first condition holds, i.e. prefix sum $$$j+1$$$ is $$$m+1$$$, and check the other conditions. Since $$$m$$$ is fixed for all $$$i$$$, this runs in $$$O(N\log{N})$$$ and maybe even $$$O(N)$$$.

If we want minimum $$$m$$$ with "increase", all prefix sums in the range $$$[i+1, j]$$$ must be at least $$$m-2$$$, at least one must be exactly $$$m-2$$$ and everything outside this range must be at least $$$m$$$. It can be solved in the same way.

It needs more ideas, but they're not really that hard.

First note that any string that can become balanced with one swap, can be rotated to be balanced. So no need to waste the swap here; find the prefix with the minimum sum ( = 1, ) = -1 and move it to the end.

If the string is still not balanced, the answer is 0.

Otherwise we need to use the swap to maximize the number of balanced parts in the first level (...)(...)(...).

There are two cases:

• (()x()()y): swapping x and y will move the parts between them to level zero and will create one more part to the left, so this swap adds 3 to the base answer.

• Swapping the two ends of any part in level 0 (...) will leave 1 + the number of parts between them. For example (()()) -> )()()( which is ()()().

In a single pass with a stack, you can consider the two cases for all ends and maximize the answer: 63011541

You mean div2 D

I did finding and counting all such suffixes such that $$$N_{closed} - N_{opened}$$$ in the suffix is less or equal than $$$min(N_{opened} - N_{closed})$$$ on all prefixes. Also make sure that overall $$$N_{opened} = N_{closed}$$$.

If the string contains an equal number of 1's and -1's, the beauty equals the number of minimum prefix sums. However I think what you described should work as well. Maybe there's a bug?

Using stack and then while inserting least recently used opening bracket may be tracked and counter increased when it matched. (for D1, do for all n rotations)

String's beauty is number of minimal balances, if balance of all string is 0; (Balance is number of '(' on prefix minus number of ')' on prefix)

Bruteforce + finding pattern for answer

I sent $$$\big(m$$$-th Fibonacci number $$$+$$$ $$$n$$$-th Fibonacci number $$$- 1\big)\cdot 2$$$. No idea why.

Consider there is only 1 line. You can use a easy DP to get that there are $$$S$$$ ways to color the first line. Except ways $$$101010...$$$ and $$$010101...$$$ there are $$$S-2$$$ ways to color the line with surely $$$\ge$$$ one pair of $$$00$$$ or $$$11$$$.

For these $$$S-2$$$ ways of coloring the first line ,because they contain substrings $$$00$$$ or $$$11$$$ ,there is excatly $$$1$$$ way to color the rest for each ways. So the contributions to the answer is just $$$S - 2$$$

For $$$101010...$$$ and $$$010101...$$$ ,in the rest lines ,there is no way to color $$$00$$$ or $$$11$$$ in a line but maybe in a column. And you can use the same DP to solve it.

My solution is cubic, it passes pretests

Isn't the intended complexity cubic? My cubic solution passed pretests in 529 ms.

$$$O(n^3/2)$$$ will pass

try to solve the problem for 1 * m table . then you can see that in only 2 cases second row isnt unique

Try to make just 1 contiguous equal pair, you'll find that you cannot place any vertical contiguous equal pair if horizontal is present and vice versa, ie, the other one is alternate.Also a row or a column can only repeat at max 2 times in an assignment, and there are only 2 types of those, alternate, so I ran a dp of n*2*2, and another along column m*2*2, and just added their final states at n,m respectively.States were (position, current type of row(column), length of contiguous sequence till then). Also at the end remember to subtract 2 from answer so as to avoid the repetition of case when no contiguous blocks are equal.... Hope it helps!

Yes, if you push given string on the stack, and pop matching ones, you will be left with something like $$$...)))(((...$$$ always, and then you can rotate the mid point to balance everything.

Yes, you can pick a k-rotation, such that count of '(' minus count of ')' on prefix n-k is minimal

Edges are actually directed so think of SCC. There's an answer iff there's more than 1 SCC.

My solution is, given the input graph, you just need to create strongly connected components and then, if there is only one, output "NO".

Don't you mean D1? D1 is less points than C.

welcome :)

This is the first time I saw Div1A and Div1D of the same diffculty.

What's wrong with that, if B and C were both 1250?

Damn right! Brother

Because when passenger 3 wants to cook their noodles, he checks the chairs left to them. In this case no one has left their seats so passenger 3 would definitely get their noodles cooked before passenger 1 does.

500^3 == 1.25*1e8 It is well within time limit

Because when passenger 3 wants to cook their noodles, he checks the chairs left to them. In this case no one has left their seats so passenger 3 would definitely get their noodles cooked before passenger 1 does.

I have the same output like you ??? I don't know where i was wrong in reading the statement :V But i don't know why the answer can reach 1e10 when p<=1e9 and ti<=1e9 :V It doesn't make any sense ???? Pls explain too me .Tks you ans sorry for my poor English

If you filled the first row cells and first colm cells you will find that there is only one way to fill the remaining cells

Codeforces plagiarism checker is really very bad that they can spot these same codes with some variables changed. Nice done buddy, I think admin must look into this once.

You should look on case when n = 1. It will help to understand whole problem.

It can be solve by easy dp.

dp[i][j] — number of such coloring, if last j colors are equal.

The same question =))