| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | Radewoosh | 3415 |
| 8 | Um_nik | 3376 |
| 9 | maroonrk | 3361 |
| 10 | XVIII | 3345 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
Расскажите, пожалуйста, В на полный балл.
Да и насчет Б на неполный балл -- там надо было как-то соптимизировать "сгенерируем все N! перестановок и каждую проверим" или что-то другое?
Да, на неполный балл в B заходил полный перебор всех перестановок.
Ну, у меня просто перебор перестановок не успевал завершиться. Поэтому я немного сбил константу таким образом: сжал повторяющиеся символы в строках в один. В итоге заработало немного быстрее. На полный балл, как я предполагаю, нужно было потом пошаманить с тем, в каком порядке мы можем располагать сжатые строки, подомножать на факториалы строк, которые станут единичными символами и проверить на Impossible.
Сначала склеим все, что необходимо склеить. Для каждой буквы бывают куски, которые на нее только кончаются (не больше одного, иначе ответ 0), которые на нее начинаются и кончаются (любое количество), и которые на нее только начинаются (не больше одного), склеим их в этом порядке. Те, что посередине, могут идти в любом порядке. Пусть их L — тогда результат домножим на L!
После склеивания по каждой букве получилось несколько кусков. Если куски хорошие (одна и та же буква не встречается в них не подряд), и каждая буква встречается не больше чем в одном куске, то их можно клеить в любом порядке, то есть результат опять домножается на факториал количества кусков.
Как решать B-, C- large?
B: построим ориентированный граф на буквах. Если в какой-то строке после a идет b, добавим ребро из a в b (возможно, будут получаться кратные ребра). Проверим, что граф является набором путей (для каждой буквы не более одного входящего и одного исходящего ребра, нет циклов). Тогда ответ = (произведение по всем буквам) (количество строк, состоящих целиком из этой буквы)! умножить на (количество путей)!.
C: оптимальная фигура — это всегда прямоугольник с отрезанными углами. Переберем размеры прямоугольника и размер каждого из углов, это уже работает очень быстро. Кроме того, в оптимальном ответе размеры отрезанных углов отличаются не более чем на 1.
А умеешь доказывать, что в C ответ такого вида?
Вроде бы это очевидно :) Понятно, что ответ выпуклый (иначе существует выпуклый не хуже), а любая такая выпуклая фигура — это и есть прямоульник с отрезанными углами.
Про размер углов тоже понятно, если они различаются сильнее, стоит один уменьшить на 1, а другой увеличить.
Ну, совсем строгое доказательство — это геморройный разбор случаев. Сперва поймем, что фигура совпадает со своей 4-связной границей (иначе что-то можно удалить). Дальше избавимся от точек сочленения (в 8-связном смысле), чтобы не было таких ситуаций:
Избавимся как-нибудь так: удалим точку, сдвинем компоненты (здесь надо разобрать случаи, как могут располагаться компоненты и почему их можно сдвинуть), приклеим точку сбоку, чтобы появился дополнительный путь; площадь не уменьшилась. Возможно, придется повторить первый пункт с удалением точек не на границе.
Теперь пойдем по границе и будем разрешать невыпуклости (к примеру, левый верхний угол):
Теперь мы можем это делать, поскольку точек сочленения нет и точки, которые были внутри, останутся внутри.
Это то, что сходу в голову пришло, возможно, есть более простой способ.
С отрезанными углами, то есть, что-то такого вида?
.***...*...*****....*..****.Мне кажется, такую фигуру всегда можно свести к прямоугольнику, у которого отсутствует только по одному символу в углах. И в котором просто будет чуть больше клеток. В данном случае это будет:
.*****.*.....**.....*.*****.Или есть пример, показывающий обратное?
А, ок, я неправильно понял, что такое прямоугольник с отрезанными углами. Ну, крутые решения, спасибо :)
Кто-то может рассказать, как на GCJ наборы тестов генерируются? Есть какой-то пул инпутов, из которого дают случайный? Или инпут генерируется на ходу?
Заинтересовался, потому что по В убогость тестов зашкаливает. С учетом того, что к результату "ответ равен 0 или х" можно прийти, посчитав одним dfs-ом количество компонент на графе из букв, и еще одним циклом — количество строк, состоящих целиком из заданной буквы, а потом перемножить все эти факториалы; а для проверки "0 или не 0" надо сделать намного больше работы... Давать наборы, в которых тестов с ответом 0 — 7 или 8 штук из 100 — это не айс.
Мое АС-решение даже на тест 2 a bac дает ответ 1.
Мне это тоже интересно. В A-large я получил набор тестов, где ни один ответ не превышал 31. Так что даже если бы я не исправил один свой мелкий баг, у меня все бы зашло.
где ни один ответ не превышал 31 — а у меня максимальный — 27.
У кого меньше? :)
Если честно — у меня на самом деле 26. Просто из-за переполнения ответ считался корректно только тогда, когда он был не больше 31, поэтому я и сказал про 31.
P.S. Баг был исправлен еще до посылки small, так что искать его в моем коде не надо.
У меня максимальный — 26.
ответ не превышает 25, а вот максимальная степень действительно 40)
в копилку к плохим тестам прошлогодний раунд 1В задача, моя история, там ниже мой же коммент, по сути почти совпадает -- сначала отсечения, потом решение. И вот решение почему-то не тестировалось должным образом...
Any idea for problem C ?
I was thinking, maybe it's always optimal to place the stones in a 'rectangle without corners'. But then, perhaps, the question is too easy..
However, according to the Russian discussion, it is true))
can anyone give a hint on how to solve problem B?
solution, probably the most complex solution that solved it correctly :P), but not B-small!
P.S. i could solve C-small (with a
duplicate post
Since I'm in the mood of writing hints, here's some for the actual gcj problem:
i was asking about GCJ round 1C, which took place earlier today.
not about CF round 245! :)
Yeah, I got it and to make up for the mess wrote some hints for a possible solution
I thought about this approach. Won't it involve finding the number of Eulerian paths in the graph so formed? (Another hint in this regard would be much appreciated)
Again, a stronger hint in edit.
As you asked, a hint: build a directed graph on letters (for example, if there goes letter b after a in some string, so you should add an edge from a to b). Ask questions (or for complete idea of solution) if needed.
WTF is happening with scoreboard? Today I found myself 6 places lower than yesterday morning. It didn't make me out of Round 2, but still is interesting.
Indeed, WTF? I had 920th place and now I have 997, that is almost at the edge...
The scoreboard was broken at the end of contest, there was a lot of bugs.
Now it is fixed. See https://groups.google.com/forum/#!topic/google-code/KLBgnIdVj_U