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


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#1 2018-01-29 19:12:10

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Розв'язки

Підведено підсумки 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 рази повільнішим за цей хак і в ТЛ він не вклався б. Якщо у когось є рішення без таких оговорок як у мене - буду вдячний, якщо поділитеся smile

Асимптотика. В принципі нічого неочікуваного. Звичайна асимптотика для дерева відрізків, але прихована константа доволі велика через хитре множення.
Відповідь на 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, тому розписувати його не бачу сенсу. Сподіваюся, хтось поділиться оптимальним рішенням smile

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)

Поза форумом

 

#2 2018-01-29 23:08:48

heimdall
Новий користувач
Зареєстрований: 2016-01-22
Повідомлень: 5

Re: Розв'язки

Як автор задачі, хотілось поділитись своїм розв’язком SegTree2k17.
Задача виглядає як звичайна задача на дерево відрізків, проте пропонувався інший розв’язок.
1. Ми не можемо просто так перемножити два великих числа, але можна використовувати алгоритм бінарного множення. Опис його роботи можна знайти за посиланням http://e-maxx.ru/algo/binary_pow#header_8. Пропонується написати нерекурсивну реалізацію.
2. Проблема дерева відрізків в тому, що виконується занадто багато операцій merge, а саме 2N + M*O(logN). Пропонуюється два схожих рішення цієї проблеми.
Перший варіант - побудувати "sqrt-tree", опис можна знайти тут: http://codeforces.com/blog/entry/57046 Кількість операцій "merge": 4*O(NloglogN) + 4*M
Як можна помітити - стаття з’явилась після того, як була запропонована задача.
Особисто я написав наступне рішення. Побудуємо за O(N) перший рівень sqrt-tree та звичайне дерево відрізків. Якщо запит знаходиться в одному блоці - викликаємо функцію find для дерева відрізків, інакше - для sqrt-tree. Оцінимо час роботи такої реалізації - Перший рівень будується за 4N операцій "merge" дерево відрізків - за 2N. К-сть операцій "merge" на один запит(в гіршому випадку) logN/2. АЛЕ оскільки тести генеруються рівноймовірно можна прийти до наступної формули: 6N операцій merge на побудову структури і M*(3+logN/sqrt(N)) на запити.
Реалізацію можна знайти за посиланням:
https://pastebin.com/dzakYfge
https://pastebin.com/jth9JmYW
P.S. Прошу вибачення за те, що множення за допомогою long double набирало повний бал.

Поза форумом

 

#3 2018-01-30 09:19:14

ikovrigin
Олімпієць
Зареєстрований: 2017-11-13
Повідомлень: 26

Re: Розв'язки

Cool2k17 Первая подзадача решается за O(1) жадно находим наибольшее крутое число, кол-во крутых чисел будет число в троичной системе с такой же записью.
Т.е если чисел 587, то наибольшее крутое число это 222 в троичной системе 222 = 2*9+2*3+2 = 26 крутых числе меньше либо равных 587.
Для числа 1231726123 наибольшее крутое 1222222222 значит кол-во крутых чисел 1222222222 = 1∙3^9+2∙3^8+2∙3^7+2∙3^6+2∙3^5+2∙3^4+2∙3^3+2∙3^2+2∙3^1+2∙3^0 = 39365

P.S Согласен с замечанием по поводу сложности O(Log N), просто оценил фиксировано 18 знаками smile
P.P.S Горю желанием увидеть решение Viability. Может быть клуб "Алгоритм" поделится своим решением ? smile

Відредаговано ikovrigin (2018-01-30 12:57:33)

Поза форумом

 

#4 2018-01-30 11:36:14

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Розв'язки

Ну це, все таки, логарифм, а не константа. Але так, це все одно краще, ніж мій логарифм квадрат)

Поза форумом

 

#5 2018-02-03 12:23:51

jurij
Новий користувач
Зареєстрований: 2009-01-23
Повідомлень: 40

Re: Розв'язки

heimdall написав:

1. Ми не можемо просто так перемножити два великих числа, але можна використовувати алгоритм бінарного множення.
P.S. Прошу вибачення за те, що множення за допомогою long double набирало повний бал.

Перемножение и взятие по модулю при помощи длинной арифметики, написанной специально под эту задачу, работает значительно быстрее, чем бинарное сложение по модулю.
Кстати, если функцию addMod (в авторском решении) встроить прямо в код mulMod, скорость выполнения тестов увеличивается в 1,5 раза.

Но использование long double в любом случае превосходит по скорости.

Время выполнения 30 теста:
авторской программы - 4,36с
авторской программы с встроенным кодом addMod - 2,82с
авторской программы с mulMod на длинной арифметике - 1,75с
авторской программы с mulMod на long double - 0,54с

Поза форумом

 

#6 2018-02-03 23:12:23

AntonR
Новий користувач
Зареєстрований: 2016-11-10
Повідомлень: 21

Re: Розв'язки

heimdall написав:

P.S. Прошу вибачення за те, що множення за допомогою long double набирало повний бал.

Взагалі то неправильна методика:
1) учасники не знають тайм ліміти, і при цьому мають лише 1 раз можливість для відправки.

2) автор "запилює" свій розв'язок так, щоб він влазив в лише йому відомі ліміти порядка 0.01-0.03 сек

3) При цьому авторський розв'язок в більшості випадків можна ще піддопиляти, і ще зменшити в 1.5-3 рази час виконання програми.

А можна і ще піддопиляти...

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

Поза форумом

 

#7 2018-02-04 15:16:14

heimdall
Новий користувач
Зареєстрований: 2016-01-22
Повідомлень: 5

Re: Розв'язки

AntonR написав:

heimdall написав:

P.S. Прошу вибачення за те, що множення за допомогою long double набирало повний бал.

Взагалі то неправильна методика:
1) учасники не знають тайм ліміти, і при цьому мають лише 1 раз можливість для відправки.

2) автор "запилює" свій розв'язок так, щоб він влазив в лише йому відомі ліміти порядка 0.01-0.03 сек

3) При цьому авторський розв'язок в більшості випадків можна ще піддопиляти, і ще зменшити в 1.5-3 рази час виконання програми.

А можна і ще піддопиляти...

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

1. Я не маю можливості змінити правил.
2. Я брав час роботи x і ставив тайм-ліміт 2.5*x + 0.05.
При цьому розв’язок як можете побачити не є доведеним до ідеалу, мене цікавили більше алгоритмічні оптимізації, ніж суто програмні.
3. В цьому і є методика NetOI: протягом місяця в вас є можливість "допиляти" свій розв’язок до бажаного стану. В цій задачі це робити легко, адже вже є готовий код і простий(але правильний розв’язок) пишеться легко. Для перевірки на ТЛ на сервері був доданий великий тест в умову.

Поза форумом

 

#8 2018-02-12 21:49:57

Arideno
Олімпієць
Зареєстрований: 2017-10-20
Повідомлень: 4

Re: Розв'язки

Можете розповісти про функцію internalNeighbour?

Поза форумом

 

#9 2018-02-13 15:15:43

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Розв'язки

Arideno написав:

Можете розповісти про функцію internalNeighbour?

Можу.

Спіраль можна розбити на витки (показані жовтуватим і блактним кольором):
https://api.monosnap.com/rpc/file/download?id=77OoQe6lvD7rdXYHw4ombTWe0UNbEn

Можна помітити, що кожен виток (крім самого першого з одиницею) починається з числа, на 1 більшого за квадрат якогось непарного числа і закінчується квадратом наступного непарного числа. Тобто починається з числа виду (2k + 1) ^ 2 + 1 і закінчується числом (2k + 3) ^ 2.
Спіраль з виділеними початками витків:
https://api.monosnap.com/rpc/file/download?id=o7eyWbTWm5fUS3nZiFyRorC1dbWUg8

Тож спочатку шукаємо номер витка, в якому знаходиться поточне число. Номером витка будемо вважати значення (2k + 1), про яке я писав вище. Щоб його знайти треба взяти корінь з n-1, округлений донизу, відняти одиницю, а якщо в результаті вийшло парне число - додати її назад. Що, власне, і відбувається ось тут:

Код:

ll turnNumber = sqrt(n - 1) - 1;
turnNumber |= 1;

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

Код:

ll turnStart = turnNumber * turnNumber + 1;

Далі знайдемо порядковий номер "сторони" витка, на якій знаходиться поточне число (мається на увазі в порядку обходу спіралі, тобто права сторона має номер 0, верхня - 1, ліва - 2, нижня 3). Довжина "сторони" витка на 1 більша за його номер, тобто номер сторони можна обчислити ось так:

Код:

ll diff = n - turnStart;
ll side = diff / (turnNumber + 1);

Під "сторонами" витка я тут маю на увазі ось ці регіони:
https://api.monosnap.com/rpc/file/download?id=Z6KT7P1cmJnB2RTuTJUud7vdeSLRgP

Ну і все. Тепер у нас є все, щоб обчислити різницю між поточним числом і його "внутрішнім" сусідом. Ця різниця дорівнюватиме

Код:

((turnNumber - 1) * 4 + 2 * side + 1)

Віднімаємо це значення від n і радіємо.

Всі використані формули без проблем виводиться емпіричним шляхом, закономірності достатньо прості, щоб відслідкувати їх неозброєним оком. Але якщо є час і натхнення, то можна і повиводити їх строго)

П.С. Функція видаватиме маячню для "кутових" значень, у яких немає сусідів (типу 10, 13, 17, 21 і т.п.), але умова гарантує, що таких вхідних даних не буде, тому можна не паритись.

Відредаговано Dim_ov (2018-02-13 15:18:57)

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt