Контест получился интересным, без засилья геометрических задач. Расстроила кривизна чекера в задаче С.
H сдал после контеста алгоритмом с асимптотикой O(n * log(n) + 50 * n * f), где f - сложность поиска в хеш-таблице. Пришлось использовать IO через fread / fwrite (scanf / putchar ловили TL). Никто больше не сталкивался с подобной проблемой?
H сдал после контеста алгоритмом с асимптотикой O(n * log(n) + 50 * n * f), где f - сложность поиска в хеш-таблице. Пришлось использовать IO через fread / fwrite (scanf / putchar ловили TL). Никто больше не сталкивался с подобной проблемой?
В общем, делал так.
Клал в hashtable тройки чисел - записи туземцев.
for(i = 0; i < N; i++)
for (j = i + 49; j > i; j--)
if ((a[j], a[i], j - i + 1) in hashtable)
красим отрезок [i, j]
break;
покраска делается с помощью дерева отрезков. break нужен, чтобы не красить лишнее (улучшает аспимтотику)
50 элементов - это классно! Когда рассуждения дошли до слова "покрасить", мозг перестал думать, а руки начали вбивать дерево :)
А с IO не было проблем?
UPD. По-видимому, именно покраска через дерево, а не напрямую давала TL со стандартным IO
дерево там не нужно, мы красим в один цвет
z[start]++, z[end + 1]--
int cur = 0;
for (int i = 0; i < n; i++) {
cur += z[i];
s[i] = cur > 0 ? '1' : '0';
}
Я тоже 2 часа пихал C из-за чекера (+19). Жаль, что так вышло.
Еще задача D расстроила своей непонятностью, с 3 попытки я угадал, что они от меня хотят.
Расскажите, как нормально решать задачу G? Как некоторые писали ее за 5 минут? Я на последнем часу сумасшедшую фигню запихал.
И было бы неплохо вообще почитать какой-нибудь разбор...
int n; int a[113]; cin>>n; for (int i=0;i<n;i++){ cin>>a[i]; } sort(a,a+n); int b[113]; b[n-1]=0; b[n-2]=a[n-1]+a[0]; for (int i=n-3;i>=0;i--){ b[i]=min(b[i+1]+a[i+1]+a[0],b[i+2]+a[i+2]+2*a[1]+a[0]); } cout<<b[1]+a[1];Решал жадностью
Рассмотрим 2 стратегии:
1) Проводить каждого участника с самым быстрым (т.е быстрый ведет кого-то, потом возвращается, и т.д)
2) Проведем 2х быстрых, вернем второго. Проведем 2х самых медленных, вернем быстрого.
Теперь непосредственно решение - это выбрать момент перехода со 2 стратегии на первую
Хотелось бы узнать "честное" решение задачи E, т.е. без отсечения по времени и всяких волшебных констант в коде. Было бы неплохо с обоснованием :) Сам же загнал в ней "нечестное" решение.
интересно как китаец сдал ее на 13 минуте, то есть через 9 минут после А
Основная идея авторского решения (как я понял) такая:
Для начала предпросчитаем маски покрываемых городов для каждого города. Дальше перебираем следующим образом: для еще непокрытых городов будем выбирать, кто этот город покроет (вместо того чтобы выбирать, берем его или нет). После того как выбрали город, который покрывает нас, сразу пересчитываем маску покрытыя городов за одну операцию or.
Я закодил эту идею. Без всяких отсечений это АС за 0.031. В перебор я передавал маску покрытых городов, город который хочу покрыть, число уже выбранных городов и маску выбранных городов (для сохранения ответа). 66 строк.
Работает быстро, потому что граф лежит на плоскости. Нестрогое объяснение: как бы худший случай, это когда все города, которые нас могут покрыть, находятся на расстоянии ровно R. Но таких городов максимум 6. Если же города ближе чем R, то тогда городов для выбора много. Но! Тогда выбранный город накрывает сразу много других городов.
А из 10 представленных задач 8 было в Вологде.
Как надоумил - сразу заслал.
До этого 2 или три раза её видел.
1.если оба равны нулю, то undefined
2.если кто-то один равен нулю, то error
http://acm.timus.ru/monitor.aspx?id=84
Дорешивание: http://acm.timus.ru/problemset.aspx?space=1&page=9 (с 1820 задачи)
ignore
Правильно ли я понимаю, что эти переменные - начальная точка прогрессии и разность членов?
Тогда вроде надо найти 2 частных производных, приравнять их к 0 и решить СЛУ?
Я сначала заметил, что в первом примере суммы всех членов в данной прогрессии и в приближении совпадают и подумал, что это всегда верно. Никаких других закономерностей не заметилось, поэтому решил написать тернарный поиск по первому элементу. Но wa 6 =( Потом просто загуглил метод наименьших квадратов и вбил формулы.