Polichka's blog

Codeforces Round #108 (Div. 2)
By Polichka, 12 years ago, translation, In English

Good day!

We have got over two weeks of our new term. And we are glad to see you on our regular rating Codeforces round for Div.2 participants. And all who wants can take part in this competition.

This round has been prepared by a team of three people: Gerald, NALP and Polichka. We are grateful for their help in preparation and translation to Artem Rakhov(RAD), Mike Mirzayanov (MikeMirzayanov) and Maria Belova(Delinur).

Today Peter entangled in the tables:-( And you can help him! It's rather easy!

Score distribution: 500-1000-1500-2500-2500

Easy solutions and high rating to all!

UPD:

Thanks all for participation!

You can read the tutorial on this link: Tutorial.

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

Comments Comments (35)
| Write comment?
»
12 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Good luck to everybody :)

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

if it is Easy for all , it is not easy for anybody ! :P

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

good luck

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

I hope C won't be tricky!

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

It was my first contest , I really enjoyed it :)

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

To the team of three writers: you guys are really productive. Thank you all.

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

I think that C was easier than B :-/

I realized too late, that result for B is bigger than long (I'm dumb, message "Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specificator." in statement didn't help me too) :-/

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

    I think they both are easy.

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

      I'm not telling that they are not easy, but I think that it is more difficult to implement B than C — I used one loop and 7 conditions in B and just 4 loops without any condition in C (I do not like line metric).

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

        "easy-ness" is a relative term btw.

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

          That's why I wrote "I think...", it's just my opinion. Opinion of problem writers is clearly different. I just wanted to let them and others to know, nothing more, nothing less...

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

        but still u need some combinatorics to solve C

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

          I don't think so, or maybe it's so trivial that I do not consider it as combinatorics, because it is such straight...

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

    Yeah, of course C was easier than B, that's why some people submited it before B.
    I failed here, because when I saw C first time, I didn't see it's ease.
    So I submit it after debugging B and lost loads of points :(

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

      Same here. I saw that coders are submiting C, but when I read the statement, I didn't see the solution in the moment.

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

    500-1000-1000-2500-2500 would be better.

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

I made an unsuccessful hack to this code thanks to lack of syntax highlighter in the hacking window. :(

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

    Yeah, it really sucks that there is no syntax highlighting while hacking...

    On the other hand in last TC SRM my unseccessful challenge was because I missed that small L is same as 1 (and there is highlighting, but not for this case) :-/

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

The problem D only 5 AC during this 2 hours! :O

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

    I think, maybe it's not difficult to solve the problem D , but it's hard to understand it's meaning. ( Maybe I have a big problem with English — -.)

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

Problem D: I thought it to solve like this, is it correct:

Find x number of potential vertical lines, and y number of horizontal lines. if x > 4 or y > 4 , return "NO"; else proceed as: take C(x,2) * C(y,2) possible combinations of those lines and test whether these lines can be part of frames in O(n^2) .

Overall complexity : C(4,2) * C(4,2) * O(n^2) .

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

    The number of the potential vertical (or horizontal) lines can be more than 4, even if the answer is "YES".
    For example: ('x' instead of '#' because of Markdown)

    5 5
    xxxxx
    xxxxx
    xx.xx
    xxxxx
    xxxxx

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

      Here only 4 potentials are there. (Those having atleast 3 consecutive X)

      May be my algo. is wrong, can there be more than 4 potential lines?

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

    what about that:
    ****
    ****
    ****
    ****
    ****
    ****
    answer is "yes"

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

      Oh, yeah. My algo is wrong.

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

      In this case we can check both rows and columns, if answer is yes then I think either rows or columns will have at most 4 lines containing potential sides, so that it can be rotated 90 degrees and solved in the same way.

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

    Test for two rectangles could be done in O(n+m) with preprocessing O(n*m), since two following conditions seems to be enough:
    1. all of points in rectangles are in our table [O(n+m)];
    2. perimeter of rectangles' union equals to amount of #s in table [O(1)].

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

I guess because of my English, I got extremely confused with this line "You wonder how many different names Vasya can write instead of name number 1" (Problem C). What the problem writer meant with "instead of name number 1"?

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

    On the place of the first name.

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

    He meant: After Vasya performs all his operations, how many possible strings can be at the place where the first name was initially.

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

When will the safe mode end?!

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

    Btw, it's going continiously since R107...

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

      And safe mode still did not ended completely: for example, country rating and contests participated by particular coder still show "Do not panic" page...

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

This contest have 3 easy problem and 2 difficult problem. This contest doesn't have any medium problem. I think it's very bad.

→ Reply