Форум Всеукраїнської інтернет-олімпіади NetOI

Ідеї та код (С++) повнобальних рішень.

Так, частина задач легко гугляться, іноді навіть з рішеннями і тестами (хоча це й не є особливістю цього туру, чи цього року. Таке бувало і раніше). Але все таки напишу короткі розбори


Щоб окремо не зупинятися на цьому в кожній задачі. Там, де час роботи впирається в швидкість I/O, використовується введення-виведення у стилі С. Там, де не впирається - у стилі C++.


Treats

В сусідній темі пишуть, що є значно швидший (для даних обмежень) розв'язок за O(n *（2 ^ n）). Буду вдячний, якщо хтось поділиться кодом, або більш детальним описом алгоритму, бо я поки що не дуже уявляю, як можна отримати таку асимптотику

Трохи нагадує задачу про рюкзак. Розв'язується так само через ДП. Розглянемо табличку А розміром n x (b + 1). Індексація з нуля. Нехай A[​i][s] - кількість способів вибрати s призів, використовуючи лише пакунки з нульового по i-й включно. У i-му пакунку у нас m[​i] призів. Якщо нам треба набрати загальну кількість призів s, то ми можемо взяти 0 призів з i-го пакунку та s призів з попередніх (i - 1) пакунків, 1 приз з i-го пакунку та (s - 1) призів з попередніх (i - 1) і так далі, аж до m[​i] призів з i-го пакунку та (s - m[​i]) призів з попередніх (i - 1) пакунків.
Таким чином, з поправками на вихід за межі таблички, отримуємо наступну формулу:

Базові значення:
A[​i][0] = 1 - не взяти жодного приза можна лише одним спосом
A[0][s] = 0 для s >= 1 - набрати ненульову кількість призів з нуля пакунків неможливо.

Якщо обчислювати табличку за формулою вище "в лоб", то отримаємо асимптотику O(n * b^2) і, враховуючи обмеження, по часу таке не зайде.
Треба оптимізувати обчислення суми.

Заведемо допоміжну табличку B, таку що

Обчислювати значення для цієї таблички ми можемо по ходу обчислення значень для таблички A, а використовуючи табличку B ми можемо обчислювати суму з формули для таблички A за константний час.

Якщо придивитися уважніше до того, що вийшло, то можна помітити, що перша табличка нам, за великим рахунком, не дуже й треба. Тож її можна викинути і обійтися лише другою.

Асимптотика.
По часу: O(n * b)
По пам'яті: O(n * b)
При бажанні можна отримати і O(b), але з даними обмеженнями на n, сенсу в цьому небагато. І так, формально в реалізації виділяється O(1) пам'яті. Але за логікою алгоритму її треба O(n * b)

Код рішення на С++.

#include <iostream>
#include <numeric>

using namespace std;

const static int mod = 1000000007;

int solve(size_t n, int a, int b, int m[]) OPTIMIZE_ATTR;
int main() OPTIMIZE_ATTR;

int solve(size_t n, int a, int b, int m[]) {
    b = min(b, accumulate(m, m + n, 0));
    if (a > b) {
        return 0;
    }
    static int dp[10][10000001] = {};

    for (size_t i = 0; i < n; ++i) {
        dp[i][0] = 1;
    }
    for (int j = 1; j <= m[0]; ++j) {
        dp[0][j] = j + 1;
    }

    for (int j = m[0] + 1; j <= b; ++j) {
        dp[0][j] = dp[0][m[0]];
    }

    for (size_t i = 1; i < n; ++i) {
        for (int s = 1; s <= b; ++s) {
            int sum = dp[i - 1][s];

            if (s > m[i]) {
                sum -= dp[i - 1][s - m[i] - 1];
                sum %= mod;
            }

            dp[i][s] = dp[i][s - 1] + sum;
            dp[i][s] %= mod;
        }
    }

    int res = dp[n - 1][b] - dp[n - 1][a - 1];

    return (res % mod + mod) % mod;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    size_t n;
    int a, b;
    int m[10];

    cin >> n >> a >> b;

    for (size_t i = 0; i < n; ++i) {
        cin >> m[i];
    }

    //cout << solve_slow_as_fuck(n, a, b, m) << endl;
    cout << solve(n, a, b, m) << endl;
}

Tickets2018

Знову ДП. Нехай T1[​i], T2[​i], T3[​i] - мінімальний час обслуговування фанатів з нульового по i-й включно за умови, що i-й купує, відповідно, 1, 2 або 3 квитка.

Обчислимо T[​i].
Позначимо мінімальний час, необхідний для продажу квитків першим i-1 фанатам за Base. Тоді, очевидно,
T1[​i] = Base + a
T2[​i] = Base + b
T3[​i] = Base + c

Обчислимо значення Base.
Щоб усі попередні фанати були з квитками треба щоб сталася одна з 3 подій:
- останній фанат купив квиток для себе,
- передостанній фанат купив 2 квитка: для себе і для останнього,
- перед-передостанній фанат купив 3 квитка.
Таким чином, Base можна обчислити за формулою
Base = min(T1[​i - 1], T2[​i - 2], T3[​i - 3])

Додати до цієї основної ідеї кілька перевірок, ініціалізувати базові значення ДП і буде рішення.

При бажанні зекономити пам'ять можна помітити, що в кожен момент часу ми використовуємо лише 3 попередніх значення. Тож для роботи рішення нам достатньо лише 4 "записів" ДП, а не цілого масиву.

Асимптотика.
По часу: O(N)
По пам'яті: O(1)

Код рішення на С++.

#include <iostream>
#include <algorithm>
#include <limits>

using namespace std;

static const int Inf = numeric_limits<int>::max();

int main() OPTIMIZE_ATTR;

struct DpRecord
{
    int take1Ticket;
    int take2Tickets;
    int take3Tickets;

    DpRecord(int take1, int take2, int take3):take1Ticket(take1), take2Tickets(take2),
        take3Tickets(take3) {}

    DpRecord(int defVal): take1Ticket(defVal), take2Tickets(defVal),
        take3Tickets(defVal) {}
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin >> n;

    DpRecord dpA(Inf), dpB(Inf), dpC(Inf);

    for (int i = 0; i < n; ++i) {
        int a, b, c;
        cin >> a >> b >> c;

        int takeTicketsBase = min(dpC.take1Ticket, min(dpB.take2Tickets, dpA.take3Tickets));
        if (takeTicketsBase == Inf) {
            takeTicketsBase = 0;
        }

        DpRecord current(a + takeTicketsBase,
                         b + takeTicketsBase,
                         c + takeTicketsBase);

        if (i >= n - 2) {
            current.take3Tickets = Inf;
        }
        if (i >= n - 1) {
            current.take2Tickets = Inf;
        }

        dpA = dpB;
        dpB = dpC;
        dpC = current;
    }

    int result = min(dpC.take1Ticket, min(dpB.take2Tickets, dpA.take3Tickets));

    cout << result << endl;
}

Кepler

Перш за все можна помітити, що для парних n рішення буде співпадати з рішенням для n/2. Тож почати варто з того, що розділити n на 2, якщо у тому є потреба. Після цієї операції парад планет буде тоді і тільки тоді, коли усі планети будуть знаходитися в одному секторі (положення усих планет будуть конгруентні по модулю n).

Також можна одразу помітити, що парад планет точно відбудеться через ціле число земних років, тобто відповіді -1 бути не може. Якщо висновок неочевидний - подумайте, в якому положенні опиняться планети через n років (незалежно від їх швидкості обертання).

Таким чином, відповіддю на задачу буде найменше додатнє рішення системи



Перекинемо ікси вліво і отримаємо 2 лінійних модульниих рівняння вигляду a * x = b (mod m)



В загальному вигляді такі рівняння розв'язуються розширеним алгоритмом Евкліда. Докладніше, наприклад, тут. Але враховуючи, що у нас b = 0 (ну або b = m, кому як зручніше), коренями наших двох рівнянь будуть числа виду k*(m/g), де k - довільне ціле число, а g - найбільший спільний дільник значень a та m. Іншими словами, достатньо звичайного, "нерозширеного" алгоритму Евкліда. Знайдемо базові розв'язки (значення m/g) для наших двох рівнянь. Нехай solA - базовий розв'язок першого рівняння, а solB - другого.
Таким чином, перша і друга планети опиняються в одному секторі кожні solA земних років, а перша і третя - кожні solB земниих років.

Тож загальною відповіддю буде найменше спільне кратне значень solA і solB.

Асимптотика.
Час: O(Log N)
Пам'ять: O(1)

Код рішення на С++.

#include <iostream>
#include <cstdlib>

using namespace std;

typedef long long ll;

int main() OPTIMIZE_ATTR;
ll gcd(ll a, ll b) OPTIMIZE_ATTR;
ll lcm(ll a, ll b) OPTIMIZE_ATTR;
ll solve(ll n, ll a, ll b, ll c) OPTIMIZE_ATTR;

ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

ll solve(ll n, ll a, ll b, ll c) {
    if(n % 2 == 0){
        n /= 2;
    }

    a %= n;
    b %= n;
    c %= n;

    ll solA = n / gcd(llabs(a - b), n);
    ll solB = n / gcd(llabs(a - c), n);

    return lcm(solA, solB);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ll n, a, b, c;

    cin >> n >> a >> b >> c;

    cout << solve(n, a, b, c) << endl;
}

Minbus
Загальна ідея - просто жадібний алгоритм. Беремо тих пасажирів, яких треба чекати найменше.

Для кожної зупинки порахуємо мінімально можливий час приїзду автобуса (коли автобус нікого не чекає). Позначимо цей час за travelTime. Час приходу пасажира на зупиинку позначимо за t. Тоді часом очікування пасажира буде значення max(0, t - travelTime).

Розіб'ємо задачу на 2 частини. Спочатку виберемо, яких пасажирів брати, потім порахуємо, скільки часу це займе.

Першу підзадачу можна ефективно розв'язати, наприклад, за допомогою збалансованого дерева пошуку, або купи.

Заведемо таку структуру даних. Це буде наш "автобус". Туди ми будемо додавати тих пасажирів, яких візьмемо.

Читаємо дані пасажирів. До тих пір, поки в автобусі менше, ніж n пасажирів - просто беремо всих підряд. Коли автобус уже заповнено - порівнюємо чергового пасажира з найгіршим пасажиром в автобусі. Якщо новий пасажир кращий за старого - безжалісно викидаємо останнього і беремо на його місце нового.
"Кращим" тут вважається пасажир з меншим часом очікування. Якщо час очікування двох пасажирів однаковий, то кращим буде той, чия зупинка раніше (краще чекати на перших зупинках, ніж на останніх. Ажде поки ми чекаємо там - на наступних зупинках можуть прийти ще пасажири і ми зможемо їх забрати без очікування). Але ця умова буде виконуватися автоматично, бо ми читаємо дані зупинок по порядку.

Друга підзадача. Тепер у нас є список пасажирів, яких ми візьмемо в автобус і час руху автобуса між зупинками. Залишилось зі списку пасажирів отримати загальний час "простою" автобуса під час очікування пасажирів. Очевидно, цей час не може бути меншим, ніж час очікування "найгіршого" пасажира зі списку (інакше ми просто не зможемо його забрати). Але в той же час, коли ми чекаємо якогось пасажира n од. часу, то час очікування усих пасажирів після нього - зменшується на n. Тож враховуючи те, яким чином формувався наш список пасажирів, час очікування найгіршого пасажира і буде загальним часом простою автобуса. І цей час очікування найгіршого пасажира з нашої структури "автобуса" можна отрмати за кнстантнй час.

Ну і оскільки автори задачі вважають обмеження на N та K адекватними - додамо ще кілька оптимізацій з ігнором непотрібних нам даних (скористаємося тим фактом, що пасажири на зупинках розташовані в порядку приходу), ну і взагалі зробимо все від нас залежне, щоб максимально швидко опрацьовувати навіть файли в сотні гігабайт. Хоча, як уже писали у інших топіках, опрацювати макс. файл за розумний час все одно неможливо фізично.

Така реалізація на моїй системі пропускає дані зі швидкістю трохи менше 1200 МіБ/с. Тобто з вхідним файлом на HDD та більшості SSD лімітуючим фактором буде швидкість носія. "Садить" пасажирів в автобус - зі швидкістю ~550-600 МіБ/с.
В конкретних числах.
З файлом у RAM розміром ~30 ГБ. "Хороший" вхідний файл (у якому можна багато даних пропустити) обробляється за 27 секунд. "Поганий" (пропускати багато не вийде) - за 53 сек.
Файл на SSD у ~200 ГБ. "Хороший" - 5,5 хв. "Поганий" - 9 хв  46 сек.
Під максимальний тест (9-розрядні значеннями часу, N = K = 200000, розмір файлу - 400 ГБ) у мене місця на SSD немає, тому результат для HDD - 45 хв.
Думаю, це не межа і при бажанні можна читати дані ще швидше. Але по-перше, це зробить рішення вже занадто багатослівним. По-друге - воно і так уже впирається у макс. швидкість читання більшості SSD. Ну і по-третє - сенсу в погоні за швидкістю на тестах, яких все одно не буде (хоча формально вони й валідні за умовою), і які все одно працюватимуть занадто повільно для олімпіади - небагато.

І окреме зауваження про оптимізації. В більшості випадків, писати свою реалізацію піраміди - безглуздо. priority_queue працює швидше і краще, якщо код збирається з оптимізаціями (а він збирається  саме так і на переважній більшості олімпіад (включаючи UOI та IOI), і у "реальному" житті при розробці комерційних програм). Але тут він збирається без оптимізацій, тому priority_queue працюватиме повільніше за свій велосипед.

Асимптотика.
Час:
Читання вхідних даних: O(N*K)
Додавання одного пасажира в автобус: O(Log M)
Загальна: O(N*K*Log M)

Пам'ять: O(M)


Код рішення на С++.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

int main() OPTIMIZE_ATTR;

template <typename T>
class MyHeap
{
    size_t _size;
    T _data[2000];

    void sift_up() OPTIMIZE_ATTR {
        size_t i = _size - 1;

        while (i) {
            size_t parent = (i - 1) / 2;

            if (_data[i] > _data[parent]) {
                swap(_data[i], _data[parent]);
            } else {
                break;
            }
            i = parent;
        }
    }


    void sift_down() OPTIMIZE_ATTR {
        size_t i = 0;

        while (i * 2 + 1 < _size) {
            size_t c1 = i * 2 + 1;
            size_t c2 = i * 2 + 2;

            size_t c = c1;
            if (c2 < _size && _data[c2] > _data[c1]) {
                c = c2;
            }

            if (_data[i] >= _data[c]) {
                break;
            }

            swap(_data[c], _data[i]);
            i = c;
        }
    }

public:
    MyHeap(): _size(0) {}

    size_t size() const OPTIMIZE_ATTR {return _size;}
    const T& top() const OPTIMIZE_ATTR {return _data[0];}

    void push(const T& val) OPTIMIZE_ATTR {
        _data[_size++] = val;

        sift_up();
    }

    void pop() OPTIMIZE_ATTR {
        _data[0] = _data[--_size];

        sift_down();
    }
};

typedef long long ll;
//typedef priority_queue<ll> Heap;
typedef MyHeap<ll> Heap;

int main() {
    static char buf[3000000];

    size_t n, m;
    scanf("%zd %zd\n", &n, &m);

    static Heap seats;
    ll travelTime = 0;

    bool zeroWaitAchieved = false;

    for (size_t i = 0; i < n; ++i) {
        fgets(buf, sizeof (buf), stdin);
        char *pbuf = buf;
        size_t k;
        ll tNext;
        int offset = 0;
        sscanf(pbuf, "%lld %zd%n", &tNext, &k, &offset);
        pbuf += offset;

        // we're not interested in passengers data anymore. The bus
        // is full of passengers with zero waiting time
        if (zeroWaitAchieved) {
            travelTime += tNext;
            continue;
        }

        for (size_t j = 0; j < k; ++j) {
            ll t;
            sscanf(pbuf, "%lld%n", &t, &offset);
            pbuf += offset;

            ll p = max(0LL, t - travelTime);

            if (seats.size() < m) {
                seats.push(p);
                continue;
            }

            ll worst = seats.top();

            if (worst == 0) {
                zeroWaitAchieved = true;
            }

            if (p >= worst) {
                // skip the rest of the line. We won't get any better passengers on this stop
                break;
            }

            seats.pop();
            seats.push(p);
        }
        travelTime += tNext;
    }

    printf("%lld\n", travelTime + seats.top());
}

Gardener

Халява. Читаємо номерии квіток, по ходу рахуємо кількість квіток кожного виду. Потім виводимо індекс максимального елемента в масиві з кількостями, або 0 якщо таких елементів кілька.

Асимптотика.
Час: O(n)
Пам'ять: O(max(c)), але формально O(1), як і в Treats.

Код рішення на С++.

#include <cstdio>

using namespace std;

int main() OPTIMIZE_ATTR;

int main() {
    int count[101] = {-1};
    int n;
    scanf("%d", &n);

    int currentMax = 0;
    bool ambiguous = false;

    for (int i = 0; i < n; ++i) {
        int c;
        scanf("%d", &c);

        ++count[c];
    }

    for (int i = 1; i <= 100; ++i) {
        if (count[i] == count[currentMax]) {
            ambiguous = true;
        } else if (count[i] > count[currentMax]) {
            currentMax = i;
            ambiguous = false;
        }
    }

    printf("%d\n", ambiguous ? 0 : currentMax);
}

Відредаговано Dim_ov (2019-01-05 02:17:40)