We will, hacking lasts 12 hours

But I have to wait until the next afternoon (or the next evening, for the poor speed of system testing and rating changing) as a Chinese. I just want to have a good sleep (instead of staying up late) and can see the rating changes as soon as I get up.

luckily for you they never make it past the fourth game.

yeah,how time flies!

To me, all rounds are special :)

Maybe it is a special round? Maybe there will be fast syste... Oh no, fast systests won't help, there is 12 hours long hacking phase...

yes! you can.

And you can copy anyone's solution before you hack others.

I agree. It is annoying to wait 12 hours

But then Chinese will have to not only stay up to participate in contests, but also keep staying up after the contests to hack.

Mmm... I made 16 hacks in the last 4 hours of hacking phase, and only 6 in the first 2 hours. I think 24 hours was too much, but 12 hours is not that bad!

I agree with you. The rating changes are always come out at the second day when we have an Educational or Div. 3 round.

After The Contest ended.....everyone Can See your solution and if he found anything wrong he can hack you and the problem won't be Accepted

Some people just want to watch the world burn!!

Educational rounds are created to solve problems and not to hack

how can codeforces community help you?

keep this fb thing there itself :|

The weird thing is you commented this in the middle of the contest!! Man, during the contest you should concentrate only on solving problems.

The task is to count subsequences which could consist of one or more consecutive subsequences which obey mentioned rules. [a1, a2, a3, a4] consists of [a1, a2] and [a3, a4] which are valid subsequences, therefore the entire subsequence is valid and should be counted.

Left a record in the standings of contest 1000 and plunged into problem preparation. (I guess)

You can do F with regular segment tree.

The idea is to sort queries by start-index, and only keep indexes i, such that index i is the first time number V[i] appears in [start-index, n).

For each such number, store where the next same number is.

Now, you just want to find the maximum element in an interval. If it's not large enough, answer is 0. Otherwise, its value is the answer.

When moving to the next query, loop from last-start-index to start-index — 1, deactivate those indexes, and activate indexes of their values's next appearances.

I think you haven't read D, E, F, G. These problems are just like what you would expect to find in a usual Educational round.

Also, I don't think the implementation in C is too heavy. A has an elegant and short implementation.

What is the story behind your username mango_lassi? You don't seem Indian to me.

Key idea, in my opinion, is to calculate for each i dp_i — maximal profit of 2-path starting at i and finishing at i. If i is a root of tree, then dp_i is just pretty standard dp for subtrees. To calculate dp for each vertex as if this vertex is root — it's possible with technique of "rerooting" (actually, I don't know it's real name as I don't know where to find materials to this quite standart technique).

Classical scanline problem.

keep a map of indices of segments and use it as partial sum. Though it struck me a little late. Solution(Easy to understand)->http://mirror.codeforces.com/contest/1000/submission/39725149

I would do nothing, but enjoy looking at standings (because you solved 6 problems).

try to find bugs in your own solutions so they don't get hacked

Yes. Though an easier way to think about it is diameter of bridge tree.

C? I don't think so. Doesn't even look like a Mo problem.

Though F definitely has a Mo solution :D Our model implementation works a bit over TL (like 3.4 seconds) but couple of participants actually squeezed it.

I would like to know the same. My submission got TLE during contest: 39712202. Fearing that the time limit is too strict I switched to C++. And here's my practice submission with an AC: 39725290

This is better, http://mirror.codeforces.com/contest/1000/submission/39704314

Чтобы после них у части участников менялся рейтинг.

А много ли участников раунда бывали на этих Московских сборах или могли встретить эти задачи? (авторы придумали эти задачи независимо) Да, возможно таски не такие оригинальные, но конкретно этот пример мне не кажется показательным.

You can find the bridges of a graph with Tarjan's like this. With them, you will then be able to combine all the nodes that share some cycle. And you will end up with a tree.

Because you need only 1 second to change one size to another if they have equal length. The answer can't be less because you need to change at least this number of strings.

lets take all the t-shirt name of lenght 3 that is xx_ so in old t-shirt either it will be present or absent so if it is absent so we only need to change the last character but if it is present we can use that and we cannot reduce or increase the length of the names so we will only consider length 3 similarly for all.

You need to find two vertices s and t such that the number of bridges on the way from s to t is maximized.

Consider this test case:

2
M
S
L
M

Your output = 2; Answer = 1;

your code is failing for this 6 L L L M M M L L M M M S output should be 1

try this testcase:

2
M
L
M
S

I have also done same mistake in my code Now understood flaw. Thanks for the test cases.

Thank you all IIIIIIIIIIIIIIIIIIIII, anno and lazyc97, now I get it.

I worked during the contest on coming up with such tests, but failed with it :(.

Basically you should notice that the best is to insert the new number just next to some a[i] or just before it.

So you can try all possibilites. To do that, could be a good idea to have an accmuluate array that tells how many time is on from number i to the end. Then you can go from left to right and get the answer for every possible insertion and take maximun.

Let's denote with dp[i] the number of good subsequences of the array a[i...n-1], and define dp[n] = 0.

The good subsequences of dp[i] either use the element a[i] or they don't. There are dp[i+1] good subsequences that don't contain a[i]. So we only need to count those that do.

These subsequences might contain multiple good arrays. Let's focus on the first one. Its size is exactly a[i] + 1. If a[i] <= 0 then there are obviously no good array starting with a[i]. So assume that a[i] > 0 iterate over the last element in this good array. It can be any element a[j] with i + a[i] <= j <= n-1, and there are nCr(j - i - 1, a[i] - 1) possibilities to pick the middle elements of this good array. We count this sequence alone, and we can also combine it with each good subsequence in dp[j+1].

Therefore we get the recursion:

And the solution to the problem is dp[0].

After contest:39725241 Hacked :D

See this submission 39747523