|
+8
md5: c8d468eb0d7c0d762071e74b92c8e2ef |
|
-3
Вы мне не верите?? %)
|
|
+29
Видимо речь идёт про меня. Всё дело в том, что слово HACKERCUP я произношу как НАХЕ?КАП (все буквы разные) поэтому просто взял минимум по соответствующим буквам, такое бывает в 2 часа ночи. А во 2-ой я дважды i и j перепутал, у меня вообще никаких идей нет почему она прошла :). |
|
0
Эта функция реализована даже в g++ 4.4. Проблема в том, что она невидимая (из-за _GLIBCXX_HAVE_BROKEN_VSWPRINTF = 1) под многими (а может и под всеми) портами g++ под Windows.
|
|
+24
Это баг GNU С++ 4.6.0, минимальный нерабочий код - http://pastebin.com/nE2UxpWW В версии 4.6.1 этого бага уже нет. UPD: Вывод: 4 7 4 7 |
|
0
My solution passes your test and works on all other tests Proof: 8·109 / (3·109) < 4 :) |
|
0
У меня отличие в том, что когда зафиксировали 2ух обезьян, получаем систему линейных уравнений относительно {p, q2}: p · xi - q2· xi2 = yi p · xj - q2· xj2 = yj Проверяем q2 > = 0, после чего подставляем остальных обезьян в уравнение. Это всё делается в целых числах, чтоб не было проблем с переполнением брал по разным простым модулям. |
|
+21
Правильное решение не нужно заталкивать. По А проходит такое деоптимизированое решение http://pastebin.com/xbgWHtKf с чтением выводом через cin/cout, использованием STL и криво вычисленными векторами длины R.
|
|
+6
Оптимизатор генерирует бесконечный цикл (без -О2 код работает):
L5: .p2align 4,,4 jmp L5 |
|
+6
При нормировании суммой коэффициентов, чтобы максимизировать рейтинг страны, достаточно оставить самого сильного участника. |
|
+5
Умножение на (1-K) сохраняет все качества оригинальной формулы и добавляет новое – похожесть на рейтинг участников (если участников больше чем несколько). При умножении на (1-K)/(1-K^N) оптимальной и выигрышной стратегией, например для Беларуси, будет поменять страну всем кроме Гены. А если без шуток, то часть формулы /(1-K^N) – как бы намекает, что чем меньше участников, тем лучше для рейтинга страны или города. |
|
+13
Поэтому нужно домножить на (1-K) = 0.25
|
|
+5
А когда деков сто тысяч??
Мне, к примеру, всегда хватало одного дека... |
|
+10
Each connected component in the graph has exactly one cycle. Pick any edge from the cycle and remove it from the graph, now we should consider two cases: a picked edge is in the answer and it isn’t there. Both cases can be easily solved with dp on tree. |
|
0
А как искать поток диницей за e*sqrt(v) ?
|
|
0
==================================================== Ну всё-таки международный стандарт С++ существует. Вижак глотает vector<vector<int>> потому что это фишка нового стандарта C++0x, GCC 4.3+ его также глотает с ключом “–std=c++0x”. По поводу конструкторов, то что я писал – это самая настоящая глупость. Когда мы пишем a = b; для старого значения a вызывается деструктор, а после – оператор копирования, и никак иначе! Тогда если объекты не будут инициализированы во время объявления, для неинициализированных значений будут вызываться деструкторы при первом же присвоении. А long double по стандарту не меньше чем double (а double не меньше чем float), и может на разных компиляторах или архитектурах отличаться так как implementation-defined. PS: Баг исправили, код товарища SkorKNURE получает Полное решение . |
|
0
Всё-таки это баг GCC.
|
|
0
Длинное доказательство :), но даже здравый смысл говорит о том что вы правы! К сожалению, как я уже написал, проблема не в этом, здешний GCC вызывает конструкторы не POD-типов в локальных массивах. |
|
0
Let discuss it in a private order, I’ve sent some questions to you. Has anyone else had a problem with updating MinGW on Dev-CPP? |
|
0
И всё-таки, пока не поздно, я перейду на белую сторону. Там дело не в конструкторе, и не в массивах (чтобы там не писали, но запуском можно убедиться, что конструкторы и деструкторы вызываются для элементов локальных массивов). Возможно, это глючная сборка MinGW (которую я порекомендовал для языка C++0x), возможно проблема с GCC 4.6 (я это проверю как перегружусь), а может мы все плохо знаем C++, и этому странному поведению есть разумное объяснение, которое нужно найти. |
|
0
Пруфлинк? И тот клас что вы написали, между прочим, является POD.
|
|
+5
When declaring a regular array of local scope (within a function, for example), if we do not specify otherwise, its elements will not be initialized to any value by default, so their content will be undetermined until we store some value in them. The elements of global and static arrays, on the other hand, are automatically initialized with their default values, which for all fundamental types this means they are filled with zeros. |
|
+5
Look below (I posted the answer in wrong branch :( )
|
|
+7
In C++0x you don’t need to put spaces between right angle brackets >.
you could initialize containers in convenient way
there is auto-typed variables
lambdas
range for statement
and as you mentioned there is unordered_map (unordered_set) which is a standardized hash table.
Also some useful functions were added to <algorithm>, <functional> and other header files. See 1, 2 for more details. |
|
+5
У всех типов в С++ есть конструктор, в том числе и у int. Пример для наглядности: cout << int() << endl;
|
|
0
Имеется ввиду %lld для языка C++0x, хотя если добавить ключ -D__USE_MINGW_ANSI_STDIO=0 то ситуация изменится, и действительно будет использоватся ввод/вывод библиотеки msvcrt.dll. UPD: и всё-таки со scanf'ом оно не работает, так что %lld не следует использовать. |
|
0
Спасибо! Из перечисленного не работает for each и лямбда-выражения. Кстати, поддержка C++0x в GCC пока ещё имеет статус эксперимента, возможно, лучше сделать его отдельным языком, ведь теоретически может возникнуть ситуация, когда ключ "-std=c++0x" изменит вердикт проверяющей системы? И возможно ли добавить GCC 4.6, ведь на самом деле я создавал тему из-за того что недавно вышел Release этого компилятора, и в нём почти весь C++0x уже реализован. |
|
0
не туда. |
|
0
… и без того самый запутаный язык программирования … :) Как было вами замечено, из C++0x не выкинули ничего что было в C++, а значит мне не нужно учить ничего нового чтоб писать программу на C++0x. Кстати, после вашего поста, список языков программирования которые я хочу выучить увеличился на 2, теперь он состоит из 7 языков. |
|
0
Согласен, но вспомним как оперативно был добавлен F# и Haskell (http://codeforces.ru/blog/entry/393). А поставить GCC 4.6 значительно проще. |
|
0
А как по мне, так это способ превратить СЗЯП в C# или Java :), по стандарту там даже сборщик мусора как-то прикрутили. |
|
0
http://blogs.msdn.com/b/vcblog/archive/2010/04/06/c-0x-core-language-features-in-vc10-the-table.aspx Судя по таблице, кое-что уже было реализовано в VC9 (=Visual C++ 2008, ведь так?) |
|
+22
Я как бы знаю только задачу которую готовил я, про то что были другие задачи впервые слышу :). Надеюсь, никто не обидится если я приму участие (свою задачу даже читать не буду). |
|
+10
Ваш алгоритм работает за квадрат на тестах такого вида: 2 4 6 8 ... 2n 1 3 5 7 ... 2n-1 |
|
+23
Решение до которого все додумались – это для каждой полоски за O(N log *) посчитать бинарным поиском ответ. Это решение базируется на том факте, что мы можем для полоски за O(N) проверить больше ли ответ на ней чем какое-то значение. Добавим в тупое решение такую штуку, перед тем как запускать бинарный поиск, просто проверим за O(N) можем ли мы улучшить наш текущий ответ, если можем, то только тогда запускаем бинарный поиск. Утверждаю, что если все полоски случайно перемешать, то ожидается log_2 N улучшений ответа, а следовательно и запусков бинарного поиска. Так происходит потому, что случайный элемент последовательности будет примерно медианой, а все меньшие элементы отбрасываем, как результат размер последовательности на каждой такой итерации сокращается вдвое. |
|
0
А у меня решение O(N^3 + N log N log *), авторы наверное про него не знают?
|
|
0
Алгоритм, о котором я говорю, и который есть в книге Гасфилда "Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология" стр. 253-255, находит не более O(N· logN) промежутков позиций, каждая из которых является серединой тандемного повтора с определённой для промежутка длиной. Если у вас есть такие промежутки, наверное не составит труда их обьеденить, и за константу отвечать на запрос, верно? |
|
0
Как бы есть алгоритм со сложностью O(N· logN) для нахождения всех тандемных повторов (даже если их порядка N2). Находим все тандемные повторы этим алгоритмом, назовём это стадией прекалка, далее на любой запрос вида проверить является ли i серединой тендемного повтора можно отвечать за O(1).
|
|
0
Читайте внимательнее, речь в том, что вы бинпоиск не запустите на описанном тесте (знак в вершинах ломаной одинаковый, и без разницы проверять с EPS или без), и даже если бинпоиск запустить, то внутренняя проверка даст фейл без EPS. |
|
+3
Если Гарри и мяч стартуют из одной точки с одинаковой скоростью, по вашему ответ NO (на концах отрезка ведь знаки одинаковые)? Даже если вы запустите бинарный поиск, то боюсь, без EPS проверка выльется в X > X, с неточно вычисленными X в обеих частях. Чтоб честно убрать EPS из того условия, нужно ещё проверить не совпадают ли точки старта. В разборе даже намёка на это нет, надеюсь, авторское решение проходит тест с одинаковым стартом. |
|
+2
Остаётся добавить эти тесты в финальный тестсет. (Или это тоже уже реализовано?) |
|
0
По задаче C if (currentTime + addTime > distance / potterSpeed - EPS) Если убрать здесь EPS, то решение имеет большой шанс упасть на таком тесте 1 0 0 0 1 1 1 1 1 0 0 0 PS: моё полное решение на таком тесте падает. |
|
+6
Действительно, как написано в GCC FAQ знаковое переполнение не должно никогда случаться, а если случилось то падает alsa, форматируется диск, вобщем undefined behaviour в программе ошибка. На предмет переполнения следует проверять до того как оно случится, потом будет поздно.
|
|
0
Возможно вы правы, тогда у меня есть ещё один пример
int f(int x) { return (int)(x * 0.33333333333333333333333); } |
|
0
На Windows также "1024 == 1024" если компилировть 64-битным gcc (или старым версии 3.4.1)
|
|
0
Maybe on Ubuntu 10.10 x86_64 gcc generates x64-binaries. Could someone run it on 32-bit linux? On mingw-w64 it also works fine. |
|
+5
Вот проще пример. Не работает с g++ 4.5 -O2 #include <cstring> #include <cstdio> int f(int x) { return 1 << x; } int main() { for (int i = 0, j = 42; i < 1000000; ++i) if (!memcmp(&i, &j, sizeof(int))) printf("%d == %d\n", f(i), f(j)); return 0; } В данном примере f(j) вычисляется на этапе компиляции(оптимизации), f(i) как и memcmp(&i, &j, sizeof(int)) - во время выполнения. Оптимизатор думает что 1 << 42 = 0, а процессор думает что 1 << 42 = 1024. |
|
0
Верно, вот только максимальный разрез это NP-полная задача даже с неотрицательными рёбрами
|
|
0
для отсортированых по площади (или по паре) конвертов функция вложености не монотонна, а значит бинарный поиск работать не будет. чтоб было наглядно, вот пример: # ## ### ## ## ##### ### ### ### |