gridnevvvit's blog

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

Hello!

A few hours later, on November 29th at 19:30 MSK, you are lucky to participate in Codeforces Round #216 for Div. 2 participants. Traditionally, Div. 1 participants can take part out of the competition.

Problems have been prepared by: Gridnev Vitaliy (gridnevvvit) and Los Ilya (IlyaLos).

We want to thank Gerald Agapov (Gerald) and Sergey Sukhov (Serega) for help in preparation of this round, Mary Belova (Delinur) for translation of statements, Michael Mirzayanov (MikeMirzayanov) for marvelous Codeforces and Polygon systems.

UPD1: Scoring will be next: 500, 1000, 1500, 2000, 2500.

UPD2: It was a misprint with scoring system, now it is correct.

UPD Contest finished, congratulations to winners!

  1. Dshovn
  2. WhitedarkWalker
  3. hexor
  4. Pandii
  5. Ronnoc_2

Good Luck!

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

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

Friday. And again, and again, and again. No problem, just discoursing :)

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

    Hope This Round to be a bridge to be a Div1 for First Time ,Hope That!

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

    What do you mean by again? there hasn't been a contest on Friday since 25th of October! :D

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

      I think what he means is there is no contest especially for DIV.1. :D

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

GL && HF!!! I hope this contest will be good for everyone!

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

Why this blog is not on the Home page ?

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

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

An empty contests list !! I hate that ...

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

    Then do something about it! Prepare a contest! No-one gets better from your trash. Sorry.

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

"Scoring will be next: 500, 1000, 1500, 2500, 2500."

So another Div.2-Only contest where maximum 10 people will solve D and/or E? :)

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

    misprint :)
    Scoring will be next: 500, 1000, 1500, 2000, 2500.

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

HF:)

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

I thought there are more than 3000 programmers taking part in this contest~Nice weekend~~&&HF

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

short statement hope .....

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

Why isn't runtime error considered as a successfull hack?

I tried and it says unsuccesfull hacking attempt

however it should have shown runtime error according to my machine

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

    A program can behave differently on different machines. (On yours, it crashes, but it works fine here.) This happens sometimes, and that's why it's risky to hack on RE or TLE.

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

      There were some sure cases of division by zero. During hack people got caught, no problem. How the passed the final test. In which machine on earth found the result of division by zero successfully!!! please, Read this thread. http://codeforces.net/blog/entry/9771

      And very carefully look at the case 19 in the test!!! how can that pass and generate correct output by dividing by zero !!!!

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

    Depends on the reason of runtime error. If it's accessing an out-of-bounds element of array, the behaviour is indeed undefined. But if it's division by zero, the hack should be successful. This time, I hacked 4 people on this, and they used different programming languages: GNU C++, MS C++ and Python 2.

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

      Actually it was modulus with 0

      something like 0%0.

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

How solve problem E?

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

Finally a contest with corner cases that are not covered in the pretests!

I made 10 successful hacks with the case: 5 5 1 1000 100 100

wohoooooooooooooo :D

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

    I've made 6 successful hacks with 3 3 1 3 9 9, but firstly found, that my oun programm can't solve it :D After blocking the solution.. It was offensively..

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

    I made 11 successful hacks with the case : 5 5 1 3 5 5
    I made 11th hack in last minute :)

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

When I wanted to hack some solution, I found something really interesting...
In GNU C++, this code doesn't get RE

cout << 0/0 << endl;

It works well and makes answer equal 0
and also this code


int a;
cin >> a;
cout << 0/a << endl;

if you get a = 0, the output is 0
but this code will get RE

int a;
cin >> a;
cout << a/0 << endl;

why??? Is this a bug or...

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

    I did the same thing.

    unsuccesful halking attempt.

    on users with (sall-sk)%(n-k).

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

    Maybe compiler optimization of the form "0/anything==0"?

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

any1 knows why i have skipped on all 3 tasks

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

What is the approach for solving problem D and E? Thanks in advance

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

very very awful system test speed

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

After many rounds.....finally a TRICKY contest!

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

    Two consecutive tricky contests , last was one also full of hacks and failed system test.

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

what's the algorithm for problem E? i tried to use Fenwick Tree(Binary Indexed Tree) but i couldn't figure out how to use it 8-|. i solved problem just for 1 point... but for couple of points :-?? can anybody give hints? it would be great!

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

What was special about test 14 in problem C ?

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

Test 32 on D is the killer of reds (me too :D), what could it be about...

My solution of E is as follows: sort the intervals by li; sort the points of all queries together and for each of them, remember all queries that include it. Now, process the points in that order; in a BIT, remember how many intervals whhich start before that point and end at position i after that point (remembering their endpoints in a set also helps remove those that end before it). Check all queries asking for the current point, and add to their answers the intervals which won't be counted for any later point of that query — that is, end before the next point of it (or infinity, if that point is the query's last), which is just a sum from the BIT. The query's next point can be found just by remembering a pointer to it and increasing it when necessary.

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

    Here's the simplified 32 test on D.

    3 2

    100 0 50

    Solutions that fail on 32 test do not find the way to kill all fools and output 4 while the correct answer is 5. The main idea behind this test is that if one alive fool remains in front of a suffix of alive fools with a gap between them and he kills the first fool from suffix and dies himself at the same time, it may produce one more answer.

    Here it looks like that:

    round 1: The second fool is shot. The other two are alive.

    round 2: Remaining fools shoot each other simultaneously.

    Solutions that do not consider this case get WA 32.

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

      I see, thanks. It really took a lot of casework, this one...

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

I liked the problems. Thanks for the contest. :) Even though I think D might be a bit hard, I have no clue on how to solve it. Hopefully, the tutorial will be out soon!

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

Problems statistics (official round participants only):

Participants count: 2021
A | first: 00:02 | sent/passed/hacked: 1963/1774/26
B | first: 00:08 | sent/passed/hacked: 1665/816/239
C | first: 00:11 | sent/passed/hacked: 819/442/1
D | first: 00:33 | sent/passed/hacked: 45/15/0
E | first: 00:44 | sent/passed/hacked: 87/11/0
→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    can u share with us how u got this data? it might help during future contests. thanks!

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

      I've parsed contest standings pages content and aggregated data from cells using javascript. It's draft, and I plan to extend the script in order to provide more interesting information in a pleasant view :)

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

    Good idea.

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

Standings :

1- Dshovn : Registered 11 Hours ago

2- WhitedarkWalker : Registered 15 Hours ago

5- Ronnoc_2 : Registered 3 Days ago

6- LinXinya : Registered 8 Hours ago

7- marcorezieho : Registered 10 Hours ago

All those newcomers are pretty good i think.

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

Shouldn't it be allowed to lock unsolved problems in order to hack other guys' wrong solutions?

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

    i dont know, that seems unfair to me

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

      You may not know how to solve the problem in an acceptable time and memory bound, but you can still have corner cases that submitter may have not handle.

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

    I don't think that's a good idea, some guy can just create new account, lock, look at other guy solution, and re-code it for his main account and you know what happen next. So I think it will increase the number of cheater since it's really easy to cheat.

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

      Good point, the fact that hacks can be made during coding time is the problem, indeed.

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

I solved A in 8 minutes, but was stuck with B because of a bug, which I manage to find only after an hour. :(

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

First time top 5 :)

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

are the tutorials posted ???

→ Reply