OpenCup 25.11 - Codeforces

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

Ох я себе слабо представляю как на контесте такую закономерность искать, я вон дома времени валом потратил) Может кто-то решил аналитически? Или там жутчайшая математика?)

→ Ответить

natalia

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

Мы сгенерировали все "умирающие" последовательности длиной до 23. Сначала обратили внимание на их количества. Для нечетных n они получаются 2 8 2 128 2 8 2 32768 ... Ясно, что все зависит от степени 2, которая входит в n + 1. Дальше посмотреть сами последовательности для 3 и 11 (которых по 8 штук) и понять, как одни получаются из других. Для 7 и 23 закономерность подтверждается. Ничего сложного. Мы на этапах Кубка и не такие закономерности находили.

→ Ответить

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

Спасибо, примерно так же рассуждал, только попутно уходил в сторону от ответа постоянно

→ Ответить

ilyakor

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

У нас вроде бы "аналитически". Посмотрим на 2 шага процесса — понятно что на нечётные позиции результата влияют только нечётные позиции исходного состояния, то же самое для чётных. Посмотрим на чётные и нечётные позиции отдельно: для чётных получаем ту же самую задачу в 2 раза меньшего размера, для нечётных — почти ту же самую; так что если разобраться с нечётными — задача решена. Как с ними в точности разобраться — не знаю, у нас это сделал Jacob (но он это сделал очень быстро, так что наверное что-то несложное).

→ Ответить

Petr

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

+13

Для нечётных надо сделать один ход, и они станут чётными.

→ Ответить

Endagorion

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

Сделаем бесконечную строку v = ... + 0 + s + 0 + reverse(s) + 0 + s + 0 + reverse(s) + 0 + .... Если за s_i и v_i обозначить соответствующие строки после i шагов, то v_i = ... + 0 + s_i + 0 + reverse(s_i) + 0 + ...

Легко доказать по индукции, что $\text{[math]}$ . Поскольку v периодическая с периодом 2|s| + 2, можно взять достаточно большую степень двойки k (например, k = 2|s| + 3) и проверить, что в v_2^k есть хотя бы одна единица. Если использовать предыдущее равенство, это делается за O(|s|).

→ Ответить

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

+10

WA1 в M. Код:

#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;

int main()
{
	int Kx, Ky, Cx, Cy;
	while(scanf("%d", &Kx)>0)
	{
		scanf("%d", &Ky);
		scanf("%d%d%d%d", &Kx, &Ky, &Cx, &Cy);
		printf("%d\n", max(abs(Cx-Kx), abs(Cy-Ky)));
	}
	return 0;
}

Как это понимать?

→ Ответить

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

← Rev. 3 →

Код даёт ОК на g++0x. На другом — ВА1.

→ Ответить

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

← Rev. 2 →

Спасибо. Это же какие кривые тесты в этой задаче... Мало того, что не сдал халяву, так и ещё время потратил впустую.

→ Ответить

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

Так всё же в чем тут ошибка?

→ Ответить

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

Возможно из-за функции модуля. Стандартный все считает в даблах. А у вас потом еще и тип приводится к целому. Попробуйте отослать с самописным модулем.

→ Ответить

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

Стандартный все считает в даблах.
Неправда, std::abs имеет несколько перегрузок.

→ Ответить

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

Да нет, в интах он считает, есть перегрзка для лонг дабла и коплексных, а вот для лонг лонга нет.

→ Ответить

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

← Rev. 3 →

Хорошо. Тогда прошу кого-нибудь объяснить, почему зашел вот такой код, почти полностью совпадающий с вашим

#include <cstdio>
#include <cmath>
#include <iostream>

using namespace std;

#define abs(x) ((x) < 0 ? -(x) : (x))

int main()
{
	int Kx, Ky, Cx, Cy;
	while(scanf("%d", &Kx)>0)
	{
		scanf("%d", &Ky);
		scanf("%d%d%d%d", &Kx, &Ky, &Cx, &Cy);
		printf("%d\n", max(abs(Cx-Kx), abs(Cy-Ky)));
	}
	return 0;
}

UPD. И еще. Было несколько раз, что код, в котором я юзал стандартный модуль с интами, просто не компилился на сервере. А в логах было написано, что у него нету функции для вызова такой штуки.

→ Ответить

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

Вставляем любую некомпилирующуюся строку после цикла, и смотрим варнинг компилятора на сервере: 002841.cpp: In function 'int main()':
002841.cpp:13:45: warning: format '%d' expects argument of type 'int', but argument 2 has type 'double' [-Wformat]

Т.е. int abs(int) это не стандарт?

→ Ответить

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

← Rev. 2 →

В референсе написано, что у него действительно есть несколько перегруженных функций для модуля. Но вот как-то работает это криво. Я думаю он берет первую, которую видит и приводит типы. Такой вот выстрел себе в ногу, ведь язык допускает такую возможность. Гарантировать правильность моего объяснения я не могу, но это единственный логичный вывод, который я могу сделать.

UPD. Порылся в исходниках cmath. Вот начало библиотеки, и сначала там действительно идет модуль для вещественных чисел. Честно говоря, для интов модуля я там не нашел вообще. Возможно он где-то там зарыт в шаблонах, но как-то совсем на это не похоже. Нужна консультация более прошаренного специалиста :)

→ Ответить

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

Ага, причем на g++0x варнинга нет. Кривой g++?

→ Ответить

andreyv

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

Если в коде вставить

#include <cstdlib>

, где объявлен abs(), то предупреждение пропадает. Сюрприз!

→ Ответить

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

Ну в этом как раз нет нестыковок, там все-таки другие реализации большой кучи функций. Увы, в этом плане g++ действительно кривоват. Такая же фигня, кстати, со стандартным возведением в степень. Была ситуация, когда на больших числах порядка 10^15, pow мне говорил: "Не, чувак, тут тебе не нужна плюс единичка, я ее выкинул". Точнее он этого не говорил, пришлось выпытать это у него. Сопротивлялся он долго и упорно, поэтому остался осадок. Теперь стараюсь такие стандартные функции, пришедшие из C, не использовать.

→ Ответить

andreyv

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

pow() работает с числами с плавающей точкой, какие к нему вопросы? Кстати, для целочисленного возведения в степень в GCC есть нестандартная функция __gnu_cxx::power() (<ext/numeric>).

→ Ответить

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

К нему вопросов никаких :) А про то, где находится интовый abs, спасибо :)

→ Ответить

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

← Rev. 2 →

Спасибо, действительно неприятный сюрприз. В VC++ интовый abs объявлен в cmath, я думал и в g++ так. Оказалось, что в cmath g++ объявлены abs'ы для вещественных аргументов, а в cstdlib для целых (в том числе и для long long).

→ Ответить

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

Вот мне тоже интересно, написал аппеляцию, мне ответили:
Первый тест совпадает с тестом из условия.

→ Ответить

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

Как решать D?

→ Ответить

KADR

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

+11

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

Итак, у нас фиксирован правый конец (пусть он имеет индекс R) и мы уже обработали все числа, которые стоят слева от него. Для каждого числа возьмем последние 2 его вхождения — пусть у числа X позиции вхождений x1 и x2 (x1 < x2). Тогда на место x1 запишем -1, а на место x2 запишем 1. На месте всех остальных чисел у нас будут стоять нули. Тогда утверждается, что существует нудный подотрезок тогда и только тогда, когда суффикс подмассива [0,R] с минимальной суммой имеет нулевую сумму.

Итак, нам нужно уметь делать изменение в точке, а также для отрезка [0,A] быстро находить суффикс с минимальной суммой. Это можно сделать обычным деревом отрезков. Сложность решения O(NlogN).

→ Ответить

it4.kp

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

Если отрезок интересный, то на нем должен быть уникальный элемент. Он разобьет отрезок на две меньших подзадачи. Сложность только в том как найти уникальный. Я для этого передавал в рекурсию, кроме концов отрезка, map, где хранил сколько раз каждый элемент входит в данный отрезок, а также очередь с уникальными элементами. Получили две подзадачи. Выбираем меньшую и для нее map считаем в лоб, проходя по всем элементам. Также проходя по всем элементам меньшего подотрезка обновляем map для большего. Итого вроде получается O(Nlog^2N)

→ Ответить

Hohol

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

← Rev. 2 →

Мы такое сдали:

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

Будем связывать подстроку s[l..r] с клеткой на плоскости с координатами (l,r).

Пусть L[i] — индекс ближайшего слева символа такого же как s[i] (или -1, если такого нет), а R[i] — индекс ближайшего справа (len(s), если такого нет).

Для каждой позиции исходной строки найдем множество подстрок, на которых символ этой позиции встречается ровно один раз. Искомое множество для s[i] — подстроки, начинающиеся на [L[i]+1; i] и заканчивающиеся на [i; R[i]-1]. Получился прямоугольник из клеток для каждой позиции. Строка не является нудной, если объединение таких прямоугольников покрывает все множество подстрок (которое выглядит как лесенка). Найдем площадь объединения этих прямоугольников. Если она равна len(s)*(len(s)+1)/2 — строка не нудная.

→ Ответить

oversolver

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

а J только за MlogN решалась?

→ Ответить

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

У нас решение за O(N + M). Выбираем начальную лабораторию. Далее, для каждой работы определим сколько еще зависимостей надо выполнить перед ней (напрямую связанные с ней). Те, у которых зависимостей нет, кидаем в одну из двух очередей, в зависимости от номера лаборатории. Затем, пока очередь с текущей лабораторией не пуста, достаём из неё работу, выполняем, и обновляем количество зависимостей у соседей. Если у соседа стало 0, добавляем его в соответствующую очередь. Как только очередь стала пустой, меняем лабораторию и продолжаем.

→ Ответить

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

Придумали так же, только с деком, но не придумали как решать для кучи компонент связности. Расскажите, пожалуйста, как это сделали вы.

→ Ответить