Google Code Jam 2014, round 1C

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
23:56:51
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

Google Code Jam 2014, round 1C

Автор artie, 11 лет назад, По-русски

Если есть еще такие же персоны, как я, то добро пожаловать — это будет последняя попытка пройти во второй раунд
Место и время.
Осталось примерно 6 часов до начала!

google code jam

artie
11 лет назад
34

Комментарии (34)

Написать комментарий?

HASP

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

Расскажите, пожалуйста, В на полный балл.

→ Ответить

1k_trash

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

Да и насчет Б на неполный балл -- там надо было как-то соптимизировать "сгенерируем все N! перестановок и каждую проверим" или что-то другое?

→ Ответить

artie

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

+12

Да, на неполный балл в B заходил полный перебор всех перестановок.

→ Ответить

adamant

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

Ну, у меня просто перебор перестановок не успевал завершиться. Поэтому я немного сбил константу таким образом: сжал повторяющиеся символы в строках в один. В итоге заработало немного быстрее. На полный балл, как я предполагаю, нужно было потом пошаманить с тем, в каком порядке мы можем располагать сжатые строки, подомножать на факториалы строк, которые станут единичными символами и проверить на Impossible.

→ Ответить

naagi

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

← Rev. 2 →

Сначала склеим все, что необходимо склеить. Для каждой буквы бывают куски, которые на нее только кончаются (не больше одного, иначе ответ 0), которые на нее начинаются и кончаются (любое количество), и которые на нее только начинаются (не больше одного), склеим их в этом порядке. Те, что посередине, могут идти в любом порядке. Пусть их L — тогда результат домножим на L!

После склеивания по каждой букве получилось несколько кусков. Если куски хорошие (одна и та же буква не встречается в них не подряд), и каждая буква встречается не больше чем в одном куске, то их можно клеить в любом порядке, то есть результат опять домножается на факториал количества кусков.

→ Ответить

adamant

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

Как решать B-, C- large?

→ Ответить

Endagorion

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

+12

B: построим ориентированный граф на буквах. Если в какой-то строке после a идет b, добавим ребро из a в b (возможно, будут получаться кратные ребра). Проверим, что граф является набором путей (для каждой буквы не более одного входящего и одного исходящего ребра, нет циклов). Тогда ответ = (произведение по всем буквам) (количество строк, состоящих целиком из этой буквы)! умножить на (количество путей)!.

C: оптимальная фигура — это всегда прямоугольник с отрезанными углами. Переберем размеры прямоугольника и размер каждого из углов, это уже работает очень быстро. Кроме того, в оптимальном ответе размеры отрезанных углов отличаются не более чем на 1.

→ Ответить

yeputons

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

А умеешь доказывать, что в C ответ такого вида?

→ Ответить

naagi

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

+16

Вроде бы это очевидно :) Понятно, что ответ выпуклый (иначе существует выпуклый не хуже), а любая такая выпуклая фигура — это и есть прямоульник с отрезанными углами.

Про размер углов тоже понятно, если они различаются сильнее, стоит один уменьшить на 1, а другой увеличить.

→ Ответить

Endagorion

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

Ну, совсем строгое доказательство — это геморройный разбор случаев. Сперва поймем, что фигура совпадает со своей 4-связной границей (иначе что-то можно удалить). Дальше избавимся от точек сочленения (в 8-связном смысле), чтобы не было таких ситуаций:

...**.
***..*
...**.

Избавимся как-нибудь так: удалим точку, сдвинем компоненты (здесь надо разобрать случаи, как могут располагаться компоненты и почему их можно сдвинуть), приклеим точку сбоку, чтобы появился дополнительный путь; площадь не уменьшилась. Возможно, придется повторить первый пункт с удалением точек не на границе.

Теперь пойдем по границе и будем разрешать невыпуклости (к примеру, левый верхний угол):

..*    .**
**. -> *..

Теперь мы можем это делать, поскольку точек сочленения нет и точки, которые были внутри, останутся внутри.

Это то, что сходу в голову пришло, возможно, есть более простой способ.

→ Ответить

adamant

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

← Rev. 2 →

С отрезанными углами, то есть, что-то такого вида?

.***...
*...***
**....*
..****.

Мне кажется, такую фигуру всегда можно свести к прямоугольнику, у которого отсутствует только по одному символу в углах. И в котором просто будет чуть больше клеток. В данном случае это будет:

.*****.
*.....*
*.....*
.*****.

Или есть пример, показывающий обратное?

→ Ответить

Endagorion

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

..*..
.*.*.
*...*
.*.*.
..*..

→ Ответить

adamant

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

А, ок, я неправильно понял, что такое прямоугольник с отрезанными углами. Ну, крутые решения, спасибо :)

→ Ответить

I_love_Tanya_Romanova

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

+10

Кто-то может рассказать, как на GCJ наборы тестов генерируются? Есть какой-то пул инпутов, из которого дают случайный? Или инпут генерируется на ходу?

Заинтересовался, потому что по В убогость тестов зашкаливает. С учетом того, что к результату "ответ равен 0 или х" можно прийти, посчитав одним dfs-ом количество компонент на графе из букв, и еще одним циклом — количество строк, состоящих целиком из заданной буквы, а потом перемножить все эти факториалы; а для проверки "0 или не 0" надо сделать намного больше работы... Давать наборы, в которых тестов с ответом 0 — 7 или 8 штук из 100 — это не айс.

Мое АС-решение даже на тест 2 a bac дает ответ 1.

→ Ответить

AlexanderBolshakov

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

← Rev. 2 →

Мне это тоже интересно. В A-large я получил набор тестов, где ни один ответ не превышал 31. Так что даже если бы я не исправил один свой мелкий баг, у меня все бы зашло.

→ Ответить

I_love_Tanya_Romanova

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

где ни один ответ не превышал 31 — а у меня максимальный — 27.

У кого меньше? :)

→ Ответить

AlexanderBolshakov

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

Если честно — у меня на самом деле 26. Просто из-за переполнения ответ считался корректно только тогда, когда он был не больше 31, поэтому я и сказал про 31.

P.S. Баг был исправлен еще до посылки small, так что искать его в моем коде не надо.

→ Ответить

dkirienko

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

У меня максимальный — 26.

→ Ответить

Igorjan94

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

ответ не превышает 25, а вот максимальная степень действительно 40)

→ Ответить

Igorjan94

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

← Rev. 2 →

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

→ Ответить

Harun

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

Any idea for problem C ?

→ Ответить

Thomas_Ahle

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

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..

→ Ответить

urusant

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

However, according to the Russian discussion, it is true))

→ Ответить

JuanMata

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

← Rev. 3 →

can anyone give a hint on how to solve problem B?
P.S. i could solve C-small (with a $\text{[math]}$ solution, probably the most complex solution that solved it correctly :P), but not B-small!

→ Ответить

JuanMata

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

← Rev. 2 →

duplicate post

→ Ответить

fetetriste

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

← Rev. 7 →

Since I'm in the mood of writing hints, here's some for the actual gcj problem:

(Small input) N <= 10, sounds like a good problem for an O(N! * something) solution!
Build a graph with letters as its vertices. If you have a letter 'x' following a letter 'y' in a string, add an edge from y to x.
What if there are cycles in this graph?
If you are told that the answer is not zero, how would you calculate it?

→ Ответить

JuanMata

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

i was asking about GCJ round 1C, which took place earlier today.
not about CF round 245! :)

→ Ответить

fetetriste

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

Yeah, I got it and to make up for the mess wrote some hints for a possible solution

→ Ответить

shubh09

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

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)

→ Ответить

fetetriste

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

← Rev. 2 →

Again, a stronger hint in edit.

Is the absence of cycles enough for the answer to be nonzero or should you forbid something else?

→ Ответить

1k_trash

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

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.

→ Ответить

AlexErofeev

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

+14

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.

→ Ответить

urusant

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

Indeed, WTF? I had 920th place and now I have 997, that is almost at the edge...

→ Ответить

dkirienko

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

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

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 22.11.2024 17:38:11 (i2).

Десктопная версия, переключиться на мобильную.

При поддержке