SRM 494 - Codeforces

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

← Rev. 4 →

Не могу ни как понять 1000 проблему в див 2(

Как так это вещественно число получатся та из целых, которые тока вычитают по модулю.

p.s. Знаю что обсуждать плохо пока еще не закончился контест, просто не понял проблему вообще, а тем более решить ее шансов нету

→ Ответить

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

Там мат.ожидание - сколько в среднем будет.
Высота каждого дерева - рандом от low до high. И далее с получившийся последовательностью что-то творят. И получают какой-то целый ответ. А рандомов много. Нужно вернуть среднее по всем возможным случаям.

→ Ответить

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

Спасибо понял (нужно чтобы последовательность была "клевая" (каждые три числа удовлетворяли условиям, если не удовлетворяет то удалить некоторые деревья) потом найти разность всех соседей по высоте и разделить сумму разностей на количество деревьев это и будет ответ. Ну и чтоб коэффициент красивости был максимальным).

→ Ответить

sdryapko

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

500 div 2 это про матрицу

→ Ответить

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

точно, ошибся хотел 1000 написать)

→ Ответить

caustique

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

← Rev. 2 →

Ну почему problem переводят как "проблема"? Это ведь "задача" :)

→ Ответить

Gantz

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

ппц бесят мудаки, которые удаляют все пробелы ради того, чтобы их не зачеленджели =/

→ Ответить

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

← Rev. 3 →

Вообще говоря, это запрещено правилами (пункт 7). Можно отписаться ~~на форуме~~ на service@topcoder.com по этому поводу.
~~http://forums.topcoder.com/?module=Category&categoryID=14~~
Сообщаем, соответственно хэндл и задачу.

→ Ответить

Gassa

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

Это надо писать на service@topcoder.com, а не на форум.

→ Ответить

dyussenaliyev

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

По идее польза от этого = 0

→ Ответить

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

Если это относилось к комменту Gantz, просьба использовать кнопку "ответить". Не затеряется под веткой обсуждения, если таковая вырастет.

→ Ответить

Gantz

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

Нет, есть польза - на такой код нет желания смотреть и что-то там разбирать!!!

→ Ответить

Vaness

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

Я участвовал сейчас в первый раз. Сколько примерно по времени занимает фаза System Testing Phase?

→ Ответить

daftcoder

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

Открываем Active contests -> SRM -> Division summary и наблюдаем сначала проверку div1, а затем и div2. :)

→ Ответить

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

Мы одновременно одинаково ответили на заданные одновременно одинаковые вопросы :)

→ Ответить

Gantz

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

Системная проверка в среднем сколько времени занимает?

→ Ответить

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

Можно смотреть на Divison Summary (Active Contests => SRM => Divison Summary) по дивам и приблизительно оценивать завершённость.
Сначала идёт первый див, потом - второй.

→ Ответить

daftcoder

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

Пля, палево)

→ Ответить

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

← Rev. 2 →

Еще раз :) Тройное комбо :)

→ Ответить

Alex_KPR

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

ребят, даже не знаю, что сказать =) звёзды там как-то по-особому встали? =)

это судьба, не иначе :D

→ Ответить

kenny59

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

когда рейтинг пересчитают?

→ Ответить

PavelKunyavskiy

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

Уже. Надо выйти из арены и войти назад, чтобы посмотреть.

→ Ответить

Jokser

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

← Rev. 2 →

Как 500 Div1 решать? Судя по коду как-то совсем просто - чистая математика.

→ Ответить

natalia

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

← Rev. 3 →

+16

1) то, что некоторые числа из последовательности выкидываются, не влияет на ее красоту,

2) ответ = $\text{[math]}$ , а это считается за O(n).

→ Ответить

AlexFetisov

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

красиво... я придумал лютую ДП с выкидыванием и пересчетом "лесенками" вида 1 + 2 + .... но такое не успел написать :( Но красивая задача)

→ Ответить

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

Я тоже писал лютую ДП, и думал "охренеть Гена маньяк написал это за несколько минут".

Первые две задачи обе клевые. Я тока за 3 минуты до конца контеста понял, что по первой задаче написал не правду :о)

→ Ответить

AlexFetisov

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

250ку кстати я уже видел, но в более сложной интерпретации. :) но блин, ты крут, что такое дп написал)

→ Ответить

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

Не-не-не, я не сказал "написал", я сказал "писал".

Тут главное было вовремя понять, что все намного проще.

→ Ответить

AlexFetisov

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

ясно) ну что, надеюсь больше так тупить не буду)

→ Ответить

Ferlon

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

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

→ Ответить

Alex_KPR

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

вот что за стереотип, что 500-ка div 1 - это обязательно динамика? да, там бывают задачи на динамику чаще, чем стоило бы давать, но это не значит, что нужно ~~вырабатывать рефлекс собаки Павлова~~ заставлять мозг думать в одном направлении

у этой задачи ключевая идея - понять, что не надо пилить деревья, а дальше уже очевидно, что несоседние деревья ну никак не будут влиять друг на друга

почему вспомнилось высказывание Андрiя Максая по задаче E тут, правка 4

→ Ответить

Gassa

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

А я начал писать динамику, но через 20 минут понял, что на самом деле надо было воспользоваться фактом “матожидание суммы равно сумме матожиданий”. Как и в половине задач на матожидание.

→ Ответить

Edvard

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

Можешь объяснить формулу. Чёт не очень понятно.

→ Ответить

natalia

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

С учетом 1) получаем, что нужно найти мат. ожидание величины |a[1] - a[2]| + |a[2] - a[3]| + ... + |a[n -1] - a[n]|. Для этого нужно найти сумму мат. ожиданий слагаемых |a[i] - a[i + 1]|. a[i] примет некоторое значение j с вероятностью P{a[i] =j} = 1 / (high[i] - low[i] + 1), a[i + 1] примет некоторое значение k с вероятностью P{a[i + 1] = k}, которая вычисляется аналогично, при этом |a[i] - a[i + 1]| = |j - k|. Находя сумму по всем i, j, k, получаем ответ.

→ Ответить

Edvard

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

А ну с учётом 1) понятно. Блин ну точно. Чётко. Мне чёт ваще в голову не пришло что от выкидывания ничего не зависит. А это прям очевидно.

→ Ответить

natalia

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

Я это поняла, когда нарисовала рисунок.

→ Ответить

Edvard

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

Жалко я не нарисовал((

→ Ответить

AndreySiunov

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

← Rev. 2 →

Почему 1 выполняется?

если взять например числа 1 3 2 (её красота равна 3) и выкинуть 3, то красота станет равна 1.

я что-то явно не понял...

UPD. Всё понял.. Спасибо.

→ Ответить

sdryapko

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

+22

Поздравляю Petra с победой в срме и с возвращением себе 1-ого места по рейтингу

→ Ответить

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

А как решать 1000 див 1?
Если N*M небольшие, то очевидно, что гауссом считаем количество свободных переменных, и ответ это 2 в этой степени.
Но в условии N и M до 150...

→ Ответить

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

Сделаем двудольный граф, левая доля - клетки, чья сумма координат четна. Правая - нечетна.

Ребро - если конь может сделать ход из одной клетки в другую (очевидно конь будет менять долю каждый ход).

Надо найти количестви минимальных вершинных покрытий этого двудольного графа. Как это сделать я не знаю :о)

→ Ответить

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

Это вроде неверно, ведь по условию инвертируется, а у в покрытии надо чтобы было хотя бы 1.

→ Ответить

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

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

→ Ответить

MBabin

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

← Rev. 2 →

Решать нужно гаусом и найти ранк матрицы. Проблема что у нас nm переменных и nm уранений. Но число переменных можно сократить до 2n + m если заметить, что когда у нас известна расстановка коней на последних двух строчках и на последнем стобце, то дальнейшее расположение коней определяется однозначно. В итоге получается 2n + m переменных и nm уравнений. И ранк можно найти за (2n + m)²· nm плюс еще битовое сжатие можно приенить для усокрения в 64 раза.

→ Ответить

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

Наверное для однозначности все-таки нужны 2 строчки и левый столбец?

→ Ответить

MBabin

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

да подправил)

→ Ответить

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

Вот у Petrа количество уравнений совпадает с количеством переменных.
Наверное нам не нужны все n*m уравнений?

→ Ответить

Petr	14 лет назад, # ^ \| +10 nm уравнений не нужно - ведь если мы восстанавливаем расстановку коней в остальных клетках, то мы автоматически получаем что везде кроме первых двух строк и первого столбца все уже как надо. Так что уравнений столько же сколько переменных ) → Ответить

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

Ах да, спасибо!

→ Ответить

http://www.topcoder.com/wiki/display/tc/Algorithm+Problem+Set+Analysis

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

← Rev. 2 →

Интересно где нибудь разборы пишутся, SRM'ов?

И еще, как 500 из див два про матрицу B W решать? Я просто искал минимум по горизонтали и вертикале в итогe fail.

→ Ответить

mexmans

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

→ Ответить

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

У меня тоже =( Что-то никак не придумать, почему это неправда.

→ Ответить

Snipx

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

← Rev. 3 →

Ну так можно ведь посмотреть, на каком тесте завалилась

UPD: вот пример:

WWBBB

WBBBB

BBBWW

ответ 2, а вернет 3

→ Ответить

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

Меня почелленджили, а автор челленджа покинул арену, и я не успел его спросить. А челленджи же вроде нельзя смотреть, или я просто не умею?

Да, теперь понятно, спасибо.

→ Ответить

Snipx

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

Это именно тот тест, на котором вас почелленджили.

Как смотреть:

Кликаете на точку в графике своего рейтинга, соответственно попадаете в резы своей комнаты, там будет список участников и их очков, а ниже ваш статус по задачам, и там где Challenge Succeeded, просто кликаете на ссылку с названием задачи и смотрите внизу =)

→ Ответить

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

Ой, точно, я же так тоже умею =)

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

→ Ответить

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

← Rev. 2 →

Я тоже :о) Потом понял это, и челенжил тестом

...XXX

.XXX..

XXX...

Поиск вернет троечку вместо двойки.

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

→ Ответить