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

Автор deinier, 12 лет назад, По-английски

Hi everybody:

Tomorrow will be this round in TopCoder. Here, I give you the link: http://community.topcoder.com/tc?module=MatchDetails&rd=15170. Have a nice contest and enjoy the EURO final game if you like football.

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

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

1.5 hours remaining!

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

Egor , Что за магию ты написал в 1000? Я не увидел никакого смысла в решении для M=1, но на маленьких оно сходится с тем что я считаю руками.

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

    Конкретно в m = 1 — посмотрим, с чем соединена особая вершина. Либо эти 2 соединены — тогда оставшееся связный граф на n-1 вершине с k-2 ребрами. Либо не соединены — тогда соединим их и оставшееся будет связным графом с n-1 вершиной и k-1 ребром. Ну и в любом таком графе это можно навесить на любое ребро — отсюда множитель

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

"However, there is an exception to the second rule: King Dengklek is also allowed to use the label 0. Moreover, he may even use this label multiple times."

my medium fell because of my inattention

actually, I see no reason in such kind of restrictions

they don't influence for difficulty of a problem

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

    I like inattented people just like you 'cos I challenge them. Two times.

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

    This restriction is present because my intended solution is in O(N^4). However, finally we decided to allow O(N^5) solutions as well.

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

Ну почему эти тупые буржуи не сделали так, чтобы можно было сабмитить без нажатия на Compile... Вновь теряю задачу из-за какой-то фигни (в данном случае не хватило пары секунд). Или Alex_KPR прав насчет того, что я неудачник?

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

да чзх, как можно было засрать 250 и сдать 500

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

Тупая бага с ресабмитом и прощай топ-3...

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

Russian Comment

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

Из-за чего у многих 450-ка слетела? Неужели из-за дробного сравнения?

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

    На том что можно нули не заменять на числа.

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

      А у меня по сравнению даблов...добавил eps, прошла.

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

        И прошлый и этот раз тривиальная 500 (450) летит из-за EPS у меня. Очень жаль, что задачу делают сложной только за счет хитрых случаев/+-EPS в решении.

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

    Ещё можно допустить много "гениальных" ошибок...

    У меня был булевский массив ok[], в котором ok[i] = true, если мы можем собрать такое множество чисел, что ровно в i исходах выигрываем (считалось это всё корректно трёхмерной динамикой). Я бежал от середины этого массива (размера l2) одновременно влево и вправо. На каждой итерации я сначала проверял позицию, на которую указывает левый указатель, затем -- позицию, на которую указывает правый. Как только какой-то из указателей стоял на позиции, в которой ok[i] = true, я возвращал ответ i / l2. Казалось бы, всё верно... но нет: решение "упало" на системных тестах из-за того, что я левый указатель двигал вправо, а правый -- влево (поэтому, например, вместо 0, 4 я мог вывести 0, 6)... Заменив L++, R-- на L--, R++, сразу же сдал в дорешку.

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

"Какая-же у меня тупая ошибка в 450!" — одновременно подумала половина участников SRM (включая меня).

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

    А что за она?

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

      Ошибка? Если вкратце, то отсутствие строчки RR[0] = 0, из-за чего неверно передавалось ДП.

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

      Лично я написал вот такую тупость:

      for (int i = 1; i < len; i++) {
      	count[i - 1] = secondDie[i] - secondDie[i - 1] - 1;
      	if (firstDie[i] > secondDie[i - 1] && firstDie[i] < secondDie[i]) {
      		count[i - 1]--;
      	}
      }
      

      Надо было так:

      for (int i = 1; i < len; i++) {
      	count[i - 1] = secondDie[i] - secondDie[i - 1] - 1;
      	for (int j = 0; j < len; j++) {
      		if (firstDie[j] > secondDie[i - 1] && firstDie[j] < secondDie[i]) {
      			count[i - 1]--;
      		}
      	}
      }
      

      Хотя бы не так обидно, что не успел заслать на контесте.

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

        Ты ноешь больше, чем я. Хватит уже.

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

          В данном посте совсем не нытье, а просто демонстрация того, как можно было тупо ошибиться в сегодняшней 450-ке.

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

Screencast: http://youtu.be/QKuMGhPHqOI?hd=1. Just several seconds short of working solution for 1000 :(

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

Что с статистикой на тс?

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

Как решать div2 hard?

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

    +1 уже несколько раз с такими задачами сталкивался, а решать так и не научился (только DFS TLовский могу сделать).