Hello Codeforces!

Soon you are lucky to participate in Codeforces Round #302, and I am writer of this contest.

I want to thank Max Akhmedov (Zlobober), Alexander Ignatyev (aiEZ), Danil Sagunov (danilka.pro) for help with preparation of this round, Maria Belova (Delinur) for translation of statements and Mike Mirzayanov (MikeMirzayanov) for marvelous Codeforces and Polygon systems.

Scoring will be next:

- Div1:
**500 — 1000 — 1750 — 1750 — 2500** - Div2:
**500 — 1000 — 1500 — 2000 — 2750**

Contest finished, congratulations to winners:

Div1:

Div2:

"you are lucky to participate in Codeforces Round #302" I think I am lucky to participate all Round :D

That's strange! Contests are starting later and later in my country (first 8:00 pm, then 8:30 and now 9:00!), but the time in Codeforces' contests page is the same! Do the time modes in countries change so frequently?!

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

Dress Colour Is Blue-Black

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

LoL~~~

Where are these coders ?! Just 2555 registrants for now ?!

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.

Yeah I didn't get one too.

One more time. A good round on codeforces good luck and have fun everyone!!!!! who do you think will win this round? someone in special ??

I hope a nice contest with interesting problems for all the participants.

hope problem A isn't going to be HACKY! :D

why minuses??

Hoping good results and high ratings... and a lot of hacks!!!

Happy New Year!

`I only say I must give up`

Are all samples included in the pretests or just the first one?

Edit: my comment is wrong.

You are wrong, it is our strict rule to always put samples as the prefix of pretests following in the same order.

Sorry... Don't know what made me understand samples as "All test cases"

Problem B confusing statement cause me a wrong submission. Should codeforces neglect the wrong submission before the announcement ?

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

existingcell 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

kconnected components, no matter which size they have.The description that you posted was absolutely correct and unambiguous, you should not have clarified or changed anything. The current description is wrong:

//start description

We will call a set of sand cells to be island if it is possible to get from each of them to each of them by moving only through sand cells and by moving from a cell only to a side-adjacent cell. The cells are called to be side-adjacent if they share a vertical or horizontal side. It is easy to see that islands do not share cells (otherwise they together form a bigger island).

//end description

Nothing in that description says that a proper subset of an island isn't be an island. Not only is it not "easy to see" that islands don't share cells, it's wrong: if they share cells, they form a bigger island, but they're still islands anyway.

That's what I mean by less formal. Of course you are right but the saddest part is that tens of questions per minute almost immediately disappeared when we rewritten the statement in such informal manner.

I don't understand. Is this an island?

It does not satisfy rule 3, you can still add some cells to the set. (Please correct me if I am wrong)

I understand that you just wanted to say "a smaller subset of cells of an island is not an island". But the definition is problematic here, because, unlike the usual graphs with nodes and edges, you have "sea cells" and "land cells" here.

The first clarification doesn't help too (it even reinforced the feeling that you have to add as many cell as possible.)

`The island is the maximal set of sand cells on existing picture`

`(meaning that you can add no new cell from the existing picture without`

Also an alternative way to clarify things is to add an extra sample that contradicts the belief.

You cannot add anything because adding an 'S' will not extend the set because it is not covered with sand.

I see. Thanks.

PlayTheGame is telling everything correctly above. Regarding the alternative way to clarify things: in this case I don't see how adding another sample could have saved the situation since the main confusion already happened because of the first sample test.

Thanks, I agree. I got confused too.

I think next time better avoid the terms set and connected component in Div 2 A, B as there are many contestants from middle school who never learned about sets, and some contestants are not familiar with graphs (in a problem which does not require knowledge in graphs).

They are grey, green and blue after all.

Thanks for the hard work and explaining to me.

What is the hack test of problem D in div1?? I think my solution is correct :(

You can let your code run this case:

200000

1 2 2 2 ... 2 2 2

My output for your test is : 543973825 87947641 543973825 543973825 543973825 ...

Is this correct?

A hack against division via multiplicative inverse: (ideone)

How to construct it:

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.

I constructed such test using binary representation of MOD: divide it by 2 while possible and add subtree with one node. when it becomes odd, subtract 1 and build new subtree with it

Thanks for the tip, that's a lot cleaner :) .

There is an easier way of getting it, as you can easily add +1, by adding one more edge. 1000000006=6+10^9=6+(1+3*3)^9

I am one of those, who was registered, but didn't participate, because.. there were no any strong ideas in any problem..

Imho, there should be at least one easy enough problem in Div.1 in order to have a more honest rating.

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

I don't think so: the naive solution, which I could generate, was O(n^4) and after optimization worked 5 secs at max test. I could not invent any O(n^3) approach during the whole round :)

So, you still think that you didn't participate because the problems were boing or because you get scared by the first problem, which, as far as I can see, you weren't able to do? N ^ 3 was the typical dp, and I heard that there is a solution in N ^ 2 too.

Because I could only solve A in N^4 and have not enough time to finish D.

D could be solve writing a very short code.You said in the above coment that the problems didn't have any strong ideas.I think that they were preety cool E seems awesome even tought I didn't solve it.I couldn't solve C and B was very interesting(In my opinion).You insulted the contest just because you couldn't solve A...

No, you get me wrong: the problems were interesting, but I could not find any solution of them, which i sure enough to code or submit.

Its a variant of knapsack with repetitions allowed.

you are lucky to participate in Codeforces Round #302 he said

Good luck and have fun he said

:(

Did better than usual, fun problems! Maybe I'll become Green again!

How to solve Div2 C Writing Code?

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

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

Problem B was quite confusing. Also the announcement just changed the problem. I think this round should not be rated

I guess almost all solutions will fail on testcase when divisibility by 10

^{9}+ 7 was involved. I thought that my code handled it correctly, but unfortunately not and I was hacked probably using such testcase.I was hacked also by such a testcase. How can we deal the problem when the number is divisible by 1000000007?

One way of doing it is keeping then number in form

a·(10^{9}+ 7)^{b}. When it is necessary to divide by 10^{9}+ 7 reduce b, otherwise multiply a by modular inverse.You can't do this in this manner.

Of course we can't keep

aexplicitly, because it will grow too large. We also can't keep just the remindera%10^{9}+ 7, because if you have some numberxin this representation then you don't know representation ofx+ 1.We can actually do it in this particular case. When we pass this value to a child of a vertex, all what we need to know is whether it is zero or not(modulo 10^9 + 7). If it is not zero(that is, b = 0), a mod 10^9 + 7 is obviously a correct value. If it zero(that is, b > 0), it is, again, correct, because it is 0 regardless of a. Put it another way, we never need to add one to a number in this representation.

How to do it, if is not possible to represent x + 1 using the x value of that representation?

Anybody else who got WA #11 on Div2 C?

I wrote (almost) correct algorithm for B and D, expecting it to pass. Then I tried to solve C for like 20mins and still have no idea how to solve it. So I decided to code whatever greedy & dp comes to mind (I first code some DP, which got WA5, so I added some greedy).

Now I failed B & D, but my C is correct.

So surprised...

What sort of greedy? I just used set cover.

Uhm, it's very complicated to describe in words, but I'll try.

So first, about the DP solution:

So I updated my DP, allowing adding single character at a time, using min(cost to change this character, cost to change all same characters),

which I think must still be wrong, and I think the correct thing to do here must be considering all subsets of S2.

If I'm reading your code right, when your DP updates mask | TWO(x) using a single character, mask | TWO(x) hasn't been processed yet, so it can add another single character when you get to that mask.

So your code actually

isconsidering all subsets, and it is actually the correct solution (iterating over all subsets would clearly TLE).But how can adding single element at a time like this be correct? In case I add 2 strings x and y with the same character c (at position i), the cost that I'm adding equal:

In case sum(a(z,i)) is smaller, I added a(y,i) twice.

In case sum(a(z,i)) is smaller, that means

`update(f[i][mask | maskSet[i][c]], t + costSet[i][c]);`

is strictly better than your single character update, so that doesn't matter.Thanks. I'm happy to see that my code is actually correct =)

i cant be happy anymin

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

You should not maximize the sizes of islands.That was after a lot of WAs. -_-

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

This is exactly what I asked as a question just before the first announcement.

O(NMB) is too slow for A Div1? I got TLE.

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

I changed your solution, now its get AC 11034034

long long -> int OK, fine, thanks...

Using mod2 can save you the copying part like http://codeforces.com/contest/544/submission/11036246

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

What was the approach to solve it?

dp[i][j][k] = No of ways for first i persons to write j lines and causing k bugs

dp[i][j][k] = dp[i-1][j][k] + dp[i][j-1][k-a[i]]

I got a memory limit exceeded with that approach. Allocated an array of 500 * 500 * 500.

Notice that dp[i] depends on only dp[i-1]. Hence you can do the dp with just M*B memory. See my accepted solution for more details.

Yeah, that's the catch! Thanks :)

can you explain more about "Notice that dp[i] depends on only dp[i-1]" please?

Well if we are in state (

i,j,k) we can either transition to (i+ 1,j,k) or (i,j+ 1,k+a[i]). So the calculation of a state (x+ 1) only depends onxand nothing else.Thank you

The time limit for A is way too tight.

I suppose there was a 500 500 500 case in the pretest. Branch predictor and memory causes it to TLE in system tests.

When I resubmit the same code, case 7's time increased from 25xx ms to 29xx ms.

UPD: gridnevvvit has replied that using

`long long`

instead of`int`

causes solution to TLE. I strongly believe that the jury should NOT test for such differences.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.

Thanks for the idea. Next time I won't make it power of 2.

I never thought that I could get TLE due to branch predictor behavior / cache collision.

Why exactly does this happen?

Because cache internally uses a hash function based on several least significant bits of memory block address. When the second dimension is a power of two, accessing a[i+1][j] will most likely result in a hash collision that will slow down everything.

More info here: http://danluu.com/3c-conflict/

How is Div2 D / Div1 B supposed to be solved?

Rule 3 : Ignore rule 3 XD

Does anyone know when the ratings will be updated?

Worst feeling of missing Rank-1 just because you kept the array size in Problem A one less than what is required. Silly mistakes!! :\ :(

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.com/contest/544/submission/11023029

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

I wonder if BFS was an overkill for DIV 2 Probelm B? Also tricky testcase. Watch out for number of island =0! eg-> 1 0. I messed up due to this. COrrected it now to get AC :/

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.

Problem — A

Why my Solution skipped? — 11027863

because your solution like another solution :D

What is the complexity of this solution 11033699 for Div.1D ?

O(n^{2}).In case 39, the calls calc(0, false), calc(1, true), calc(2, true), ..., do

O(n) operations each.It looks that case 39 is my hack :-)

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

Is it written anywhere that today's contests are unrated? seems something is missing in the highlighted area which exists in other rated contests!

UPD:Actually I wanted to tell about rating changes, but some reason the picture had not shown. However, Ratings are updated and all confusion went out of the air!Highlighted area like?

Hello mihir, Sorry, for some reason, the attached picture was not shown. The picture link is here. But now it is showing and all things are going like other usual rounds. Thanks. :)

I wish I had fixed my hacked B 30 seconds earlier......

What was the official solution of E. My O(S(32 + N / 32)) passed with 3.7 seconds and 54MB.

My solution works in and uses linear amount of memory

Then why 7 seconds time limit? Is there a huge constant or something?

My java solution works in about 4 or 5 seconds

where is editorial??

Can someone explain why my Solution on Div2 B got a TimeLimit in the first Testcase? On my Computer i got an solution instantly and uploaded it twice in the contest

http://codeforces.com/contest/544/submission/11031166

I noticed that i have an WA as well, but there wasn't enough time to fix both...

/**/

What an awful contest?!

Why do you think so?

I didn't receive email notification for this round :(

My code (for Div1 D) is getting WA. I couldn't find it. What do you think is my mistake?

Submission: 11058128

0 has no mod inverse.

So, it's not possible to do it by dividing, I can't fix it, right?

I think so. In my solution, I do extra preprocessing during build to get the result by only multiplication. Edit: You can use mod inverse to solve this problem too, but you should treat the cases containing "dividing 0" specially. This can be done by recording more data in your "build" function.

Why the memory limit is 64MB, not 256MB, in Div.1 E?