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

Автор Egor, 15 лет назад, По-русски
Предлагаю здесь обсуждать TopCoder SRM 472 который пройдет 5 июня в 22:00
  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

15 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Главное чтобы было что обсуждать. Что-то в последнее время матчи частенько срываются...
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В последнее время - не слишком удачно выступаю на СРМах. В итоге случайно ушел во второй дивизион. Надо будет попытаться его выиграть!

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

15 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Всем удачи во втором раунде субботнего развлечения
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Надеюсь, после второй части развлечения мне будет веселее, чем после первой.
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Ужс... сколько нечестных людей.. несколько сабмит за 499, 249.

15 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Ну сегодня прямо не контест, а рай для челенджа

  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Даааа... это было классно.. я жаль сразу не догадался, что люди так лагают. У меня в комнате 10 решений по второй упало :)  я только два успел зачелленджить. Тест 8 оказался супер пупер :)
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как решать третью второй див? у меня есть только решение w*h*s
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    switch(n & 5)
            {
                case 0: return "Hanako";
                case 1: return "Taro";
                case 2: return "Hanako";
                case 3: return "Taro";
                case 4: return "Taro";
            }
  • 15 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    можно ее решить за O(max(h,w)*s)

    Для каждой координаты по оси X и Y отдельно посчитаем вероятность попадания в нее за D ходов (ходим только по этой оси). Пусть они будут dpX[x][d] и dpY[y][d].

    Теперь, пусть мы сделали A шагов по X, s-A по Y. Вероятность что мы на доске - (dpX[1][A]+...+dpX[h][A])*(dpY[1][s-A]+...+dpY[w][s-A]). Осталось перебрать по всем A и все сложить.
    • 15 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Похоже на правду. Спасибо, большое!
    • 15 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Осталось, ага. Там дальше самое интересное.
      Перебирать-то надо с весом , и возникают проблемы с точностью.
      Можно считать   динамикой.
      Но тут возникают проблемы с памятью, так что в динамике нужно хранить только два ряда таблицы.
      Перегробили, на мой взгляд.
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Идея была такая. За n*m можно посчитать сколько раз будем из клетки ходить. (k-(abs(xi-x) + abs(yi-y)) + 1)/2 вроде. Тогда ответ - число плохих ходов (из боковых) /  число всех. Но не успел :(
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    В итоге её никто не решил. :)
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Вы лучше напишите какой рост. У меня +75. С 90м местом.
    Контест действительно сказочный был, только написал его плохо.
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Мда, контест был явно не для меня. 500-ку и 1000-ку - никаких идей не было. Точнее были, но с Тайм-лимитом.

Так и не понял почему работает n%5 в 500-ке. Хоть 150 очков на челленже заработал.

  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Потому что нужно тупо закодить банальную динамку и посмотреть закономерность.. я ещё для пущей уверенности проверил для n<10000.
    • 15 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я после сабмита проверил на всех числа до 100 миллионов :-)
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ну это легко элементом 4 можно сгенерировать группу по модулю 5 в ней всего два элемента 1 и 4. Теперь возьмем наш паттерн 0 1 0 1 1 по понятно что из 0 мы можем приди либо в 5-ый элемент паттерна либо во 2-ой. Т.е. по теории игр получаем там проигрышные позиции. Ну и аналогично для выйгрышных.
    • 15 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      из 0 мы можем приди либо в 5-ый элемент паттерна либо во 2-ой
      из первого 0 мы можем приди либо в 5-ый элемент паттерна либо во 2-ой
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Можно доказать из соображений делимости.  Все переходы на +-1 по модулю 5.

    Если остаток 0 то нам его всегда смогут вернуть. Если остаток 2 то всегда смогут вернуть кроме случая что осталось 1. В таком случае есть переход в 0 который тоже проигрышен.  Из 4 и 1 всегда есть переход в 0 а из 3 в 2.

    Таким образом остатки 1,3,4 выигрышны а 0,2 проигрышен.
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Вот динамка (сразу с проверкой):

    int a[10000],b[5];
    b[0]=2;
    b[1]=1;
    b[2]=2;
    b[3]=1;
    b[4]=1;
    a[0]=2;
    for (int i=1;i<10000;i++){
    a[i]=2;
    for (int j=1;j<=i;j*=4){
    if (a[i-j]==2){
    a[i]=1;
    break;
    }
    }
    if (a[i]!=b[i%5]){
    cout<<i<<endl;
    }
    }

15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Точно тестирование затягивается...
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
System tests for this SRM will be delayed a bit while we try to resolve a system issue.
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Может кто-нибудь рассказать, как решать div1 500?
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Разбиваем на простые циклы. Для простого цикла - динамика, у меня была динамика от (число j, сколько мы имеем в последовательности чисел j, какой стороной карточка j, j - 1, какой стороной карточка 0, n - 1). Мне еще потом, правда, понадобилось почему то вычесть q! (q - число элементов цикла)
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Ох, как бы Div II 250я у меня не упала... Написал перебор. :D Жуть...
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Не упала. А у меня на компе в студии не выполнялась на макстесте.
15 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Клево, что в первом дивизионе единственный чувак, сдавший и вторую и третью не сдал первую :о)
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да... это жесть.. сделать единственным две задаче в первом диве и не сделать такую простую задачу.
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У него просто минуты три на неё оставалось, он открыл её последней.
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Третью див 2 никто не сделал :)
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Эх. Я хотел вернуться в Див-1 красиво, заняв место минимум в первой десятке. Настраивался на этот СРМ как на последний в жизни.

В итоге еле заполз с рейтингом 1205, благодаря халявным челленжам :)

15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Наконец-то в первом диве! После 13-го контеста. Всё-таки не зря моя команда называется TEAM13 :)
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Блин, куда-то не туда комменты идут сегодня...
Вы лучше напишите какой рост. У меня +75. С 90м местом.
Контест действительно сказочный был, только написал его плохо.
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
+211..
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
+67

Блин, когда пористость не нужна, занимаю 15-е место, когда нужна, не могу в топ500 пройти :о(
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Видимо дело в психологическом настрое. Я, например, когда на результат не зацикливаюсь, получается лучше. Более расковано пишется ) Хотя тут нужна золотая середина. Без настроя на результат писать тоже плохо )
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Есть у меня один друг... он в 1C еле-еле вышел из отбора.. 900 с мелочью место. На 2-ом у него 93 место. (это ещё при условии что были ещё крутые из 1A и 1B)
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
И обновление результатов затягивается.
Интересно, это у них какие-то внутренние проблемы или они решают что делать с читерами из Индии?
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Хм... никто не знает.. почему  у меня был рейт после этого срм стал 1248... а щас зашёл, а там уже 1247 ?

Может ещё у кого так?

  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У меня повышение/понижение рейтинга на один пункт через неделю после СРМа бывало не раз. Я думаю, что это связано с дисквалификацией читеров.