TopCoder SRM 472 - Codeforces

14 лет назад, # ^ |

Вот это и обсуждать :)

→ Ответить

14 лет назад, # |

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

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

→ Ответить

14 лет назад, # ^ |

Аналогичная проблема

→ Ответить

Egor	14 лет назад, # \| +3 Всем удачи во втором раунде субботнего развлечения → Ответить

Fcdkbear

14 лет назад, # ^ |

Надеюсь, после второй части развлечения мне будет веселее, чем после первой.

→ Ответить

14 лет назад, # |

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

→ Ответить

maslowmw

14 лет назад, # ^ |

Почему же? сегодня же задача на 600
Или ты во 2м?

→ Ответить

14 лет назад, # ^ |

Во втором

→ Ответить

14 лет назад, # ^ |

Я во втором. Замечу, что многие из таких сабмитивших из Индии.

→ Ответить

14 лет назад, # ^ |

Ага :) Кажись умнее всех :)

→ Ответить

14 лет назад, # ^ |

Что-то они долго не начинают тестировать...
Или не обновляют результаты в таблице.

→ Ответить

L.I.S.

14 лет назад, # |

Ну сегодня прямо не контест, а рай для челенджа

→ Ответить

14 лет назад, # ^ |

Даааа... это было классно.. я жаль сразу не догадался, что люди так лагают. У меня в комнате 10 решений по второй упало :) я только два успел зачелленджить. Тест 8 оказался супер пупер :)

→ Ответить

14 лет назад, # |

Как решать третью второй див? у меня есть только решение w*h*s

→ Ответить

slalex

14 лет назад, # ^ |

switch(n & 5)
       {
           case 0: return "Hanako";
           case 1: return "Taro";
           case 2: return "Hanako";
           case 3: return "Taro";
           case 4: return "Taro";
       }

→ Ответить

14 лет назад, # ^ |

Внимание. Третью :)

→ Ответить

slalex

14 лет назад, # ^ |

аааа)))) К третей подход пока не известен.... ((( Сорри, за флуд.....

→ Ответить

Ruslan

14 лет назад, # ^ |

У меня есть подозрение, что такое решение можно зачелленджить тестом n = 5.

→ Ответить

slalex

14 лет назад, # ^ |

switch(n % 5) ... опечаточка..... ХД

→ Ответить

Ripatti

14 лет назад, # ^ |

можно ее решить за 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 и все сложить.

→ Ответить

14 лет назад, # ^ |

Похоже на правду. Спасибо, большое!

→ Ответить

fetetriste

14 лет назад, # ^ |

Осталось, ага. Там дальше самое интересное.
Перебирать-то надо с весом $\text{[math]}$ , и возникают проблемы с точностью.
Можно считать $\text{[math]}$ динамикой.
Но тут возникают проблемы с памятью, так что в динамике нужно хранить только два ряда таблицы.
Перегробили, на мой взгляд.

→ Ответить

fetetriste

14 лет назад, # ^ |

т.е. $\text{[math]}$ , конечно

→ Ответить

Ripatti

14 лет назад, # ^ |

Да, именно коэффициенты C_s^A / 2^s я и забыл.

→ Ответить

Artishok

14 лет назад, # ^ |

Идея была такая. За n*m можно посчитать сколько раз будем из клетки ходить. (k-(abs(xi-x) + abs(yi-y)) + 1)/2 вроде. Тогда ответ - число плохих ходов (из боковых) / число всех. Но не успел :(

→ Ответить

14 лет назад, # ^ |

Что то мне кажется не то что-то.

→ Ответить

14 лет назад, # ^ |

В итоге её никто не решил. :)

→ Ответить

14 лет назад, # ^ |

Вы лучше напишите какой рост. У меня +75. С 90м местом.
Контест действительно сказочный был, только написал его плохо.

→ Ответить

14 лет назад, # |

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

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

→ Ответить

14 лет назад, # ^ |

Потому что нужно тупо закодить банальную динамку и посмотреть закономерность.. я ещё для пущей уверенности проверил для n<10000.

→ Ответить

Fcdkbear

14 лет назад, # ^ |

Я после сабмита проверил на всех числа до 100 миллионов :-)

→ Ответить

L.I.S.

14 лет назад, # ^ |

Ну это легко элементом 4 можно сгенерировать группу по модулю 5 в ней всего два элемента 1 и 4. Теперь возьмем наш паттерн 0 1 0 1 1 по понятно что из 0 мы можем приди либо в 5-ый элемент паттерна либо во 2-ой. Т.е. по теории игр получаем там проигрышные позиции. Ну и аналогично для выйгрышных.

→ Ответить

L.I.S.

14 лет назад, # ^ |

~~из 0 мы можем приди либо в 5-ый элемент паттерна либо во 2-ой~~

из первого 0 мы можем приди либо в 5-ый элемент паттерна либо во 2-ой

→ Ответить

PavelKunyavskiy

14 лет назад, # ^ |

Можно доказать из соображений делимости. Все переходы на +-1 по модулю 5.

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

Таким образом остатки 1,3,4 выигрышны а 0,2 проигрышен.

→ Ответить

14 лет назад, # ^ |

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

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;
}
}

→ Ответить

14 лет назад, # |

Точно тестирование затягивается...

→ Ответить

14 лет назад, # |

System tests for this SRM will be delayed a bit while we try to resolve a system issue.

→ Ответить

mastersobg

14 лет назад, # |

Может кто-нибудь рассказать, как решать div1 500?

→ Ответить

Egor

14 лет назад, # ^ |

Разбиваем на простые циклы. Для простого цикла - динамика, у меня была динамика от (число j, сколько мы имеем в последовательности чисел j, какой стороной карточка j, j - 1, какой стороной карточка 0, n - 1). Мне еще потом, правда, понадобилось почему то вычесть q! (q - число элементов цикла)

→ Ответить

14 лет назад, # |

Ох, как бы Div II 250я у меня не упала... Написал перебор. :D Жуть...

→ Ответить

14 лет назад, # ^ |

Не упала. А у меня на компе в студии не выполнялась на макстесте.

→ Ответить

AlexSkidanov

14 лет назад, # |

Клево, что в первом дивизионе единственный чувак, сдавший и вторую и третью не сдал первую :о)

→ Ответить

14 лет назад, # ^ |

Да... это жесть.. сделать единственным две задаче в первом диве и не сделать такую простую задачу.

→ Ответить

steiner

14 лет назад, # ^ |

У него просто минуты три на неё оставалось, он открыл её последней.

→ Ответить

14 лет назад, # |

Третью див 2 никто не сделал :)

→ Ответить

14 лет назад, # |

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

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

→ Ответить

14 лет назад, # |

Наконец-то в первом диве! После 13-го контеста. Всё-таки не зря моя команда называется TEAM13 :)

→ Ответить

forest

14 лет назад, # ^ |

А вы командой топкодер решаете ?

→ Ответить

14 лет назад, # ^ |

ROFL

Нет, ест-нно. Я про командные :)

→ Ответить

14 лет назад, # ^ |

А я там (в 1 диве) был дважды. Пока безрезультатно. :)

→ Ответить

14 лет назад, # |

Блин, куда-то не туда комменты идут сегодня...
Вы лучше напишите какой рост. У меня +75. С 90м местом.
Контест действительно сказочный был, только написал его плохо.

→ Ответить

14 лет назад, # ^ |

178 см.

→ Ответить

14 лет назад, # ^ |

Не помню сколько у меня было.. но что то около +200. 9-ое место

→ Ответить

14 лет назад, # ^ |

протупил... +164

→ Ответить

Artishok

14 лет назад, # |

+211..

→ Ответить

14 лет назад, # ^ |

Ага, и первое место. Поздравляю!

→ Ответить

Artishok

14 лет назад, # ^ |

спасибо)

→ Ответить

AlexSkidanov

14 лет назад, # |

+67

Блин, когда пористость не нужна, занимаю 15-е место, когда нужна, не могу в топ500 пройти :о(

→ Ответить

Arkadiy

14 лет назад, # ^ |

Видимо дело в психологическом настрое. Я, например, когда на результат не зацикливаюсь, получается лучше. Более расковано пишется ) Хотя тут нужна золотая середина. Без настроя на результат писать тоже плохо )

→ Ответить

14 лет назад, # ^ |

Есть у меня один друг... он в 1C еле-еле вышел из отбора.. 900 с мелочью место. На 2-ом у него 93 место. (это ещё при условии что были ещё крутые из 1A и 1B)

→ Ответить

14 лет назад, # |

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

→ Ответить

14 лет назад, # ^ |

...
Всё, спать пора.

→ Ответить