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

Підведено підсумки 3 туру, тож знову пропоную ділитися рішеннями. Мої (крім Viability) нижче:

Hoard

Будуємо граф, вершини якого - кімнати. Причому, беремо тільки початкову, кінцеву кімнати, а також ті, біля яких немає однієї зі стін. Ребра додаємо не між усіма парами вершин, а тільки між суміжними (тобто якщо, наприклад, є вершини для кімнат 1, 7, 9, то додаємо тільки ребра 1-7 та 7-9) і між тими кімнатами, які з'єдналися внаслідок руйнування стіни. Таким чином, кожна вершина матиме не більше 4 інцидентних ребер. Далі запускаємо алгоритм Дейкстри і радіємо.

Все доволі типово. Єдина річ у задачі, для якої немає "класичного" алгоритму - це обчислення номеру кімнати-сусіда. Див. ll internalNeighbour(ll n). Якщо по коду не зрозуміло - пишіть, розпишу словами.


Асимптотика.
Побудова графу - O(K)
Дейкстра - O(K * Log K) (оскільки кількість ребер у нас обмежена значенням 4K)
Загальна асимптотика - O(K * Log K)

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

#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <limits>

using namespace std;

typedef long long ll;
typedef map<ll, vector<pair<ll, ll> > > Graph;

ll internalNeighbour(ll n) {
    ll turnNumber = sqrt(n - 1) - 1;
    turnNumber |= 1;
    ll turnStart = turnNumber * turnNumber + 1;
    ll diff = n - turnStart;
    ll side = diff / (turnNumber + 1);

    return n - ((turnNumber - 1) * 4 + 2 * side + 1);
}

ll dijkstra(Graph &g, ll start, ll target) {
    map<ll, ll> d;

    for (Graph::const_iterator it = g.begin(); it != g.end(); ++it) {
        d[it->first] = numeric_limits<ll>::max();
    }

    d[start] = 0;

    set<pair<ll, ll> > q;
    q.insert(make_pair(d[start], start));

    while (!q.empty()) {
        ll v = q.begin()->second;
        q.erase (q.begin());

        if (v == target) {
            break;
        }

        for (size_t i = 0; i < g[v].size(); ++i) {
            ll to = g[v][i].first, len = g[v][i].second;

            if (d[v] + len < d[to]) {
                q.erase (make_pair (d[to], to));
                d[to] = d[v] + len;
                q.insert (make_pair (d[to], to));
            }
        }
    }

    return d[target];
}

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

    ll n;
    int k;
    cin >> n >> k;

    set<ll> nodes;
    Graph graph;

    nodes.insert(1);
    nodes.insert(n);

    for (int i = 0; i < k; ++i) {
        ll b;
        cin >> b;
        ll a = internalNeighbour(b);

        nodes.insert(a);
        nodes.insert(b);
        graph[a].push_back(make_pair(b, 1));
        graph[b].push_back(make_pair(a, 1));
    }

    for (set<ll>::iterator prev = nodes.begin(), i = nodes.begin(); i != nodes.end(); ++i, ++prev) {
        if (i == prev) {
            ++i;
        }
        ll a = *prev;
        ll b = *i;
        ll len = llabs(a - b);
        graph[a].push_back(make_pair(b, len));
        graph[b].push_back(make_pair(a, len));
    }

    cout << dijkstra(graph, 1, n) << endl;
}

П.С. У такому вигляді деякі великі тести можуть не заходити, бо перевіряюча система збирає код без оптимізацій. Тому є сенс скомпілювати цей код з оптимізаціями в асемблерний код і відправляти вже його. В такому випадку все працюватиме до 3 разів швидше. Ну або довго й нудно сидіти і вручну виконувати роботу компілятора: інлайнити функції, переставляти місцями інструкції і вручну писати структури збалансованих дерев або хеш таблиць і черг з пріоритетами. Можливо, якийсь глибокиц педагогічний сенс у цьому і є (хоча й теж сумнівний. Нічого не завадить просто взяти в інтернеті готові реалізації усіх необхідних алгоритмів і структур даних і так само використовувати, не сильно задумуючись про принцип їх роботи, як і з STL), але з практичної точки зору це просто безглузде витрачання часу. В реальному житті всі програми будуть збиратися з увімкненими оптимізаціями. І навіть в олімпіадах в 90% випадків компіляція буде з -O2. Коротше кажучи, якщо код вище скомпілювати ось так: g++ -O2 -S -o Hoard.s Hoard.cpp і трохи підправити, то вийде ось такий код, який працює значно швидше і в ТЛ вкладається: https://pastebin.com/N4Dvzmes.

Cool2k17

На перший погляд все виглядає страшно з обмеженнями до 10^18. Але на щастя, значення кількості перестановок росте дуже швидко. Для K порядку 10^18 переставлені будуть лише ~20 останніх чисел, а перші N - 20 йтимуть по порядку від 1 до N - 20. Таким чином, задача розбивається на 2 підзадачі:
- кількість крутих чисел на крутих місцях у "лівій" частині перестановки (тій, де числа йдуть по порядку);
- кількість крутих чисел на крутих місцях у "правій" частині перестановки (тій, де числа йдуть не підряд).

Перша підзадача. Оскільки числа йдуть підряд, вони співпадають зі своїми індексами в перестановці. Тобто треба просто знайти кількість крутих чисел, менших за дане.
Позначимо довжину десяткового запису числа за l.
1) Перш за все, додаємо до результату кількість "крутих" чисел з довжиною, меншою за l. Це 3^(l - 1) - 1. Адже у нас є l - 1 позицій, кожна з яких може містити цифри 0, 1, 2. Але числа у нас натуральні і 0 рахувати не треба, тому ще віднімаємо 1.
2) Перевіряємо першу цифру числа.
2.1) Якщо вона більша за 2, значить всі круті числа довжини l менші за дане і до результату треба додати 2 * 3^(l - 1). Бо на старшу позицію ми можемо поставити 1 або 2, а на всі інші позиції - 0, 1 або 2.
2.2) Якщо перша цифра - 2, то по-перше, всі "круті" цифри довжини l, у яких перша цифра 1 - менші за дане. Тому додаємо до результату 3^(l - 1). По-друге - рекурсивно рахуємо кількість крутих чисел, менших за дане число без старшого розряду (наприклад, для числа 2345 рекурсивно викликаємося для значення 345). З невеликим нюансом - для рекурсивного виклику 0 треба теж враховувати, бо цей нуль насправді має старші ненульові розряди. Тобто в кроці 1 одиницю віднімати не треба.
2.3) Якщо перша цифра - 1, то до відповіді додаємо тільки значення рекурсивного виклику з попереднього пункту.

Друга підзадача. Оскільки чисел тут буде дуже небагато, ми можемо просто влоб перевіряти "крутість" чисел та індексів. Треба лише швидко знайти K-ту перестановку. Це робиться за квадрат з використанням факторіальної системи числення (при бажанні і за NLogN, але для 20 значень це ролі не грає). Докладно розписувати не буду, ось кілька посилань: раз, два, три.

Асимптотика.
Перша підзадача - O(Log^2 N)
Друга підзадача - O(Log^2 K + Log K * Log N)
Загальна асимптотика - O(Log^2 N + Log^2 K)

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

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

typedef long long ll;

ll fpow(ll m, ll e) {
    ll res = 1;
    while (e) {
        if (e & 1) {
            res *= m;
        }
        m *= m;
        e >>= 1;
    }
    return res;
}

bool isCool(ll n) {
    for (; n; n /= 10) {
        if (n % 10 > 2) {
            return false;
        }
    }
    return true;
}

ll fact(ll n) {
    ll res = 1;
    for (int i = 2; i <= n; ++i) {
        res *= i;
    }
    return res;
}

int len(ll n) {
    int res = 0;
    for (;n;++res, n /= 10);

    return res;
}

ll nCool(ll n, bool recursive = false) {
    if (n < 2) {
        return n + recursive;
    }
    if (n < 10) {
        return 2 + recursive;
    }
    int lenMinusOne = len(n) - 1;
    ll res = fpow(3, lenMinusOne) - !recursive;
    ll tenPow = fpow(10, lenMinusOne);
    int firstDigit = n / tenPow;

    if (firstDigit > 2) {
        res += 2 * fpow(3, lenMinusOne);
    } else {
        ll remainder = n % tenPow;
        res += nCool(remainder, true);
        if (firstDigit == 2) {
            res += fpow(3, lenMinusOne);
        }
    }

    return res;
}

ll nShuffled(ll k) {
    --k;
    if (k == 0) {
        return 0;
    }
    for (ll i = 1, res = 1; ; ++res, i *= res) {
        if (i > k) {
            return res;
        }
    }
}

void getPermutation(ll k, ll from, ll to, vector<ll> &dst) {
    const ll n = to - from + 1;
    vector<ll> src(n);
    for (int i = 0; i < src.size(); ++i) {
        src[i] = from + i;
    }
    vector<char> used(n, false);

    ll curFact = fact(n - 1);

    vector<ll> factRepr;
    for (ll divisor = n - 1, t = k; divisor > 0; curFact /= divisor, --divisor) {
        factRepr.push_back(t / curFact);
        t %= curFact;
    }

    for (int i = 0; i < factRepr.size(); ++i) {
        int idx = -1;
        for (int j = 0, cnt = -1; j < used.size(); ++j) {
            if (!used[j]) {
                cnt++;
                if (cnt == factRepr[i]) {
                    idx = j;
                    break;
                }
            }
        }

        if (idx < 0) {
            break;
        }

        used[idx] = true;
        dst.push_back(src[idx]);
    }

    for (int i = 0; i < used.size(); ++i) {
        if (!used[i]) {
            dst.push_back(src[i]);
        }
    }
}

ll solve(ll n, ll k) {
    ll notShuffled = n - nShuffled(k);
    if (notShuffled < 0) {
        return -1;
    }

    ll res = nCool(notShuffled);
    vector<ll> remainder;

    getPermutation(k - 1, notShuffled + 1, n, remainder);

    for (ll i = 0; i < remainder.size(); ++i) {
        ll idx = notShuffled + i + 1;
        res += isCool(idx) && isCool(remainder[i]);
    }

    return res;
}

int main() {
    ll n, k;
    cin >> n >> k;

    cout << solve(n, k) << endl;
}

Segtree2k17

Класична задача на дерево відрізків без модифікації. Єдина проблема - обмеження на розмір чисел. В стандартні типи числа такої довжини не влізуть, а "чесна" довга арифметика не зайде по часу. Тому будемо використовувати хак.

На самій структурі дерева відрізків зупинятись не буду. Достатньо загуглити це словосполучення, щоб отримати купу статей, пояснень та реалізацій алгоритму.

Єдина операція, яку нам треба виконувати над числами - це множення двох чисел з отриманням результату по модулю. Власне сам хак:
1) Привівши множники і модуль до типу long double (на більшості платформ - 80-бітне число з плаваючою крапкою), порахуємо приблизну частку від ділення добутку чисел на модуль. Результат знову приведемо до 64-бітного беззнакового цілого.
2) Знайдемо приблизну остачу від ділення: від добутку віднімемо значення, отримане в кроці 1, помножене на значення модуля. В цьому кроці у нас може статися переповнення, але це не так страшно, бо при переповненні результат буде правильним по модулю 2^64 і в наступному кроці ми знову зробимо його більшим за наш модуль.
3) Враховуючи, що остача у нас приблизна - додаємо до неї ще значення модуля, помножене на 8. І беремо остачу від ділення цього всього добра на модуль.

Кілька зауважень:
1) Ми розраховуємо, що "приблизна частка" віздрізнятиметься від правильної менш ніж на 8.
2) Значення 8 взяте з тим розрахунком, що нам треба, щоб в останньому кроці не сталося переповнень. Оскільки обмеження на модуль - 10^18, а в 64-бітне ціле влазить ~18*10^18, 8 - це найбільше значення, яке ми можемо взяти (якщо похибка - 8, то приблизне значення остачі = <справжнє значення остачі> +/- 8 * mod і якщо ми до нього ще додамо 8 * mod, то отримаємо <справжнє значення остачі> + [0; 16 * mod], тобто макс. значення може досягати 17 * mod).
3) Ми сподіваємося, що long double - це таки 80-бітний тип (за стандартом це не обов'язково так, він може запросто бути таким-же, як і звичайний double), бо 64-бітного double не вистачить для того, щоб похибка ділення була <= 8.

Зауважень і нюансів доволі багато, але найкращий результат, якого мені вдавалося досягти з "чесним" і гарантовано працюючим множенням був у ~4 рази повільнішим за цей хак і в ТЛ він не вклався б. Якщо у когось є рішення без таких оговорок як у мене - буду вдячний, якщо поділитеся

Асимптотика. В принципі нічого неочікуваного. Звичайна асимптотика для дерева відрізків, але прихована константа доволі велика через хитре множення.
Відповідь на 1 запит: O(Log N)
Побудова дерева відрізків: O(N)
Загальна асимптотика - O(N + MLogN)


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

#include <iostream>
#include <utility>
#include <limits>

using namespace std;

typedef unsigned long long ull;

const int MAXN = 1000000;
ull a[MAXN];
ull in[MAXN];
ull mod;
unsigned n;

unsigned s;
unsigned getNext(){
    s ^= (s << 13);
    s ^= (s >> 17);
    s ^= (s << 5);
    return s;
}

ull mulmod(ull a, ull b, ull mod) {
  ull q = (long double)a * b / mod;
  ull r = a * b - q * mod;
  return (r + 8 * m) % mod;
}

void build (ull in[], int v, int tl, int tr) {
    if (tl == tr)
        a[v] = in[tl];
    else {
        int tm = (tl + tr) / 2;
        build (in, v * 2, tl, tm);
        build (in, v * 2 + 1, tm + 1, tr);

        a[v] = mulmod(a[v * 2], a[v * 2 + 1], mod);
    }
}

ull product (int v, int tl, int tr, int l, int r) {
    if (l > r)
        return 1;
    if (l == tl && r == tr)
        return a[v];
    int tm = (tl + tr) / 2;

    ull pl = product (v * 2, tl, tm, l, min(r, tm));
    ull pr = product (v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);

    return mulmod(pl, pr, mod);
}

int main() {
    unsigned m, seed ;
    cin >> n >> m >> mod >> seed;
    s = seed;
    for(unsigned i = 0; i < n; i++){
        in[i] = getNext() % mod;
    }

    build(in, 1, 0, n - 1);

    ull ans = 0;
    for(unsigned i = 0; i < m; i++){
        unsigned left = getNext() % n;
        unsigned right = getNext() % n;
        if(left > right) swap(left, right);

        ull result = product(1, 0, n - 1, left, right);

        ans = (ans + result) % mod;
    }

    cout << ans << endl;
}

Viability
Моє рішення вкладається в ТЛ тільки для N в районі 10^12, тому розписувати його не бачу сенсу. Сподіваюся, хтось поділиться оптимальним рішенням

Vinsoft

Очевидно, що фірми зі зв'язками довіри формують граф.

Розглянемо одну компоненту зв'язності цього графа. Якщо в ній всього одна вершина, то після першої ж ітерації чайника згода "затухне" і більше ніколи не з'явиться. Якщо вершин більше, то навпаки - в цій компоненті зв'язності згода не затухне ніколи - завжди буде хоча-б одна фірма, що згодна на пропозицію чайника. Розглянемо докладніше, що відбуватиметься в таких випадках.
1) Перед першою ітерацією горять лише ті фірми, які погодилися на початкову пропозицію Чайника.
2) Після першої ітерації горять лише ті фірми, що знаходяться на відстані 1 від тих, що погодилися спочатку і ніякі інші.
3) Після другої - знову горять ті, що погодилися спочатку, а також ті, що знаходяться на відстані 2.
4) Після третьої - ті, що на відстані 1 або 3
5) Після четвертої - на відстані 0, 2, 4
і т.д.

Оскільки граф не є нескінченним, рано чи пізно він прийде до "стабільного" стану - буде "блимати" різними наборами вершин для парних і непарних ітерацій. На парних ітераціях горітимуть вершини, відстань від яких до будь-якої з початкових вершин - парна. А не непарних - ті, відстань від яких непарна.

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

Таким чином, все що нам треба зробити - запустити обхід графа (в ширину, чи в глибину, неважливо) з тих вершин, які погодилися спочатку, відмічаючи, з якою парністю довжини шляху ми заходили в кожну вершину. В кінці перебираємо всі вершини і рахуємо, скільки з них горять на парних ітераціях, а скільки - на непарних. І виводимо максимум з цих значень. І ще не забуваємо про фірми, які нікому не довіряють. Їх треба викинути з розгляду при обході, достатньо просто порахувати кількість фірм, які погодилися з самого спочатку.

Асимптотика.
Оскільки кожну вершину ми відвідуємо не більше 2 разів (для парної і непарної довжини шляху), маємо звичайну асимптотику для обходу в ширину:
O(N + M)

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

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

typedef unsigned char byte;

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

    int n, m;
    cin >> n;

    byte agree[2000];
    vector<int> g[2000];
    queue<pair<int, byte> > q;
    int countAtStart = 0;

    for (int i = 0; i < n; ++i) {
        agree[i] = 0;
        bool f;
        cin >> f;
        if (f) {
            ++countAtStart;
            q.push(make_pair(i, 0));
        }
    }

    cin >> m;

    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    while (!q.empty()) {
        pair<int, byte> p = q.front();
        int c = p.first;
        byte parity = p.second;
        byte parityBit = 1 << parity;
        q.pop();

        if (agree[c] & parityBit) {
            continue;
        }
        agree[c] |= parityBit;
        if (g[c].size() == 0) {
            agree[c] = 0;
        }

        for (int i = 0; i < g[c].size(); ++i) {
            if ((agree[g[c][i]] & (1 << !parity)) == 0) {
                q.push(make_pair(g[c][i], !parity));
            }
        }
    }

    int countEven = 0;
    int countOdd = 0;

    for (int i = 0; i < n; ++i) {
        countEven += agree[i] & 1;
        countOdd += (agree[i] >> 1) & 1;
    }

    cout << max(countAtStart, max(countEven, countOdd)) << endl;
}

Відредаговано Dim_ov (2018-01-30 13:49:11)