Блог пользователя gridnevvvit

Автор gridnevvvit, 11 лет назад, По-русски

Всем привет!

Скоро, 29 ноября в 19:30 MSK, состоится очередной Codeforces Round #216 для участников Div. 2. Как обычно, Div. 1 участники смогут поучаствовать в этом раунде вне конкурса.

Задачи были подготовлены группой авторов в составе: Гриднев Виталий (gridnevvvit), Лось Илья (IlyaLos).

Большое спасибо Гере Агапову (Gerald) и Сергею Сухову (Serega) за помощь в подготовке задач, Марии Беловой (Delinur) за переводы на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.

UPD1: Распределение баллов будет таким: 500, 1000, 1500, 2000, 2500.

UPD2: Это была опечатка с распределением, теперь все верно.

UPD Соревнование закончено, поздравляем победителей!

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

Удачи!

  • Проголосовать: нравится
  • +81
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Why this blog is not on the Home page ?

»
11 лет назад, # |
Rev. 3   Проголосовать: нравится -13 Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Всем Удачи!!))) GooD LucK

»
11 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

"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? :)

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

HF:)

»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

short statement hope .....

»
11 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +34 Проголосовать: не нравится

    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.

    • »
      »
      »
      11 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
11 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

How solve problem E?

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

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

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

any1 knows why i have skipped on all 3 tasks

»
11 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

Я бы хотела помогать переводить. На каких условиях это происходит и что я могу для этого сделать?

  • »
    »
    11 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +14 Проголосовать: не нравится

    Напиши Михаилу Мирзаянову или Геральду Агапову.

»
11 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

very very awful system test speed

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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!

»
11 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

What was special about test 14 in problem C ?

»
11 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Условие 4-ой задачи улыбнуло:)

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Бывали и позабавнее. На одном контесте была задача про раскрашивание яиц. Все фразы были специально так подобраны, чтобы у всех фантазия разыгралась :)

    Была и задача, в которой надо было вывести "I'm too stupid to solve this problem", если решения нет (а оно было всегда)

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    Это неловкое чувство, когда после контеста не помнишь ни одно из условий.

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится -6 Проголосовать: не нравится

Это нормально? 2 задача валилась на 4 тесте, сейчас посмотрел ошибку: wrong answer sum of scores of the team doesn't equal to 892330, 892248 попробовал свой код для входных данных на 4 тесте, посчитал сумму. Сумму выводит правильно. Спрашивается, каким образом тут вылезает эта ошибка.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    А, нет, нормально все, не тот код проверял :)

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Тогда может кто сказать, в чем принципиальная разница между этими двумя кодами:

      5306082

      5305733

      Вроде как они одинаковы, а ответы разные дают.

      • »
        »
        »
        »
        11 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        тест: 3 2 3 4 10 7 первое решение вернет ответ 3 3 3(7/2 +7/2!=7), что неверно, нужно 4 3 3

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Обьясните кто-нибудь идею решения задачи С. Спасибо.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Подкину идейку.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Я это читал. Я хотел бы услышать суть решения, а не сделай так, раскрась так и выйдет так.

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        А суть в том, что нужно найти все "самые нижние" проблемные дороги, такие, от которых если идти вниз по дереву, не встретишь больше проблемных. И в ответ записать нижнюю вершину каждого такого ребра. Это так, потому что если ниже какой-то проблемной дороги есть ещё одна проблемная дорога, то верхняя будет покрашена по пути из нижней. Посчитать же все такие "нижние" можно, например, как в разборе.

»
11 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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.

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
11 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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!

»
11 лет назад, # |
  Проголосовать: нравится +42 Проголосовать: не нравится

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
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

    • »
      »
      »
      11 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

      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 :)

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Good idea.

»
11 лет назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

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.

»
11 лет назад, # |
Rev. 3   Проголосовать: нравится +26 Проголосовать: не нравится

мне одному задача С напомнила цитату коммента с хабра?

"Alexey2005: ...Кстати, асфальта там тоже почти нет. Поэтому местные жители на выборах мэра всегда выбирают того, который, во-первых, живёт совсем не там, где предыдущий, и во-вторых, такого, чтобы жил как можно дальше от местной мэрии. Потому как первое (и обычно единственное), что делает новый мэр — прокладывает асфальт от своего дома до мэрии. Так-то вот постепенно и прирастает дорожная сеть."

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +41 Проголосовать: не нравится

    Задача была придумана как раз по мотивам этого коммента)

»
11 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    i dont know, that seems unfair to me

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

    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.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

многие ошиблись по поводу деления на ноль :))) я взломал 5 решении

»
11 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

First time top 5 :)

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Будет ли разбор задач?

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

are the tutorials posted ???