Напоминаю, что раунд начнется через полчаса. Первая тысяча проходит дальше. Ссылка Предлагаю после окончания обсуждать тут задачи, всем удачи!
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.04.2026 02:15:54 (g2).
Десктопная версия, переключиться на мобильную.
При поддержке
Как решалась B large?
Та вроде бфс писали.
Че минусуете, я коды смотрел, у некоторых бфс) Хотя не факт, что он рабочий)
Жадностью
Если бы у нас была одна координата, наверное, можно было набирать двигаться в сторону точки пока мы не перейдём ей, иначе назад. А для 2 координат, какая жадность?
Ну как бы понятно, что можно решать задачу независимо по обеим координатам, разве нет?
_Upd. А. Ну да, лажу написал. Там ведь размер шага меняется. _
А на самом деле жадность действительно работает. Сначала посчитать, сколько нужно шагов, потом — выставлять эти шаги от более длинных к менее длинным (каждый раз выбирая ту из координат, которая больше по модулю).
Тоесть бфс по одной, а потом по второй координате?
я решал так, у меня файл получился большой и система не приняла решение:-(
Да, только надо начинать движение с наибольших по длине шагов. Для двух координат все также. Допустим знаем минимальное количество шагов, которое необходимо сделать. Тогда начиная с последних (наибольших по длине) шагов будем ходить в той координате, чье значение по модулю больше в нужном направлении. Для количество ходов k можно прийти в точку (x;y) если выполняется k * (k + 1) / 2 > = |x| + |y| (т.е. суммарная длина сколько пройдем нам хватит чтобы дойти до точки) и
(т.к. если у одного шага изменить + на -, то конечная четность не изменится). Этого хватает чтобы определить минимальное количество шагов.
ясно, спасибо
Написав перебор, посмотрим, на каких позициях мы сможем оказаться после i-ого хода. Заметим, что после i-ого хода мы сможем дойти до всех клеток внутри квадрата, образованного четырьмя вершинами с координатами
которые при покраске в шахматную раскраску имеют такой же цвет, что и вершины этого квадрата.
Таким образом, мы можем быстро узнать длину минимального ответа. Дальше, нам надо его восстановить. Будем восстанавливать с конца рекурсивно. Мы можем прыгнуть в 4-ых направлениях. Прыгнем в том направлении, при котором сумма модулей координат меньше всего и запустимся рекурсивно от этой клетки.
Вот код
World chart showing
1000 * #Remaining / #Qualification_roundtaken from Google CodeJam statistics page.Chart with
#Remainingonly (colors are not the best)Can anyone tell me whats wrong with my code for problem A which passes the small input, but not the large one? My idea is, that I count for every position the number of substring which could end at this position and sum them all up in the end...
Maybe accumulate is the problem:
vector<int> v(m);return accumulate(v.begin(),v.end(),0);will returnintinstead oflong longtemplate <class InputIterator, class T>T accumulate ( InputIterator first, InputIterator last, T init );accumulate(v.begin(),v.end(),0**LL**);
Thank you, got it!
why the analysis for 1B round hasn't been published yet?
а как на халяву реализовать C? Есть способ проще чем дерево отрезков с проталкиваением?
Я написал sqrt-декомпозицию.
А координаты сжимал? там ведь 10^6 (еще на два умножить ибо со знаком)
Да, сжимал. Вот код: http://pastebin.com/VGHRMmZ8
Или что то другое подразумевалось под сжатием? У меня как раз 2*10^6 и есть. Для GCJ это нормально. За минуту-две успевает посчитать.
Под сжатием координат подразумевается заменение реальных значений на значения поменьше с сохранением исходного порядка значений. К примеру есть у тебя q=10^5 запросов L[i], R[i] к дереву отрезков на интервале [1..10^6]. Понятно, что для обработки запросов достаточно q * 2 т.е. 2 * 10^5 ячеек в дереве отрезков. Можно посортировать массив всевозможных значений L[i], R[i] сделать значения уникальными, и заменить L[i], R[i] на индекс соответствующего значения в сортированном уникальном массиве. тогда будет достаточным q * 2 ячеек в дереве отрезков
Внимание вопрос: что ты называешь сжатием координат?
Я называю сжатием координат именно то, что ты сейчас описал.
Меня просто смутила фраза "там ведь 10^6".
Упс, не заметил. Ты мапой сжимаешь а не сортировкой :)