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

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

Всем привет!

Это 150й (юбилейный?) раунд на Codeforces. Для 1го и 2го дивизионов.

Раунд готовили: Ripatti , Gerald , Delinur .

Enjoy!

UPD. Разбалловка стандартная: 500-1000-1500-2000-2500 для обоих дивизионов.

UPD2. Контест окончен. Читеры удалены. Рейтинги пересчитаны.

Победители в дивизионе 1:
1. scottai1
2. vepifanov
3. rng_58
4. Egor
5. Komaki

Победители дивизиона 2:
1. mochavic
2. hanamaki
3. mfv
4. shef_2318
5. TangJie

Всем спасибо за участие. Приходите еще.

Разбор задач будет завтра.

UPD3. Разбор

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

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

юбилейный говоришь, 150 футболок будет?

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

I hope problems will be as good as contest number :)

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

What a short post! Great!!

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

Why is 150 a good number?

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

    There's no accounting for taste.

    But probably beause we still think of numbers decimally.

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

ill hope it will be good contest like last

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

Краткость — сестра таланта. =)

P.S. А разбалловка будет стандартная или динамическая?

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

I wanna pass a vector as a reference to a function. can anybody help me??? template code or helping links pls.

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

Will the problems be sorted by order of difficulty? What is the scoring system gonna be??

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

..... contest number is good, lets try to make our rating good :)

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

all you guys be cool like me !!

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

My contribution is positive. What did I do? o.O

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

Good luck & have fun !

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

Amazing anniversary :-ss I have never a problems like Div 1.A Amazing or bitwise

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

Seriously, why? Not enough servers? 'Shut down all the servers' button was clicked by an accident? Slow code? Strange Java behavior? 'The load was so high that we were not ready for it?'

It looks very strange and unnaturaly for me; CF rounds are not beta for a long time and there are still problems sometimes.

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

mnlfrnnds04 had made many hacks and only one person has been hacked! Guys, how do you like this?

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

    I think it's another user of himself or it's his friend because both users are from Turkey and have the same picture.

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

mnlfrnnds04 has 24 hacks so far, all of them on the same person. With 1 correct task he is third. Seems legit...

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

А вернут 50 баллов за неверную отправку по задаче A div. 2, когда условия были некорректны?

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

what kind of sorcery is this :) 44 hacks, same user, same country, same profile :)

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

PRETEST 4 WAS A TRICKY ONE FOR THE PROBLEM HYDRA............... ALMOST EVERYONE HAS A WRONG ON IT........

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

Could anyone explain me, what is the statement of the problem B? Let's assume two middle vertexes as S and T. I can't understand, could neighbours of vertex S be connected to vertex T. I thought, no. And, server problems...((

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

    tree with h+t+2 nodes

    I think no except you don't select the neighbour nodes for both S and T

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

Will this compitition be rated?The Net was error for too much time.

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

    But they increased the time to overcome that .. So I suppose it is alright

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

      I'm disagree.

      Imagine the following situation (it's from real contest): I opened one problem, solved it and then server gone away. I have to wait and can neither send my solution (and I lose some points), nor read the next problem (here I lose contest's time).

      Then imagine one (I know such persons too) who opens all problems in the beginning of contest. So, he have 5 additional minutes over me. Not fair, huh?

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

        You also had the opportunity to open all 5 problems. So it is fair to everyone.

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

        Well, I think it is reasonable precaution to open all tasks when contest starts

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

        My situation was better: I waited for five minutes to send problem, and than waited 5 more without any other opened problem. Than I got WA. Nice:)

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

        I'm just the first situation,and I solve the second problem but I can't submit at once,when I submit it,it's already 20 minutes later.

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

        Imagine if you want to ask a clarification (my case). Let's hope this doesn't keep happening in future rounds.

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

Как понять эти 44 взлома mnlfrnnds04???

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

    понять, простить...

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

    Мне кажется немного странным, что он 44 раза взломал одного и того же человека. ^_^)

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

      Только мне кажется странным, что он взломал 44 раза одного и того же человека, у которого , более того, совпадает с ним аватарка

      http://codeforces.net/profile/mnlfrnnds04

      http://codeforces.net/profile/hgrsm07

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

        Ок, в следующий раз, если ты взломаешь меня, я поставлю твою аватарку и тебя забанят!!! зловещий смех

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

        Странным? Это чуть более, чем очевидно. А про него уже сообщений 30 написали точно.

        Абсолютно очевидно, что писать такое кол-во раз неправильное решение, которое проходит все претесты и взломы, невозможно, если каждый раз не добавлять 1-2 случая (собственно, взломы), для чего необходимо знать эти взломы.

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

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

      Ага, а ещё более странно, что у них с этим человеком идентичные решения задач.

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

      Его программа -- правильное решение + неправильный вывод на определенном тесте! Капитан очевидность как бы намекает...

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

mnlfrnnds04 this person should be banned, he is first in div-2 illegally.

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

автором предполагалось такое классное решение, удивительно, что пробежка по сету заходит?

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

    Сервера codeforces настолько мощные, что...

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

    Размер сета не более 20. У меня такое же.

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

      хм, на первый взгляд кажется подозрительно неверным

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

        При росте числа биты строго увеличиваются. Значит не более 20 различных? Что из этого подозрительно?

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

И никто задачи не обсуждает :( Мне понравились A и B, хотя по-моему они одинаковой сложности. А вот задачу типа C я уже где-то видел, поэтому она мне не очень понравилась, вот.

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

    В B у меня зашла проверка каждого ребра и хеш-таблица для соседних. По-моему она легче, чем А. Как ее решать?

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

congratulations mnlfrnnds04!! The successful of a lot of challenges is the very great achievement!!!

...Oops...? Something seems to be wrong... (o_O)

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

The expected score for this match was 2158. :D

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

std::set — зло! Товарищи фиолетовые, я снова с вами!

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

in Problem E, In pretest, My program prints "NO" in test case 1, but my program prints right answer in custom test. Please check my program..

-------------------------------- Sorry, my program was wrong.

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

I got this verdict in problem D(case 21) — "wrong output format Unexpected end of file — int32 expected". Does this mean I'm giving too much out-put? Submission link

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

    No, it means exactly the reverse — you gave checker not enough output — it tries to read int32, but gets EOF.

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

    It mean that you miss one (or more) integer

    UPD: I was too late(

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

can tell how made problem B???

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

    Note that there are not a lot of undoubtly lucky number upto 10^9 . So generate all of them

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

    I did a backtracking solution. You try all the pairs of (x,y), after that you produce all the possible numbers with a backtracking. This gives approximately O( 10^2*(2^10-2) ).

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

Div1 for first time .. so happy :D

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

Доказательство хорошей сложности алгоритма в B, который перебирает рёбра, и находит пересечение множеств соседей двух вершин.

Допустим, что юзаем хэш-таблицы с операцией за O(1), а при нахождении пересечения ищем элементы меньшего множества в таблице большего множества. Доказываем, что работает за , аналогично доказательству алгоритма, который считает треугольники в графе (насколько помню, KADR рассказывал в Петрозаводске). Пусть вершина тяжёлая, если у неё больше соседей.

  1. Сколько раз мы будем искать одну тяжёлую вершину в хэш-таблицах в сумме? Не более, чем m раз (количество соседей). А т.к. тяжёлых вершин не больше , то все тяжёлые вершины мы ищем раз.
  2. Сколько раз мы будем искать одну лёгкую вершину? Не более, чем . Лёгких вершин может быть m, поэтому все лёгкие вершины в таблицах мы ищем тоже за .
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Это круто, только в конкретной задаче доказательство гораздо проще есть. При добавлении условия, что у одной вершины рассматриваемого ребра >= h ребер, а у другой >= t, все получается хорошо. Если условие не выполняется мы не рассматриваем ребро, иначе делаем так. Если количество ребер от двух вершин > 2 * (h + t), очевидно, что решение найдется (и "тяжелую" проверку сделаем только один раз). Если же ребер меньше, то сложность алгоритма O (m * (h + t)).

    P. S. помню я сколько потребовалось нам попыток, чтобы в Петрозаводске загнать O(m * sqrt(m))... Это плохая сложность (например, со стандартной Java хеш-таблицей она не заходила).

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

      Там был какой-то хак, что никаких таблиц не надо было использовать. Мы потом в дорешке сдали...

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

        Ну понятно — храним массив, в котором для каждой вершины помечаем последнюю из рассматриваемых вершин, с которой у нее есть ребро. Тогда действительно получаются все операции за О(1).

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

Can anyone tell me why this brute force solution is able to pass Problem A (Div 1)? Solution I am not able to prove its worst case complexity. Perhaps, it is because of the pigeonhole principle. Is it possible that the tests were weak?

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

    Your code is correct and runs in O(N*20) for the worst case. When inner loop breaks with (temp==cur[j]) condition, it means that, a[j] and a[i] has some bit b set in their binary representation, but none of the a[j+1],....,a[i-1] has this bit set. If we contribute (i-j) to b(or to one of the bits which has above property), we see that for each 0<=bit<=20 we will do at most O(N) operations.Therefore complexity is O(N*20).

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

Was getting a TLE on Test 47 for problem B, and after the contest changing the loop from 0 -> N — 1 to N — 1 -> 0 reduced the time from hitting the TL on 2000ms to 281ms!

I still can't see any sense in making the TL that strict on the problem.

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

Объясните условие B, пожалуйста. Лишние ребра мешают? Могут ли центральные вершины быть соединены не со своими листами? Последнее не видно из семплов :(

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

    Разобрался. Как и думал, на контесте написал не ту задачу. Пожалуйста, делайте условия понятнее. Я уже раз третий за месяц не могу понять условие во время контеста.

    P.s. Позиция "сам дурак" конечно восхитительна, но все же прошу поддержки.)

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

Как решать C, D, E?

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

    C: будем рассматривать не все координаты подряд, а только интересные. Координата интересная, если чувак останавливался прямо в ней, или в соседней. (Например если чувак двигался из (0, 0) в (10, 0), а затем в (10, 5), то интересные Х координаты будут -1, 0, 1, 9, 10, 11, интересные Y координаты -1, 0, 1, 4, 5, 6). Промасштабируем поле, теперь одна клетка нового поля — какой то прямоугольник на старом поле, причем этот прямоугольник окажется либо целиком заражён, либо нет. Размеры нового поля теперь достаточно маленькие, и можно запускать тупой dfs или bfs из какой нибудь граничной точки. Таким образом мы помечаем всё что сожрут жуки. Остается только пробежаться по нашему полю, найти всё не помеченное, и вспомнить, что наша клетка это какой то прямоугольник в старых координатах, и добавить соответствующую площадь к ответу.

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

      Сходу непонятно, как зная интересные координаты масштабировать поле, то есть сжимать прямоугольники в точки.

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

        посмотрим на передвижения чувака и запомним в каких точках он бывал, соответственно теперь мы знаем интересные координаты. Теперь отсортим их отдельно по Х и по Y, выкинем повторяющиеся. Теперь как узнать по интересной координате xs, xn в новых координатах? Очень просто — xn такое что X[xn] == xs; где Х — массив всех интересных координат. Т.е. одним бинарным поиском по старой координате находим новую. Теперь повторим движения чувака, делая тоже самое, но заменяя его реальные координаты на сжатые. Решим исходную задачу, заведя матрицу всего поля, и думая что у чувака грядка размером 3000х3000 и он ни когда не доходит до её границ. А когда будем считать ответ вспомним, что размер клетки (i, j) на поле не 1x1, а axb, где a = X[i+1] — X[i], b = Y[j+1] — Y[j]; как то так

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

hi, i'm confused that why the java function BigInteger.isProbablePrime always lead to Runtime Error? It's right in some OJ, but always RE in others like CF. Can you explain it? Thank you!

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

    It has been discussed in Russian somewhere. The problem occurs because of security policies: BigInteger.isProbablePrime() uses SecureRandom which could be prohibited

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

Как скоро будет разбор?

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

When we can have the tutorial??

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

The post said that day (contest day) "Editorial will be tomorrow." actually it didn't happened. But we can't say the are saying lies. because today it says "Editorial will be tomorrow.".. so logically they can never post a editorial :D but we can hope they will. (just joking) i hope this "tomorrow" will have an upper bound. :D

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

    It seems editorial is ready, but it still isn't available in english, but you can see it in russian.

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

So how do u solve The Brand New Function

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

What's the idea of div2_C?

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

It would be great if we have a tutorial soon :) :). waiting for the tutorial :) :) :) thanks.

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

tourist ты пьян иди домой)

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

Why my code get TLE on DIV2_D?2602812,I need your help!

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

What a coincidence. All the codes of MDantas and Manoel look identical.