TopCoder SRM 496 - Codeforces

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

До соревнования
Educational Codeforces Round 173 (Rated for Div. 2)
33:48:13
Зарегистрироваться »

→ Трансляции

aryanc403

До начала 35:58:11

Всё →

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

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

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

Всё →

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

№	Пользователь	Вклад
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	151

Всё →

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

→ Прямой эфир

Детальнее →

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

TopCoder SRM 496

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

Будет через пол часа

Одному мне письмо с напоминалкой не пришло?

srm, topcoder

Egor
14 лет назад
45

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

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

PavelKunyavskiy

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

Мне пришло. Вчера в 14:35:49.

→ Ответить

daftcoder

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

← Rev. 2 →

31 января 2011 г. 11:41
TopCoder(R) Single Round Match 496 is scheduled for Tuesday, February 1, 2011 at 7:00 UTC -5 hours.

→ Ответить

PML	14 лет назад, # \| +1 Мне тоже приходило. → Ответить

daftcoder

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

← Rev. 5 →

Ну и комната попалась... kuniavski, Gassa, Adamax (не пришел), elizarov...

А задачи Div. 1 вроде проще, чем обычно. Хотя всё равно интересно как вторую решать. Да и третью.

UPD: Кстати из комнаты не пришел только один участник, что радует.

UPD 2: Так как решать Div. 1 - 500 и 950?

UPD 3: Кажется первое непадение из Div. 1 -- 211 место.

→ Ответить

Vasya.V

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

500:

Решал брутфорсом

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

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

→ Ответить

winger

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

Каждая компонента связности будет "змейкой", так что количество вариантов можно посчитать и по формуле

→ Ответить

Egor

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

500 - фиксируем модуль расстояния, преодоленного шариками. Тогда у нас все распадается на некоторое количество независимых подсистем и в каждой подсистеме вариантов - число шаров в подсистеме + 1. Перемножаем, получаем ответ для данного времени. Подсистема - это когда у нас есть несколько шариков на первой картинки, для каждого из которых 2 варианта на 2й и при этом каждый, кроме крайних, из этих вариантов является вариантом для 2 шариков с 1й картинки

→ Ответить

Egor	14 лет назад, # ^ \| 0 Насчет 950 - если мне кто-то объяснит, почему мое решение работает - будет круто Писал в последний момент, за 2 минуты до конца дописал, оно сразу прошло семплы и, что самое удивительное, в итоге прошло систесты → Ответить

gojira

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

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

→ Ответить

Salat

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

я что то не понял чего там хотят (див 2 задача на 1000), странно как то

количество строк длиной N таких чтобы подстроки длиной M были палиндромами и чтобы их было не меньше K?

→ Ответить

mavr	14 лет назад, # ^ \| +2 У строки длинны N рассматриваются все подстроки длинны M, если из этих подстрок не меньше K - палиндромы, то строка (длинны N) - палиндромополная. Нужно найти к-во палиндромополных строк длинны N, состоящих из латинских заглавных букв. → Ответить

Kostroma

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

а как ее решать? :)

→ Ответить

Salat

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

ее решили три человека и все три китайцы.

→ Ответить

winger

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

← Rev. 3 →

Проходит перебором масок

http://pastebin.com/6dJUapNe

→ Ответить

Vaness

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

Можно ли решение словами? Смотрел код - не понял.

→ Ответить

Kenny_HORROR

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

Можно и не масками. Пускай у нас используется m различных символов для нашей строки (не нарушая общности первый встерчающийся будет номером 1, второй 2 и т.д. (всего не более 11 символов будет)).

Рассмотрим все возможные строки которые состоят из указанных символов с указанным порядком вхождения и проверим подходит ли она под условие палиндромности. Если подходит тогда ей соотвествует P₂₆^m строк из больших букв, причем различным строкам будут соответсвовать различные строки из исходных.

Все строки генерируются и считается число палиндромов за O(N!), а при N = 11 этого более чем достатчно, чтобы вложиться в 2 секунды.

→ Ответить

NotImplemented

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

Можно найти все разбиения строки из N элементов, используя, например, схему Эрлиха. При N=11 разбиений будет 678570, http://oeis.org/A000110. Затем можно действовать, как написано выше - проверять палиндромность и, если подходит, умножать на P₂₆^m, где m - количество подмножеств в разбиении.

→ Ответить

winger

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

Можно уточнить что такое схема Эрлиха, а то гугл говорит что это "схемы образования высших спиртов")

→ Ответить

NotImplemented

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

http://www.codeforces.com/blog/entry/834, задача I.

→ Ответить

Egor	14 лет назад, # \| +1 Ага, это у меня на домене просто почта перестала ходить. Сейчас посмотрим, в чем дело → Ответить

kenny59

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

А как посмотреть тест на котором меня почеленджили?

→ Ответить

daftcoder

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

Примерно минут через 20-40 вся инфа появится на сайте.

→ Ответить

daftcoder

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

Что-то пока не появилась инфа пока, но должна будет появиться.

→ Ответить

daftcoder

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

← Rev. 2 →

http://www.topcoder.com/stat?c=room_stats&rd=14425&rm=307129

1) Please select a room: ищем свою комнату (можно в арене посмотреть в какой был)

2) Кликаем на у себя.

3) Problem Information for %username% - Problems - Class Name - Выбираем. Снизу смотрим.

→ Ответить

Vasya.V

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

Невероятно!

Отправил div1-500 за 3 сек до конца и AC!

Вот это поперло.

→ Ответить

Salat

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

Поздравляю!)

А я наконец-то на ТопКодере получил два АС'а!=)

→ Ответить

AlexSkidanov

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

Слава, почему твое решение по 950 работает? :о)

→ Ответить

winger

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

1) Если отсортировать все строки лексикографически, получим минимум по всем гамильтоновым путям
2) Если положить все строки в бор, сыновей любой вершины можно переставлять произвольно

Чтобы получить нужные начало и конец, нужно "разорвать" вершину - lcp начала и конца, поправка на это у меня и вычисляется в последних двух строчках

→ Ответить

AlexSkidanov

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

Спасибо. Красивое решение.

→ Ответить

sweiss

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

а можно как-нибудь доказать первый пункт? для меня он почему-то неочевиден

→ Ответить

yaro

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

← Rev. 2 →

Очевидно, можно искать максимальный гамильтонов путь для графа с ребрами, равными lcp^2(s_i, s_j) вместо того, что написано в условии. Ну а в таком графе мы для каждой вершины в пути берем два (или одно) самых больших ребра, так что путь максимален.
Мне скорее непонятно, как формально трюк с разрывом в середине и добавлением ребра между максимальной и минимальной строками объяснять.

===
Ох, да, чушь написал. См. ниже.

→ Ответить

ivan.metelsky

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

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

Это неправда. Например, если у нас есть "a", "bba", "bbb", "bbc", то "bba" соединяется ведь с "a" и "bbb", а не с "bbb" и "bbc".

===

В целом второй пункт легко обосновывается, если в первом пункте доказать, что это не только оптимальный гамильтонов путь, но и оптимальный гамильтонов цикл. Тогда мы посредством перестановок сыновей ставим 0 и 1 рядом в цикле, а отсюда сразу следует, что если разорвать ребро между ними, то получится оптимальная гамильтонова цепочка.

Для доказательства первого пункта в принципе нужно доказать, что (в гамильтоновом цикле или пути), если у вершины бора есть несколько сыновей, то обязательно все слова внутри каждого из соответствующих поддеревьев посещать "за один заход". Это несложно доказать от противного.

→ Ответить

Edvard

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

Кто-нибудь знает как найти количество совершенных паросочетаний в двудольном графе? А то я в 500ке до этого дошёл а как посчитать не знаю.

→ Ответить

PavelKunyavskiy

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

← Rev. 3 →

По 500-ой есть решение без этого, смотри выше. Вообще я где-то такую задачу видел. Сейчас попытаюсь вспомнить решение. Если вспомню напишу.

UPD :Не видел, там было найти все ребра которые могут лежать в совершенном паросочетании.

→ Ответить

Edvard

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

Я чёт не очень понял почему перебор должен быстро работать. И что за "змейка" и как в ней считать ответ.

→ Ответить

Vasya.V

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

Пусть все шарики упорядочены по возрастанию

Если i шарик можно переместить в положения x1, x2, тогда не существует такого шарика j, который можно переместить в те же положения (т.к. x[i] = (x1 + x2) / 2 - однозначно).

Следовательно, при j > i, j может попадать либо в x2, либо не попадать в x1, x2 вообще. Аналогично при j < i. Отсюда получается, что каждая компонента связности - "змейка", и простой перебор на ней будет работать (думаю, что за O(l^2), но могу ошибаться)

→ Ответить

Edvard

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

Понятно

→ Ответить