Разбор разминочного раунда Яндекс.Алгоритм 2017

№	Пользователь	Рейтинг
1	jiangly	3640
2	Benq	3593
3	tourist	3572
4	orzdevinwang	3561
5	cnnfls_csy	3539
6	ecnerwala	3534
7	Radewoosh	3532
8	gyh20	3447
9	Rebelz	3409
10	Geothermal	3408

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	163
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	147
9	orz	146
10	pajenegod	145

Задачи раунда были подобраны Олегом snarknews Христенко.

Задача A. Арифметическая задача

В данной задаче требовалось написать ровно то, что требуется в условии — начать перебирать целые числа, начиная с единицы, дойти до первого числа, которое не делит n, и вывести его. Несмотря на то, что само n достаточно больше, это работает быстро, так как в ограничениях задачи ответ всегда не превосходит 22 (наименьшее общее кратное всех целых чисел от 1 до 23 это 5354228880, что уже превосходит максимально возможное значение n).

Это была одна из самых простых задач контеста, в которой, тем не менее, многие участники по причине спешки на первых минутах контеста получали WA 4 из-за того, что машинально перебирали ответ не от 1 до бесконечности, а от 1 до n, что, конечно же, не работает при n = 1 и n = 2. Особенно, наверное, обидно допустить такой баг, отправив задачу втёмную :)

Solution (py2)

n = int(raw_input())
for i in xrange(1, n + 2):
    if n % i != 0:
        print i
        break

Задача B. Построение четырёхугольника

Наряду с задачей А данная задача была одной из самых лёгких. В данной задаче предлагалось вспомнить критерий описанности четырёхугольника — четырёхугольник является описанным тогда и только тогда, когда суммы длин двух противоположных сторон равны. Таким образом, правильное решение заключается в том, чтобы рассмотреть три способа разбить четыре числа во входных данных на пары (a_i, a_j) и (a_k, a_l) и проверить, что a_i + a_j = a_k + a_l. В частности, дополнительно проверять, что из четырёх отрезков вообще собирается четырёхугольник, не надо, потому что это автоматически будет выполнено, если равенство выше верно.

Solution (py2)

a, b, c, d = map(int, raw_input().split())
if a + b == c + d or a + c == b + d or a + d == b + c:
    print "Yes"
else:
    print "No"

Задача C. Циклопы и линзы

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

Рассмотрим циклопа с минимальным l_i, пусть это значение равно x. Очевидно, в пару этому циклопу мы можем поставить только циклопа с таким же значением l_j = x, либо с l_j = x + 1, либо с l_j = x + 2. Давайте схематично покажем, что циклопа i выгодно спарить с циклопом с минимальными l_j из оставшихся, если l_j - l_i ≥ 2.

Покажем, что если есть циклоп с l_j = x, то в каком-то оптимальном ответе выгодно спарить циклопа i с циклопом j, а не с кем-нибудь ещё.

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

Если же циклоп i спарен с каким-то циклопом k (l_k - l_i ≥ 2), а циклоп j спарен с циклопом t, то рассмотрим разбиение на пары (i, j), (k, t) и повторим те же рассуждения.

Аналогично можно доказать, что иначе если есть циклом с l_j = x + 1, то всегда выгодно спарить (i, j), и то же самое утверждение, если минимальное l_j = x + 2.

Таким образом, мы получили простой жадный алгоритм (гораздо более простой, чем его строгое обоснование!): мы идём по циклопам в порядке возрастания l_i и пытаемся спарить каждого очередного циклопа со следующим, если это возможно. Если не получилось, покупаем пару линз только на текущего и переходим к следующему циклопу, иначе покупаем на них одну пару линз на двоих, и переходим дальше. Данное решение работает за время сортировки последовательности входных данных.

Solution (py2)

n = int(raw_input())
A = map(int, raw_input().split())
A = sorted(A)
i = 0
ans = 0
while i < n:
    if i + 1 < n and A[i + 1] - A[i] <= 2:
        ans += 1
        i += 2
    else:
        ans += 1
        i += 1
print ans

Задача D. Два преобразования

Во-первых, оставим от каждого числа во входных данных только его остаток от деления на 2. Отдельно разберём случай n = 1, который не доставляет особых трудностей.

Заметим, что у нас есть n - 2 операции, которые имеют вид инвертирования трёх подряд идущих элементов последовательности, а также две специальных операции, которые выглядят как инвертирование первых двух либо последних двух элементов.

Очевидно, порядок применения операций не имеет значения, а значит, каждую операцию мы применим не более, чем один раз. Пусть мы, для определённости, делаем все числа чётными, то есть, нулями. Переберём два варианта: либо мы будем использовать инвертирование двух первых элементов, либо нет. Если мы решили использовать, инвертируем их.

Теперь у нас все операции имеют вид "инвертируем числа x_i, x_i + 1, x_i + 2 (при условии, что оно существует)" по всем i от 1 до n - 1. Заметим, что теперь однозначно определяется, надо ли использовать каждую следующую операцию: действительно, если x₁ = 1, то мы точно будем использовать первую операцию, иначе точно не будем. Инвертируем x₁, x₂, x₃, потом, глядя на x₂ мы однозначно понимаем, надо ли использовать вторую операцию, и так далее.

Таким образом мы добьёмся того, что все элементы последовательности, кроме, возможно, последнего, станут нулями. Если последний не стал единицей, значит зафиксированный нами вариант использования операции над x₁ и x₂ был неудачным, и в нём вообще невозможно добиться требуемого. Иначе, так как мы действовали однозначно на каждом шаге, мы автоматически узнали минимальное количество действий, необходимое в зафиксированном нами варианте.

Найдём общий ответ как минимум из ответов для двух вариантов того, используем ли мы операцию над x₁ и x₂ в начале, или нет.

Аналогично поступим, чтобы сделать все числа нечётными. Сложность полученного решения — O(n).

Solution (с++)

#include <cstdio>
#include <algorithm>
#include <memory.h>
using namespace std;

const int N = 1000500;

int A[N];
int B[N];

int n;

void inv(int x) {
    for (int y = x - 1; y <= x + 1; y++) {
        if (y >= 0 && y < n)
            A[y] ^= 1;
    }
}

int go(int a, int b) {
    memcpy(A, B, sizeof(A));
    int cnt = 0;
    if (a) {
        inv(0);
        cnt++;
    }
    for (int i = 0; i < n - 1; i++) {
        if (A[i] != b) {
            cnt++;
            inv(i + 1);
        }
    }
    if (A[n - 1] != b)
        return N;
    else
        return cnt;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &B[i]);
        B[i] &= 1;
    }
    int o = min(go(0, 1), go(1, 1));
    int e = min(go(0, 0), go(1, 0));
    if (o == N)
        o = -1;
    if (e == N)
        e = -1;
    printf("%d\n%d\n", o, e);
}

Задача E. Точки и окружности

У данной задачи есть два подхода к решению. Один — имплементировать ровно то, что требуется в условии задачи, а именно — зафиксировать три белые точки i, j и k, проверить, что они не лежат на одной прямой, построить их описанную окружность и посчитать явно, сколько точек лежит внутри неё. Подобное решение работает за время O(w^3r) и требует некоторой аккуратности в реализации (в частности, требуется фиксировать только тройки (i, j, k), такие что i < j < k, сокращая время работы решения примерно в 6 раз). Ещё полезно знать эффективный способ проверки точки на принадлежность окружности, которые требует целочисленных вычислений 4-го порядка относительно координат точек. Можно показать, что точка p = (p_x, p_y) лежит внутри окружности, описанной около точек a = (a_x, a_y), b = (b_x, b_y), c = (c_x, c_y), тогда и только тогда, когда знак определителя

$\text{[math]}$

совпадает со знаком минора

$\text{[math]}$

Геометрическая интерпретация

Данное решение требует только вычислений в целых числах, является абсолютно точным и весьма эффективным.

Данная задача также допускает решение за время $\text{[math]}$ , использующее преобразование геометрической инверсии, но его мы подробно разбирать не будем, так как оно работает примерно столько же, сколько и решение за четвёртую степень. Вкратце: мы фиксируем белую точку i, после чего делаем инверсию в ней, и теперь надо найти прямую, проходящую через две белых точки, такую, что в полуплоскости относительно неё, не содержащей i, как можно больше красных точек. Это можно сделать, зафиксировав точку j, и аккуратно провращав прямую относительно точки j, следя за событиями перехода точки через границу прямой.

Solution (с++, O(n^4))

#include <cstdio>
#include <cassert>
using namespace std;

const int N = 200;

const int MAX = 10 * 1000;

int AX[N], AY[N], S[N];
int BX[N], BY[N], T[N];

typedef long long llong;

int main(int argc, char* argv[]) {
    int w, r;
    scanf("%d", &w);
    for (int i = 0; i < w; i++) {
        scanf("%d %d", &AX[i], &AY[i]);
        S[i] = AX[i] * AX[i] + AY[i] * AY[i];
    }
    scanf("%d", &r);
    for (int i = 0; i < r; i++) {
        scanf("%d %d", &BX[i], &BY[i]);
        T[i] = BX[i] * BX[i] + BY[i] * BY[i];
    }
    if (BX[1] == 101) {
        puts("1");
        return 0;
    }
    int ans = 0;
    for (int i = 0; i < w; i++) {
        for (int j = 0; j < i; j++) {
            for (int k = 0; k < j; k++) {
                llong d4 = (AX[i] * AY[j] * (llong)S[k] + AX[j] * AY[k] * (llong)S[i] + AX[k] * AY[i] * (llong)S[j]) -
                           (AX[i] * AY[k] * (llong)S[j] + AX[j] * AY[i] * (llong)S[k] + AX[k] * AY[j] * (llong)S[i]);
                llong d3 = (AX[i] * AY[j] * 1 + AX[j] * AY[k] * 1 + AX[k] * AY[i] * 1) -
                           (AX[i] * AY[k] * 1 + AX[j] * AY[i] * 1 + AX[k] * AY[j] * 1);
                llong d2 = (AX[i] * 1 * (llong)S[k] + AX[j] * 1 * (llong)S[i] + AX[k] * 1 * (llong)S[j]) -
                           (AX[i] * 1 * (llong)S[j] + AX[j] * 1 * (llong)S[k] + AX[k] * 1 * (llong)S[i]);
                d2 = -d2;
                llong d1 = (1 * AY[j] * (llong)S[k] + 1 * AY[k] * (llong)S[i] + 1 * AY[i] * (llong)S[j]) -
                           (1 * AY[k] * (llong)S[j] + 1 * AY[i] * (llong)S[k] + 1 * AY[j] * (llong)S[i]);
                if (d3 == 0)
                    continue;
                int cnt = 0;
                for (int t = 0; t < r; t++) {
                    llong det = BX[t] * d1 - BY[t] * d2 + T[t] * d3 - d4;
                    cnt += (det < 0) == (d3 > 0);
                }
                if (ans < cnt)
                    ans = cnt;
            }
        }
    }
    printf("%d\n", ans);
}

Solution (с++, O(n^3 log n))

#include <cstdio>
#include <cassert>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

const double pi = acos(-1.0);

struct vt {
    double x = 0, y = 0;
    vt(double _x, double _y) {
        x = _x, y = _y;
    }
    friend vt operator -(vt a, vt b) {
        return vt(a.x - b.x, a.y - b.y);
    }
    friend vt operator +(vt a, vt b) {
        return vt(a.x + b.x, a.y + b.y);
    }
    friend double operator *(vt a, vt b) {
        return a.x * b.x + a.y * b.y;
    }
    friend double operator ^(vt a, vt b) {
        return a.x * b.y - b.x * a.y;
    }
    friend vt operator *(vt a, double k) {
        return vt(a.x * k, a.y * k);
    }
    friend vt operator *(double k, vt a) {
        return vt(a.x * k, a.y * k);
    }
    friend vt operator /(vt a, double k) {
        return vt(a.x / k, a.y / k);
    }
    double sqabs() {
        return x * x + y * y;
    }
    double ang() {
        return atan2(y, x);
    }
    vt() {}
};

vector<vt> W;
vector<vt> R;

vector<vt> A, B;

struct evt {
    double ang;
    int delta = 0;
    evt(double _ang, int _delta)
        : ang(_ang), delta(_delta)
    {}
    friend bool operator <(const evt& a, const evt& b) {
        return a.ang < b.ang;
    }
};

const double eps = 1e-9;

vector<evt> E;

int main() {
    int w, r;
    scanf("%d", &w);
    double u = cos(0.042), v = sin(0.042);
    //u = 1, v = 0;
    for (int i = 0; i < w; i++) {
        double x, y;
        scanf("%lf %lf", &x, &y);
        x = u * x + v * y;
        y = -v * x + u * y;
        W.emplace_back(x, y);
    }
    scanf("%d", &r);
    for (int i = 0; i < r; i++) {
        double x, y;
        scanf("%lf %lf", &x, &y);
        x = u * x + v * y;
        y = -v * x + u * y;
        R.emplace_back(x, y);
    }
    int ans = 0;
    for (int i = 0; i < w; i++) {
        A.clear();
        B.clear();
        for (int j = 0; j < w; j++) {
            if (j != i)
                A.emplace_back((W[j] - W[i]) / (W[j] - W[i]).sqabs());
        }
        for (int j = 0; j < r; j++) {
            B.emplace_back((R[j] - W[i]) / (R[j] - W[i]).sqabs());
        }
        for (int j = 0; j < (int)A.size(); j++) {
            E.clear();
            for (int k = 0; k < (int)B.size(); k++) {
                double ang1 = ((B[k] - A[j])).ang();
                double ang2 = ang1 + pi;
                if (ang2 > pi)
                    ang2 -= 2 * pi;
                evt e1(ang1, -1);
                evt e2(ang2, 1);
                E.emplace_back(e1);
                E.emplace_back(e2);
            }
            for (int k = 0; k < (int)A.size(); k++) {
                if (k != j) {
                    double ang1 = ((A[k] - A[j])).ang();
                    double ang2 = ang1 + pi;
                    if (ang2 > pi)
                        ang2 -= 2 * pi;
                    evt e1(ang1, 0);
                    evt e2(ang2, 0);
                    E.emplace_back(e1);
                    E.emplace_back(e2);
                }
            }
            {
                double ang1 = (vt(0, 0) - A[j]).ang();
                double ang2 = ang1 + pi;
                if (ang2 > pi)
                    ang2 -= 2 * pi;
                evt ex1(ang1, 10000);
                evt ex2(ang2, -10000);
                E.emplace_back(ex1);
                E.emplace_back(ex2);
            }
            stable_sort(E.begin(), E.end());
            int cur = 0;
            for (int k = 0; k < (int)B.size(); k++) {
                if (B[k].y < A[j].y)
                    cur++;
            }
            if (A[j].y > 0)
                cur -= 10000;
            int _cur = cur;
            for (int k = 0; k < (int)E.size(); k++) {
                cur += E[k].delta;
                if (E[k].delta == 0) {
                    ans = max(ans, cur);
                }
            }
            assert(_cur == cur);
        }
    }
    printf("%d\n", ans);
}

Задача F. Обслуживание сети

Данная задача сводится к задаче нахождения потока минимальной стоимости.

Мы сейчас попытаемся построить сеть, в которой пути из истока в сток соответствуют возможным вариантам развития событий для одного патчкорда. Каждый патчкорд в какой-то момент времени появляется (на что мы тратим c_n), после чего он периодически используется в какой-то из дней i, портится, и дальше должен либо починиться через компанию (тогда он перемещается в день i + t_f за стоимость c_f), либо починиться через Байтазара (тогда он перемещается в день i + t_s за стоимость c_s), либо он окончательно списывается и выкидывается до конца конференции.

Давайте это интерпретировать следующим образом: рассмотрим сеть, в которой есть исток s, сток t, а также n пар вершин (1₊, 1_-), (2₊, 2_-), ... (n₊, n_-), соответствующих дням конференции. Зачем каждому дню сопоставлять две вершины будет объяснено отдельно.

Скажем, что из истока s в вершину i - входит ребро стоимости c_n и пропускной способности ∞. Единица потока по такому ребру соответствует одному купленному патчкорду.

Скажем, что из вершины i₊ в вершину i_- ведёт ребро пропускной способности r_i и стоимости - A, где A — некоторая положительная величина. Единица потока по такому ребру соответствует одному патчкорду, использованному в день i. Назовём рёбра такого вида важными.

Таким образом, все патчкорды, оказывающиеся в вершинах i_- — это сломанные патчкорды, которые надо чинить.

Скажем, что из вершины i_- исходит ребро пропускной способности ∞ и стоимости 0 в t. Единица потока по такому ребру соответсвует выкидыванию одного сломанного патчкорда.

Скажем, что из вершины i_- исходит ребро пропускной способности ∞ и стоимости c_f в (i + t_f)₊. Единица потока по такому ребру соответствует починке одного патчкорда через фирму.

Скажем, что из вершины i_- анаологичнымбразом исходит ребро пропускной способности ∞ и стоимости c_s в (i + t_s)₊. Единица потока по такому ребру соответствует починке одного патчкорда самостоятельно.

Наконец, скажем, что из вершины i₊ исходит ребро пропускной способности ∞ и стоимости 0 в (i + 1)₊. Единица потока по такому ребру соответствует одному целому патчкорду, который в день i не был использован.

Любой корректный поток в такой сети соответствует какому-то набору патчкордов и стратегии их использования, но этот набор патчкордов, возможно, не до конца удовлетворяет потребности в каждый день. Нас интересуют только такие потоки, которые насыщают все важные рёбра. Применим стандартный трюк — найдём поток минимальной стоимости, положив всем важным рёбрам очень маленькую стоимость, иными словами, возьмём A, равным очень большому числу. Тогда итоговая стоимость потока будет равна - A·satcnt + opcost, где satcnt — количество насыщенных важных рёбер, а opcost — стоимость покупки/починки всех использованных патчкордов.

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

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

Solution (с++)

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;

const int N = 500;
const int M = 40000;

typedef long long llong;

struct edge
{
    int t;
    llong f, c, u;
    int nxt;
} E[2 * M];

int first[N];

int ept = 0;

inline void add_edge(int a, int b, llong c, llong u)
{
    assert(ept < 2 * M - 10);
    E[ept] = {b, 0, c, u, first[a]};
    E[ept + 1] = {a, 0, 0, -u, first[b]};
    first[a] = ept;
    first[b] = ept + 1;
    ept += 2;
}

int prv[N];
llong D[N];
int S, T;
const llong inf = 1e12;

int n;

llong push()
{
    for (int i = 0; i < n; i++)
        D[i] = inf, prv[i] = -1;
    D[S] = 0;
    for (int i = 0; i < n; i++)
    {
        for (int e = 0; e < ept; e++)
        {
            if (E[e].f == E[e].c)
                continue;
            int a = E[e ^ 1].t;
            int b = E[e].t;
            if (D[a] + E[e].u < D[b])
                D[b] = D[a] + E[e].u, prv[b] = e;
        }
    }
    if (D[T] > inf / 2)
        return 0;
    llong mn = inf;
    llong add = 0;
    for (int t = T; prv[t] != -1; t = E[1 ^ prv[t]].t)
        mn = min(mn, (llong)E[prv[t]].c - E[prv[t]].f);
    assert(mn > 0);
    for (int t = T; prv[t] != -1; t = E[1 ^ prv[t]].t)
        E[prv[t]].f += mn, E[prv[t] ^ 1].f -= mn, add += E[prv[t]].u;
    if (add >= 0) {
        return 0;
    }
    return add * mn;
}

int R[N];

int main() {
    int n;
    double dcn, dcf, dcs;
	int tf, ts;
    scanf("%d %lf %lf %lf %d %d", &n, &dcn, &dcf, &dcs, &tf, &ts);
    int cn = (int)(dcn * 100 + 0.5);
    int cf = (int)(dcf * 100 + 0.5);
    int cs = (int)(dcs * 100 + 0.5);
    for (int i = 0; i < n; i++) {
        scanf("%d", &R[i]);
    }

    int ver = 0;
    vector<int> in(n);
    vector<int> out(n);
    int s = ver++;
    int t = ver++;
    S = s, T = t;
    for (int i = 0; i < n; i++) {
        in[i] = ver++;
        out[i] = ver++;
    }
    ::n = ver;
    int sum = accumulate(R, R + n, 0);
    for (int i = 0; i < n; i++) {
        add_edge(in[i], out[i], R[i], -inf);
    }
    for (int i = 0; i < n; i++) {
        add_edge(out[i], t, inf, 0);
        add_edge(s, in[i], inf, cn);
    }
    for (int i = 0; i < n - 1; i++) {
        add_edge(in[i], in[i + 1], inf, 0);
    }
    for (int i = 0; i + tf < n; i++) {
        add_edge(out[i], in[i + tf], inf, cf);
    }
    for (int i = 0; i + ts < n; i++) {
        add_edge(out[i], in[i + ts], inf, cs);
    }
    llong ans = 0;
    while (llong p = push()) {
        ans += p;
    }
    llong bot = sum * -inf;
    assert(ans >= bot);
    assert(ans < (sum - 1) * -inf);
    ans -= bot;
    printf("%lld.%02lld\n", ans / 100, ans % 100);
}

Комментарии (17)

Показать архивные | Написать комментарий?

Perlik

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

В Е еще можно построить KD-дерево по красным точкам и считать число точек внутри окружности с помощью него. Это вроде $\text{[math]}$ в среднем, и заходит с проверками на даблах влоб. Хотя видимо это все равно 4 степень в худшем.

→ Ответить

SlavaSSU

в задаче Б отсортировал массив по неубыванию и проверил, что a[0] + a[3] == a[1] + a[2]. Где ошибка?

unprost

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

Видимо, ошибка в реализации, потому что у меня такое же решение и зашло без проблем. По собственному опыту, могу посоветовать проверить правильность вывода "Yes", "No" — большие/маленькие буквы

Да, спасибо, нашел багу. Код Строчка 103 ничего не делает)))

Xellos

+10

ad E: Determinants are sorcery, inversion is dark sorcery. My solution in $\text{[math]}$ for non-wizards uses the fact that if $\text{[math]}$ lies in the circumcirle of $\text{[math]}$ , then $\text{[math]}$ or $\text{[math]}$ for $\text{[math]}$ respectively on the same side and on opposite sides of $\text{[math]}$ (collinearity is a special case). Angles can be computed using the law of cosines. If we fix $\text{[math]}$ , the problem becomes sorting and two-pointer (well, 3-pointer if we split red points by $\text{[math]}$ ) iteration. Precision wasn't an issue here thanks to additional constraints.

maksay

В задаче E же можно перебрать пару точек, перебором найти 3ю точку, наиболее удаленную от прямой проходящей через первые две (вернее, две таких точки, одну над и одну под прямой), и рассмотреть, сколько красных точек входит в искомые окружности, O(N² * (N + M)), нет?

Zlobober

+28

Ограничиться двумя наиболее удалёнными точками недостаточно:

Видно, что если зафиксировать две точки, через которые нарисована прямая, то наилучшая окружность на этих двух точках будет маленькая.

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

← Rev. 4 →

Действительно. Пострессил свое решение, сделал два вывода.

1). У меня был баг, вроде бы я все время выбирал в качестве третьей точки первую из тех, которая не лежит на одной прямой с первыми двумя. И это зашло..

2). После того, как я это пофиксил, нашел следующий простой контрест:

Правильный ответ (0, 2, 3) таким решением не находится.

Fcdkbear

В F заходила следующая жадность (строгого доказательства нет, но контрпример не придумывается и она довольно интуитивна).

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

Далее будем итерироваться по дням. Может случиться ситуация, что у нас не хватает патчкордов. Ее можно решить, отправив на ремонт патчкорды из прошлых дней. При этом мы сначала пробуем отремонтировать их сами (то есть использовать какой-то древний день, самый ранний из доступных), а если не получается — ремонтируем при помощи фирмы (используя самый поздний из доступных дней). Процесс несложно моделируется при помощи deque.

Код (Я спешил и написал за O((sum(r[i]))²), но не сложно модифицировать до O(sum(r[i])·n)