CleRIC's blog

Codeforces Round #226 (Div. 2)
By CleRIC, 11 years ago, translation, In English

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:

  1. cptbtptp

  2. SquirrelDetected

  3. MahooshojoNHB

  4. Dong5k

  5. yada

  • Vote: I like it
  • +180
  • Vote: I do not like it

Comments Comments (87)
| Write comment?
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it -24 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +34 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck and have fun.

hope all get positive ratings :)

→ Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Finally can join a contest without any pressure...

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it -20 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +38 Vote: I do not like it

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.

→ Reply
»
11 years ago, # |
  Vote: I like it -17 Vote: I do not like it

why +5 min ?

→ Reply
»
11 years ago, # |
  Vote: I like it -12 Vote: I do not like it

5 minutes delay?
Why!?!

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    maybe he forgot to write the last problem! :D

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +13 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      There is an O(N) solution also.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        can u plz share the idea with us?

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it +9 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
            ← Rev. 3   Vote: I like it +3 Vote: I do not like it

            thanks a lot! :)

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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              11 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

              → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Couldnt submit my code in last 20 seconds :-@
Again loss of rating :-(

→ Reply
»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

I really hate this!!!

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I complained about this. Answer: "No comments"

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Whats the idea of problem C ,i got TLE.

→ Reply
»
11 years ago, # |
  Vote: I like it +27 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

Can anybody help me why is this happening ??

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
11 years ago, # |
  Vote: I like it +36 Vote: I do not like it

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?

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    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

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

What a "runtime error" contest!

→ Reply
»
11 years ago, # |
  Vote: I like it +4 Vote: I do not like it

How solve problem E?

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 4   Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it

    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

    → Reply
»
11 years ago, # |
← Rev. 13   Vote: I like it +97 Vote: I do not like it

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...!

→ Reply
»
11 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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
→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Well, we will be working with 0-indexed coordinates, ok? Now, dx is updated as follows dx = dx + sx + sy

        But 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 + 2

        Now 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

        → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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]);

    → Reply
»
11 years ago, # |
  Vote: I like it +30 Vote: I do not like it

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!

→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply