you forgot the final D1,D2

Maybe that means some official div1 participants in div2 contest?

Will the ratings be updated after finish of both of them or individually?

Unfortunately one of them clashes with my class time.

Please don't use that word. It sounds negative :(

Even if jqdai0815 overtakes Tourist today, tourist will be able to overtake him later. Also, a lot of Legendary Grand Masters like Radewoosh will compete. It is not as easy as you think!

Seems like your prediction was wrong. You got minus for only 606. Other two gave you positive rating.

I think problem with short statement are hard to solve compare to problem with long statement.

Queue finished. And there was many queue in some of the previous rounds but that rounds doesn't become unrated so this round should be rated because the only worst thing is queue.(There isn't any problem...)

DFS from $$$a$$$ without going past $$$b$$$, call the set of reached vertices $$$r_a$$$, and DFS from $$$b$$$ without going past $$$a$$$, call this set of reached vertices $$$r_b$$$. The answer should be $$$|r_a \setminus r_b|*|r_b \setminus r_a|$$$.

It seems that the answer is $$$(\text{No. of vertex not reachable by 'a' without going through 'b'}) \cdot (\text{No. of vertex not reachable by 'b' without going through 'a'})$$$

Run two DFS from a and b individually ignoring b and a respectfully and save the visited nodes in two sets. Now, we have to delete the commonly visited nodes from the two sets. Then, the answer will be the multiplication of the size of these two sets.

Find connected components of the graph without $$$a$$$ and $$$b$$$. Then for each component, determine whether it is adjacent to $$$a$$$, $$$b$$$, or both. The answer is the product of (sums of sizes of components adjacent to $$$a$$$ only) and (sums of sizes of components adjacent to $$$b$$$ only).

My approach was bit different. I did it by doing dfs from a. Find the sum of size of subtree of b's children in dfs tree from which there is no back edge above b. Now, multiply it by (n — (Size of subtree of a's child which contains b) — 1).

I made two dominator trees, using a and b as roots. The answer is: ((size of subtree b on first tree) -1) * ((size of subtree a on second tree) -1)

Another way to find it:

Run a dfs from A and as soon as you reach a vertex (and it's not visited), add it to cnt. If you reach B, add it to cnt but do not move forward. It's obvious that n — cnt is equal to the nodes that are not reachable by A if we disconnect B.

Do the same from B and you'll find the nodes that are not reachable from B if we disconnect A. Now, if we get 1 node from cntA and 1 from cntB, we can see that the only way to connect them would be to pass through both A and B. Hence, it's a valid answer!

So, if we multiply cntA and cntB, we get the answer! :)

Can anyone tell me why my solution is wrong? 66888589

My approach was as follows :-

Remove all the edges from and to b, then count the number of nodes which can't be visited through dfs from a, since these nodes could be visited by adding the edges of b, this simply means that any path from a to these nodes passes through b. Count this number and let it be A.

Do the same after swapping a and b. Let the new number be B.

Then the answer should be A*B, this fails testcase 18 :(

UPD :- Nevermind, I messed up ll and int, fuck my life

Check when shortest side is greater than the biggest number of duplicates.

CF-Predictor is predicting you're going green :)

Try "ttwoonee" For me this was the case.

[Deleted]

Resulting sequence can be made of the form — (10)(00,00,00,....00)(01+10, 01+10,......,01)(11,11,11,.....11)(10)

it can be solved in O(nlog(n)) but still 800 ms for me ...

It's easy to improve $$$O(n \sqrt{n})$$$ solution to $$$O(n\log(n))$$$ with 2 pointers.

My solution has O(n) complexity :O Capped by the input tho. only took sqrt(n)*log^2(n) to binary search the grid. Upd : nvm. i got sort.

Can you elaborate? I did A,B,C without needing anything specific (unless my solutions fail).

Check the first and the last digit of each string. And you'll be able to classify them as [0~0], [0~1], [1~0], [1~1]. If the second and the third group are all empty, handle that case separately, otherwise regulate the size of the second and the third group properly.

Maybe this "twoooneeee"

1) two -> t#o 2) one -> o#e 3) twone -> tw#ne

There are none. No of indices are twone + (twone-one) + (twone-two).

Remove allways the middle character of the match.

if the string is "ooneee" , you should only delete 'n' not('o' or 'e') coz if you did you will get oneee or oonee (Invalid output)

The idea is kinda seems correct, but it can be simplified by thinking it like:
Answer = (n -Size of the component where 'a' is present after removing 'b' and its incident edges) * (n -Size of the component where 'b' is present after removing 'a' and its incident edges).
This requires just 2 dfs's.
You can find my submission here.

Your idea is correct, but probably you have a bug in your implementation. Anyway, you can solve it much more easily, see here: https://codeforces.com/blog/entry/72120?#comment-564067 (I used a similar approach)

I also get the idea for E quickly but i have no time to code.

We do subtree dp. For each vertex $$$v$$$ we calculate 3 dp values: when parent $$$p$$$ of $$$v$$$ is taken before we go through edge $$$(v, p)$$$, when $$$p$$$ is taken by edge $$$(v, p)$$$ and when $$$p$$$ is either taken after edge $$$(v, p)$$$ or never taken at all. To calculate it we go through edges incident to $$$v$$$ in sorted order and store intermediate dp for wether we have taken $$$v$$$ and $$$p$$$.

Run two DFS from a and b individually ignoring b and a respectfully and save the visited nodes in two sets. Now, we have to delete the commonly visited nodes from the two sets. Then, the answer will be the multiplication of the size of these two sets.

I also do the same, but consider only rectangles where height is smaller than or equal to width. Now consider that you don't need to simulate the process (except at the end). If you have a fixed height H, you know you can't take more than H samples from each number. So, with Fenwick tree, count the sum S of all numbers from which there are at most H samples. Then, count the number N of numbers which occur more than H times in the array. In the end, calculate S + H * N — this is the maximal amount of numbers you can get. You can then find the max. width you can have for height H.

Struggling for the same