Hello!

Soon, on January 24th at 19:30 MSK, you are lucky to participate in Codeforces Round #226 for Div. 2 participants. Traditionally, Div. 1 participants can take part out of the competition.

Problems have been prepared by: Aleksey Chesnokov (CleRIC), Kirill Butin (KirillB) and Ivan Popovich (NVAL). This is the first round prepared by us and we hope that everything will be OK.

During the round you will be helping to the hero of the problems — usual bear.

We want to thank Gerald, Delinur, Aksenov239 and MikeMirzayanov for the system.

Scoring: 500-1000-1500-2000-2500.

Good Luck!

UPD: Round rescheduled for 5 minutes later

UPD: Editorial

UPD: We hope that you liked round.

Congratulations to winners:

November 29th?? When you click the link, it shows the correct time.

Thanks:)

Fianally a new contest author for Div 2! Sounds good...

I think this is contes — very simple contest ! :)

New contest author, I am look forward this contest :D

It is so relaxing to be a div1 and participate at Div.2 Friday evening...Thanks for the round!

good luck and have fun.

hope all get positive ratings :)

Only div2...But It doesn't matter.Just enjoy this contest!

Finally can join a contest without any pressure...

whats meant by "Div. 1 participants can take part out of the competition"?

it means that they can compete but it will be unofficial for them

so these div1 participants wont be given rankings along with the div2 participants, right?

yep

Its going to be great to solve as much as i can lol

I want to rating under color of my eyes... (red)

You say this in all contests?! :D

i think i've heard this earlier

Take a look at this.

I was always curious why not just to add 2 more problems and make Div1+Div2 round instead of just Div2 one. It seems to me that the level of Div1 problems is not always very high — for example, take a look at D and E from previous round 225. They're just medium, not hard and still were not solved by a lot of contestants. I mean, one doesn't need to overestimate level of Div1 participants but it would me much cooler to have more frequent Div1 rounds.

Big Like

Just like topcoder.

why +5 min ?

All right, I was late, but now I'm here. Start!

(just a joke):)Don't worry Lasha !!!

5 minutes delay?

Why!?!

maybe he forgot to write the last problem! :D

Solution for B with n^2 complexity passed my hacking test :'(

B is supposed to be solved in . ofcourse it will pass the hack!!

There is an O(N) solution also.

can u plz share the idea with us?

For each occurrence of "bear", you have to count the number of valid indices to the left of this, and to the right. It will contribute countLeft*countRight number of tuples. For each "bear", left count will be the number of characters from 'b' of previous "bear" to this 'b'.Right count will be number of characters from this 'r' to the end of string.

You can check my submission(5788550) for details.

thanks a lot! :)

EDIT: i wonder how your submission and my submission (5791720) both pass with a time of

`78 ms`

:DI got TLE at first with O(n²), then got AC with O(n) :(

Man, just a piece of advice for you. On Codeforces if you wanna hack somebody on time limit, you gotta be sure, that his/her program will perform at least 10^9 operations on your test. Because the servers are really fast. On this contest I tried to hack a program, which performed in the worst case about 4*10^8 operations, but the result was just 1668 ms.

Couldnt submit my code in last 20 seconds :-@

Again loss of rating :-(

at last minute codeforces was unavailable, So I couldn't submit my soln.Did someonne else have this problem?

Yeah same thing happened here!!!

Couldn't submit a problem in the last two minutes because of constantly getting the message "Codeforces is temporary unavailable "

I really hate this!!!

Me too -_- .. spent 1.5 hours for 1 problem , couldn't submit it.. what a joke ..

I complained about this. Answer: "No comments"

Hello,

I need guidance on problem B.

Can it be solved by suffix array?

I thought of using suffix array + lcp to get all substrings only containing bear and count those.. Maybe even suffix tree was better choice but couldnt implement it yet.. was that the way to go?

nope, solution is very simple. For each "bear" count positions on left from which we can start, it will be (i — prev 'bear' position), because we shouldnt use the positions already used by previous bear and positions on right on which we can end, it will be = n — i — 3. then increment ans to rightcount*leftcount, and change last bear index.

sorry for bad explanation. if you disunderstand then look to others code

I've BruteForced it , and it passed

Edit : TLE in testcase 9

Codeforces is temporary unavailable :(:( It cost me hack in the last minute :(

Whats the idea of problem C ,i got TLE.

you need to use sieve of Eratosthenes in liner time

I got AC with simple sieve of Eratosthenes.

I liked problems very much,exceptionally problem C,thanks CleRIC for great contest ;)

I wasted 10 minutes to write a generator. It only gives the error that first line should not be empty.

http://codeforces.com/contest/385/hacks/91276/test

Can anybody help me why is this happening ??

For problem D constraint n <= 20 suggested that something like bitmask dp could be done. But I can not find any reason why not to use just all the flash lights instead of a subset of them ?

Not sure but I think this is because the order of lights matters.

I got the idea, infact it is true that all the lights can be used. But the bitmask can be used to extend intermediate result dp (mask) to dp (newmask) easily using geometric manipulations.

My hack #91170 was marked as unsuccessful. But the details contains "Time: 2152" and this problem (Problem C) has 2 seconds time limit. Doesn't 2152 > 2000?

in the last two contests, i saw problems with time limit of

`2 seconds`

, and submissions that took`2011 ms`

got accepted.wait 2-3 mins, i will post the links.

EDIT: sorry for the delay, but finally found them! 5722902 5706257

I'll handle it. Already has found the issue. Thanks.

There may be something wrong.

I found a successful submission for problem C which takes 2245ms to execute. 5796553

And I hacked a code which causes TLE, according to verdict, it ran 2000ms.

To keep contests fair, this problem should be deeply discussed.

What a "runtime error" contest!

How solve problem E?

What was the idea behind D? (n<=20 sugests that the problem is NP for bigger values of n). Was is something like meet in the middle?

More like travelling salesman dp. For every subset of lamps store the farthest point that can be reached using them. When adding a lamp to a subset it is easy to see, how much it extends the reach.

I just solved D, the dp[] size is (1<<n), than every step only turn on one unused light and update dp[cur|(1<<k)] (k is the unused light)

For the first time, my rating is going to go above 1500 (hopefully) :)

Any idea why http://codeforces.com/contest/385/submission/5798194 gives a run time error. But uncommenting the commented lines doesnt give. I cant see what fails.

yes, i have the same mistake, the thingis that s.size() is an unsigned int... and when it is 1 and substract 3, it is 4294967294, because all the expresion is indeed unsigned int, and then when you access to the element 4294967294 of the string it give you RE, because it only has 1 element.

ohh interesting. yeah this makes sense. thanks !

I think there is nothing wrong on your code. but the compiler make infinte loop but I don't know why.

because s.length() is unsigned int

and by negating 3 from it, it will give another unsigned int, so

s.length()-3

will be some non-negative number

Rank

2:SquirrelDetectedRegistered: 4 hours ago(Before Contest)Rank

3:MahooshojoNHBRegistered: 7 weeks ago(Before Contest)Rank

4:Dong5kRegistered: 4 hours ago(Before Contest)Rank

6:UniRegistered: 4 hours ago(Before Contest)Rank

7:FastYesRegistered: 3 hours ago(Before Contest)Rank

9:akatsukiLHRegistered: 9 hours ago(Before Contest)The

NEWbrains...!Can Someone Explain problem E in details (i.e : How the matrix was built?? )

Well, instead of the first 4 zeros in the last column, they all should be 2. I got a WA during the contest because of this stupid bug. Note that you need to decrease sX, sY by one to turn the coordinates to 0-index instead of 1-indexed to make it easier, consequently, you will need to add 2 to K in each step.

Why they first 4 zeros need to be 2 ? What is the logic behind this?? I don't understand.. And when

sXorsYis greeter thanNwe need to mod them byN... how to applymod Noperation in matrix multiplication?Well, we will be working with 0-indexed coordinates, ok? Now,

dxis updated as followsdx = dx + sx + syBut since we are working with 0-indexed coordinates then this should be

dx = dx + sx + syWhy? Assume sx == 1 && sy == 3 in 1-indexed mode, now when we turn it to 0-indexed then we havesx== 0 &&sy== 2, sodxshould equalsx + sy + 2Now for

modding by Npart, you can mod every thing byNin every step of your calculations, because the only operations you do are addition and multiplication, and the mod can be distributed over these operations normallyMy solution of problem C fails on pretest 7. I just used a BIT with sieve of Eratosthenes. I can't find the mistake. Could someone help me find it? Thanks.

just skimmed.. i guess you should run another loop inside this loop for multiples of i when notp[i]=false

`for(;i<mx;i++) if(!notp[i]) update(i,cnt[i]);`

Didn't notice that. Thanx.

In recent contest, there are Div1 users that register a new account to participate officially!!

Why? What's the difference?

Then Div2 users should compete with some Div1 users, too!

where can i find test file for a particular case that my solution fails

Can anyone tell me why the first code got runtime error while the second got accepted ??? 1. http://codeforces.com/contest/385/submission/5791451 2. http://codeforces.com/contest/385/submission/5798703

s.size() returns an unsigned number. And the trick of unsigned numbers that if it overflows, or goes negative, it takes by modulo 2 ^ 32 (int) or 2 ^ 64 (long long). So, if the length of the string is less than 3, it takes by modulo and becomes something lika 2 ^ 32 — l. Just output s.size() — 3 and you will see yourself.

http://codeforces.ru/contest/385/submission/5789899 http://codeforces.ru/contest/385/submission/5798663

I have this error too. it is because, str.size() — 3 in for — it is size_t type

try to

`cout << s.size() - 3;`

when`s = "a";`

!`s.size()`

is`unsigned int`

and`(unsigned int - int) -> unsigned int`

! it cant be negative!thnx a lot M.Mahdi, i see this issue before but couldn't understand the reason :)

Kept getting Runtime error on 385B - Bear and Strings Spent much time to figure out it..

just use

`i+1<v.size()`

instead of`i<v.size()-1`

Your first contest very good held.Thanks for this interesting contest :) CleRIC KirillB NVAL...!!!

The problem D is about Greedy and Geometry? I have no idea about it! Who can help me ?Thanks.

Bitmasks,DP,Geometry

I think it's useless to me. . . .

Problem Ci got wa on test 6i cannot understand the what kind of test case it is ..please explain any body.. here is my code:..