izban's blog

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

Hello everybody!

Today, Codeforces Round #137 for the Second Division Participants will take place. As usual, all other interested persons can take part in it.

The problems have been developed by a group of authors from Vladivostok: Ilya Zban (izban), Alexey Evsyukov (aevsyukov), Zakhar Voit (zakharvoit).

Gerald Agapov (Gerald) has greatly contributed as well and we thank him for it. The translation of the problems has been done by Maria Belova (Delinur) — thanks to her! We are also grateful to Pavel Kunyavskiy (PavelKunyavskiy), who has help us in the preparation of the contest.

We hope you will have fun and like this round. The points distribution will be standard (500 — 1000 — 1500 — 2000 — 2500).

Good luck to everybody!

UPD: The start will be 15 minutes later due to technical reasons, we apologize.

UPD2: Congratulation to winners!

In second division:

1: zxl0714

2: resodo

3: mugurelionut

4: hmspmy077

5: CCC

6: white_rich_beautiful

7: loveSakura

8: gcwtft827

9: yuxingdubai

10: b821213

In first division:

1: navi

2: Shik

3: SteamTurbine

UPD3: The editorial is published.

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

Comments Comments (33)
| Write comment?
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I am a novice and competing first time on codeforces. Can you please guide me through the blueprints of competition process. Thanks for your help in advance!

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

 

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

thanks

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

Codeforces servers went owie. :(

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

Eat lunch as fast as you can... and wait 12minutes for contest start :D

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

What's the trouble before?

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

Can someone explain test 1 on div2 C problem? Why is it: 2 3 2 1 1 1 1 and not for example: 1 1 2 1

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

    Codeforces rules forbid asking about problems during the contest.

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

      It is related to the clarity of the test case , I think, but nvm :)

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

I can't understand problem C and D mean. :|

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

Could anyone give me an Idea for solving C without having to decompose all the values to its prime factors (this strategy gave me TLE)? Or is it mandatory to do that and my implemtation was simply too slow?

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

    Are You using Eratostenes sieve or naive approach?

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

When I finally did dare to lock my C, I found that I can hack 2 solutions with max tests, then the contest ended. Sigh. Seems courage is really important.

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

There was a slight error in the problem description. The "Input" says columns will be given first then the rows. However, the examples showed that this was not the case. Anyway, the round was good.

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

Very long systest.

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

    I feel there was not a need for so many test cases for Problem B. Perhaps that is why systests are slow.

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

      Yes it's very slow. Now it reach the first hour submission in one hour to.

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

Reds( http://www.codeforces.com/contest/222/submission/2109757 ) can also fail div-2's A. Well done problem setters! :)

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

Is there a particular reason why the two pointer solution gives TLE when using library sort in Java but gives AC when using library sort in C++? Is it Java I/O or the library sort? I see that uwi has an AC Java solution using radix sort, but I am yet to see an AC Java solution using Arrays.sort.

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

    google "java sort hack site:codeforces.com".
    in a nutshell:
    int[] a; Arrays.sort(a); // — N^2 operations
    Integer[] a; Arrays.sort(a); // — N Log N operations

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

      The root of this problem is that Java uses mergesort to sort Reference types and qsort to sort Basic types. So simple anti-qsort test can fail all your attempts when you sort int[] instead of Integer[]

      → Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it 
if (a >= 'A' && a <= 'Z') a -= 'A' + 26;

So, stupid of me! This cost me E. Wasted too much time on A, so didn't had time to debug :(. Anyway, I feel happy that my approach was correct.

It was a good problem set. Thanks!

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

I think the problems in this contest is so simple that too many people killed all the problems :(

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

Hi, I have a question on test 8 of Problem D. The test is : 10 5

3 1 1 2 1 3 1 1 2 3

2 1 3 2 1 3 3 3 3 1

If we sort the array we will get: 6 5 5 4 4 4 4 4 2 2 So isn't the worst place is 3 ? But the answer is 5, i don't get this.

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

    You arrange the resulting array in not optimal way.

    It's possible to do so: (3 + 3) (3 + 3) (3 + 2) (3 + 2) (3 + 2) ...

    and our guy has 5 points, so he's on the 5th place.

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

      Thank you a lot.

      My bad. I thought 1 column is the points of 1 person.

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

        In second example testcase from problem statement you could see that this is not true :P

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

user editorial for the round please?

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

Can someone please explain the correctness of C problem. Actually I understood the approach, but i am not able to figure out why it will work Thanks.

→ Reply