Задача предложена пользователем Ali Ibrahim C137.
Заметим, что если есть пара соседних не взаимнопростых чисел, то мы обязаны между ними вставить какое-нибудь число. С другой стороны мы всегда можем вставить число 1.
Решение на С++const int N = 1010;
int n, a[N];
bool read() {
if (!(cin >> n)) return false;
forn(i, n) assert(scanf("%d", &a[i]) == 1);
return true;
}
void solve() {
function<int(int, int)> gcd = [&](int a, int b) { return !a ? b : gcd(b % a, a); };
vector<int> ans;
forn(i, n) {
ans.pb(a[i]);
if (i + 1 < n && gcd(a[i], a[i + 1]) > 1)
ans.pb(1);
}
cout << sz(ans) - n << endl;
forn(i, sz(ans)) {
if (i) putchar(' ');
printf("%d", ans[i]);
}
puts("");
}
Сложность: O(nlogn).
Задача предложена пользователем Srikanth Bhat bharsi.
В этой задаче нужно было сделать ровно то, что написано в условии. Никаких хитростей и подвохов.
Решение на C++int n, m;
bool read() {
return !!(cin >> n >> m);
}
const int N = 111;
int a[N][4];
void solve() {
forn(i, n) {
a[i][0] = 2 * i;
a[i][1] = 2 * (n + i);
a[i][2] = 2 * (n + i) + 1;
a[i][3] = 2 * i + 1;
}
vector<int> ans;
forn(i, n) {
ans.pb(a[i][1]);
ans.pb(a[i][0]);
ans.pb(a[i][2]);
ans.pb(a[i][3]);
}
nfor(i, sz(ans)) // inverse order
if (ans[i] >= m)
ans.erase(ans.begin() + i);
forn(i, m) {
if (i) putchar(' ');
printf("%d", ans[i] + 1);
}
puts("");
}
Сложность: O(n).
Задача предложена пользователем Mohammad Amin Raeisi Smaug.
Назовём отрезок [l, r] хорошим если в нём не более k ноликов. Заметим, что если отрезок [l, r] хороший, то отрезок [l + 1, r] тоже хороший. Таким образом, можно воспользоваться методом двух указателей: один указатель это l, а второй это r. Будем перебирать l слева направо и двигать r пока можем (для этого нужно просто поддерживать количество ноликов в текущем отрезке).
Решение на C++const int N = 1200300;
int n, k;
int a[N];
bool read() {
if (!(cin >> n >> k)) return false;
forn(i, n) assert(scanf("%d", &a[i]) == 1);
return true;
}
void solve() {
int ansl = 0, ansr = 0;
int j = 0, cnt = 0;
forn(i, n) {
if (j < i) {
j = i;
cnt = 0;
}
while (j < n) {
int ncnt = cnt + !a[j];
if (ncnt > k) break;
cnt += !a[j];
j++;
}
if (j - i > ansr - ansl)
ansl = i, ansr = j;
if (cnt > 0) cnt -= !a[i];
}
cout << ansr - ansl << endl;
fore(i, ansl, ansr) a[i] = 1;
forn(i, n) {
if (i) putchar(' ');
printf("%d", a[i]);
}
puts("");
}
Сложность: O(n + k).
Задачу предложена участником Sadegh Mahdavi smahdavi4.
Как известно диагонали параллелограмма делят друг друга пополам. Переберём пару точек a, b и рассмотрим середину отрезка : c = (a + b) / 2. Для всех середин отрезков посчитаем число cntc — количество пар точек, с этой серединой. Легко видеть, что ответ это .
Решение на C++const int N = 2020;
int n;
int x[N], y[N];
bool read() {
if (!(cin >> n)) return false;
forn(i, n)
assert(scanf("%d%d", &x[i], &y[i]) == 2);
return true;
}
inline li C2(li n) { return n * (n - 1) / 2; }
void solve() {
map<pti, int> cnt;
forn(i, n)
forn(j, i) {
int cx = x[i] + x[j];
int cy = y[i] + y[j];
cnt[{cx, cy}]++;
}
li ans = 0;
for (const auto& p : cnt)
ans += C2(p.y);
cout << ans << endl;
}
Сложность: O(n2logn).
Задача предложена пользователем Lewin Gan Lewin.
Рассмотрим некоторую подпоследовательность длины k > 0 (пустые подпоследовательности можно учесть отдельно, прибавив в конце к ответу число mn) и посчитаем количество последовательностей в которых она будет учтена. Нам это нужно сделать аккуратно, чтобы всё посчитать ровно по одному разу. Пусть x1, x2, ... , xk это наша подпоследовательность. Тогда в исходной последовательности перед элементом x1 могли находиться ещё числа, но число x1 не могло встретиться (поскольку мы хотим всё посчитать по разу, варианты когда x1 уже встречалось нам не нужно учитывать). Таким образом, у нас (m - 1) вариант для каждого из чисел перед x1. Аналогичо, между числами x1 и x2 могут находиться некоторые числа (но не может находиться число x2). И так далее. После числа xk может находиться ещё некоторое количество чисел (пусть их j штук), причём на них не накладывается никаких ограничений (то есть m вариантов для каждого числа). Мы зафиксировали, что в конце стоит j чисел, значит n - k - j чисел нужно распределить между числами перед x1, между x1 и x2, \ldots , между xk - 1 и xk. Легко видеть, что это можно сделать способами (это просто биномиальный коэффициент с повторениями). Количество последовательностей x1, x2, ... , xk, конечно, равно mk. Таким образом, ответ это . Последнюю сумму легко преобразовать к виду . Заметим, что последняя внутренняя сумма легко суммируется с помощью известной формулы параллельного суммирования: . Таким образом, ответ равен: . Можно далее сворачивать сумму, чтобы получить логарифмическое решение (закнутую формулу), но в задаче это не требовалось.
Решение на C++int n, m;
bool read() {
return !!(cin >> n >> m);
}
const int N = 1200300;
const int mod = 1000 * 1000 * 1000 + 7;
int gcd(int a, int b, int& x, int& y) {
if (!a) {
x = 0, y = 1;
return b;
}
int xx, yy, g = gcd(b % a, a, xx, yy);
x = yy - b / a * xx;
y = xx;
return g;
}
inline int inv(int a) {
int x, y;
assert(gcd(a, mod, x, y) == 1);
x %= mod;
return x < 0 ? x + mod : x;
}
inline int mul(int a, int b) { return int(a * 1ll * b % mod); }
inline int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
inline int sub(int a, int b) { return a - b < 0 ? a - b + mod : a - b; }
inline void inc(int& a, int b) { a = add(a, b); }
int fact[N], ifact[N];
inline int C(int n, int k) {
if (k < 0 || k > n) return 0;
return mul(fact[n], mul(ifact[k], ifact[n - k]));
}
int pm[N], pm1[N];
void solve() {
const int N = n + 1;
fact[0] = 1; fore(i, 1, N) fact[i] = mul(fact[i - 1], i);
forn(i, N) ifact[i] = inv(fact[i]);
pm[0] = 1; fore(i, 1, N) pm[i] = mul(pm[i - 1], m);
pm1[0] = 1; fore(i, 1, N) pm1[i] = mul(pm1[i - 1], sub(m, 1));
int ans = pm[n];
fore(s, 1, n + 1) {
int cur = 1;
cur = mul(cur, pm[s]);
cur = mul(cur, pm1[n - s]);
cur = mul(cur, C(n, s - 1));
inc(ans, cur);
}
cout << ans << endl;
}
Сложность: O((n + m)log MOD), где MOD = 109 + 7.
Задача предложена пользователем Kamil Debowski Errichto.
Далее приводится разбор моего решения. Также вы можете посмотреть разбор от автора задачи в английском треде.
Применим метод разделяй и властвуй. Рассмотрим отрезок [l, r] и найдём в нём подотрезок с максимальной взвешенной суммой. Для этого разобьём отрезок на две части [l, md - 1] и [md, rg], где . Согласно методу разделяй и властвуй посчитаем рекурсивно ответ, если он лежит целиком в левой или правой половине. Теперь нужно учесть отрезки, пересекающие середину. Рассмотрим некоторый отрезок [i, j], i < md, md ≤ j. Взвешенная сумма на ней равна: , где --- взвешенная сумма в подотрезке [i, md], — взвешенная сумма на подотрезке [md + 1, r], а srj — просто сумма на подотрезке [md + 1, r]. Знак × применяется в смысле геометрического псевдовекторного произведения. Таким образом, у нас есть набор векторов вида (md - i, 1) и некоторый набор точек и для каждого вектора первого набора нужно найти точку из второго набора, максимизирующую значение векторного произведения. Это легко сделать, построив выпуклую оболочку по множеству точек и далее, двигая указатель по выпуклой оболочке.
Обратите внимание, что в данном решении есть проблема переполнения значений векторного произведения. Эту проблему можно обойти, если сначала сравнивать значение векторного произведения в типе long double или double и только потом в типе long long. Оригинальное решение автора задачи не имеет такой проблемы.
Решение на C++const int N = 200200;
int n;
li a[N];
bool read() {
if (!(cin >> n)) return false;
forn(i, n) {
int x;
assert(scanf("%d", &x) == 1);
a[i] = x;
}
return true;
}
inline ptl operator- (const ptl& a, const ptl& b) { return mp(a.x - b.x, a.y - b.y); }
inline li cross(const ptl& a, const ptl& b) { return a.x * b.y - a.y * b.x; }
inline bool crossLess(const ptl& a, const ptl& b) {
ld dif = a.x * ld(b.y) - a.y * ld(b.x);
if (abs(dif) > INF) return dif <= 0;
li difl = a.x * b.y - a.y * b.x;
return difl <= 0;
}
vector<ptl> convexHull(vector<ptl> a) {
sort(all(a));
a.erase(unique(all(a)), a.end());
vector<ptl> up, dw;
forn(i, sz(a)) {
while (sz(up) > 1 && crossLess(a[i] - up.back(), up.back() - up[sz(up) - 2]))
up.pop_back();
up.pb(a[i]);
}
forn(i, sz(a)) {
while (sz(dw) > 1 && crossLess(dw.back() - dw[sz(dw) - 2], a[i] - dw.back()))
dw.pop_back();
dw.pb(a[i]);
}
reverse(all(up));
if (sz(up) > 1) dw.insert(dw.end(), up.begin() + 1, up.end() - 1);
return dw;
}
li solve(int lf, int rg) {
if (lf + 1 == rg) return a[lf];
int md = (lf + rg) >> 1;
li ans = 0;
ans = max(ans, solve(lf, md));
ans = max(ans, solve(md, rg));
vector<ptl> hull(rg - md);
li s1 = 0, s2 = 0;
fore(i, md, rg) {
s1 += (i - md + 1) * a[i];
s2 += a[i];
hull[i - md] = {-s1, s2};
}
hull = convexHull(hull);
s1 = 0, s2 = 0;
int p = 0;
for (int i = md - 1; i >= lf; i--) {
s1 += a[i];
s1 += s2;
s2 += a[i];
ptl curp(md - i, 1);
if (i == md - 1)
forn(j, sz(hull))
if (cross(curp, hull[p]) < cross(curp, hull[j]))
p = j;
while (true) {
int np = p - 1;
(np < 0) && (np += sz(hull));
if (cross(curp, hull[np]) <= cross(curp, hull[p])) break;
p = np;
}
ans = max(ans, s1 + cross(curp, hull[p]));
}
return ans;
}
void solve() {
li ans = 0;
ans = max(ans, solve(0, n));
cout << ans << endl;
}
Сложность: O(nlog2n).