gridnevvvit's blog

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

Hello!

Soon (on August 9 at 19:30 MSK) you are lucky to participate in Codeforces Round #195 for Div. 2 participants. Traditionally, Div. 1 participants can take part out of the competition.

Problems have been prepared by me. I want to thank Gerald Agapov (Gerald) for help in preparation of this round, Eugene Sobolev (Seyaua), Vitaly Aksenov (Aksenov239) and Sergey Sukhov (Serega) for testing of problems, Alexander Ignatyev (aiMR) for testing of problems and for translation of tutorial, Michael Mirzayanov (MikeMirzayanov) for marvelous Codeforces and Polygon systems, Mary Belova (Delinur) for translation of statements.

We wish everyone good luck and high rating!

UPD: English tutorial

UPD: Congratulations for winners:

  1. Triolossus_3
  2. WHITE2302
  3. PM2.5

Separately, I want to congratulate Egor Kulikov (Egor) — the only person who had passed the all problems!

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

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

how and when can I be sure that I am registered for the contest ??

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

    about 18 hours before the round , you can find the registration link , in contest page.

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

    Hi . first login then Go to the hereand see your name and all registerant or goto the here see your name and friend name if your name is be there your register . Excuse me for my bad writing .

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

The Div.1 participants will be rated???

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

i think this contest should be "Eid Special" :)

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

I hope a non-russian-speaking person had the chance to proofread the problem statements

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

Ans scoring system ???

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

Scoring system will be announced later

Later means after the contest ?

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

edited

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

The website is too busy... terrible T T

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

boring problem set, specially problem B :-| Really miss interesting problems on CF

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

For some reason when we have only div2 rounds they are much harder than when we have both div1 and div2 rounds.

I wonder why this is the case.

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

any further explanation for problem C ?? .. i think it's not clear atleast for me :D

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

dirty problemset :| [kaCf]

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

I enjoyed this problemset, though most people probably don't like tricky cases.

Edit : Express your opinion and get downvoted. Communism for the win.

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

Problems was bad! But Thanks for fast system testing!

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

    Your avarar shows typical Div2 participant's face after this round ended I guess :) Cool problems, but a bit harder, than Div2 used to be

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

How fast the system testing!!

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

What's the solution for problem C? Thanks.

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

    for every bit position (0 to 32), consider numbers in the array that have this bit set (= 1). Take bitwise and of all these numbers for each position i in [0,32), this takes O(32*n) time. Note that AND has "the more, the better" scenario, ie, for a particular v let set S be solution; if (v+1)th bit is set for a number N, then N \union S will also be a set with solution v. Using this, calculate above array. Now find maximum i 0<=i<32 such that the "bitwise and" calculated above has all bits 0 to i-1 unset (=0). This is the solution

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

    Make 30 buckets (vectors) and if a number from array has i-th bit turned on (0 <= i < 30) put the number in i-th bucket.

    After that for each bucket calculate the bit-wise and of all the numbers in that bucket and if that sum is divisible by 2^i output all the numbers in that bucket and the size of the bucket, of course choose i to be as high as possible.

    Edit: got ninja'd by the user above me :D

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

    same as c0d3junki3, but i use a builtin function named __builtin_ctz . It returns the number of trailing 0-bits in x, starting at the least significant bit position.(I think it's faster than %)

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

Wow system test is so fast now...I like it. Problems are great, a little bit too much math though. Have enjoyed it. Thanks to authors!

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

why this submission skipped???it's correct![submission:4249620] please help!

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

I think there is something wrong in the description of the problem C. I wonder how to understand this sentence in problem C: "If such number v doesn't exist (that is, for any non-negative integer v, number b1 and b2 and ... and bk is divisible by 2v without a remainder), " if v doesn't exit,number b1 and b2...and bk is divisible by 2^v should with a remainder,am I right?

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

    meaning if bitwise and is zero, then v can be as large as you want. In this case, answer is -1

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

    if b1&b2&...&bk == 0 it divides to all 2^v, and we don't have maximum v

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

    Really, all this sentence is saying is that the number (b1 and b2 and ... and bk) should not be 0. If it was 0, it would be divisibly by 2v for any non-negative integer v.

    It was hard to understand though. I wish they just said "(b1 and b2 and ... and bk) should not be 0".

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

why not make a scoring board for Div.2 only without the out of competition participants ? To know your real ranking during the contest

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

    you can unchecklist "show unofficial" :|

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

    In top right corner of scoreboard is checkbox "show unofficial". Just uncheck it and you've got it :)

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

    You can see the Div. 2 only scoreboard by unchecking the "show unofficial" checkbox in the top right corner

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

    Click that "show unofficial" checkbox (in particular, untick it).

    EDIT: TOO MANY SNIPES

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

Is there a problem with the contest list? round 196(div 1) is 4 days later than round 196(div 2)!

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

For problem A, if you see sample test 1, input: 10 5 output : 0 15 15 0 But how about 0 9 23 0 ? The conditions are still held, moreover its area is smaller. What would you say?

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

    Oh, it's my bad. I thought "isosceles" is right angle because it was written as "isosceles(<ABC is right)". Should have looked up.

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

    The triangle must be isosceles which means that the two sides are equal in length.

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

why this submission skipped???it's correct![submission:4249620] please help!during the contest this submission had accept!why now is skipped??:(

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

Whats wrong with this solution? C WA6

http://codeforces.com/contest/336/submission/4257324

actually my beauty is 29 :|

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

    I've got the same question. My solution write beauty 29 too.

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

    The beauty of your answer is 21 not 29, the remainder with 2^29 is not 0.

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

      I was thinking why they are telling their solution's beauty is 29 instead of 21!

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

    Note that if you claim the beauty to be 29, then the AND of all numbers you pick must be divisible by 229. In your case, the AND of all numbers you pick is actually 229 + 221, which means it's not evenly divisible by 229. (The actual beauty in this case is 21; 229 + 221 is divisible by 221 (giving a quotient of 28 + 20 = 257).)

    I suppose you misunderstand the problem.

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

    Did you find out what's wrong with that ur approach? Now even i'm curious..

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

If I registered and didn't attempt any problem, will my rating be calculated.??

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

ABCE's name is "Vasily the Bear .."
and D's name is "Bear Vasily"

What's the point?

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

    The problem title might be limited at either 35 or 36 characters; "Vasily the Bear" for D causes the problem title to go to 37 characters. (The next longest is E at 35 characters.)

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

      I'm not sure about what you say! For example problem 319C's name is "Kalila and Dimna in the Logging Industry" which has a length of 40!

      "Bear Vasily and Beautiful Strings" can change to "Vasily the Bear and Beautiful Strings" which has a length of 37. (37 < 40) ! Maybe it has another reason!

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

Can anyone tell me, why was this round JUST AND JUST geometry?!

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

Quick question...

On 336b, the one with the circles and the ant, I am getting a different answer when I run my code than what the tester is getting. I'm using python 2.7, and when I enter 2 2 for the second test, I get 5.41421356237 in my python interpreter, but the tester is getting 7.41421356237 when it runs my code. Does anyone know why this is happening? I did not import any external libraries and all my code is pretty standard...

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

    Even when computing manually (by hand, not by an interpreter), I got 7.414 as your output. Are you sure you didn't misread 5 as 7?

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

      Oh, whoops...I edited one file and submitted a different one xD Sorry about that

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

Why the rating not change?

sorry for my bad English

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

deleted. was about repeated topic

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

    The beauty of such sequence is -1 according to the problem statement

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

when will rating change?

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

codeforces is not bad

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

I think gridnevvvit doesn't want to write the editorial of this contest!

P.S: Ratings changed!!!

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

Problem D is quite nice.

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

Classic Contest

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

how to prove problem A in simple out 1 I think (0,10),(20,0) is more small than (0,15),(15,0)

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

My first time facing a floating point problem on codeforces. The custom test case was outputting -0.0000 for all my answers on g++ 4.7 using printf. What is the reason for this ?

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

    Can you show a testcase where it doesn't work?

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

      Sure. Here is the code : ( Problem C : http://codeforces.com/problemset/problem/336/B ) http://ideone.com/SxkStn Run it on any test case 2 2 or 1 1 The same code gave me AC on submitting using setprecision

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

        You're right, there seems to be something wrong with GCC on Codeforces: even the following program

        #include <cstdio>

using namespace std;

int main()
{
    printf("%Lf\n", 3.14L);
}

        outputs -30329013470001650000000000000000000000000000.000000 instead of the correct answer.

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

          I got wrong on Pretest 1 twice. So thankfully no negative points, but wasted 20 minutes to figure out was going on.

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

solve problem a in a few minutes, and try to understand other problems for about 2h...

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

Sorry but I really can't hold it anymore. With all respect the way the problems are written is not clear at all. Well not all of them but some.

→ Reply