Seems that it's your country where time zones are changed frequently :)

It seems Chinese students are lucky because we always do it in 00:30am.
LoL~~~

I re-checked my email right now, I didn't received notification about this round. I am visiting CF quite often, so I knew about contest anyway; but some people may actually miss round becuase of missing notification.

why minuses??

Happy New Year!

Edit: my comment is wrong.

oh if we maximize also it gets accepted.

yeah, it is extremely rare that a problem description (in this case div2 B) is changed multiple times during the contest.

Let me clarify what happened during the contest.

The original statement looked like the following:

[start of the fragment]

We will assume that a set of cells is an island, if the following conditions hold:

• each cell of the set is covered with sand;
• from each cell of the set you can get to any other cell of the set by moving only through the cells of the set, considering that in one move you are only allowed to move from one cell to a side-adjacent one;
• you cannot add any cell to the set so that conditions 1 and 2 hold (in other words, the set of cells should be maximal).

[end of the fragment]

It is definition of the island that has nothing common with the rest of the statement. The given definition is one of the classical definitions of the connected component: the connected component is a maximal (i. e. unextendable, not maximum size!) set of vertices such that any two of them are connected with a path.

In English words "maximal" and "maximum" have different meanings. For example, here you can see two different objects: maximum matching and maximal mathcing. When we say maximum, we mean maximum-cardinality. When we say maximal we mean such set that can't be extended with any other element without losing some property. And this was explicitly said in previous statement. It doesn't say that you should have no way to convert sea cell to a sand cell such that conditions 1 and 2 hold; it says that you should have no way to add an existing cell without losing conditions 1 and 2.

Also, this part describes the definition of island. The actual task follows after this paragraph and it doesn't say anything about maximizing any kind of value. It is also illustrated by the sample test.

Nevertheless, we've seen many clarification requests asking why the answer to the sample test isn't maximal in some manner. So we decided to clarify this part as possible. We said twice in global announcements that this definition is a usual definition of the connected component. That still didn't work, some people still were asking questions. Then we decided to even rewrite the definition making it less formal (!) but more clear to a newbie. But we want to point out the fact that at no moment the question was incorrect.

You can try to formulate by yourself what is "connected component", it's not easy to do that without mentioning maximalness in some way. On CodeForces we usually try to provide formal definitions of things used in problems. Unfortunately, it sometimes leads to such issues.

After a long discussion we decided to leave everything as it is and make the round rated. After all, there were lots of people who understood the statement correctly.

Also, as someone noticed above in comments, even if you try to maximize something (total size of all components, for example) and you do that correctly, you will get your "Accepted" since our checker accepts all solution that have k connected components, no matter which size they have.

а какая идея была в Б не подскажешь ?

You can let your code run this case:

200000

1 2 2 2 ... 2 2 2

A hack against division via multiplicative inverse: (ideone)

How to construct it:

factor 1000000006: 2 500000003
factor 500000002: 2 41 41 148721
factor 148720: 2 2 2 2 5 11 13 13

So, to get a subtree with answer 148720, we have to unite eight chains of lengths (2-1) (4 times), (5-1), (11-1) and (13-1) (2 times). After that, the subtree contributes a multiplier of 148721 to its parent. Proceed with constructing 500000002 from three short chains and the 148720 subtree... and so on.

Problem Div.1A is a typical dp problem, isn't it?

it must be dynamic programming.. my code keep getting WA on pretest 6 anyway :(

f[j][k] — count of plans with j lines and k bugs. f[j][k] = (f[j][k] + f[j-1][k-a[i]]) % mod

 MEM(dp,0);
    dp[0][0]=1;
    FOR(i,n){
        FOR(j,m){
            for(int k=0;k<=b-a[i];k++) 
                dp[j+1][k+a[i]]= (dp[j+1][k+a[i]]+dp[j][k])%v; //dp[i][j] where i represents the number of lines and j represents the number of bugs.
        }
    }
    ll ans = 0;
    for(int i=0;i<=b;i++)
    ans = (ans + dp[m][i])%v;

I got WA 6 because I was running the k loop upto b (instead of b-a[i]) which was causing WA.

I was hacked also by such a testcase. How can we deal the problem when the number is divisible by 1000000007?

What sort of greedy? I just used set cover.

I was in similar situation, but a bit luckier :D

Ты уверен, что i <= s.length(); верно?

I think case 1 itself was self-explanatory that it is not necessary to maximize the sizes of islands. If we had to maximize the size of islands, one of the possible answer could have been: YES

LLLLL

LLLLL

SSSSS

LLLLL

LLLLL

My O(NMB) solution works 500ms on fpc. What language are you use?

Same here. Can't understand why the time limit is set so strictly time and again.

What was the approach to solve it?

Yeah, I have similar issue as I see.

What is the reason to make array size as a power of 2? It leads to problems with cache.

For example, you can increase 512 to 520 and got Accepted: 11026552 and 11034250.

Hey, dude, I just saw that your code in Problem A so perfectly repeats my. I'm not saying that you are cheater, but tell me: "How?"

UPD: If someone wants to see that:

My code: http://codeforces.net/contest/544/submission/11023029

His code: http://codeforces.net/contest/544/submission/11023693

BFS was certainly an overkill for this problem. You just have to create islands skipping one cell after each island. A simple traversal of O(n*n) does the job.

Как это NO если: LLSL SSLS SLSL LSLS

Случайно не помните дословно определение компоненты, которое изначально было?

because your solution like another solution :D

O(n²).

In case 39, the calls calc(0, false), calc(1, true), calc(2, true), ..., do O(n) operations each.

Well, I think it's sigma(deg(i)^2), which can be O(N^2) in worst case.

Highlighted area like?

My solution works in and uses linear amount of memory

where is editorial??

Делаем сканлайн по значению, песни разбиваем на блоки длины . Каждые обновлений сохраним три величины: значение первого элемента в блоке, минимум на блоке, и плюс дополнительно не более обновлений, которые пришли в текущем блоке, но не покрывали полностью заданный блок. Используя эти значения ответим на запросы. Итог: 8мб памяти и примерно в два раза медленнее решения с деревом отрезков

Похоже авторы решили завалить это решение, поскольку оно слишком простое. У тебя 70MB чистое решение дало или хорошо нахаченное? У меня решение без хаков занимает около 300MB при n=200000, m=33000 (не очень понятно при каком m достигается наибольшее количество вершин, так что точно сказать не могу). Конечно на запросы максимума я вершины не создаю.

Why do you think so?

0 has no mod inverse.