Привет, сообщество CodeForces!

Недавно вспомнил одну интересную задачу на C++. Если кратко: можно ли написать такие функции action и cond так, чтобы следующие куски кода работали по-разному:

// Snippet #1:
action();
while (cond()) {
    action();
}

// Snippet #2:
do {
    action();
} while (cond());

Более формально: у вас есть следующие три файла:

#include <iostream>

bool cond() {}

void action() {
    std::cout << "Action" << std::endl;
}

#include "common.h"

int main() {
    action();
    while (cond()) {
        action();
    }
    return 0;
}

#include "common.h"

int main() {
    do {
        action();
    } while (cond());
    return 0;
}

Вам разрешено менять лишь common.h. Сделайте это так, чтобы слово Action напечаталось разное количество раз для запусков main_while.cpp и main_do_while.cpp.

Одно из возможных решений (настоятельно рекомендуется сначала подумать самостоятельно!):

#include <iostream>

bool cond() {
    #define do if(true)
    static int attempt = 0;
    attempt++;
    return attempt % 2 != 0;
}

void action() {
    std::cout << "Action" << std::endl;
}

Скидывайте свои решения в комментариях, не забывайте прятать под спойлеры! Было бы интересно посмотреть на более умные решения (например на такие, которые будут применимы в любом языке, где есть аналоги while и do-while).

Привет, сообщество и с наступающим Новым Годом!

Решая одну задачу, придумал интересный макрос, позволяющий сортировать объекты по определенному полю. Получается очень лаконично, но требует C++11. Собственно, макрос:

#define by(T, x) [](const T& a, const T& b) { return a.x < b.x; }

Использование:

struct Item {
    int a, b;
};

sort(arr, arr + N, by(Item, a));

Полный пример: http://pastebin.com/Cp5ZkwE4.

Всем счастливого нового года!

UPD: В комментариях указали, что C++14 позволяет еще короче:

#define by(x) [](const auto& a, const auto& b) { return a.x < b.x; }
sort(arr, arr + N, by(a));

Привет, CodeForces!

Время от времени на CodeForces появляются вопросы о центре, радиусе и диаметре графа (смог нагуглить только о дереве, хотя было больше). В этом топике даны определения этим понятиям а также описаны алгоритмы для их нахождения.

Задача: дан не взвешенный неориентированный граф G = (V, E), где V это множество вершин, а E — множество ребер. Необходимо найти его радиус, диаметр и центр.

Определим d_i, j как кратчайшее расстояние между парой вершин . Тогда диаметр графа определяется как максимально возможное среди всех кратчайших расстояний между парой вершин:

Также введем понятие эксцентриситета вершины как максимальное расстояние от вершины до какой-либо другой:

Зная эксцентриситет всех вершин, можно определить и радиус графа, как минимальный из них:

Сразу можно заметить, что диаметр графа это максимальный эксцентриситет в графе, т.е:

Центром графа назовем все вершины с эксцентриситетом, равным радиусу графа:

Определения даны и в голову приходит тривиальный алгоритм для нахождения центра, радиуса и диаметра для произвольного графа при помощи алгоритма Флойда-Уоршелла:

const int   N = ...; // Количество вершин в графе
const int   INF = ...; // Бесконечность
int         d[N][N]; // Дистанции в графе
int         e[N]; // Эксцентриситет вершин
set <int>   c; // Центр графа
int         rad = INF; // Радиус графа
int         diam; // Диаметр графа

// Алгоритм Флойда-Уоршелла
for (int k = 0; k < N; k++) {
    for (int j = 0; j < N; j++) {
        for (int i = 0; i < N; i++) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}

// Нахождение эксцентриситета
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        e[i] = max(e[i], d[i][j]);
    }
}

// Нахождение диаметра и радиуса
for (int i = 0; i < n; i++) {
    rad = min(rad, e[i]);
    diam = max(diam, e[i]);
}

for (int i = 0; i < n; i++) {
    if (e[i] == rad) {
        c.insert(i);
    }
}

Теперь немного изменим постановку задачи: допустим, что граф G является деревом. Для дерева несложно доказать следующий факт: количество вершин в центре дерева равно одному или двум.

На CodeForces когда-то слышал следующий алгоритм для нахождения центра дерева: с помощью BFS-а из любой вершины (обозначим ее как v1) найти самую удаленную от v1 вершину (обозначим как v2), затем запустить BFS из v2, выбрать любую самую удаленную от v2 вершину (пусть будет v3). Вершина(-ы) на середине пути между v2 и v3 образуют центр графа, расстояние между ними — диаметр. Радиусом же будет половина диаметра, округленная вверх: (diam(G) + 1) / 2. Реализацию этого алгоритма здесь приводить не буду, так как она мне показалась несколько громоздкой. Вместо этого приведу другой алгоритм, который мне показался проще в реализации.

Теорема: Пусть L — множество всех листьев графа. Если |V| ≤ 2, то L является центром графа, иначе можно удалить все листья и центр графа не изменится:

Эта теорема приводит нас к следующему алгоритму: будем удалять листья дерева, слой за слоем, пока не останется  ≤ 2 вершин. Эти вершины и будут центром графа. Реализация данного алгоритма очень похожа на поиск в ширину:

const int   N = ...; // Количество вершин в графе
int         maxlevel = 0; // Уровень, на котором будет расположен центр графа
int         level[N]; // Уровень вершины
int         degree[N]; // Степень вершины
int         g[N][N]; // Матрица смежности
set <int>   c; // Центр графа
queue <int> q; // Очередь для алгоритма

// Начинаем с листьев
for (int i = 0; i < N; i++) {
    if (degree[i] == 1) {
        q.push(i);
    }
}

while (!q.empty()) {
    int v = q.front();
    q.pop();

    // Удаляем лист и пытаемся добавить его предка
    for (int i = 0; i < N; i++) {
        if (g[v][i]) {
            degree[i]--;
            
            if (degree[i] == 1) {
                q.push(i);
                level[i] = level[v] + 1;
                maxlevel = max(maxlevel, level[i]);
            }
        }
    }
}

for (int i = 0; i < N; i++) {
    if (level[i] == maxlevel) {
        c.insert(i);
    }
}

Нетрудно доказать, что после исполнения данного алгоритма, центр дерева будет во множестве c, и rad(G) = (diam(G) + 1) / 2.

Задачек на порешать сходу не нашел, так что если знаете — ждем в комментах.

Задачки по теме:

• IOI2013 Dreaming
• 456E - Цивилизация
• 592D - Супер М
• Задача F отсюда

Спасибо за внимание, насчет опечаток просьба писать в личку.

519A - A и B и шахматы

Автор: BekzhanKassenov

В этой задаче необходимо было найти чья шахматная позиция сильнее.

Решение: Пробегаемся по всей доске, складывая веса фигур игроков, и в конце выводим ответ.

Асимптотика: O(n²), где n — длина стороны доски (в этой задаче — 8)

Код: 10083191

519B - A и B и ошибки компиляции

Автор: ADJA

В этой задаче вам было дано 3 массива. Второй содержал все элементы первого, за исключением одного, третий массив содержал все элементы второго, за исключением одного. Необходимо было вывести удаленные элементы.

Решение: Я опишу простейшее решение этой задачи: Обозначим сумму элементов в первом, втором и третьем массиве как a, b и c соответственно. Ответом будут числа a - b и b - c

Также существуют множество других решений, использующих map, xor и прочее.

Асимптотика: O(N)

Код: 10083248

519C - A и B и командная тренировка

Автор: ADJA

В этой задаче вам необходимо было поделить n опытных участников и m новичков на команды.

Решение: Обозначим команды с 2 опытными участниками и 1 новичком как type1 и команды с 1 опытным участником и 2 новичками как type2. Зафиксируем количество команд type1 как i. Их количество не превышает m. Тогда количество команд type2 равно min(m - 2 * i, n - i). Осталось проверить все возможные варианты i и выбрать оптимальный.

Асимптотика: O(N)

Код: 10083265.

519D - A и B и интересные подстроки

Автор: ADJA

В этой задаче необходимо было найти количество подстрок данной строки таких, что каждая подстрока начинается и заканчивается на одну и ту же букву и сумма весов букв в этой подстроке (кроме начала и конца) равно нулю.

Решение: Обозначим sum[i] как сумму весов первых i букв. Создадим 26 map < longlong, int > -ов, 1 на каждую букву. Пусть в данный момент мы находимся на позиции i и map текущего символа m. Тогда необходимо добавить к ответу m[sum[i — 1]], и sum[i] в m.

Асимптотика: O(Nlog(N)), где N — длина исходной строки.

Код: 10083293.

519E - A и B и аудитории

Автор: BekzhanKassenov

В задаче необходимо было отвечать на следующие запросы на дереве: для заданных пар вершин найти количество вершин, равноудаленных от них.

Принятые обозначения:

dist(a, b) — расстояние между вершинами a и b.

LCA(a, b) — наименьший общий предок вершин a и b.

depth[a] — расстояние от корня дерева до вершины a.

size[a] — размер поддерева, корнем которой является вершина a.

На каждой картинке вершины, покрашенные в зеленый цвет — вершины из ответа, вершины, покрашенные в синий цвет — вершины из запросов.

Препроцессинг: Для начала необходимо считать ребра дерева и построить по ним структуру данных для нахождения LCA (удобнее всего использовать двоичный подъем, так как в будущем он понадобится для других целей). Асимптотика: O(NlogN)

Ответы на запросы:

Для каждого запроса необходимо рассмотреть несколько случаев:

1) a = b. В этом случае ответ равен n.

2) dist(a, b) нечетно. Тогда ответом будет 0.

3) dist(a, l) = dist(b, l), где l = LCA(a, b).

Двоичным подъемом найдем сыновей вершины l, которые являются предками вершин a и b (обозначим их как aa и bb соответственно). Ответом будет n - size[aa] - size[bb].

4) Все остальные случаи.

Предположим, что depth[a] > depth[b]. Тогда найдем с помощью двоичного подъема dist(a, b) / 2-ого предка вершины a (обозначим его как p1), dist(a, b) / 2 - 1-ого предка вершины a (обозначим его как p2). Ответом будет size[p1] - size[p2].

Асимптотика: O(logN) на запрос, O(MlogN) на все запросы.

Итоговая асимптотика: O(MlogN + NlogN)

Код: 10083310.

Привет всем!

Сегодня в 21.00 EDT состоится Topcoder SRM 634.

Удачного раунда!

P.S Все никак не могу разобраться с новым интерфейсом их сайта. Как по сайту попасть на описание соревнования, которое я выложил? Я получил его через clist.by

Хотелось бы поздравить всех женщин мира с этим светлым праздником и пожелать им всего наилучшего!

Женщины, вы — незаменимая часть нашей жизни. Будьте всегда рядом с нами.

Всем привет!

30 января, в 6.00 MSK состоится Topcoder SRM 606.

Предлагаю после контеста обсудить здесь задачи.

GL & HF

Здравствуй, сообщество CodeForces!

Иногда бывает так, что удобнее было бы, если бы мы имели возможность обращаться к элементам массива, которые имеют отрицательный индекс. Распространенное решение — узнать минимальный возможный индекс (mn), максимальный возможный индекс (mx) и создать массив размером abs(mn) + mx + 1. В таком случае обращение к -1 элементу превращается в обращение к -1 + abs(mn) элементу. Этот подход имеет несколько недостатков: легко забыть дописать + abs(mn) при обращении к массиву, тяжелее дебагать, код становится громоздким.

Решая задачу с последнего контесте (383D - Antimatter), я придумал похожее, но более удобное решение (в этой задаче нужно было обращаться к отрицательной сумме в динамике). Допустим, вам необходим массив, индексы которого лежат в промежутке [mn; mx] и mn < 0. Заведем массив mem[mx + abs(mn) + 1] и int* dp. В начале программы проинициализируем dp = mem + abs(mn). Готово! Можно обращаться к dp по отрицательным индексам в промежутке [mn, 0).

Пример использования 5771473.

А теперь вопросы:

1) Бояниста ли идея? Существуют ли другие пути обратиться к отрицательному индексу массива?

2) Есть ли подводные камни у этого метода? Чем это может быть плохо?

На этом все, спасибо за внимание.

Здравствуй, сообщество CodeForces!

Открыл я сегодня с утречка КФ, почитать что нового здесь пишут, и увидел это

.

10 из 25 блогов в прямом эфире — какая-то реклама! Ну это ни в какие ворота уже не лезет. На сайте, посвященному спортивному программированию, админами которого являются программисты, висит реклама обуви и прочая дребедень. Тема ведь уже поднималась, но тогда от администрации никаких заявлений/обещаний не последовало. Было бы неплохо услышать хотя бы что-нибудь от администрации по этому поводу.

А пока мои мысли по этому поводу:

1. Давно пора усложнить форму регистрации — насколько я понял, там не требуется даже капчу вводить
2. Сделать прямой эфир модерируемым — помимо рекламы, там периодически появляются всякие неадекватные записи, которые видеть там особого желания нет.
3. Разделить прямой эфир на несколько разделов (например Q&A, анонсы, туториалы), и раздел, в который блог будет опубликован, будет решаться модератором.

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

P.S. С новым 2014 годом!

Здравствуй, сообщество Codefores!

Рад сообщить вам, что 19 октября на тимусе состоится Открытый Чемпионат УрФУ 2013.

Время начала соревнования в вашем часовом поясе вы можете посмотреть здесь.

Предлагаю после контеста обсудить задачи в комментариях.

GL & HF

Здравствуй, сообщество Codeforces!

Через несколько минут стартует очередной этап Открытого Кубка.

Предлагаю обсудить задачи после контеста здесь.

GL & HF!

P.S Если что, начало раунда было перенесено.

UPD Раунд перенесли еще на 15 минут полчаса. Обещают начать в 12.45 MSK в 13.00 MSK

Здравствуй, сообщество Codefores!

Рад сообщить вам, что 3 августа на тимусе состоится интернет-версия XVII Чемпионата Урала.

Время начала соревнования в вашем часовом поясе вы можете посмотреть здесь.

Предлагаю после контеста обсудить задачи в комментариях.

GL & HF

UPD: Напоминаю, что до начала контеста осталось совсем немного.

Привет всем!

Завтра Сегодня, в 12.00 EDT, состоится Topcoder SRM 586.

Предлагаю после контеста обсудить здесь задачи.

GL & HF

Сегодня, во время MemSQL start[c]up, я заметил забавный баг, когда перешел в свой профиль.

Ссылка на скрин — на нем все выделено.

22 июня в 11.00 по Московскому времени состоится Открытое личное первенство УрФУ 2013.

Соревнование будет проводится на тимусе — ссылка на контест. Посмотреть время начала в вашем часовом поясе можно здесь.

Предлагаю после контеста обсудить здесь задачи.

P.S 8к гет удался!

UPD: До начала контеста осталось всего несколько часов!

Здравствуй, сообщество Кодефорсес!

Решая задачу с тимуса, я с ужасом осознал, что не умею писать бинарный поиск. Оказывается у меня есть лишь общее представление о нем, вроде такого:

int l = xxx, r = xxx; // здесь инициализация границ

while (xxx) {// пока условие, зависящее от границ 
    int m = f(l, r); // середина - какая-то функция от левой и правой границ

    if (check(m))  // это я знаю!!!
        l = f1(m); // мы каким-то образом меняем левую границу
    else
        r = f2(m); // мы каким-то образом меняем правую границу
}

//здесь вывод/возвращение/использование ответа (тоже непонятного)

Просмотр кодов, получивших АС по бин. поиску, гугла, википедии тоже утешительных результатов не дал — этих неизвестных параметров там такое многообразие, что непонятно что использовать.

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

Спасибо за внимание!

Здравствуй, сообщество Кодфорсес! Как вы уже догадались, я решил найти источник халявной длинки хочу начать учить Java. Под рукой есть хорошая книга — Г. Шилдт, Java, полное руководство — некоторые основы я (надеюсь) изучил. Но эта книга не нацелена помочь олимпиаднику, потому я здесь, со своими вопросами:

1) Как лучше всего хранить графы в Java? Какие структуры, их комбинации наиболее выгодны для использования?

2) Насколько я знаю, Java — язык довольно медленный. Какие хаки используются для ускорения программ? (Про быстрое чтение я знаю)

3) Допустим мне надо n деревьев отрезков, каждое из которых хранится в массиве (т.е. массив деревьев отрезков). Какой вариант будет более выигрышным — описать класс, в котором будут храниться непосредственно деревья и дополнительная информация, и в нем описывать необходимые методы, или же завести двумерный массив, отдельный (static?) метод и просто передавать туда массив, хранящий дерево, в качестве параметра? Что сожрет больше времени и памяти?

4) Убрано (было непонятно)

5) Насколько применимы в олимпиадах HashSet/HashMap? Есть ли вероятность что они упадут? Где можно прочитать о времени работы их методов? (Гугл особо не помог).

6) Решил скачать IDEA и начать работать в ней. Где можно найти русскоязычную документацию?

На этом все, надеюсь я не сильно вам надоел :). Если у вас есть примеры применения чего-либо — буду очень рад вашим исходникам. Заранее спасибо!

Сегодня читал старый и многим известный пост. Читая комментарии, заметил такую проблему: если пользователь сменил хэндл, а ссылку на него использовали с помощью тега [user:], то этот тег без форматирования вставляется в текст (например здесь). Думаю, стоит что-нибудь сделать.

Решая задачу 251C - Number Transformation, столкнулся с такой проблемой:

Мой код ловит какой-то странный рантайм. То на 3 тесте, то на 9, то ВА 5. Локально рантайм тоже вылетает не всегда. Если убрать поставленные cerr, то рантайм вылетает всегда, с ними — рандомно. Оптимизацию -O2 я не включал.

Идея решения такова: есть функция make, принимающая 2 параметра l и r. Она возвращает минимальное количество ходов, необходимых чтобы из числа r получить число l. Ну и дальше очевидные ифы из кода. Если что не понятно — пишите, объясню.

Здравствуй, сообщество Кодфорсес! В прошлом году я участвовал в олимпиаде, которую проводил МУИТ (Международная олимпиада по спортивному программированию среди учащихся 10-11 классов). Там попалась интересная задача, которую так никто и не решил.

Вот собственно и задача:

Даны 2 числа a и b и уравнение (a / x) + (b / y) = 1, где |a|, |b| <= 10^14. Нужно найти количество целочисленных решений этого уравнения.

Архив соревнования здесь. Каковы идеи решения?

Здравствуй, сообщество Кодфорсес! Я хотел узнать о прикреплении материала (обсуждения, блога, разбора итд) к соревнованию. Когда эта возможность появилась на КФ (я имею ввиду скрепочку возле поста) у меня появились такие мысли: "ооо круто теперь если разбор не прикреплен к соревнованию можно самому это делать...". Прост бывает так, что хочешь по разбору дорешать задачу, открываешь ее, рассчитывая что там рядом будет ссылка на разбор, а ее нету((( Приходится тыкать в анонс (это, например, есть в 136 кажется раунде). Но когда я нажимаю на скрепку, и стрелочку вниз на списке соревнований, там пусто. Это баг, недоделка, или я как всегда все не так понял?

Здравствуй, Сообщество Codeforces! Я довольно-таки часто сталкиваюсь с проблемой: ловлю СЕ, когда на компе все нормально. Этот СЕ связан с СТЛ, а точнее с algorithm. Я не знаю как, но когда я подключаю string или vector некоторые функции (sort, reverse) включаются автоматически. Использую я Far + mingw. Ну естественно, без алгоритма у меня все компилится, я отправляю, а на сервере — СЕ. То есть потеря времени. Кто знает как решить эту проблему (м.б. какие-нибудь параметря компилятору надо передавать?). Я начал использовать заготовки, куда все инклудил, но иногда кажется проще без них. Заранее благодарен всем, кто ответит.