На форумі обговорюються лише питання, пов'язані з олімпіадою
Ви не зайшли.
Повнобальні рішення з короткими розборами.
SnakeWay
Відповідь до задачі, очевидно, буде або на 1 більша за кількість різних шляхів, що ведуть від початкового кутка до кінцевого (з урахуванням обмежень з умови), або -1, якщо таких шляхів не існує.
Для виведення закономірності, як кількість шляхів залежить від n, можна спробувати повиводити формули з рекурентних співвідношень і індукції. Можна помалювати шляхи на листочку і порахувати вручну. Можна поберегти папір і змусити "малювати" і рахувати комп'ютер. Простим перебором "в лоб". Наприклад якось так. Неефективно, але для N < ~14 порахує за адекватний час, і цього цілком достатньо, щоб помітити закономірності.
В усіх випадках отримуємо наступні формули:
D(n) = L(n) = 2 ^ (n - 2)
S(n) = 2 ^ ((n - 1)/2)
І окремо враховуємо граничні випадки: D(1) = 1, L(1) = 0, S(2 * k) = 0 (тобто S шляхів для парних n не існує).
Значення N можуть бути доволі великими, тому використовуємо алгоритм бінарного піднесення до степені.
Після цього залишаються тільки питання акуратної реалізації: ніде не забути, що обчислення треба проводити по модулю 1000000007 і врахувати, що в процесі може виникнути потреба перемножувати числа порядку 10^9, тому варто використовувати 64-бітний тип даних.
Асимптотика.
По часу: O(Log N)
По пам'яті: O(1)
Код рішення на С++.
#include <iostream>
using namespace std;
const long long mod = 1000000007;
long long binpow (long long a, long long n) {
long long res = 1;
while (n) {
if (n & 1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
int main() {
int n;
char c;
cin >> n >> c;
long long count = 0;
switch (c) {
case 'D':
count = n == 1 ? 1 : binpow(2, n - 2);
break;
case 'L':
count = n == 1 ? 0 : binpow(2, n - 2);
break;
case 'S':
count = n & 1 ? binpow(2, n/2) : 0;
break;
}
cout << (count ? (count + 1) % mod : -1) << endl;
}Vars2019
Масиви не можна прирівняти у двох випадках:
1. У масивах є числа, що не збігаються. У такому випадку що б ми не робили зі змінними - це нас не врятує. Наприклад,
y 2 3 1 x 4
2. Масиви у різних місцях задають вимоги до значень групи змінних, що суперечать одна одній. Наприклад,
x 2 3 1 x 3
Тут змінна x має прийняти значення 1, щоб задовольнити вимогу першого елементу і значення 2, щоб задовольнити вимогу другого елементу.
y 2 x 1 x y
У даному випадку третій елемент масивів прирівнює змінні x та y між собою. Тобто по суті їх можна сприймати як одну змінну. Таким чином отримали ситуацію, аналогічну попередньому прикладу.
Таким чином, загальний алгоритм буде таким:
1. Пробігаємося по масивах. Розглядаємо тільки пари чисел і шукаємо такі, що не збігаються. Якщо знайшли - відповідь N, кінець роботи.
2. Пробігаємося по масивах. Розглядаємо тільки пари змінних. Формуємо групи змінних, що мають бути однаковими (як x та y з останнього прикладу).
3. Востаннє біжимо по масивах і пробуємо задати значення змінним. Для цього розглядаємо тільки пари змінна-число. Беремо групу, якій належить змінна. Якщо цій групі уже присвоєне число і воно не співпадає з поточним числом - відповідь N, кінець роботи. Якщо число ще не присвоєне - присвоюємо поточне.
4. Якщо на попередніх етапах алгоритм не зупинився - відповідь Y.
Залишилося кілька нюансів:
1. Треба швидко знаходити, до якої групи належить змінна (і швидко об'єднувати групи змінних). Для цього можна використати структуру disjoint-set. Докладніше про неї можна почитати, наприклад, тут, або тут. Але варто звернути увагу, що евристика об'єднання за рангом/за розміром хоч формально і покращує асимптотику однієї операції з DSU до константної (а загальну, відповідно - до лінійної), але на практиці у даному випадку працює повільніше. Тому її я не використовував.
2. Треба ефективно працювати з іменами змінних. Якщо так і залишити їх 10-символьними рядками, то усі операції з ними будуть занадто повільними. Щоб обійти це обмеження - помітимо, що маленьких латинських букв всього 26. Відповідно, всього існує трохи менше, ніж 27^10 = 2 * 10^14 різних змінних. Тобто якщо сприймати імена змінних як числа, що записані у 27-чній системі числення, то для зберігання імені змінної буде достатньо всього 48 біт. А отже ім'я змінної "влізе" в 64-бітний цілий тип (наприклад long long в C++). Всі операції з 64-бітними цілими - значно швидші, ніж аналогічні операції з 10-символьними рядками.
3. 48 біт - це небагато для зберігання імені однієї змінної, але 2^48 - це дуже багато, якщо мова йде про пам'ять. Виділити статичні масиви такого розміру не вийде. Однак зустрінеться нам різних 48-бітних значень не більше, ніж 2*N. А отже замість масивів можна використати, наприклад, хеш-таблиці. До речі, хороші новини для C++-ників: у цьому році програми компілюються з підтримкою C++11. Тому можна взяти бібліотечний unordered_map замість написання свого велосипеда.
Асимптотика.
Час: O(N * Log N)
Пам'ять: O(N)
Код рішення на С++.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int MAX_N = 100000;
struct Element {
ll value;
bool is_variable() { return value < 0; }
friend istream &operator >>(istream &in, Element &element) {
char buf[16];
in >> buf;
bool is_variable = *buf >= 'a' && *buf <= 'z';
if (is_variable) {
element.value = 0;
for (char *pbuf = buf; *pbuf; ++pbuf) {
element.value *= 27;
element.value += *pbuf - 'a' + 1;
}
element.value = -element.value;
} else {
element.value = atoi(buf);
}
return in;
}
};
ll find_set (ll v, unordered_map<ll, ll> &parent) {
auto it = parent.find(v);
if (it == parent.end())
return v;
return parent[v] = find_set (it->second, parent);
}
void union_sets (ll a, ll b, unordered_map<ll, ll> &parent) {
a = find_set (a, parent);
b = find_set (b, parent);
if (a != b) {
parent[b] = a;
}
}
bool solve() {
size_t n;
cin >> n;
unordered_map<ll, ll> var_val;
unordered_map<ll, ll> parent;
var_val.reserve(n * 2);
parent.reserve(n * 2);
static Element a[MAX_N], b[MAX_N];
for (size_t i = 0; i < n; ++i) cin >> a[i];
for (size_t i = 0; i < n; ++i) cin >> b[i];
for (size_t i = 0; i < n; ++i) {
if (a[i].is_variable() != b[i].is_variable()) continue;
if (!a[i].is_variable() && a[i].value != b[i].value) {
return false;
}
if (a[i].is_variable()) {
union_sets(a[i].value, b[i].value, parent);
}
}
for (size_t i = 0; i < n; ++i) {
if (a[i].is_variable() == b[i].is_variable()) {
continue;
}
auto number = a[i].value;
auto var_id = b[i].value;
if (a[i].is_variable()) {
swap(number, var_id);
}
var_id = find_set(var_id, parent);
if (var_val.count(var_id) && var_val[var_id] != number) {
return false;
}
var_val[var_id] = number;
}
return true;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--) {
cout << (solve() ? 'Y' : 'N');
}
cout << endl;
}SqStr
Цікава задача. Доволі багатокрокова, але більшість кроків дозволяють відкинути частину інформації з попередніх кроків, тож кінцевий код виходить доволі коротким і виглядає нескладно.
По-перше відмітимо, що якщо число є повним квадратом, то кількость усіх простих дільників у факторизації такого числа будуть парними. По-друге, коли ми множимо два числа - кількості їх простих дільників додаються. Наприклад, 12 (2^2 * 3^1) * 18 (2^1 * 3^2) = 216 (2^3 * 3^3). Таким чином, ми можемо звести задачу пошуку підмасивів з "квадратним добутком" до задачі пошуку підмасивів з парною сумою.
Отже, першим кроком - проводимо факторизацію елементів вхідного масиву. Оскільки обмеження на елементи невеликі (до 255) - можна забити прості числа, менші за 255, у статичний масив і використовувати його. Отримали 2-мірний масив factor такий, що factor[i][j] - кількість j-го простого дільника у факторизації i-го вхідного числа.
Далі для простоти розглянемо тільки один простий дільник (наприклад, 2). Тобто у масиві factor розглядаємо тільки один стовпчик. Нам треба знайти у цьому стовпчику кількість підмасивів з парною сумою. Для початку помітимо, що шукати суми взагалі значно зручніше і швидше не на початковому масиві, а на масиві з кумулятивними сумами. Тобто коли prefix_sum[i] - це сума усіх елементів масиву factor від 0 до i-го. У такому випадку сумою елементів factor від i-го до j-го буде значення prefix_sum[j] - prefix_sum[i]. Нам треба, щоб ця сума була парною. Різниця двох чисел буде парною тоді і тільки тоді, коли і зменшуване і від'ємник або обидва парні, або обидва непарні. Отже кількістю парних сум буде кількість пар парних елементів масиву плюс кількість пар непарних елементів масиву. У цьому місці можна помітити, що нам і кумулятивні суми виявилися не дуже-то й потрібними. Нас цікавить тільки парність цих сум.
Тепер ми могли б розв'язати задачу, якби в початковому масиві були лише степені двійки. Але у нас, нажаль, там можуть бути й інші значення. Тож повернемось тепер до повної задачі. Тут ситуаця дуже схожа. Єдина відмінність - тепер нам треба, щоб парною на проміжку була сума не одного масиву, а одразу декількох. Як ми з'ясували, початковий масив factor нам не треба. І навіть масив кумулятивних сум prefix_sum нам не потрібен. Будемо зберігати лише масив парностей кумулятивних сум: prefix_parity[i][j] зберігає значення 1 або 0. 1 означає, що сума кількостей j-го простого дільника для елементів від 0-го до i-го - непарна. Відповідно, 0 означає, що ця сума парна. Тепер ми могли б розв'язати нашу задачу за квадрат. Псевдокод:
результат = 0
для кожного i від 0 до n:
для кожного j від i + 1 до n:
якщо prefix_parity[i][k] == prefix_parity[j][k] для усіх k:
результат = результат + 1Але це занадто повільно. Застосуємо 2 оптимізації.
1. Бітові маски. Простих чисел, менших за 255 всього 54 штуки. А отже замість того, щоб зберігати одиниці і нулі парності в окремих елементах масиву - ми можемо зберігати їх в бітах одного 64-бітного цілого. Крім оптимальнішого використання пам'яті це також дозволить швидше порівнювати значення. Алгоритм стане таким:
результат = 0
для кожного i від 0 до n:
для кожного j від i + 1 до n:
якщо prefix_parity[i] == prefix_parity[j]:
результат = результат + 12. Тепер можна помітити, що ми по суті просто рахуємо кількість пар однакових чисел у масиві prefix_parity. Але ми робимо це "в лоб". Можна рахувати швидше за допомогою комбінаторної формули комбінацій з n по 2: n*(n - 1) / 2. Тобто виходить, що нам навіть масив prefix_parity не потрібен. Нам потрібні лише кількості різних значень у цьому масиві для обчислення відповіді.
Асимптотика.
По часу: O(N)
По пам'яті: O(N)
Код кінцевого рішення на С++.
#include <iostream>
#include <unordered_map>
using namespace std;
typedef unsigned long long ull;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
const size_t N_PRIMES = 54;
int primes[N_PRIMES] {
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251};
size_t n;
cin >> n;
ull parity = 0;
unordered_map<ull, ull> parity_count;
parity_count.reserve(n);
for (size_t i = 0; i < n; ++i) {
int a;
cin >> a;
for (size_t j = 0; j < N_PRIMES && a != 1; ++j) {
while (a % primes[j] == 0) {
a /= primes[j];
parity ^= 1ULL << j;
}
}
++parity_count[parity];
}
auto result = parity_count[0];
for (auto kv : parity_count) {
result += kv.second * (kv.second - 1) >> 1;
}
cout << result << endl;
}Megacube
Задача полягає в знаходженні (ну або не-знаходженні) протиріч у вхідних даних. Якщо протиріччя є, то відповідь - N. Якщо немає - Y.
Кожне число з вхідних даних дає нам наступну інформацію:
1. Координати одного не з'їденого квадрату (якщо це число не -1).
2. Одне з обмежень для відповідного стовпчика чи рядка:
2.1. Інформація про те, що цей рядок (стовпчик) пустий.
2.2. Мінімальна можлива координата у рядку (стовпчику).
2.3. Максимальна можлива координата у рядку (стовпчику).
Таким чином, читаємо вхідні дані, зберігаючи координати не з'їдених плиток і всі обмеження. Після цього проходимося по плитках (їх буде не більше, ніж 4N) і перевіряємо, чи відповідає кожна з них обмеженням для своїх координат (обмежень всього 6 штук).
Асимптотика.
Час: O(N)
Пам'ять: O(N)
Код рішення на С++.
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
bool solve() {
const int MAX_N = 10000;
int n;
cin >> n;
int min_x[MAX_N], max_x[MAX_N], min_y[MAX_N], max_y[MAX_N];
bool empty_row[MAX_N] {}, empty_col[MAX_N] {};
int n_cells = 0;
pair<int, int> cells[MAX_N * 4];
const auto input = [&cells, n, &n_cells](bool *empty_arr, int *opt_arr, bool is_max, bool is_y) {
for (int i = 0; i < n; ++i) {
int d;
cin >> d;
if (d == -1) {
empty_arr[i] = true;
} else {
opt_arr[i] = is_max ? n - d - 1 : d;
auto cell = make_pair(opt_arr[i], i);
if (is_y) swap(cell.first, cell.second);
cells[n_cells++] = cell;
}
}
};
input(empty_row, min_x, false, false);
input(empty_row, max_x, true , false);
input(empty_col, min_y, false, true);
input(empty_col, max_y, true , true);
for (int i = 0; i < n_cells; ++i) {
int x = cells[i].first;
int y = cells[i].second;
if (
x < min_x[y] ||
x > max_x[y] ||
y < min_y[x] ||
y > max_y[x] ||
empty_col[x] ||
empty_row[y])
{
return false;
}
}
return true;
}
int main() {
int t;
cin >> t;
while (t--) {
cout << (solve() ? 'Y' : 'N');
}
cout << endl;
}Bracket2019
Просто жадібний алгоритм. Завжди міняємо місцями самі крайні "неправильні" дужки.
Заведемо два вказівника: лівий і правий. Першим будемо йти по рядку від початку до кінця, іншим - від кінця до початку. В процесі для кожного вказівника окремо рахуємо відкриваючі-закриваючі дужки як у класичній задачі на перевірку правильності дужкової послідовності (відкриваючі дужки збільшують лічильник, а закриваючі - зменшують). Коли один із лічильників стає меншим за 0 (наприклад, лівий) - зупиняємося і починаємо йти іншим вказівником (відповідно, правим). Коли і його лічильник став меншим за нуль - міняємо місцями символи, на які вони вказують, збільшуємо відповідь на 1 і продовжуємо алгоритм. Якщо так сталося, що один із лічильників став меншим за 0, а у іншого вказівник уже дійшов до кінця рядка (ну або до початку) - значить отримати правильну дужкову послідовність шляхом перестановок неможливо і треба вивести -1.
Асимптотика.
Час: O(n)
Пам'ять: O(n)
Код рішення на С++.
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
char buf[1000002];
fgets(buf, sizeof (buf), stdin);
char *end = buf + strlen(buf) - 1;
if (*end == '\n') --end;
int cnt_l = 0;
int cnt_r = 0;
int res = 0;
char *l = buf;
char *r = end;
while (l <= end && r >= buf) {
while(l <= end && cnt_l >= 0) {
cnt_l += *l == ')' ? -1 : 1;
++l;
}
while(r >= buf && cnt_r >= 0) {
cnt_r += *r == '(' ? -1 : 1;
--r;
}
if ((cnt_l < 0) != (cnt_r < 0)) break;
if (cnt_l < 0 && cnt_r < 0) {
--l;
++r;
swap(*l, *r);
cnt_l = cnt_r = 0;
++res;
}
}
if (cnt_l || cnt_r) res = -1;
printf("%d\n", res);
}Відредаговано Dim_ov (2019-12-30 23:47:28)
Поза форумом