TCO 2011: Qualification Round 2

№	Пользователь	Рейтинг
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
2	adamant	164
4	TheScrasse	159
4	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

Всем привет!

Кто писал, или просто смотрел задачи - у меня 2 вопроса:

(Кто хочет посмотреть - вот ссылки:

Первая - http://www.topcoder.com/stat?c=problem_statement&pm=11418&rd=14530

Вторая - http://www.topcoder.com/stat?c=problem_statement&pm=11424&rd=14530

Третья - http://www.topcoder.com/stat?c=problem_statement&pm=11372&rd=14530)

1. Какой самый плохой тест для второй? У меня 10000 шагов пересчета возможных позиций на всем поле улетели. Какой тест дает больше? (UPD: упал на тесте ".CKC.CKC.CKC.CKC.CKC.CKC.CKC.CKC.CKC.CKC.CKC.CKC.", 50, 49 дает в ответе 29401, обидно)

2. Как просто решить третью? Я придумал алгоритм, но не очень простой. А там ее даже синие сдавали. Либо я недооцениваю синих, либо может быть есть относительно простое решение задачи?

Спасибо!

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

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

steiner

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

← Rev. 3 →

d(n) - это остаток от деления n на 9, если n не кратно 9, и 9 иначе.

Получаем систему соотношений вида j * (9 * k + j % 9) = x, j = 1...9.

То есть х = bj (mod a_j) для некоторых a_j и b_j .

Можно заметить, например, что все a_j делят число m = 5 * 7 * 8 * 9 * 9.

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

→ Ответить

goryinyich

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

Спасибо, действительно проще, чем я придумал с включением-исключением

1a1a1a

а как Вы думали с включением-исключением ?

Довольно стандартно. Классы чисел имеют вид (9i+1)*1, (9i+2)*2, ..., (9i+9)*9. Сначала складываем кол-во чисел в каждом классе (найти легко), потом вычитаем кол-ва, которые в двух классах, прибавляем - которые в трех и т.д. Можно заметить (по остаткам от деления на 9), что лишь немногие классы пересекаются (либо по 2, и только с остатком 0 - 3 класса), я вручную выписал формулы и начал их забивать. Немного не успел. Решение, которое описал awanim, конечно, намного изящнее.

impetus

В принципе формула там не очень большая. У меня получилось 7 слагаемых на включение (для 1, 2, 3, 4, 5, 7, 9) и 2 на исключение (для 4x5 и 2x7). А конкретные коэффициенты у слагаемых можно было быстро вывести перебором.

Не очень понял, почему 7. 9 классов - 9 слагаемых на включение (класс 6, например, не является подклассом класса 3, как может показаться), у классов 1 и 8, 2 и 7, 4 и 5 есть пересечения, кроме того, пересекаются классы 3, 6 и 9 - нужно искать сразу пересечение трех

9 не пересекается с 3 и 6, т. к. все числа класса 9 делятся на 81, а 3 и 6 нет. Кроме того, класс 3 включает класс 6. Аналогично, класс 1 включает класс 8. Остается только то, что я написал в предыдущем посте.

Согласен, да, я че-то затупил

Как подсказывают тесты, для такого примера

".CKC.CKC.CKC.CKC.CKC.CKC.CKC.CKC.CKC.CKC.CKC.CKC..", 50, 49

ответ 29402.

В принципе понятно, что можно оценить ответ сверху как N * lcm(K, C) <= 50 * 49 * 50, и это зашло бы по времени.

iensen

← Rev. 2 →

Во второй еще можно было Дейкстру за MlogN писать,где каждая вершина определяется номером ячейки и двумя остатками от деления на K,C.

al13n

+19

Достаточно обхода в ширину: ребра невзвешенные.

Sammarize

Да, я тоже поставил 10000+ шагов и обломался с попаданием в десятку =(

NKolotey

А я чёта оборзел, просто поставил проверку в цикле - если уже > 1.9 секунд всё никак не родится ответ, то return -1.

wistful23

Да, с 10000 обидно (
Перед отправкой добавил 0 и сразу убрал - зачем лишний раз программу гонять )

pva701

я тоже чуть было не поставил 10000, но потом подумал 5*10^6 проходит, почему бы не поставить 10^5 и хорошо что так и сделал

Правильно, я уже тоже решил, что в следующий раз так и сделаю.

Ferlon

И всё равно ведь можете нарваться, потому что в другой раз задача может так не решаться. Здесь вот, например, проходил BFS по 50³ состояний - 50 на размер массива, ещё квадрат - на время по модулю K * C (а значение - время без модуля). У меня, если что, тоже упало, но по другой причине - за каким-то лешим догадался брать время для параметра по модулю N * K * C, а увидев, что очередь такого объёма (50⁴) в память не помещается, сделал отсечение, чтобы рассматривалось только порядка 50³.
P.S. Кстати, я одного свалил именно на том, что он решал итерациями, но поставил их мало.

Гм, если делать память 50⁴то локально у меня не запускается, но если сабмитить в арену, там отлычно все проходит. Не подскажете почему так ? Как сделать чтобы локально все было хорошо ?

+10

Ну, строго говоря, у меня не проходило в "Арене" не 50⁴, а 64⁴. А как именно у Вас "не запускается", что конкретно происходит? А ещё сбросьте тогда на всякий случай код сюда и скажите, каким компилятором и с какими ключами Вы его локально собираете.

P.S. И незачем так ОРАТЬ :)

Программа просто вилетает. Такое впечетление что нехватает памяти.

Вот код http://pastebin.com/T2xPWgft

Пользуюсь gcc 4.4.1, ключи -s -O2

Вот я попробовал собрать под MSVS 2008 - вроде нормально работает. Насколько я знаю (гарантировать не могу, пусть подтвердят те, кто юзает gcc), стек под g++ растягивается не директивой прагме (она просто игнорируется), а как-то хитрее.

Спасибо.

riadwaw

AFAIK только через ком. строку при запуске

как именно ?

тут указано, как это делается на этом сайте

dmitrydyatlov

off-top
у всех календарь на http://topcoder-calendar.appspot.com/ поломался?

diogen

да, у меня тоже не работает

goo.gl_SsAhv

я во время контеста тупил с 500, и даже не прочел 1000. 1000 оказалась для меня очень простой, заметим что d(n) = 1 + (n - 1) % 9 я это давно знаю, с какой-то задачки помню. f(x) = 1 если x представимо, f(x) = 0 иначе. последовательность f(1), f(2) .... f(n) циклична, это как-то интуитивно чувствуется, безо всяких вычислений. построим 100 000 первых членов в лоб, найдем длину цикла опять влоб. 100 000 в квадрате, но там обламывается почти сразу, если длину цикла неугадали поэтому все это работает 30 мс. ну а теперь зная длину цикла K и начальные K членов последовательности не сложно научиться считать количество еденичек на интервале [1..n]

Такой интуиции можно позавидовать. Мне вот только очевидно, что циклично идут те n, которые представимы как yd(y) с каким-то одним d(y), соответственно там, казалось бы, должно быть несколько циклов, которые местами-временами ещё и пересекаются. Но Вы утверждаете, что цикл на самом деле один? И как это всё-таки доказать?

Ну, если есть несколько циклов, то их LCM один цикл.

Ну, это в некотором смысле да, но как это относится к вопросу? :)

У нас есть несколько циклических последовательностей, они все объединяются в одну, операцией "или". В худшем случае длина общего цикла равна произведению длин всех циклов. Это же тебе было очевидно в задаче 500? что K * C * n это общее число состояний, в которых чувак может находиться.

Очевидно также что если сливать два цикла длин A и B и B % A = 0, то длина общего цикла будет B.

Про LCM тоже понятно, это как китайская теорема об остатках. всего может быть не более LCM(m1, m2, .. mn) решений системы уравнений.

а да, вообще говоря про LCM не так очевидно, но мне уже хватило того что цикл существует, чтобы попытаться найти его длину.

Мы, видимо, о разных "циклах" говорим. Вот смотри, для d(y) = 2 последовательность таких x, что yd(y) = x, выглядит так:
4, 22, 40, 76, ...
А для d(y) = 3 - так:
9, 36, 63, 90, ...
И как же эти две последовательности слить в одну с периодом? Или, может быть (такую возможность я тоже допускаю), в последовательность с одним периодом они сливаются не попарно, а только для (почти) всех возможных d(y) сразу?

рассмотрим последовательность f1, f1(x) равно 1, если существует y, такое что d(y) = 1 и d(y) * y = x
рассмотрим последовательность f2, f2(x) равно 1, если существует y, такое что d(y) = 2 и d(y) * y = x
рассмотрим последовательность f3, f2(x) равно 1, если существует y, такое что d(y) = 3 и d(y) * y = x
...
все эти последовательности состоят из 0 и 1, и все цикличны.
теперь объеденим их в общую последовательность f, f[x] = f1[x] or f2[x] or f3[x] ...
она тоже циклична, смотри пояснения выше

Ну замечательно, для d(y) = 1 последовательность выглядит так: 1, 10, 19, 28, .... Объединяем с двойкой и тройкой, получаем: 1, 4, 9, 10, 19, 22, 28, 36, ....
Где цикличность, где??? В упор не вижу. Но, что самое страшное, ты говоришь, что сдал задачу, значит ты прав. Видимо, я в этой жизни чего-то очень сильно не понимаю :-X

http://www.everfall.com/paste/id.php?zsjlp85c5wbq

Ну вооот, теперь понятно - как я и сказал, мы говорили о разных циклах. Ну а ты-то понял, что я имел в виду?

нет, в самом первом посте я определил последовательность как последовательность из 0 и 1, f(x) = 1 если x представимо

Alex_KPR

я посмотрел код и мне стало интересно другое: функция ASS(0) гарантированно крэшит программу в любой жизненной ситуации?

Должна бы, с таким-то названием...

========================

не, ну я просто не очень осознаю, как именно она крэшит =)

очень полезная вещь на самом деле, я обычно оставляю "while(true);", но так можно перепутать ассерт с таймлимитом

обращение к элементу памяти с адресом ноль на чтение и на запись, конечно вылет будет. а вот ТЛ не имеет side effects по мнению оптимизирующего компайлера, и он его оптимиздит

"оптимиздит" - слово-то какое =)

спасибо за разъяснение :)

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

Qulinxao

по первой задаче

одни делали 2 подсчётами ,

вторые сжиганием свечки с двух сторон(like while(l<r){while(f(l))l++;while(g(r))r--; dosome;})

кто нить делал за один проход ? (like for(i=0;i<somefunc;i++){dosome2})

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