Did you notice account LLM_AI_Testing on --best site to train competitive programming-- Timus?
It actually solves most of hardest problems.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 153 |
| 2 | nik_exists | 151 |
| 3 | maroonrk | 150 |
| 4 | maspy | 149 |
| 5 | AmShZ | 146 |
| 6 | Um_nik | 143 |
| 7 | Errichto | 139 |
| 8 | adamant | 135 |
| 9 | BledDest | 134 |
| 10 | cry | 130 |
Did you notice account LLM_AI_Testing on --best site to train competitive programming-- Timus?
It actually solves most of hardest problems.
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int n, k;
cin >> n >> k;
vector < vector <int> > b(k);
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
b[x % k].push_back(i);
}
int res = -1;
for (int i = 0; i < k; i++) {
if ((int)b[i].size() == 1) {
res = b[i][0];
break;
}
}
if (res == -1) {
cout << "NO" << endl;
}
else {
cout << "YES" << endl << res << endl;
}
}
return 0;
}
for _ in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [[] for _ in range(k)]
for i in range(0, n):
x = a[i]
b[x % k].append(i + 1)
res = -1
for i in range(k):
if len(b[i]) == 1:
res = b[i][0]
break
if res == -1:
print("NO")
else:
print("YES\n" + str(res))
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
for (int ans = 1, cur = 1; ; ans++, cur = cur * 2 + 2) {
if (cur >= n) {
cout << ans << '\n';
break;
}
}
}
return 0;
}
tt = int(input())
for _ in range(tt):
n = int(input())
ans = 1
cur = 1
while True:
if cur >= n:
print(ans)
break
ans += 1
cur = cur * 2 + 2
В какой-то момент разработки этой задачи появилось следующее альтернативное условие: нам необходимо минимизировать общее количество операций обоих типов. Как решить эту задачу?
2040C - Упорядоченные перестановки
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int n;
long long k;
cin >> n >> k;
vector <int> a, b;
if (n <= 60 && (1ll << (n - 1)) < k) {
cout << -1 << endl;
continue;
}
k--;
vector <int> d;
while (k) {
d.push_back(k % 2);
k /= 2;
}
while (d.size() < n - 1) d.push_back(0);
for (int i = n - 2, j = 1; i >= 0; i--, j++) {
if (d[i] == 0) a.push_back(j);
else b.push_back(j);
}
reverse(b.begin(), b.end());
for (int i : a) cout << i << ' ';
cout << n << ' ';
for (int i : b) cout << i << ' ';
cout << endl;
}
return 0;
}
tt = int(input())
for _ in range(tt):
n, k = map(int, input().split())
a, b = [], []
if n <= 60 and (1 << (n - 1)) < k:
print(-1)
continue
k -= 1
d = []
while k:
d.append(k % 2)
k //= 2
while len(d) < n - 1:
d.append(0)
a, b = [], []
j = 1
for i in range(n - 2, -1, -1):
if d[i] == 0:
a.append(j)
else:
b.append(j)
j += 1
b.reverse()
print(*a, n, *b)
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector < vector <int> > g(n);
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
a--, b--;
g[a].push_back(b);
g[b].push_back(a);
}
vector <int> res(n);
int lst = 1;
res[0] = lst;
function <void(int, int)> dfs = [&](int v, int p) {
for (int to : g[v]) {
if (to == p) continue;
res[to] = lst + 1;
while (res[to] != res[v] + 1 &&
(res[to] % 2 != res[v] % 2 || res[to] - res[v] == 2)) {
res[to]++;
}
lst = res[to];
dfs(to, v);
}
};
dfs(0, 0);
for (int i : res) cout << i << ' ';
cout << endl;
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void dfs(int v, vector<vector<int>>& g, vector<int>& h, int p) {
h[v] = h[p] + 1;
for (int u : g[v]) {
if (u == p)
continue;
dfs(u, g, h, v);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector<vector<int>> g(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--, v--;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> h(n);
dfs(0, g, h, 0);
vector<vector<int>> hs(n + 1);
for (int i = 0; i < n; i++)
hs[h[i]].push_back(i);
int l = 2, r = 2 * n;
int cur = 0;
vector<int> ans(n);
for (int i = 1; i <= n; i++) {
if (cur) {
for (int v : hs[i]) {
ans[v] = r;
r -= 2;
}
}
else {
for (int v : hs[i]) {
ans[v] = l;
l += 2;
}
}
cur ^= 1;
}
bool found = false;
for (int i = 0; i < n; i++) {
for (int v : g[i]) {
if (h[v] < h[i])
continue;
if (abs(ans[v] - ans[i]) == 2) {
ans[v] = ans[i] - 1;
found = true;
break;
}
}
if (found)
break;
}
for (int i = 0; i < n; i++)
cout << ans[i] << ' ';
cout << '\n';
}
return 0;
}
Существует множество возможных решений этой проблемы, и почти все тестировщики реализовали уникальное решение. Есть решения, правильность которых мы не смогли доказать, но и взломать их тоже не смогли.
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, q;
cin >> n >> q;
vector < vector <int> > g(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--, v--;
g[u].push_back(v);
g[v].push_back(u);
}
vector <int> depth(n);
vector <int> d(n);
vector <int> par(n);
function <void(int, int)> dfs = [&](int v, int p) {
if (depth[v] == 1) d[v] = 1;
if (depth[v] > 1) d[v] = d[par[p]] + 2 * (int)g[p].size();
par[v] = p;
for(int to : g[v]) {
if (to == p) continue;
depth[to] = depth[v] + 1;
dfs(to, v);
}
};
dfs(0, 0);
while (q--) {
int v, p;
cin >> v >> p;
v--;
int res = d[v];
vector <int> cnt;
while (v != 0 && par[v] != 0) {
cnt.push_back((int)g[par[v]].size());
v = par[par[v]];
}
sort(cnt.rbegin(), cnt.rend());
for (int i = 0; i < min(p, (int)cnt.size()); i++) {
res -= 2 * (cnt[i] - 1);
}
cout << res << '\n';
}
}
int main() {
int tt;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, q;
cin >> n >> q;
vector < vector <int> > g(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--, v--;
g[u].push_back(v);
g[v].push_back(u);
}
vector <int> depth(n);
vector <int> d(n);
vector < vector < pair <int,int> > > qrs(n); // <p, idx>
vector <int> res(q);
for (int i = 0; i < q; i++) {
int v, p;
cin >> v >> p;
v--;
qrs[v].push_back({p, i});
}
multiset <int> st[2]; // store negative number to be able to use usual foreach loop
function <void(int, int, int)> dfs = [&](int v, int p, int pp) {
if (depth[v] == 1) d[v] = 1;
if (depth[v] > 1) d[v] = d[pp] + 2 * (int)g[p].size();
for (pair <int, int> qr : qrs[v]) {
int p = qr.first, idx = qr.second;
int ans = d[v];
for (int i : st[1 - depth[v] % 2]) {
if (p == 0) break;
ans -= (-i - 1) * 2;
p--;
}
res[idx] = ans;
}
if (depth[v] != 0) st[depth[v] % 2].insert(-(int)g[v].size());
for (int to : g[v]) {
if (to == p) continue;
depth[to] = depth[v] + 1;
dfs(to, v, p);
}
if (depth[v] != 0) st[depth[v] % 2].erase(st[depth[v] % 2].find(-(int)g[v].size()));
};
dfs(0, 0, 0);
for (int i = 0; i < q; i++)
cout << res[i] << '\n';
}
int main() {
int tt;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
Изначально эта задача имела следующие ограничения:
$$$1 \le n, q \le 2 \cdot 10^5$$$
Сумма $$$p$$$ во всех запросах не больше $$$2 \cdot 10^5$$$
Как решить эту задачу?
Могли бы вы решить эту задачу и без второго ограничения?
Однако это несложно благодаря недавнему блогу.
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3000010;
const int mod = 998244353;
int fact[N], ifact[N], phi[N];
int powmod(int a, int n) {
int res = 1;
while (n) {
if (n % 2 == 0) {
a = (a * a) % mod;
n /= 2;
}
else {
res = (res * a) % mod;
n--;
}
}
return res;
}
int inv(int a) {
return powmod(a, mod - 2);
}
void prepare() {
fact[0] = 1;
for (int i = 1; i < N; i++) {
fact[i] = (fact[i - 1] * i) % mod;
}
ifact[N - 1] = inv(fact[N - 1]);
for (int i = N - 2; i >= 0; i--) {
ifact[i] = (ifact[i + 1] * (i + 1)) % mod;
}
phi[0] = 0;
phi[1] = 1;
for (int i = 2; i < N; i++) {
phi[i] = i - 1;
}
for (int i = 2; i < N; i++) {
for (int j = i * 2; j < N; j += i) {
phi[j] -= phi[i];
}
}
}
int C(int n, int k) {
return ((fact[n] * ifact[k]) % mod * ifact[n - k]) % mod;
}
int MC(vector <int> &a) {
int sum=0;
for (int i : a) sum += i;
int res = fact[sum];
for (int i : a) {
res = (res * ifact[i]) % mod;
}
return res;
}
int lcm(int a, int b) {
return a / __gcd(a, b) * b;
}
vector <int> all_divs(int x) {
vector <int> d;
for (int i = 1; i * i <= x; i++) {
if (x % i == 0) {
d.push_back(i);
if (i * i != x) {
d.push_back(x / i);
}
}
}
return d;
}
void solve() {
int a, b, c, k;
cin >> a >> b >> c >> k;
vector <int> v(k);
for (int &i : v) cin >> i;
int g = v[0];
for (int i : v) g = __gcd(g, i);
map <int, int> mp;
for (int i : all_divs(a)) {
for (int j : all_divs(b)) {
for (int l : all_divs(c)) {
int N = lcm(i, lcm(j, l));
if (g % N == 0) {
mp[N] += phi[i] * phi[j] * phi[l];
}
}
}
}
int sum = 0;
for (pair <int, int> pr : mp) {
int N = pr.first, cnt = pr.second;
vector <int> u;
for (int t : v) u.push_back(t / N);
sum = (sum + (MC(u) * cnt) % mod) % mod;
}
sum = (sum * inv(a * b * c)) % mod;
cout << sum << endl;
}
int32_t main() {
prepare();
int tt;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3000010;
const int mod = 998244353;
int fact[N], ifact[N];
int pos[N];
int powmod(int a, int n) {
int res = 1;
while (n) {
if (n % 2 == 0) {
a = (a * a) % mod;
n /= 2;
}
else {
res = (res * a) % mod;
n--;
}
}
return res;
}
int inv(int a) {
return powmod(a, mod - 2);
}
void prepare() {
fact[0] = 1;
for (int i = 1;i < N; i++) {
fact[i] = (fact[i - 1] * i) % mod;
}
ifact[N - 1] = inv(fact[N - 1]);
for (int i = N - 2; i >= 0; i--) {
ifact[i] = (ifact[i + 1] * (i + 1)) % mod;
}
}
int C(int n, int k) {
return ((fact[n] * ifact[k]) % mod * ifact[n - k]) % mod;
}
int MC(vector <int> &a) {
int sum=0;
for (int i : a) sum += i;
int res = fact[sum];
for (int i : a) {
res = (res * ifact[i]) % mod;
}
return res;
}
int lcm(int a, int b) {
return a / __gcd(a, b) * b;
}
vector <int> all_divs(int x) {
vector <int> d1, d2;
for (int i = 1; i * i <= x; i++) {
if (x % i == 0) {
d1.push_back(i);
if (i * i != x) {
d2.push_back(x / i);
}
}
}
reverse(d2.begin(), d2.end());
for (int i : d2) d1.push_back(i);
return d1;
}
void solve() {
int a, b, c, k;
cin >> a >> b >> c >> k;
vector <int> v(k);
for (int &i : v) cin >> i;
int g = v[0];
for (int i : v) g = __gcd(g, i);
vector <int> divs_g = all_divs(g);
set <int> divs;
for (int i : all_divs(a)) divs.insert(i);
for (int i : all_divs(b)) divs.insert(i);
for (int i : all_divs(c)) divs.insert(i);
for (int i : all_divs(g)) divs.insert(i);
int D = divs.size();
int i = 0;
for (int j : divs) {
pos[j] = i;
i++;
}
int n = max({a, b, c}) + 1;
vector < vector <int> > tmp(3, vector <int> (D));
vector < vector <int> > cnt(3, vector <int> (D));
for (int t = 0; t < 3; t++) {
int x;
if (t == 0) x = a;
if (t == 1) x = b;
if (t == 2) x = c;
vector <int> divs_x = all_divs(x);
for (int i = (int)divs_x.size() - 1; i >= 0; i--) {
tmp[t][pos[divs_x[i]]] += x / divs_x[i];
for (int j = 0; j < i; j++) {
if (divs_x[i] % divs_x[j] == 0) {
tmp[t][pos[divs_x[j]]] -= tmp[t][pos[divs_x[i]]];
}
}
cnt[t][pos[x / divs_x[i]]] = tmp[t][pos[divs_x[i]]];
}
}
vector < vector <int> > dp(4, vector <int> (D));
dp[0][0] = 1;
for(int i = 0; i < 3; i++) {
for (int t1 : divs_g) {
for (int t2 : divs_g) {
int new_pos = lcm(t1, t2);
if (t2 < n) {
dp[i + 1][pos[new_pos]] = (dp[i + 1][pos[new_pos]] + dp[i][pos[t1]] * cnt[i][pos[t2]]) % mod;
}
}
}
}
int sum = 0;
i = 0;
for (int j : divs) {
if (g % j != 0) continue;
int N = j, cnt = dp[3][pos[j]];
vector <int> u;
for (int t : v) u.push_back(t / N);
sum = (sum + (MC(u) * cnt) % mod) % mod;
}
sum = (sum * inv(a * b * c)) % mod;
cout << sum << endl;
}
int32_t main() {
prepare();
int tt;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
Привет!
В 08.12.2024 17:35 (Московское время) состоится Codeforces Round 992 (Div. 2).
Задачи написал и подготовил Igor_Parfenov.
Я хотел бы поблагодарить всех, кто сделал этот раунд возможным:
Этот раунд будет рейтинговым для участников с рейтингом менее 2100.
У вас будет 2 часа для решения 6 задач.
Разбалловка: 500 — 1000 — 1500 — 2000 — 2250 — 2750.
Удачи!
UPD: Разбор
UPD: Поздравления победителям!
Div.2:
Div.1 + Div.2:
Добрый день. Пару месяцев назад я закончил написание книги и выставляю её в открытый доступ: GitHub
В чём идея? Контент этой книги представляет собой не только обучение языку C, но и обучение большому количеству прикладных вещей с серьёзной глубиной погружения. Я постарался дать ответ на как можно большее количество вопросов, которые возникают в процессе изучения, оставив минимальное количество дыр в понимании, как всё работает.
Посмотреть .html файл книги можно на GitHub-е. Но он не рендерит MathJax, поэтому лучше скачать файл c-book.html локально. Можно как угодно (в том числе в issues) сообщать мне о нерабочем коде в примерах, опечатках, неправильных утверждениях с моей стороны. Буду также рад увидеть конструктивную критику. Возможно, в ответ на неё, я буду добавлять новые главы в книгу.
(Эта книга абсолютно точно не является рекламой Zig-а.)
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int n, k, x = -1;
cin >> n >> k;
for (int i = 0; i <= n; i++) {
if (i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2 == k) {
x = i;
}
}
if (x == -1)
cout << "NO\n";
else {
cout << "YES\n";
for (int i = 0; i < n; i++) {
if (i < x)
cout << 1 << ' ';
else
cout << -1 << ' ';
}
cout << '\n';
}
}
return 0;
}
for tt in range(int(input())):
n, k = map(int, input().split())
x = -1
for i in range(0, n + 1):
if i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2 == k:
x = i
if x == -1:
print("NO")
else:
print("YES")
for i in range(0, n):
if i < x:
print("1 ", end = '')
else:
print("-1 ", end = '')
print("")
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int n, k;
cin >> n >> k;
vector <int> p(n);
for (int i = 0; i < n; i++) {
cin >> p[i];
p[i]--;
}
int bad = 0;
for (int i=0; i<n; i++) {
if (p[i] % k != i % k) {
bad++;
}
}
if(bad == 0)
cout << 0 << '\n';
else if(bad == 2)
cout << 1 << '\n';
else
cout << -1 << '\n';
}
return 0;
}
for tt in range(int(input())):
n, k = map(int, input().split())
p = list(map(int, input().split()))
for i in range(0, n):
p[i] -= 1
bad = 0
for i in range(0, n):
if p[i] % k != i % k:
bad += 1
if bad == 0:
print(0)
elif bad == 2:
print(1)
else:
print(-1)
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
map <int,int> a;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
for (int j = 2; j * j <= x; j++) {
while (x % j == 0) {
x /= j;
a[j]++;
}
}
if (x != 1) {
a[x]++;
}
}
int res = 0, rem = 0;
for (pair <int, int> p : a) {
int num = p.first;
int cnt = p.second;
res += cnt / 2;
rem += cnt % 2;
}
res += rem / 3;
cout << res << '\n';
}
return 0;
}
def is_prime(x):
i = 2
while i * i <= x:
if x % i == 0:
return False
i += 1
return True
def is_strongly_composite(x):
m = []
i = 2
while i * i <= x:
while x % i == 0:
x = x // i
m.append(i)
i += 1
if not x == 1:
m.append(i)
return (len(m) >= 3 or (len(m) == 2 and m[0] == m[1]))
for tt in range(int(input())):
n = int(input())
lst = list(map(int, input().split()))
a = {}
for x in lst:
i = 2
while i * i <= x:
while x % i == 0:
x = x // i
if i in a:
a[i] += 1
else:
a[i] = 1
i += 1
if x != 1:
if x in a:
a[x] += 1
else:
a[x] = 1
res, rem = 0, 0
for num in a:
cnt = a[num]
res += cnt // 2
rem += cnt % 2
res += rem // 3
print(res)
Изначально была более сложная версия этой задачи. Сможете ее решить?
Вам даны $$$n$$$ чисел $$$a_1, a_2, \dots, a_n$$$ ($$$a_i \gt 1$$$). Вы можете выполнить следующую операцию с массивом $$$a$$$ любое количество раз:
выбрать два индекса $$$i$$$ и $$$j$$$ ($$$i \lt j$$$);
удалить элементы $$$a_i$$$ и $$$a_j$$$ из $$$a$$$;
вставить элемент $$$a_i \cdot a_j$$$ в $$$a$$$.
После выполнения одной такой операции длина $$$a$$$ уменьшается на единицу.
Назовем массив $$$a$$$ хорошим, если он содержит только сильно составные числа.
Какое минимальное количество операций необходимо выполнить, чтобы сделать массив $$$a$$$ хорошим.
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int n, k;
cin >> n >> k;
vector <int> x(k), c(k);
for (int i = 0; i < k; i++)
cin >> x[i];
for (int i = 0; i < k; i++)
cin >> c[i];
if (c[0] < 3 || c[0] > x[0]) {
cout << "NO\n";
continue;
}
string s;
char cur = 'a';
for (int i = 0; i < c[0] - 3; i++)
s.push_back('a');
for (int i = c[0] - 3; i < x[0]; i++) {
s.push_back(cur);
cur++;
if (cur == 'd') cur = 'a';
}
bool good = true;
for (int j = 1; j < k; j++) {
int dx = x[j] - x[j - 1];
int dc = c[j] - c[j - 1];
if (dc > dx) {
good = false;
break;
}
for (int i = 0; i < dc; i++)
s.push_back('c' + j);
for (int i = dc; i < dx; i++) {
s.push_back(cur);
cur++;
if (cur == 'd') cur = 'a';
}
}
if (good)
cout << "YES" << endl << s << endl;
else
cout << "NO" << endl;
}
return 0;
}
for tt in range(int(input())):
n, k = map(int, input().split())
x = list(map(int, input().split()))
c = list(map(int, input().split()))
if c[0] < 3 or c[0] > x[0]:
print("NO")
continue
s = ""
cur = 'a'
for i in range(0, c[0] - 3):
s += "a"
for i in range(c[0] - 3, x[0]):
s += cur
cur = chr(ord(cur) + 1)
if cur == 'd':
cur = 'a'
good = True
for j in range(1, k):
dx = x[j] - x[j - 1]
dc = c[j] - c[j - 1]
if dc > dx:
good = False
break
for i in range(0, dc):
s += chr(ord('c') + j)
for i in range(dc, dx):
s += cur
cur = chr(ord(cur) + 1)
if cur == 'd':
cur = 'a'
if good:
print("YES")
print(s)
else:
print("NO")
Изначально была упрощенная версия этой задачи с $$$k = 1$$$, но она совпала с другой задачей.
А как в этой задаче работает чекер?
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, l, r;
cin >> n >> l >> r;
vector < vector <int> > g(n);
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
a--, b--;
g[a].push_back(b);
g[b].push_back(a);
}
int res=0, size;
vector <int> used(n);
function <void(int)> dfs = [&] (int v) {
used[v] = true;
size++;
for (int to : g[v]) {
if (!used[to])
dfs(to);
}
};
for (int i = 0; i < n; i++) {
if (!used[i]) {
size = 0;
dfs(i);
if (size <= l + r - 1) {
res ^= size / l;
}
}
}
if (res)
cout << "Alice\n";
else
cout << "Bob\n";
return 0;
}
from sys import setrecursionlimit
import threading
def main():
n, l, r = map(int, input().split())
g = [[] for i in range(0, n)]
for i in range(0, n):
a, b = map(int, input().split())
a -= 1
b -= 1
g[a].append(b)
g[b].append(a)
res = 0
used = [False for i in range(0, n)]
def dfs(v):
used[v] = True
size = 1
for to in g[v]:
if not used[to]:
size += dfs(to)
return size
for i in range(0, n):
if not used[i]:
size = dfs(i)
if size <= l + r - 1:
res ^= size // l
if res:
print("Alice")
else:
print("Bob")
setrecursionlimit(10 ** 9)
threading.stack_size(2 ** 27)
thread = threading.Thread(target=main)
thread.start()
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int main(){
int n, s, t;
cin >> n >> s >> t;
s--, t--;
vector < vector <int> > g(n);
vector <int> previous(n, -1);
vector <int> inPath(n);
vector <long long> res(n);
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
a--, b--;
g[a].push_back(b);
g[b].push_back(a);
}
function <void (int, int)> dfs = [&] (int v, int p) {
for (int to : g[v]) {
if (to == p) continue;
previous[to] = v;
dfs(to, v);
}
};
function <void (int, int, long long)> dfs2 = [&] (int v, int p, long long k) {
res[v] = k * (long long)g[v].size();
for (int to : g[v]) {
if (to == p) continue;
dfs2(to, v, k);
}
};
dfs(s, -1);
int ptr = t;
inPath[t] = true;
while (ptr != s) {
res[previous[ptr]] = res[ptr] + 2;
ptr = previous[ptr];
inPath[ptr] = true;
}
for (int v = 0; v < n; v++) {
if (inPath[v]) {
res[v] = res[v] / 2 * (long long)g[v].size();
for (int to : g[v]) {
if (!inPath[to]) {
dfs2(to, v, res[v] / (int)g[v].size());
}
}
}
}
res[t]++;
for (long long i : res)
cout << i % mod << ' ';
cout<<'\n';
return 0;
}
from sys import setrecursionlimit
import threading
mod = 998244353
def main():
n, s, t = map(int, input().split())
s -= 1
t -= 1
g = [[] for i in range(0, n)]
previous = [-1 for i in range(0, n)]
inPath = [False for i in range(0, n)]
res = [0 for i in range(0, n)]
for i in range(0, n - 1):
a, b = map(int, input().split())
a -= 1
b -= 1
g[a].append(b)
g[b].append(a)
def dfs(v, p):
for to in g[v]:
if to == p:
continue
previous[to] = v
dfs(to, v)
def dfs2(v, p, k):
res[v] = k * len(g[v])
for to in g[v]:
if to == p:
continue
dfs2(to, v, k)
dfs(s, -1)
ptr = t
inPath[t] = True
while ptr != s:
res[previous[ptr]] = res[ptr] + 2
ptr = previous[ptr]
inPath[ptr] = True
for v in range(0, n):
if inPath[v]:
res[v] = res[v] // 2 * len(g[v])
for to in g[v]:
if not inPath[to]:
dfs2(to, v, res[v] // len(g[v]))
res[t] += 1
for i in res:
print(i % mod, end = ' ')
print("")
setrecursionlimit(10 ** 9)
threading.stack_size(2 ** 27)
thread = threading.Thread(target=main)
thread.start()
Привет!
В 27.04.2023 17:35 (Московское время) состоится Codeforces Round 868 (Div. 2).
Задачи написал и подготовил Igor_Parfenov.
Я хотел бы поблагодарить всех, кто сделал этот раунд возможным:
Этот раунд будет рейтинговым для участников с рейтингом менее 2100.
У вас будет 2 часа для решения 6 задач.
Разбалловка: 500 — 1000 — 1250 — 2000 — 2000 — 2500.
Удачи!
UPD: Разбор
UPD: Поздравления победителям!
Div.2:
Div.1 + Div.2:
#include <iostream>
#include <vector>
#include <functional>
using namespace std;
int main(){
function <bool()> func=[](){
vector <bool> a(1,true);
return a[0];
};
for(int i=0;i<10;i++)
cout<<func()<<'\n';
return 0;
}
Look at this code. It seems, the expected output is always 1. However, in
the output is always 0. In Codeforces::Clang++17 & Clang++20 the output is
==4924==ERROR: AddressSanitizer: heap-use-after-free on address 0x129004d0 at pc 0x00ff646e bp 0x116cf574 sp 0x116cf570 READ of size 4 at 0x129004d0 thread T0 #0 0xff646d in std::_Vb_reference<std::_Wrap_alloc<std::allocator > >::operator bool C:\Program Files (x86)\Microsoft Visual Studio\2017\Enterprise\VC\Tools\MSVC\14.11.25503\include\vector:2213 #1 0xff294d in std::_Invoker_ret<bool,0>::_Call<`lambda at p71.cpp:8:2...
Used: 46 ms, 16108 KB
#include <iostream>
#include <vector>
#include <functional>
using namespace std;
int main(){
function <bool()> func=[](){
vector <bool> a(1,true);
bool t=a[0];
return t;
};
for(int i=0;i<10;i++)
cout<<func()<<'\n';
return 0;
}
Now look at this code. Here in all previously mensioned compilers (including Clang++) the output is always 1.
I solved a problem in Timus, and approximately this function was called several times on sample. In my local Windows G++ 8.1.0 the output was always correct. In Timus the output was incorrect in first call (I got WA1). In Codeforcess::CustomTest the output first 3 times was correct, then incorrect (I mension, that internal body of the function with all variables' values it used was the same). I can show code with this behaviour, but not in public, as except this place, this is the correct solution of some problem.
В этом посте я подробно объясню принцип работы алгоритма Быстрого преобразования Фурье. Будет необходимо знание базовых операций с комплексными числами. Здесь приложена краткая реализация комплексных чисел.
/**< Будем представлять комплексное число парой (действительная часть, мнимая часть) */
typedef pair <long double,long double> comp;
const long double pi=2*acos(0.0);
/**< Сложение двух комплексных чисел */
comp operator +(comp a,comp b){
comp c={a.first+b.first,a.second+b.second};
return c;
}
/**< Разность двух комплексных чисел */
comp operator -(comp a,comp b){
comp c={a.first-b.first,a.second-b.second};
return c;
}
/**< Произведение двух комплексных чисел */
comp operator *(comp a,comp b){
comp c={a.first*b.first-a.second*b.second,a.first*b.second+a.second*b.first};
return c;
}
/**< Деление комплексного числа на действительное число */
comp operator /(comp a,long double b){
comp c={a.first/b,a.second/b};
return c;
}
Даны два полинома: $$$A = a_{0} + a_{1} \cdot x + \dots + a_{n-1} \cdot x^{n-1}$$$ и $$$B = b_{0} + b_{1} \cdot x + \dots + b_{n-1} \cdot x^{n-1}$$$. Для удобства будем записывать их как $$$[a_{0}, a_{1}, \cdot a_{n-1}]$$$ и $$$[b_{0}, b_{1}, \cdot b_{n-1}]$$$. Необходимо найти полином $$$C = A \cdot B$$$. Его размер равен $$$2n$$$.
Задачу можно решить за асимптотику $$$O(n^{2})$$$, напрямую посчитав $$$C = A \cdot B = [a_{0} \cdot b_{0}, a_{0} \cdot b_{1} + a_{1} \cdot b_{0}, \dots ] = [\sum\limits_{i \in [0,0]}(a_{i} \cdot b_{0-i}), \sum\limits_{i \in [0,1]}(a_{i} \cdot b_{1-i}), \dots, \sum\limits_{i \in [0,k]}(a_{i} \cdot b_{k-i}), \dots]$$$.
Решение с помощью быстрого преобразования Фурье будет состоять из трех шагов:
Вычислить $$$A(x_{0}), A(x_{1}), \dots A(x_{2n-1})$$$ и $$$B(x_{0}), B(x_{1}), \dots B(x_{2n-1})$$$.
Вычислить значение $$$C$$$ в точках: $$$C(x_{0}) = A(x_{0}) \cdot B(x_{0}), C(x_{1}) = A(x_{1}) \cdot B(x_{1}), \dots C(x_{2n-1}) = A(x_{2n-1}) \cdot B(x_{2n-1})$$$.
Интерполировать $$$C$$$ по известным $$$2n$$$ значениям.
Вычисление значения полинома в точке в общем случае решается за $$$O(n)$$$. Поэтому первый шаг требует $$$O(n^{2})$$$ действий. Второй шаг решается одним проходом по массивам за $$$O(n)$$$. Интерполяция полинома решается в общем случае за $$$O(n^{2})$$$ с помощью интерполяционной формулы Лагранжа. Итоговая асимптотика решения для произвольных $$$x_{0}, x_{1}, \dots x_{2n-1}$$$ — $$$O(n^{2})$$$. Количество действий может быть существенно уменьшено, если выбрать $$$x_{0}, x_{1}, \dots x_{2n-1}$$$ особым образом.
Рассмотрим множество $$$S$$$ комплексных чисел, модуль которых равен $$$1$$$. На комплексной плоскости ГМТ множества $$$S$$$ — окружность радиуса $$$1$$$ с центром в начале координат. Будем обозначать элемент множества $$$S$$$, аргумент которого равен $$$\phi$$$, как $$$\overline{\phi}$$$. Данное множество обладает замечательным свойством, на которое мы и будем опираться при написании алгоритма:
Теорема: Для $$$n \in \mathbb{Z}$$$ верно $$$(\overline{\phi})^{n} = \overline{n\phi}$$$.
Доказательство: докажем с помощью математической индукции. Для $$$n=0$$$ утверждение очевидно. Пусть утверждение верно для $$$n=k$$$. Докажем, что оно верно для $$$n=k+1$$$ и для $$$n=k-1$$$. $$$(\overline{\phi})^{k+1} = (\overline{\phi})^{k} \cdot \overline{\phi} = \overline{k\phi} \cdot \overline{\phi}$$$. Известно, что при перемножении комплексных чисел их модули перемножаются, а аргументы складываются. Поэтому $$$\overline{k\phi} \cdot \overline{\phi} = \overline {(k+1)\phi}$$$. Аналогично $$$(\overline{\phi})^{k-1} = \overline{k\phi} / \overline{\phi}$$$. Известно, что при делении комплексных чисел их модули делятся, а аргументы вычитаются. Поэтому $$$\overline{k\phi} / \overline{\phi} = \overline {(k-1)\phi}$$$.
Основной смысл этой теоремы — тот факт, что мы можем заменить степени на суммы. Кроме того, если выбрать в качестве множества $$$X$$$ точек числа $$$\overline{\frac{0 \cdot 2\pi}{2n}}, \overline{\frac{1 \cdot 2\pi}{2n}}, \dots \overline{\frac{(2n-1) \cdot 2\pi}{2n}}$$$, то любое число из этого множества в произвольной целой степени будет в этом множестве (говорят, множество $$$X$$$ замкнуто относительно операции целой степени).
Задача: дан многочлен $$$A = [a_{0}, a_{1}, \dots a_{n-1}]$$$. Необходимо вычислить $$$A(\overline{\frac{0 \cdot 2\pi}{n}}), A(\overline{\frac{1 \cdot 2\pi}{n}}), \dots A(\overline{\frac{(n-1) \cdot 2\pi}{n}})$$$. (Важно: выше мы вычисляли значения функция в $$$2n$$$ точках, так как нам необходимо знать $$$2n$$$ значений полинома $$$C$$$. Сейчас же мы вычислим значения в $$$n$$$ точках, а перед вызовом этого алгоритма просто допишем к $$$A$$$ $$$n$$$ нулей.) Для удобства будем считать $$$n$$$ целой степенью числа $$$2$$$.
Решение:
Будем решать задачу рекурсивно. Для $$$n=1$$$ нам необходимо вычислить массив из одного элемента $$$A(\overline{0}) = A(1) = a_{0}$$$. То есть, нам нужно вернуть массив без изменений.
Пусть теперь $$$n \ge 2$$$. Заметим, что $$$A(x) = a_{0}x^{0} + a_{1}x^{1} + \dots + a_{n-1}x^{n-1} = (a_{0} + a_{2}x^{2} + a_{4}x^{4} + \dots + a_{n-2}x^{n-2}) + x(a_{1} + a_{3}x^{2} + a_{5}x^{4} + \dots + a_{n-1}x^{n-2})$$$. Пусть $$$A_{1} = [a_{0}, a_{2}, a_{4}, \dots a_{n-2}]$$$ и $$$A_{2} = [a_{1}, a_{3}, a_{5}, \dots a_{n-1}]$$$. Тогда $$$A(x) = A_{1}(x^{2}) + x A_{2}(x^2)$$$. Кажется, что члены $$$x^{2k}$$$ усложняют задачу, но согласно теореме выше это $$$2kx$$$! Поэтому $$$A(x) = A_{1}(2x) + x A_{2}(2x)$$$.
Предположим, у нас есть алгоритм, решающий задачу для $$$n=\frac{k}{2}$$$. Решим задачу для $$$n=k$$$. Построим массивы $$$A_{1}$$$ и $$$A_{2}$$$ по определению выше и вызовем БПФ для них. Согласно предположению, мы умеем это делать. Теперь необходимо простроить БПФ для $$$A$$$. Пусть в массивах $$$B_{1}$$$ и $$$B_{2}$$$ лежат БПФ от них $$$A_{1}$$$ и $$$A_{2}$$$. Вспомним, что это $$$B_{1} = [A_{1}(\overline{\frac{0 \cdot 2\pi}{\frac{k}{2}}}), A_{1}(\overline{\frac{1 \cdot 2\pi}{\frac{k}{2}}}), \dots A_{1}(\overline{\frac{(\frac{k}{2}-1) \cdot 2\pi}{\frac{k}{2}}})]$$$ и $$$B_{2} = [A_{2}(\overline{\frac{0 \cdot 2\pi}{\frac{k}{2}}}), A_{2}(\overline{\frac{1 \cdot 2\pi}{\frac{k}{2}}}), \dots A_{2}(\overline{\frac{(\frac{k}{2}-1) \cdot 2\pi}{\frac{k}{2}}})]$$$. То есть, это значения полиномов $$$A_{1}$$$ и $$$A_{2}$$$ в $$$\frac{k}{2}$$$ точках равномерно распределенных по окружности комплексной плоскости. Пусть $$$B$$$ — результат БПФ для $$$A$$$. Заполним этот массив: $$$B[i] = A(\overline{\frac{i \cdot 2\pi}{k}}) = A_{1}(\overline{\frac{2i \cdot 2\pi}{k}}) + \overline{\frac{i \cdot 2\pi}{k}} \cdot A_{2}(\overline{\frac{2i \cdot 2\pi}{k}}) = A_{1}(\overline{\frac{i \cdot 2\pi}{\frac{k}{2}}}) + \overline{\frac{i \cdot 2\pi}{k}} \cdot A_{2}(\overline{\frac{i \cdot 2\pi}{\frac{k}{2}}}) = B_{1}[i] + \overline{\frac{i \cdot 2\pi}{k}} \cdot B_{2}[i]$$$. Для $$$i \ge \frac{k}{2}$$$ мы таким образом не можем посчитать $$$B[i]$$$, так как $$$B_{1}[i]$$$ и $$$B_{2}[i]$$$ мы явно не считали. Но заметим, что $$$B_{1}[i]=B_{1}[i+\frac{qk}{2}]$$$ и $$$B_{2}[i]=B_{2}[i+\frac{qk}{2}] \; q \in \mathbb{Z}$$$, то есть, значения функций периодические с периодом $$$T=\frac{k}{2}$$$. Но тогда для $$$i \ge \frac{k}{2}$$$ мы можем посчитать значения так: $$$B[i] = B_{1}[i-\frac{k}{2}] + \overline{\frac{i \cdot 2\pi}{k}} \cdot B_{2}[i-\frac{k}{2}]$$$, или для $$$i \lt \frac{k}{2}$$$ имеем $$$B[i+\frac{k}{2}] = B_{1}[i] + \overline{\frac{(i - \frac{k}{2}) \cdot 2\pi}{k}} \cdot B_{2}[i] = B_{1}[i] - \overline{\frac{i \cdot 2\pi}{k}} \cdot B_{2}[i]$$$, так как если отобразить аргумент комплексного числа, оно отобразится.
Асимптотика алгоритма $$$O(n \log{n})$$$.
/**< Будем передавать массивы по ссылке */
void fft(vector <comp> &a){
int n=a.size();
if(n==1) return; //Для полинома нулевой степени БПФ - он сам
vector <comp> a1(n/2),a2(n/2); //Кладем, чередуя, коэффициенты в a1 и a2
for(int i=0;i<n/2;i++)
a1[i]=a[i*2],a2[i]=a[i*2+1];
fft(a1),fft(a2);//Теперь в a1 и a2 - их БПФ
for(int i=0;i<n/2;i++){
comp x={cos(2*pi*i/n),sin(2*pi*i/n)}; //Это комплексное число с единичным модулем и аргументом равным 2*pi*i/n
a[i]=a1[i]+x*a2[i];
a[i+n/2]=a1[i]-x*a2[i];
}
}
Второй шаг плана выполняется за $$$O(n)$$$, необходимо просто одним проходом по массиву посчитать $$$C[i]=A[i] \cdot B[i]$$$.
Выполним теперь быструю интерполяцию. Заметим для начала, что уже написанный алгоритм БПФ решает следующую задачу: по данному массиву $$$A$$$ он считает:
$$$[w^{0} \quad w^{0} \quad w^{0} \dots \quad w^{0n-1}] \quad [a_{0}] \quad [x_{0}]$$$
$$$[w^{0} \quad w^{1} \quad w^{2} \dots \quad w^{1n-1}] \quad [a_{1}] \quad [x_{1}]$$$
$$$[w^{0} \quad w^{2} \quad w^{4} \dots \quad w^{2n-1}] \cdot [a_{2}] = [x_{2}]$$$
$$$[w^{0} \quad w^{3} \quad w^{6} \dots \quad w^{3n-1}] \quad [a_{3}] \quad [x_{3}]$$$
$$$\dots$$$
$$$[w^{0} \quad w^{n} \quad w^{2n} \dots \quad w^{n \cdot n -1}] \quad [a_{n-1}] \quad [x_{n-1}]$$$
, где $$$w = \overline{\frac{2\pi}{n}}$$$. (Это можно увидеть, перемножив матрицы и воспользовавшись тем, что $$$\overline{\phi}^{n} = \overline{n\phi}$$$.) Перепишем равенство в виде $$$W \cdot A = X$$$. Обратите внимание, что $$$W$$$ не зависит от содержимого $$$A$$$, для фиксированного $$$n$$$ она всегда одинакова. Теперь нам нужно по известному $$$X$$$ найти $$$A$$$. Предположим, что $$$W$$$ имеет обратную. Умножим равенство с двух сторон слева на обратную: $$$W^{-1} \cdot W \cdot X = W^{-1} \cdot A$$$, откуда $$$W^{-1} \cdot A = X$$$.
Утверждение: $$$W^{-1} = \frac{1}{n} \cdot$$$
$$$[w^{-0} \quad w^{-0} \quad w^{-0} \dots \quad w^{-0n+1}]$$$
$$$[w^{-0} \quad w^{-1} \quad w^{-2} \dots \quad w^{-1n+1}]$$$
$$$[w^{-0} \quad w^{-2} \quad w^{-4} \dots \quad w^{-2n+1}]$$$
$$$[w^{-0} \quad w^{-3} \quad w^{-6} \dots \quad w^{-3n+1}]$$$
$$$\dots$$$
$$$[w^{-0} \quad w^{-n} \quad w^{-2n} \dots \quad w^{-n \cdot n +1}]$$$
Доказательство: Нам необходимо показать, что $$$W \cdot W^{-1} = I$$$. Перемножим строку $$$i$$$ матрицы $$$W$$$ со столбцом $$$j$$$ матрицы $$$nW^{-1}$$$, так, что $$$i \neq j$$$. Имеем: $$$w^{0}w^{0} + w^{i}w^{-j} + w^{2i}w^{-2j} + \dots + w^{(n-1)i}w^{(n-1)j} = \overline{\frac{0(i-j) \cdot 2\pi}{n}} + \overline{\frac{1(i-j) \cdot 2\pi}{n}} + \overline{\frac{2(i-j) \cdot 2\pi}{n}} + \dots + \overline{\frac{(n-1)(i-j) \cdot 2\pi}{n}}$$$. Но это четное количество комплексных чисел, размещенных на единичной окружности с равным шагом, поэтому их сумма равна $$$0$$$. Перемножим теперь строку $$$i$$$ матрицы $$$W$$$ со столбцом $$$i$$$ матрицы $$$nW^{-1}$$$. Имеем $$$w^{0}w^{0} + w^{i}w^{-i} + w^{2i}w^{-2i} + \dots + w^{(n-1)i}w^{(n-1)i} = \overline{\frac{0 \cdot 2\pi}{n}} + \overline{\frac{0 \cdot 2\pi}{n}} + \overline{\frac{0 \cdot 2\pi}{n}} + \dots + \overline{\frac{0 \cdot 2\pi}{n}} = n$$$.
Будем искать $$$nW^{-1}X = nA$$$, а затем поделим результат на $$$n$$$. Тот факт, что теперь все степени в матрице $$$nW^{-1}$$$ отображены означает, что и значение $$$x$$$ в формуле $$$B[i] = B_{1}[i] + \overline{\frac{i \cdot 2\pi}{k}} \cdot B_{2}[i]$$$ должен поменять знак. Так как $$$B_{1}$$$ и $$$B_{2}$$$ содержат в качестве аргумента $$$x^{2}$$$, их значение не поменяется. Тогда $$$B[i] = B_{1}[i] + \overline{-\frac{i \cdot 2\pi}{k}} \cdot B_{2}[i]$$$. Аналогично $$$B[i+\frac{n}{2}] = B_{1}[i] - \overline{-\frac{i \cdot 2\pi}{k}} \cdot B_{2}[i]$$$.
Асимптотика алгоритма $$$O(n \log{n})$$$.
void revfft(vector <comp> &a){
int n=a.size();
if(n==1) return;
vector <comp> a1(n/2),a2(n/2);
for(int i=0;i<n/2;i++)
a1[i]=a[i*2],a2[i]=a[i*2+1];
revfft(a1),revfft(a2);
for(int i=0;i<n/2;i++){
comp x={cos(2*pi*i/n),-sin(2*pi*i/n)}; //Это комплексное число с единичным модулем и аргументом равным -2*pi*i/n
a[i]=a1[i]+x*a2[i];
a[i+n/2]=a1[i]-x*a2[i];
a[i]=a[i]/2; //Глубина рекурсии lb(n), поэтому мы поделим a на 2 всего lb(n) раз, в результате он уменьшится в n раз
a[i+n/2]=a[i+n/2]/2;
}
}
Теперь мы готовы написать умножение полиномов за $$$O(n \log{n})$$$.
vector <int> mult(vector <int> a,vector <int> b){
/**< Подготовка полиномов */
vector <comp> fa,fb; //Переводим числа в комплексные
for(int i=0;i<a.size();i++) fa.push_back({a[i],0});
for(int i=0;i<b.size();i++) fb.push_back({b[i],0});
int l=0;
while(1<<l < a.size()+b.size())
l++;
int n=1<<l; //n - наименьшая целая степень числа 2 не меньшая, чем сумма длин данных полиномов
while(fa.size()<n*2) fa.push_back({0,0}); // Дополняем массивы до размера 2n
while(fb.size()<n*2) fb.push_back({0,0});
fft(fa),fft(fb); //Шаг 1
for(int i=0;i<n*2;i++) //Шаг 2
fa[i]=fa[i]*fb[i];
revfft(fa); //Шаг 3
vector <int> res(fa.size()); // Переводим комплексные числа в целые
for(int i=0;i<fa.size();i++)
res[i]=(int)(fa[i].first+0.5);
while(!res.empty() && res.back()==0) res.pop_back();
return res;
}
Полученный алгоритм сильно блуждает по памяти, из за чего необходимые значения плохо кэшируются. Можно алгоритм сильно ускорить, изменив принцип обхода. Посмотрим, как в процессе вычисления БПФ делится наш полином. На первом этапе в первый полином попадают числа, чей последний бит в индексе равен $$$0$$$, а во второй полином — чей бит равен $$$1$$$. На втором этапе числа делятся по второму с конца биту. Иными словами, если мы отсортируем числа в зеркально написанной двоичной форме, массив на каждом этапе будет делится ровно на две части: левая половина уйдет в первый массив, а правая — во второй.
Хотелось бы вставить пояснительную картинку, но как это сделать, я так и не понял.
Для $$$n=4$$$, эта перестановка: $$$[0,2,1,3]$$$, для $$$n=8$$$, эта перестановка: $$$[0,4,2,6,1,5,3,7]$$$.
Отсортировать числа по зеркально написанной двоичной форме можно за $$$O(n)$$$. После этого мы можем избавиться от рекурсии. Для начала разделим массив на отрезки длины $$$2$$$ и посчитаем БПФ от них, запишем результат в них же. Затем разделим массив на отрезки длины $$$4$$$ и повторим процесс. Когда мы на очередном этапе хотим посчитать БПФ на отрезке $$$[l,r)$$$, в отрезках $$$[l,m)$$$ и $$$[m,r)$$$ уже записаны их БПФ.
void fft(vector <comp> &a){
int n=a.size();
/**< Сортировка по двоичной форме, записанной зеркально */
for(int i=1,j=0;i<n;i++){
int bit=(n>>1);
while(j>=bit){
j-=bit;
bit>>=1;
}
j+=bit;
if(i<j)
swap(a[i],a[j]);
}
for(int len=2;len<=n;len<<=1){ //Строим итеративно БПФ для отрезков длины 2, 4, 8, ... n
comp w={cos(2*pi/len),sin(2*pi/len)}; //Множитель, умножив на который, мы прокрутим аргумент на один пункт длины 2*pi/len дальше
for(int i=0;i<n;i+=len){ //Обрабатываем поблочно, i - начало очередного блока
comp cur_w={1,0}; //Аргумент
for(int j=0;j<len/2;j++){ //Итерируемся по блоку
comp u=a[i+j],v=a[i+j+len/2]*cur_w; //Так как записываем в эти элементы массива, их нужно скопировать
a[i+j]=u+v;
a[i+j+len/2]=u-v;
cur_w=cur_w*w; //Прокручиваем аргумент на угол 2*pi/len
} //Когда мы вышли из цикла, аргумент cur_w снова равен нулю, так как мы добавили 2*pi/len len раз.
}
}
}
void revfft(vector <comp> &a){
int n=a.size();
/**< Сортировка по двоичной форме, записанной зеркально */
for(int i=1,j=0;i<n;i++){
int bit=(n>>1);
while(j>=bit){
j-=bit;
bit>>=1;
}
j+=bit;
if(i<j)
swap(a[i],a[j]);
}
for(int len=2;len<=n;len<<=1){
comp w={cos(2*pi/len),-sin(2*pi/len)}; //Значения аргумента отображены
for(int i=0;i<n;i+=len){
comp cur_w={1,0};
for(int j=0;j<len/2;j++){
comp u=a[i+j],v=a[i+j+len/2]*cur_w;
a[i+j]=u+v;
a[i+j+len/2]=u-v;
cur_w=cur_w*w;
}
}
}
for(int i=0;i<n;i++) //Мы вычислили nW^{-1}, нужно разделить массив на n
a[i]=a[i]/n;
}
Так как мы $$$\log{n}$$$ раз проходимся по всему массиву без прыжков, данные хорошо кэшируются, и алгоритм ускоряется в $$$\sim 10$$$ раз.
В этом посте я расскажу о четырех основных и простых алгоритмах поиска максимального потока, к каждому алгоритму прилагается описание работы, псевдокод, нестрогое объяснение корректности, реализация на C++11, и ссылки на задачи.
Пусть дан граф $$$G= \lt V,E \gt $$$ и две вершины $$$s,t \in V$$$, которые в дальнейшем будем называть исток и сток, и каждому ребру из вершины $$$a$$$ в вершину $$$b$$$ сопоставлена пропускная способность $$$c_{a,b}$$$. Определим сопоставление каждому ребру $$$ \lt a,b \gt $$$ числа $$$g_{a,b}$$$. Назовем это сопоставление потоком, если для каждого ребра $$$ \lt a,b \gt $$$ верны два утверждения:
1) $$$0 \le g_{a,b} \le c_{a,b}$$$
2) $$$ \sum_{i \in V} g_{i,a} = \sum_{i \in V} g_{a,i} \forall a \in V \setminus \{ s,t \} $$$
Величина потока равна $$$ \sum_{i \in V} g_{s,i} = \sum_{i \in V} g_{i,t} = |F|$$$. Задача — вычислить $$$|F|$$$ и все $$$g_{a,b}$$$.
Пусть дан граф с пропускными способностями. Будем хранить его пропускные способности в матрице смежности $$$c[][]$$$, если ребра $$$ \lt a,b \gt $$$ нет в графе, $$$c[a][b]=0$$$. Определим операцию проталкивания потока: пусть мы выбрали путь $$$p_{1},p_{2}, \dots ,p_{k}$$$ из истока $$$s$$$ в сток $$$t$$$ такой, что пропускные способности между соседними вершинами положительны: $$$c_{p_{i-1},p_{i}} \gt 0 \forall i \in [2,k]$$$. Пусть $$$AugFlow$$$ — минимальная пропускная способность на ребре на пути: $$$AugFlow = min_{i \in [2,k]} c_{p_{i-1},p_{i}}$$$. Пройдем по этому пути и вычтем из пропускных способностей $$$AugFlow$$$ по направлению к стоку и добавим против стока. Итак, если у нас есть путь ненулевой пропускной способности, мы можем увеличить поток. Можно ли, вычисляя такие пути, всегда найти максимальный поток? Работает следующая теорема:
Теорема 1.1 Для того, чтобы поток был максимальным, необходимо и достаточно, чтобы отсутствовал путь из истока в сток ненулевой пропускной способности.
поток:=0;
пока истина:
найти любой путь из истока в сток p[];
если путь не нашелся:
выйти из цикла;
иначе:
дополняющий_поток:=min(c[p[i-1]][p[i]]);
поток+=дополняющий_поток;
для всех i:=1 до p.size-1:
c[p[i-1]][p[i]]-=дополняющий_поток;
c[p[i]][p[i-1]]+=дополняющий_поток;
Асимптотика Если пропускные способности целочисленные, то дополняющий поток всегда не меньше единицы. Тогда, так как асимптотика обхода графа $$$O(E)$$$, асимптотика алгоритма составляет $$$O(E|F|)$$$. К сожалению, это не так для графов с вещественными пропускными способностями. Но если использовать обход графа в ширину, действует следующая теорема:
Теорема 1.2 В течении алгоритма с обходом в ширину расстояние от истока до любой вершины по ребрам ненулевой пропускной способности не уменьшается.
Это дает еще одну асимптотику: $$$O(VE^{2})$$$. Данный алгоритм называется алгоритмом Эдмондса-Карпа. Его реализация здесь дана.
/**
* Дано количество вершин и ребер, исток и сток, затем ребра с их пропускными способностями.
* Везде 0-индексация. Необходимо вывести максимальный поток и матрицу остаточных пропускных способностей.
*/
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
const int inf=1e9;
int n,m,s,t;//Количество вершин и ребер, исток и сток
int c[1000][1000];//Матрица пропускных способностей
int main(){
scanf("%d %d %d %d",&n,&m,&s,&t);
for(int i=0;i<m;i++){
int a,b,cap;
scanf("%d %d %d",&a,&b,&cap);
c[a][b]=cap;
}
int MaxFlow=0;//Искомый максимальный поток
while(true){
/**< Поиск в ширину */
vector <int> parent(n,-1);
vector <bool> used(n,false);
queue <int> q;
used[s]=true;
q.push(s);
while(!q.empty()){
int v=q.front();
q.pop();
for(int i=0;i<n;i++){
if(!used[i] && c[v][i]>0){
parent[i]=v;
used[i]=true;
q.push(i);
}
}
}
if(!used[t])//Не дошли до стока - поток уже максимальный
break;
int AugFlow=inf;//Дополнительный поток
/**< Бежим по пути и ищем ребро с минимальной пропускной способностью */
int ptr=t;
while(ptr!=s){
AugFlow=min(AugFlow,c[parent[ptr]][ptr]);
ptr=parent[ptr];
}
/**< Изменяем пропускные способности */
ptr=t;
while(ptr!=s){
c[parent[ptr]][ptr]-=AugFlow;//По пути вычитаем
c[ptr][parent[ptr]]+=AugFlow;//Против пути добавляем
ptr=parent[ptr];
}
MaxFlow+=AugFlow;
}
/**< Выводим ответ */
printf("%d\n",MaxFlow);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
printf("%3d ",c[i][j]);
}
printf("\n");
}
return 0;
}
Алгоритм Форда-Фалкерсона можно ускорить, использую следующую идею. Выполним поиск в ширину из истока и, игнорируя ребра с нулевой пропускной способностью, вычислим расстояния $$$d[]$$$ до каждой вершины. Будем говорить, что мы построили слоистую сеть. Затем будем искать такие дополняющие пути $$$p[]$$$, что $$$d[p[1]]-d[p[0]]=d[p[2]]-d[p[1]]= \dots =1$$$. Все эти пути можно найти довольно быстро — за $$$O(VE)$$$: очевидно, что в силу ограничения, наложенного на путь, если по ребру $$$ \lt a,b \gt $$$ не удалось протолкнуть путь, в течении фазы по нему нельзя будет протолкнуть путь. Поэтому будем поддерживать у каждой вершины первую нерассмотренную вершину для каждой фазы, и искать следующие пути в этой фазе, начиная с первой нерассмотренной вершины и увеличивать это значение, если путь с этой вершины не нашелся. После того, как мы нашли все пути, мы приступаем к следующей фазе. При этом работает следующая теорема:
Теорема 2.1 Расстояние до стока после каждой фазы строго возрастает.
Тогда, так как путь из истока в сток не больше $$$V$$$, количество фаз $$$O(V)$$$.
c[][]
left[];
d[];
функция решить():
поток:=0;
пока истина:
вычислить расстояния до каждой вершины d[];
если пути до стока нет:
выйти из цикла;
заполнить(left[],V,0);
пока истина:
дополняющий_поток=протолкнуть(s,inf);
если дополняющий_поток==0:
выйти из цикла;
иначе:
поток+=дополняющий_поток;
функция протолкнуть(вершина,поток):
если вершина==сток:
вернуть поток;
пока left[вершина]<V:
если d[left[вершина]]+1==d[вершина] и c[вершина][left[вершина]]>0:
дополняющий_поток=протолкнуть(left[вершина],min(поток,c[вершина][left[вершина]]));
если дополняющий_поток>0:
c[вершина][left[вершина]]-=дополняющий_поток;
c[left[вершина]][вершина]+=дополняющий_поток;
вернуть дополняющий_поток;
вернуть 0;
Асимптотика $$$O(V)$$$ фаз и $$$O(VE)$$$ на каждую фазу — итого $$$O(V^{2}E)$$$.
Частный случай использования этого алгоритма для поиска максимального паросочетания в двудольном графе называется алгоритмом Хопкрофта-Карпа. Он имеет более сильную асимптотику $$$O(\sqrt{V}E)$$$.
/**
* Дано количество вершин и ребер, исток и сток, затем ребра с их пропускными способностями.
* Везде 0-индексация. Необходимо вывести максимальный поток и матрицу остаточных пропускных способностей.
*/
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
const int inf=1e9;
int n,m,s,t;//Количество вершин и ребер, исток и сток
int c[1000][1000];//Матрица пропускных способностей
int d[1000];//Расстояния
int left[1000];//Самый левый нерассмотренный сосед
/**< Построить слоистую сеть обходом в ширину */
void buildNet(){
for(int i=0;i<n;i++)
d[i]=-1;//Пути до вершины нет
queue <int> q;
d[s]=0;
q.push(s);
while(!q.empty()){
int v=q.front();
q.pop();
for(int i=0;i<n;i++){
if(d[i]==-1 && c[v][i]>0){
d[i]=d[v]+1;
q.push(i);
}
}
}
}
/**< Протолкнуть поток обходом в глубину */
int push(int v,int flow){
/**< Уже прошли какой-то путь из s в v, минимальная пропускная способность - flow */
if(v==t){//Если зашли в сток, нашли дополняющий путь, возвращаем минимальную пропускную способность на пути, завершаем обход
return flow;
}
for(;left[v]<n;left[v]++){//Перебираем вершины не от начала (без этого алгоритм деградирует!)
int to=left[v];
if(d[to]==d[v]+1 && c[v][to]>0){//Если вершина на следующем слое
int AugFlow=push(to,min(flow,c[v][to]));//Проталкиваем от нее, путь увеличился на ребро c[v][to], поэтому flow возможно уменьшился
if(AugFlow>0){//Если протолкнули - завершаем обход
c[v][to]-=AugFlow;//По пути вычитаем
c[to][v]+=AugFlow;//Против пути добавляем
return AugFlow;
}
}
}
return 0;
}
int main(){
scanf("%d %d %d %d",&n,&m,&s,&t);
for(int i=0;i<m;i++){
int a,b,cap;
scanf("%d %d %d",&a,&b,&cap);
c[a][b]=cap;
}
int MaxFlow=0;//Искомый максимальный поток
while(true){
buildNet();//Строим новую слоистую сеть
if(d[t]==-1)//Если пути до стока нет, поток максимальный
break;
for(int i=0;i<n;i++)//Начинаем новые проталкивания
left[i]=0;
while(true){
int AugFlow=push(0,inf);//Проталкиваем из истока, пока минимальная пропускная способность на пути отсутствует
if(AugFlow==0)//Если не протолкнули, строим новую слоистую сеть
break;
else
MaxFlow+=AugFlow;//Добавляем дополняющий поток
}
}
/**< Выводим ответ */
printf("%d\n",MaxFlow);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
printf("%3d ",c[i][j]);
}
printf("\n");
}
return 0;
}
Назовем предпотоком сопоставление каждому ребру в графе числа, при котором выполняется:
1) $$$0 \le g_{a,b} \le c_{a,b}$$$
2) $$$ \sum_{i \in V} g_{i,a} \ge \sum_{i \in V} g_{a,i} \forall a \in V \setminus \{ s,t \} $$$
Определим переполнение $$$e_{i}$$$ вершины как значение $$$ \sum_{i \in V} g_{i,a} - \sum_{i \in V} g_{a,i} $$$, и высоту $$$h_{i}$$$ вершины. Будем выполнять две операции:
1) Проталкивание из вершины $$$a$$$ в вершину $$$b$$$. Допустимо тогда, когда $$$h_{a}=h_{b}+1$$$. Проталкиваем столько потока, на сколько переполнена $$$a$$$, но не более, чем может вместить ребро $$$ \lt a,b \gt $$$: $$$pushed=min(e_{a},c_{a,b})$$$.
2) Поднятие вершины $$$a$$$: допустимо, если $$$a$$$ переполнена, но нет такой вершины $$$b$$$, что $$$h_{a}=h_{b}+1$$$.
Алгоритм заключается в использовании этих операций в любом порядке, пока хотя бы одна из них допустима. Можно для удобства определить операцию разрядить вершину, которая выполняет проталкивания из нее и поднятия, пока она переполнена (это не повлияет на асимптотику).
Перед основным циклом необходимо выполнить следующую инициализацию: проталкиваем тривиально из истока во все соседние вершины.
c[][];
e[];
h[];
функция решить():
e[s]=inf;
h[s]=n;
для всех i:=1 до n:
h[i]:=0;
если c[s][i]>0:
протолкнуть(s,i);
пока есть переполненная вершина i, которая не исток или сток:
разрядить(i);
функция протолкнуть(откуда,куда):
величина:=min(e[откуда],c[откуда][куда]);
e[откуда]-=величина;
e[куда]+=величина;
c[откуда][куда]-=величина;
c[откуда][куда]+=величина;
функция поднять(вершина):
h[вершина]:=1+min(h[i]) для такой i что c[вершина][i]>0, если такой i существует;
функция разрядить(вершина):
пока вершина переполнена:
для всех i:=1 до n:
если c[вершина][i]>0 и h[вершина]==h[i]+1:
протолкнуть(вершина,i);
поднять(вершина);
Теорема 3.1 Подъем вершины строго увеличивает ее высоту.
Теорема 3.2 Если ни одно действие недопустимо — предпоток есть максимальный поток.
Асимптотика Высота каждой вершины во время работы алгоритма не превышает $$$2V$$$, откуда количество вызовов операции поднять есть $$$O(V^{2})$$$, а количество вызовов операции протолкнуть есть $$$O(V^{2}E)$$$. Итоговая асимптотика — $$$O(V^{2}E)$$$.
/**
* Дано количество вершин и ребер, исток и сток, затем ребра с их пропускными способностями.
* Везде 0-индексация. Необходимо вывести максимальный поток и матрицу остаточных пропускных способностей.
*/
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
const int inf=1e9;
int n,m,s,t;//Количество вершин и ребер, исток и сток
int c[1000][1000];//Матрица пропускных способностей
int e[1000],h[1000];//Переполнение и высота
int MaxFlow=0;//Максимальный поток
/**< Протолкнуть по ребру */
int push(int from,int to){
int pushed=min(e[from],c[from][to]);//Проталкиваем на столько, на сколько переполнен from, но не более, чем позволит протолкнуть ребро
if(to==t)//Если протолкнули в сток, добавляем в ответ
MaxFlow+=pushed;
e[from]-=pushed;
e[to]+=pushed;
c[from][to]-=pushed;
c[to][from]+=pushed;
return pushed;
}
/**< Поднять вершину */
void lift(int v){
/**< Ищем вершину с минимальной высотой и устанавливаем высоту на единицу больше, если таковая есть */
int New=inf;
for(int i=0;i<n;i++){
if(c[v][i]>0){
New=min(New,h[i]);
}
}
if(New!=inf)
h[v]=New+1;
}
/**< Разрядить */
void discharge(int v){
/**< Пока вершина переполнена, проталкиваем во все вершины, затем поднимаем */
while(e[v]>0){
for(int i=0;i<n;i++){
if(c[v][i]>0 && h[v]==h[i]+1){
push(v,i);
}
}
lift(v);
}
}
int main(){
scanf("%d %d %d %d",&n,&m,&s,&t);
for(int i=0;i<m;i++){
int a,b,cap;
scanf("%d %d %d",&a,&b,&cap);
c[a][b]=cap;
}
/**< Начальная инициализация */
e[s]=inf;
h[s]=n;
for(int i=0;i<n;i++){
if(c[s][i]>0){
push(s,i);
}
}
while(true){
bool good=false;//Есть вершины, которые нужно разрядить
for(int i=0;i<n;i++){
if(i!=s && i!=t && e[i]>0){
discharge(i);
good=true;
}
}
if(!good)//Все вершины разряжены - предпоток есть максимальный поток
break;
}
/**< Выводим ответ */
printf("%d\n",MaxFlow);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
printf("%3d ",c[i][j]);
}
printf("\n");
}
return 0;
}
Задачи 4 5
Те же, что и для Диница
Краткая идея: будем хранить все переполненные вершины в очереди, и разряжать первую вершину.
c[][];
e[];
h[];
очередь;
функция решить():
e[s]=inf;
h[s]=n;
для всех i:=1 до n:
h[i]:=0;
если c[s][i]>0:
протолкнуть(s,i);
пока очередь не пуста:
разрядить(очередь.начало);
очередь.удалить_начало;
функция протолкнуть(откуда,куда):
величина:=min(e[откуда],c[откуда][куда]);
если e[куда]==0 и куда не исток или сток:
положить куда в очередь;
e[откуда]-=величина;
e[куда]+=величина;
c[откуда][куда]-=величина;
c[откуда][куда]+=величина;
функция поднять(вершина):
h[вершина]:=1+min(h[i]) для такой i что c[вершина][i]>0, если такой i существует;
функция разрядить(вершина):
пока вершина переполнена:
для всех i:=1 до n:
если c[вершина][i]>0 и h[вершина]==h[i]+1:
протолкнуть(вершина,i);
поднять(вершина);
Асимптотика $$$O(V^{3})$$$.
/**
* Дано количество вершин и ребер, исток и сток, затем ребра с их пропускными способностями.
* Везде 0-индексация. Необходимо вывести максимальный поток и матрицу остаточных пропускных способностей.
*/
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
const int inf=1e9;
int n,m,s,t;//Количество вершин и ребер, исток и сток
int c[1000][1000];//Матрица пропускных способностей
int e[1000],h[1000];//Переполнение и высота
int MaxFlow=0;//Максимальный поток
queue <int> q;//Очередь
/**< Протолкнуть по ребру */
int push(int from,int to){
int pushed=min(e[from],c[from][to]);//Проталкиваем на столько, на сколько переполнен from, но не более, чем позволит протолкнуть ребро
if(to==t)//Если протолкнули в сток, добавляем в ответ
MaxFlow+=pushed;
if(e[to]==0 && to!=t)//Вершина to не была переполненной, а теперь переполненна
q.push(to);
e[from]-=pushed;
e[to]+=pushed;
c[from][to]-=pushed;
c[to][from]+=pushed;
return pushed;
}
/**< Поднять вершину */
void lift(int v){
/**< Ищем вершину с минимальной высотой и устанавливаем высоту на единицу больше, если таковая есть */
int New=inf;
for(int i=0;i<n;i++){
if(c[v][i]>0){
New=min(New,h[i]);
}
}
if(New!=inf)
h[v]=New+1;
}
/**< Разрядить */
void discharge(int v){
/**< Пока вершина переполнена, проталкиваем во все вершины, затем поднимаем */
while(e[v]>0){
for(int i=0;i<n;i++){
if(c[v][i]>0 && h[v]==h[i]+1){
push(v,i);
}
}
lift(v);
}
}
int main(){
scanf("%d %d %d %d",&n,&m,&s,&t);
for(int i=0;i<m;i++){
int a,b,cap;
scanf("%d %d %d",&a,&b,&cap);
c[a][b]=cap;
}
/**< Начальная инициализация */
e[s]=inf;
h[s]=n;
for(int i=0;i<n;i++){
if(c[s][i]>0){
push(s,i);
}
}
/**< Пока есть переполненные вершины - разрядить */
while(!q.empty()){
int v=q.front();
q.pop();
discharge(v);
}
/**< Выводим ответ */
printf("%d\n",MaxFlow);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
printf("%3d ",c[i][j]);
}
printf("\n");
}
return 0;
}
Задачи 6
К сожалению, к данной задаче принимается Диниц, а не должен.
...
| Название |
|---|


