Похоже, что на codeforces в компиляторе haskell Int - 32 битный: в этой задаче, посылка 528293(у меня не получилось получить ссылку на посылку, кто-нибудь подскажет, как это делать?) получается переполнение на 16 тесте, после изменения Int на Integer(он произвольной точности), посылка 528297 - проходит. По стандарту вроде написано что должно быть хотя бы -2^29..2^29 - 1, но все же, может, можно явно указать это при компиляции и поставить на codeforces. Попытался найти как это сделать - не получилось. Может тут есть знатоки haskell, которые знают?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Захотелось научиться писать БПФ без арифметики с плавающей точкой - начал изучать по этой статье. Вроде все более-менее понял, написал и даже кое-что работает, но остается непонятными несколько вещей:
Во-первых - пусть A = B*C(в смысле полиномов) и мы посчитали FFT(B), FFT(C). Все значения в этих массивах меньше модуля. Потом мы должны скалярно перемножить (FFT(B), FFT(C)) и применить обратное FFT. Но когда мы перемножим - не все элементы этого массива уже будут меньше модуля - что с этим делать? просто брать их по тому же модулю и считать обратное? Если я так делаю, у меня начинает все неправильно работать(из-за таких переполнений), числа длиной около тысячи знаков умножаются правильно только при базе 10 или 100, что очень печально.
Во-вторых - пусть после FFT у нас получилось: FFT(A) = (1, 3), FFT(B) = (4, 0). После того как мы скалярно перемножим, у нас получится (4, 0), и после обратного FFT мы получим тот же B. Такое бывает(может я не понял чего-то в теории), и если да - что делать?
И последнее - модуль в статье на e-maxx подходит для случая, когда в векторе не более 2^20 элементов. Вряд ли мне понадобится больше - но вопрос - а где-то есть готовые последовательности типа "модуль - образующий элемент" ?. На oeis - только для небольших чисел, можно конечно прочитать и познать еще один алгоритм - но очень уж лень :)
Кстати - мне кажется, или на e-maxx единственная статья про целочисленное БПФ в интернете? Если есть еще что почитать(на русском или английском), очень буду рад ссылкам.
upd: еще на всякий случай код
Хочу извращений выучить функциональный язык. Но я не представляю, как юзать всякие фишки функционального программирования. Не могли бы назвать кого-нибудь, пишущего на haskell, я бы смотрел их код после контеста и познавал ФП.
Не подскажете, вообще для студентов проводятся какие-то личные олимпиады? Особенно интересует программирование(хотя по нему личных контестов итак полно), математика и физика.
Где можно поискать разборы задач топкодера? А то задачи в первом диве интересные, но как их решать часто неясно(особенно третью :) ). И если нигде, может топовые кодеры возьмутся за это полезное дело?
UPD: извиняюсь, поторопился. Уже нашел.
Может кто подскажет тогда, как по-английски "Разбор задач"?
Доступны окончательные результаты. Вот, видимо, те, кому дадут 1 диплом.
| Гомель, Сборная #1 (Артюхов, Демидко, Короткевич) | +1 162:10 | + 36:05 | + 49:43 | + 13:20 | + 20:57 | +1 128:44 | +2 139:32 | +1 119:49 | + 268:55 | + 3:57 | +2 251:02 | 11 | 1328 | 1 |
| Москва, СУНЦ МГУ #2 (Лифарь, Пахарев, Шлюнкин) | . | + 55:05 | + 83:03 | + 28:43 | +1 182:08 | -8 | + 204:50 | +1 116:33 | . | + 10:26 | . | 7 | 718 | 2 |
| СПб, Сборная #1 (Мукосеева, Пышкин, Суворов) | -6 | + 47:35 | +5 228:19 | + 38:21 | + 63:57 | . | + 248:56 | + 178:15 | . | + 12:30 | . | 7 | 914 | 3 |
| Мозырь, Сборная #2 (Коноплич, Малашенков, Собин) | -6 | + 76:51 | +5 250:46 | + 27:15 | + 114:49 | . | + 149:26 | + 224:14 | . | + 10:50 | . | 7 | 950 | 4 |
| Москва, СУНЦ МГУ + Школа 57 + Школа 1189 (Ахмедов, Григорьев, Иванов) | . | + 94:10 | +2 144:32 | +2 46:14 | + 79:20 | . | +3 281:19 | + 190:50 | . | + 8:03 | . | 7 | 982 | 5 |
| Саратов, ФТЛ #1 (Бабанин, Дубинин, Кунявский) | . | + 24:50 | + 107:55 | + 37:35 | + 60:03 | . | + 293:51 | +11 291:38 | . | + 11:05 | . | 7 | 1043 | 6 |
| Москва, Центр «Дистантное обучение» (Лахтанов, Смирнов, Сурин) | -10 | +1 110:30 | +6 181:31 | + 60:32 | + 153:28 | . | +2 173:24 | + 234:19 | . | +2 25:49 | . | 7 | 1156 | 7 |
| Алматы, РСФМСШИ #1 (Алдан, Аттапханов, Сагатай) | . | + 37:00 | +8 209:21 | + 28:20 | +1 120:30 | . | +5 193:22 | +4 284:41 | . | + 7:02 | . | 7 | 1238 | 8 |
| СПб, Сборная #2 (Грановский, Егоров, Коротеев) | . | + 45:00 | +5 212:36 | +1 29:38 | +1 278:34 | . | + 230:35 | +3 246:13 | . | + 12:57 | . | 7 | 1252 | 9 |
| Москва, СУНЦ МГУ #1 (Великанов, Тимин, Фадеев) | + 137:35 | + 75:50 | +9 285:35 | +1 30:57 | -7 | . | +2 265:09 | +2 215:30 | . | + 16:12 | . | 7 | 1303 | 10 |
А вообще там очень удобно - наверное, 1 диплом 7 - 11(!) задач, 2 диплом - 5-6 задач, 3 диплом - 4 задачи.
Гена, как видите, обогнал всех как минимум на 4 задачи :)
Тут недавно один добрый человек сделал парсер топкодерского календаря в гугл, Code Jam тоже интегрируется с гуглом. Предлагаю добавить это и к codeforces :) Как минимум, полезно тем что можно настроить, например, за два часа до начала напоминание о контесте)
Можно ли добавить оценку решения участника(после контеста, когда можно исходный код смотреть). Я, например, сейчас изучаю python и мне интересны различные(и, желательно, лучшие) реализации решений на нём. Ну я чисто физически просмотреть все решения не могу, естественно, поэтому можно было бы добавить оценку решения, или несколько, как:
-реализация
-эффективность(время, память)
-использование возможностей языка
ну и т.д)
-количество строк(слов и т.д) в решении(это можно даже автоматически делать)
Как вам такая идея?)
что-то проглючило и создалось 2 поста. можно как-нибудь это удалить?
Наверное, большинство после соревнований(codeforces,topcoder) спрашивают друг друга "ну как написал?" и выискивают в рейтинговой таблице. Так почему бы не упростить задачу - добавить список слежения за некоторыми никами. Заходишь - и видишь статистику только по ним. Наверное, многим бы такая фича понравилась =)
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 26.04.2024 17:04:21 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
