Всем привет....
Желающие участвовать могут войти в систему/зарегиться здесь.
Для входа выберите COCI 2011/2012 - Contest #2.
Всем заранее желаю удачи...
UPD: появились результаты.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
7 | cnnfls_csy | 3569 |
9 | ecnerwala | 3494 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 158 |
4 | awoo | 158 |
4 | cry | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 153 |
10 | maroonrk | 152 |
Название |
---|
Не понравилось то, что 3я задача задачей являлась только на C/C++ и Pascal, где длинной арифметики нет.
4. Разобъём все числа на 1024 группы, в зависимости от множества числа {присутствует 0, присутствует 1, ...}. После этого достаточно квадратичного перебора по группам, каждый раз проверяя, есть ли между ними хотя бы одна общая цифра.
5. Представим все переменные в виде множества деревьев, где b сын a, если b зависит от a. После этого запускаем ДП. Посчитаем для каждой переменной, сколько раз выполниться код, если учитывать только поддерево этой переменной, и значение этой переменной равно х. Для конкретного х - произведение по всем сыновьям сумм значений сына на отрезке, который даёт использование конкретного х. Сумму на отрезке считаем константно, с ипользованием частичных сумм. Ответ - произведение корней по всем деревьям сумм значений на допустимом отрезке.
6. Заметим, что ответ для одного случая ответ = (сумма времён трапез) - x. Чтобы получить х, отсортируем времена приготовления пиц по возрастанию, посчитаем частичные суммы (у нас только одна печь) и сумма всех частичных сумм и будет х. Соответственно, если мы храним частичные суммы, нам надо уметь изменить все значения на отрезке на какую-то дельту - для реализации прихода и ухода числа. Это можно реализовать с помощью двух деревьев отрезков, например. Одно - для хранения частичных сумм, при этом оставлять свободные места для тех чисел, которые ещё придут; а второе - чтобы определить, каких элементов в первом дереве ещё (или уже) не существует, чтобы мы могли всё время пересчитывать, сколько именно мы пересчитали.
Да и сжимать координаты не обязательно. Ti, T ≤ 100000 же — достаточно хранить количество или сумму, чтобы корректно обрабатывать ситуации, когда Ti повторяются.
Ещё можно pi не хранить, а считать на лету (всё тем же деревом), а их сумму отдельно хранить и вместо уменьшения/увеличения всех pi, стоящих после заданного TR, сразу уменьшать/увеличивать эту сумму на pR + (N - j)TR, где j — номер (начиная считать с единицы), на котором TR стоял бы в отсортированном списке всех Ti; этот номер можно получить из дерева (если TR там встречается несколько раз, годится любой номер — взяв какой-то один вместо другого, мы вычтем ровно столько, сколько потом и прибавим, и в итоге от этого ничего не изменится, — но pR должен соответствовать сумме первых j отсортированных Ti).
Пятую залажал, в итоге -150. Оказывается, топсорт был неверной идеей и лес не всегда вырождался в бамбук. Шестую отправил за 20 секунд до конца - давно не писал декартовы, отсутствие практики сказывается.
First, notice that the graph of dependencies between variables is a forest. We call b a "left child" of a if a is the Xi of b. Similarly, b is a "right child" if a is the Yi of b.
Now consider variable a, value i, and the subtree rooted in a. We want counter[a][i] contain the number of all possible value assignments of the variables in the subtree such that a=i and that each of them respects the constraints (given by Xi and Yi).
We notice that this value can be computed easily based on the values of the children of a. It's the product of sum(c,i) for each child c of a, where sum(c,i) is the sum of counter[c][1..i] if c is a right child or the sum of counter[c][i..100000] if c is a left child.
So, through recursion (well, actually dynamic programming), we can compute counter[a][i] for all a and for all i. To get the final result we multiply, for all roots r of the trees, the sum of counter[r][i] for all values of i.
Don't worry, it sounds more complicated than it actually is!
The complexity should be O(N) (with a factor of 100000 :) and it actually runs really fast: my implementation has an execution time of max. 0.04s.
When you have the values of sum(c,i) for all children, you multiply them all to get the value of counter[a][i].
I hope it's more clear now!
Thanks a lot ..
I'll have a try ..
-----------
How about this input:
3
2 3
1 a
b a
You can't get a fix count[r][i] for some node ..
вот моя реализация третьей задачи на JAVA
Но почему не надо? Ведь везде я так писал и если бы не написал, то в вывод могло не выйти часть вывода (масло масляное).
судя по всему он выкидывает System.exit(1), т.к. не может закрыть реадер ... когда я отписал по этому поводу организаторам, мне сказали не закрывать реадер и врайтер :) Ну а вообщем на JAVA пишу редко :) Предпочетаю С++ :)