### CleRIC's blog

By CleRIC, 6 years ago, translation, ,

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:

• +180

 » 6 years ago, # |   +3 November 29th?? When you click the link, it shows the correct time.
•  » » 6 years ago, # ^ |   0 Thanks:)
 » 6 years ago, # |   +4 Fianally a new contest author for Div 2! Sounds good...
 » 6 years ago, # |   -24 I think this is contes — very simple contest ! :)
 » 6 years ago, # |   +6 New contest author, I am look forward this contest :D
 » 6 years ago, # |   +34 It is so relaxing to be a div1 and participate at Div.2 Friday evening...Thanks for the round!
 » 6 years ago, # |   0 good luck and have fun.hope all get positive ratings :)
 » 6 years ago, # |   +1 Only div2...But It doesn't matter.Just enjoy this contest!
 » 6 years ago, # |   +6 Finally can join a contest without any pressure...
 » 6 years ago, # |   0 whats meant by "Div. 1 participants can take part out of the competition"?
•  » » 6 years ago, # ^ |   0 it means that they can compete but it will be unofficial for them
•  » » » 6 years ago, # ^ |   0 so these div1 participants wont be given rankings along with the div2 participants, right?
•  » » » » 6 years ago, # ^ |   0 yep
 » 6 years ago, # |   0 Its going to be great to solve as much as i can lol
 » 6 years ago, # |   -20 I want to rating under color of my eyes... (red)
•  » » 6 years ago, # ^ |   +13 You say this in all contests?! :D
•  » » 6 years ago, # ^ |   +16 i think i've heard this earlier
•  » » » 6 years ago, # ^ |   +9 Take a look at this.
 » 6 years ago, # |   +38 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.
•  » » 6 years ago, # ^ |   0 Big Like
•  » » 6 years ago, # ^ |   0 Just like topcoder.
 » 6 years ago, # |   -17 why +5 min ?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +26 All right, I was late, but now I'm here. Start! (just a joke) :)
•  » » 6 years ago, # ^ |   +2 Don't worry Lasha !!!
 » 6 years ago, # |   -12 5 minutes delay? Why!?!
•  » » 6 years ago, # ^ |   +19 maybe he forgot to write the last problem! :D
 » 6 years ago, # |   0 Solution for B with n^2 complexity passed my hacking test :'(
•  » » 6 years ago, # ^ | ← Rev. 2 →   +13 B is supposed to be solved in . ofcourse it will pass the hack!!
•  » » » 6 years ago, # ^ |   +23 There is an O(N) solution also.
•  » » » » 6 years ago, # ^ |   +3 can u plz share the idea with us?
•  » » » » » 6 years ago, # ^ |   +9 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.
•  » » » » » » 6 years ago, # ^ | ← Rev. 3 →   +3 thanks a lot! :)EDIT: i wonder how your submission and my submission (5791720) both pass with a time of 78 ms :D
•  » » » » » » » 6 years ago, # ^ |   0 I got TLE at first with O(n²), then got AC with O(n) :(
•  » » 6 years ago, # ^ | ← Rev. 2 →   +9 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.
 » 6 years ago, # |   0 Couldnt submit my code in last 20 seconds :-@ Again loss of rating :-(
 » 6 years ago, # |   +2 at last minute codeforces was unavailable, So I couldn't submit my soln.Did someonne else have this problem?
•  » » 6 years ago, # ^ |   0 Yeah same thing happened here!!!
 » 6 years ago, # |   +2 Couldn't submit a problem in the last two minutes because of constantly getting the message "Codeforces is temporary unavailable "I really hate this!!!
•  » » 6 years ago, # ^ |   0 Me too -_- .. spent 1.5 hours for 1 problem , couldn't submit it.. what a joke ..
 » 6 years ago, # |   0 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?
•  » » 6 years ago, # ^ |   0 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
•  » » » 6 years ago, # ^ | ← Rev. 5 →   0 I've BruteForced it , and it passedEdit : TLE in testcase 9
 » 6 years ago, # |   +1 Codeforces is temporary unavailable :(:( It cost me hack in the last minute :(
 » 6 years ago, # |   0 Whats the idea of problem C ,i got TLE.
•  » » 6 years ago, # ^ |   0 you need to use sieve of Eratosthenes in liner time
•  » » » 6 years ago, # ^ |   +14 I got AC with simple sieve of Eratosthenes.
 » 6 years ago, # |   +27 I liked problems very much,exceptionally problem C,thanks CleRIC for great contest ;)
 » 6 years ago, # |   0 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/testCan anybody help me why is this happening ??
 » 6 years ago, # |   0 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 ?
•  » » 6 years ago, # ^ |   0 Not sure but I think this is because the order of lights matters.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 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.
 » 6 years ago, # |   +36 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?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +4 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
•  » » 6 years ago, # ^ |   +12 I'll handle it. Already has found the issue. Thanks.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +1 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.
 » 6 years ago, # |   +5 What a "runtime error" contest!
 » 6 years ago, # |   +4 How solve problem E?
 » 6 years ago, # |   0 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?
•  » » 6 years ago, # ^ |   0 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.
•  » » 6 years ago, # ^ |   0 I just solved D, the dp[] size is (1<
 » 6 years ago, # |   +5 For the first time, my rating is going to go above 1500 (hopefully) :)
 » 6 years ago, # |   0 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.
•  » » 6 years ago, # ^ | ← Rev. 4 →   +3 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.
•  » » » 6 years ago, # ^ |   0 ohh interesting. yeah this makes sense. thanks !
•  » » 6 years ago, # ^ |   0 I think there is nothing wrong on your code. but the compiler make infinte loop but I don't know why.
•  » » 6 years ago, # ^ | ← Rev. 3 →   +8 because s.length() is unsigned intand by negating 3 from it, it will give another unsigned int, sos.length()-3 will be some non-negative number
 » 6 years ago, # | ← Rev. 13 →   +97 Rank 2:SquirrelDetected Registered: 4 hours ago(Before Contest) Rank 3:MahooshojoNHB Registered: 7 weeks ago(Before Contest) Rank 4:Dong5k Registered: 4 hours ago(Before Contest) Rank 6:Uni Registered: 4 hours ago(Before Contest) Rank 7:FastYes Registered: 3 hours ago(Before Contest) Rank 9:akatsukiLH Registered: 9 hours ago(Before Contest) The NEW brains...!
 » 6 years ago, # |   +4 Can Someone Explain problem E in details (i.e : How the matrix was built?? ) // So far I go... | 1 0 1 0 1 0 | | sx | | 0 1 0 1 1 0 | | sy | | 1 1 1 0 1 0 | * | dx | | 1 1 0 1 1 0 | | dy | | 0 0 0 0 1 1 | | M | M= Number of moves so far | 0 0 0 0 0 1 | | 1 | 1= Constant term to increase M 
•  » » 6 years ago, # ^ |   0 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.
•  » » » 6 years ago, # ^ |   0 Why they first 4 zeros need to be 2 ? What is the logic behind this?? I don't understand.. And when sX or sY is greeter than N we need to mod them by N ... how to apply mod N operation in matrix multiplication?
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Well, we will be working with 0-indexed coordinates, ok? Now, dx is updated as follows dx = dx + sx + syBut since we are working with 0-indexed coordinates then this should be dx = dx + sx + sy Why? Assume sx == 1 && sy == 3 in 1-indexed mode, now when we turn it to 0-indexed then we have sx == 0 && sy == 2, so dx should equal sx + sy + 2Now for modding by N part, you can mod every thing by N in every step of your calculations, because the only operations you do are addition and multiplication, and the mod can be distributed over these operations normally
 » 6 years ago, # |   0 My 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.
•  » » 6 years ago, # ^ |   0 just skimmed.. i guess you should run another loop inside this loop for multiples of i when notp[i]=falsefor(;i
•  » » » 6 years ago, # ^ |   0 Didn't notice that. Thanx.
 » 6 years ago, # |   +30 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!
 » 6 years ago, # |   +3 where can i find test file for a particular case that my solution fails
 » 6 years ago, # |   0 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
•  » » 6 years ago, # ^ |   0 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.
•  » » 6 years ago, # ^ |   0 I have this error too. it is because, str.size() — 3 in for — it is size_t type
•  » » 6 years ago, # ^ |   +4 try to cout << s.size() - 3; when s = "a";! s.size() is unsigned int and (unsigned int - int) -> unsigned int! it cant be negative!
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +1 thnx a lot M.Mahdi, i see this issue before but couldn't understand the reason :)
 » 6 years ago, # | ← Rev. 4 →   0 Kept getting Runtime error on 385B - Медведь и строки Spent much time to figure out it..
•  » » 6 years ago, # ^ |   +1 just use i+1
 » 6 years ago, # |   +10 Your first contest very good held.Thanks for this interesting contest :) CleRIC KirillB NVAL...!!!
 » 6 years ago, # |   0 The problem D is about Greedy and Geometry? I have no idea about it! Who can help me ?Thanks.
•  » » 6 years ago, # ^ |   0 Bitmasks,DP,Geometry
•  » » » 6 years ago, # ^ |   +6 I think it's useless to me. . . .
 » 5 years ago, # |   0 Problem C i got wa on test 6 i cannot understand the what kind of test case it is ..please explain any body.. here is my code:..