Мы надеемся, что вам понравился контест! Спасибо вам за участие! Для нас это третий официальный раунд, поэтому мы были бы рады услышать ваши отзывы в комментариях и в мини опросе ниже.
2184A - Социальный эксперимент
Идея: fstilus; разработчик: fstilus
Сколько человек может быть в одной цивилизации?
Любое неотрицательное количество человек, кроме количества $$$1$$$.
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
if (n == 2) cout << "2\n";
if (n == 3) cout << "3\n";
if (n >= 4) cout << n % 2 << '\n';
}
return 0;
}
Идея: fstilus; разработчик: fstilus
Сколько минут песка останется в верхней половине часов сразу после второго переворота?
$$$s$$$ минут.
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int s, k, m;
cin >> s >> k >> m;
if (s <= k) cout << max(0, s - m % k) << '\n';
else cout << (((m % (2 * k)) < k) ? s - m % k : k - m % k) << '\n';
}
return 0;
}
Идея: Friendiks; разработчик: fstilus
Почему полный перебор неэффективен? Как его можно улучшить?
Происходит многократное посещение одних и тех же чисел.
Сколько различных значений можно получить, начиная с числа $$$n$$$?
$$$O(\log n)$$$.
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
int l = n, r = n;
int cnt = 0;
while (r != 1) {
if (l <= k && k <= r) break;
l = l / 2;
r = r / 2 + r % 2;
cnt++;
}
if (l <= k && k <= r) cout << cnt << '\n';
else cout << -1 << '\n';
}
return 0;
}
Идея: Friendiks; разработчик: Friendiks
Выигрышная стратегия Алисы связана с битами.
Оптимальное количество ходов для Алисы зависит только от старшего бита и количества единичных битов.
Число $$$n$$$ является степенью двойки, а значит, если вычесть $$$1$$$, то любое подмножество битов числа $$$n-1$$$ не будет превышать $$$n-1$$$.
#include <bits/stdc++.h>
using namespace std;
int c_n_k[31][31];
int main() {
for (int i = 0; i < 30; ++i) {
for (int j = 0; j < 30; ++j) {
if (i < j) c_n_k[i][j] = 0;
else if (j == 0) c_n_k[i][j] = 1;
else c_n_k[i][j] = c_n_k[i - 1][j] + c_n_k[i - 1][j - 1];
}
}
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
int d = 0;
while (n % 2 == 0) {
n /= 2;
++d;
}
int ans = 0;
for (int max_bit = 0; max_bit < d; ++max_bit) {
for (int cnt_bit = 1; cnt_bit <= max_bit + 1; ++cnt_bit) {
if (max_bit + cnt_bit <= k) continue;
ans += c_n_k[max_bit][cnt_bit - 1];
}
}
if (d + 1 > k) ++ans;
cout << ans << "\n";
}
return 0;
}
Решите задачу, когда $$$n$$$ — любое целое число от $$$1$$$ до $$$10^9$$$, не обязательно степень двойки.
Идея: fstilus; разработчик: fstilus
Если какой-то массив $$$k$$$-изысканный, то любой его подотрезок длины не менее $$$2$$$ также $$$k$$$-изысканный.
Если $$$k_1 \gt k_2$$$ и какой-то массив $$$k_1$$$-изысканный, то он также и $$$k_2$$$-изысканный.
Если какой-то массив длины $$$m$$$ $$$k$$$-изысканный, то сколько у него $$$k$$$-изысканных подотрезков?
$$$\frac{m \cdot (m - 1)}{2}$$$.
Для фиксированного $$$k$$$ придумайте, как разбить всю исходную перестановку на отрезки, каждый из которых либо $$$k$$$-изысканный, либо длины $$$1$$$, так, чтобы можно было воспользоваться формулой из предыдущей подсказки.
Как переходить от разбиения на отрезки для $$$k+1$$$ до разбиения на отрезки для $$$k$$$?
Нужно найти все позиции, где разница между элементами перестановки равна $$$k$$$, и объединить соответствующие отрезки.
Найдите, как изменяется ответ при каждом объединении двух отрезков.
#include <bits/stdc++.h>
using namespace std;
vector <int> parent;
vector <int> rnk;
vector <int> sz;
void make_set(int v) {
parent[v] = v;
rnk[v] = 0;
sz[v] = 1;
}
int find_set(int v) {
if (v == parent[v])
return v;
return parent[v] = find_set(parent[v]);
}
void union_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
if (rnk[a] < rnk[b])
swap (a, b);
parent[b] = a;
if (rnk[a] == rnk[b])
++rnk[a];
sz[a] += sz[b];
}
}
long long cnt(int x) {
x = find_set(x);
return (long long)sz[x] * (sz[x] - 1) / 2;
}
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
map <int, vector <int>> m;
int pr;
for (int i = 0; i < n; i++) {
int a;
cin >> a;
if (i > 0)
m[abs(a - pr)].push_back(i);
pr = a;
}
parent.resize(n);
rnk.resize(n);
sz.resize(n);
for (int i = 0; i < n; i++) make_set(i);
vector <long long> ans;
long long cur = 0;
for (int i = n - 1; i > 0; i--) {
for (auto y : m[i]) {
cur -= cnt(y);
cur -= cnt(y - 1);
union_sets(y, y - 1);
cur += cnt(y);
}
ans.push_back(cur);
}
reverse(ans.begin(), ans.end());
for (auto x : ans) cout << x << ' ';
cout << '\n';
parent.clear();
rnk.clear();
sz.clear();
}
return 0;
}
Идея: gravitsapa; разработчик: gravitsapa
Придумайте динамику $$$dp[u][k]$$$ с $$$O(n^2)$$$ состояний, где $$$u$$$ это номер вершины, $$$k$$$ — дополнительный параметр, а $$$dp[u][k]$$$ — можно ли собрать всю вишню в поддереве вершины $$$u$$$ при условии, что дополнительный параметр равен $$$k$$$.
Можно использовать дополнительный параметр, равный количеству вершин в поддереве вершины $$$u$$$, за которые потрясли.
Параметр $$$k$$$ имеет смысл рассматривать по модулю $$$3$$$. Таким образом состояний динамики становится $$$O(n)$$$.
Где будет находиться ответ на задачу?
Ответ на задачу находится в $$$dp[1][0]$$$.
Какая будет база динамики?
Если вершина $$$u$$$ является листом, то $$$dp[u][0] = False, dp[u][1] = True, dp[u][2] = False$$$.
Для того, чтобы пересчитать динамику $$$dp[u]$$$, нужно рассмотреть два случая: потрясли за вершину $$$u$$$ или нет. Если за вершину $$$u$$$ потрясли, то это, очевидно, единственная вершина во всем поддереве, за которую потрясли.
Если за вершину $$$u$$$ не потрясли, то нужно собрать вишню в каждом её сыне независимо. Информация о том, как это можно сделать для сына $$$v$$$ хранится в $$$dp[v]$$$.
Для того, чтобы пересчитать $$$dp[u]$$$ через её сыновей, нужно снова использовать динамическое программирование.
Изначально будем трясти только за корневую вершину. Затем будем брать какую-то вершину, за которую нужно потрясти, и заменять её на её сыновей. Так можно получить любое корректное решение.
При таком процессе количество выбранных вершин меняется в зависимости от количества сыновей вершины, которую заменяют. При этом имеет значение лишь количество сыновей по модулю $$$3$$$.
Для каждой вершины, не являющейся листом, можно записать количество её сыновей по модулю $$$3$$$ и найти закономерность между ответом и этими числами.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200001;
int n;
vector <int> graph[MAXN];
vector <bool> dp[MAXN];
void merge_dp(vector <bool>& lhs, vector <bool>& rhs, vector <bool>& result) {
for (int i = 0; i < 3; ++i) {
if (!lhs[i]) continue;
for (int j = 0; j < 3; ++j) {
if (!rhs[j]) continue;
result[(i + j) % 3] = true;
}
}
}
void dfs(int u, int p) {
vector <int> child;
for (auto v : graph[u]) if (v != p) {
dfs(v, u);
child.push_back(v);
}
dp[u].resize(3);
if (!child.empty()) {
dp[u][0] = true;
for (auto v : child) {
vector <bool> result(3, false);
merge_dp(dp[u], dp[v], result);
dp[u] = result;
}
}
dp[u][1] = true;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
cin >> n;
for (int i = 1; i <= n; ++i) {
graph[i].clear();
dp[i].clear();
}
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
dfs(1, -1);
cout << (dp[1][0] ? "YES" : "NO") << '\n';
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200001;
int n;
vector <int> graph[MAXN];
bool ans;
int dfs(int u, int p) {
vector <int> child;
int cnt = 0;
for (auto v : graph[u]) if (v != p) {
cnt++;
auto t = dfs(v, u);
if (t != 0) {
child.push_back(t);
}
}
if (child.size() > 1) {
ans = true;
return 0;
}
int type = cnt == 0 ? 0 : (cnt + 2) % 3;
vector <int> ord;
if (type) {
ord.push_back(type);
}
if (!child.empty()) {
ord.push_back(child[0]);
}
if (ord.size() == 2 && ord[0] + ord[1] != 3) {
ans = true;
return 0;
}
if (ord.size() >= 1) return ord[0];
return 0;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
cin >> n;
for (int i = 1; i <= n; ++i) {
graph[i].clear();
}
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
ans = false;
int res = dfs(1, 1);
if (res == 2) {
ans = true;
}
cout << (ans ? "YES" : "NO") << '\n';
}
return 0;
}
Идея: Friendiks; разработчик: Friendiks
Зафиксируем $$$L$$$ и $$$R$$$ и введем функции от целых $$$d$$$: $$$f(d) = d$$$, $$$g(d) = \min(a_L, \dots, a_{L+d})$$$, где $$$0 \le d \le R-L$$$. Что можно сказать об этих функциях?
$$$f(d)$$$ — возрастающая, $$$g(d)$$$ — невозрастающая.
Сколько раз может выполниться условие задачи, если выразить его через $$$f$$$ и $$$g$$$?
Условие задачи равносильно поиску точки пересечения $$$f(d)$$$ и $$$g(d)$$$, а значит, существует максимум одна подходящая точка.
Функция $$$h(d) = f(d) - g(d)$$$ монотонна, поэтому единственный кандидат на роль точки пересечения — это минимальное $$$d$$$, при котором $$$h(d) \ge 0$$$ (или $$$f(d) \ge g(d)$$$).
Дерево отрезков.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 7;
int a[MAXN], st[4 * MAXN];
void build(int v, int l, int r) {
if (l + 1 == r) {
st[v] = a[l];
return;
}
int m = (r + l) / 2;
build(v * 2 + 1, l, m);
build(v * 2 + 2, m, r);
st[v] = min(st[v * 2 + 1], st[v * 2 + 2]);
}
void upd(int v, int l, int r, int i, int x) {
if (i < l || r <= i) return;
if (l + 1 == r) {
a[i] = x;
st[v] = x;
return;
}
int m = (r + l) / 2;
upd(v * 2 + 1, l, m, i, x);
upd(v * 2 + 2, m, r, i, x);
st[v] = min(st[v * 2 + 1], st[v * 2 + 2]);
}
int getMin(int v, int l, int r, int lq, int rq) {
if (rq <= l || r <= lq) return (int) 1e6;
if (lq <= l && r <= rq) return st[v];
int m = (r + l) / 2;
return min(getMin(v * 2 + 1, l, m, lq, rq), getMin(v * 2 + 2, m, r, lq, rq));
}
int ans, currMn;
void findInter(int v, int l, int r, int lq, int rq) {
if (rq <= l || r <= lq || ans != (int) 1e6) return;
if (lq <= l && r <= rq && min(currMn, st[v]) > r - lq - 1) {
currMn = min(currMn, st[v]);
return;
}
if (l + 1 == r) {
ans = l;
return;
}
int m = (r + l) / 2;
findInter(v * 2 + 1, l, m, lq, rq);
findInter(v * 2 + 2, m, r, lq, rq);
}
int main() {
int t;
cin >> t;
while (t--) {
int n, q;
cin >> n >> q;
for (int i = 0; i < n; ++i) cin >> a[i];
build(0, 0, n);
while (q--) {
int idx;
cin >> idx;
if (idx == 1) {
int i, x;
cin >> i >> x;
upd(0, 0, n, i - 1, x);
} else {
int l, r;
cin >> l >> r;
l--;
if (getMin(0, 0, n, l, r) > r - l) {
cout << "0\n";
continue;
}
ans = currMn = (int) 1e6;
findInter(0, 0, n, l, r);
cout << (ans != (int) 1e6 && getMin(0, 0, n, l, ans + 1) == ans - l) << "\n";
}
}
}
return 0;
}
Bad contest for me, I struggled on B!
For me too, I haven't solved a single problem
wow me too all feeling very weird.. ha ha ha
I solved C but couldn't solve B
hey !
could you please explain the problem -C and give the code for the same .
Hello, I can share my method for C if you wish to go through it.
First, I noticed that to get any pile size k in one pile division, the current pile size must be either 2k-1, 2k or 2k+1. So the current pile size must lie between 2k-1 and 2k+1, inclusive. We can then set a range, such that if it consists of a number, it is possible to get 2k-1, 2k, or 2k+1. This would be 2(2k-1)-1 to 2(2k+1)+1, inclusive.
Using this, we can set a range of what the current pile size should be for it to be possible to get k. We can keep increasing the range as long as the lower limit is less than n+1 and also increase a variable i per iteration.
If at any point of time, the starting pile size (n) falls into the range, the number of pile divisions taken is i. If it doesn't fall in the range while the loop is going on, it is not possible.
Edge cases can be handled separately.
This is my understanding, hope it helps. I can attach my code for reference if you want it.
yeah same got idea for c but took time for B lol
Yeah same struggle on b
yeah b felt kinda hard as well i cant lie. but honestly failing d is probably the biggest sign for me that this was a hard contest because im strongest at binary problems
i find A and B quite easy. C's a bit of a struggle for me tho
SAME
E can actually be addressed in O(n) easily.
How?
Each merge requires information only from the two sides of a component, so we can dynamically maintain them.
Using stacks approach
Yeah I did through the same process. But how did you come up with this logic for avoiding the overcounting, Like I was stuck here only rest I did the same and then I looked at your comment.
I had already solved a similar question involving this idea: question link
So back then, I think I was mostly just guessing, and then introducing asymmetry worked. I think you can just try guessing it unless you can prove its correctness, or prove it by getting AC.
Use stack and do it like largest area in histogram on leetcode.
can you explain how?
Simply using Monotonic Stack is also O(n).
Problems were hard T-T
it is crazy for me
Posted editorial faster then judging solutions lol!!, unnecessary penalties because of the lag.
im dead
those problems are so good!
Tutorials of D and G not understandable.
What is D about, what does it ask for?
What "function" is there in G?
D asks for how many numbers from 1 to n such that you can't reach 0 from them using the specified operations in k operations or less
Ok, and why does it matter which response Alice receives from Bob?
If she plays optimally, she would play optimally anyway, independend of the answers. So again, what does this problem asks for?
What strategy do we want to follow here to find what?
What I said it's what follows from the statement. She doesn't know the number but the infomation she receives is enough to play optimally.
As I said the problem asks for how many numbers from 1 to n she can't reach 0 in k operations or less...
The response from bob tells her if the given number is odd or even, its just a way to make it seem more complicated or llm proof ig
yes,it is helpful in finding if number is odd or even,
if number is odd then it is not divisible by any power of 2 except 0,ie 1
so if x==1 then number is odd else number is even
D is asking the amount of numbers that its total digits plus the number of digits equals to "1",are bigger than k, under binary expressions. And it can be solved using the Psacal triangle
Because Bob gives her enough information to determine the current number is even or odd ,so she will always halve the number if it's even and minus it by 1 if the number is odd.
E can be solved with monotonic stack for contribution in O(n) 357602037
Can you please explain for [5, 1, 4, 2, 3](test case — 1) for k = 2, why the answer is 6.
Clearly I can count more than 6. Am I missing something?
7th case , 3-2=1
but it is saying any two adjacent elements should differ by atleast k, so 4 — 1 = 3 is satisfying for k = 2.
I think the wording is a bit confusing — I initially had the same confusion as you. What the question means is: "for any two adjacent elements, the difference >= k" i.e. all pairs of adjacent elements differ by at least k.
It means if we pick any pair, it should have atleast k difference
Edit : i.e.,every pair should differ by atleast k
Felt like a div 2
Great contest, my first AK on div3 <3.
ive been grinding 1500-1700 in an effort to reach expert and i really thought i was making some progress. i mean, i solved many questions on my own. if not, i was able to atleast get close to the key observations.
and yet i could not solve B and C. even after trying for nearly an hour.
if my math is really this weak, there is no hope of me ever actually getting good at CP, is there? im cursed to never actually improve. all the questions i solved were probably very easy with inflated ratings. or it was just a fluke.
i have had bad contests but this one was the worst. maybe i should just go back to doing LeetCode
EDIT: turns out my mistake for B was that i accidently inverted the if-else conditions and for C i simply missed the case where n == k. i shouldnt have given up so quickly lol. oh well
practise makes man perfect. Believe in yourself, consistency is the key.
Nah, it's fine... bad contests happen. for me as well, that was the worst contest I've done in months (and I'm doing virtual Div. 3 pretty often ), so... don't let yourself down over just one bad contest :) There is no such thing as "never improving", you just need to compare yourself with yourself from a month ago / year ago for seeing how much you have improved, this here is just a rating that while it should show "how much you improved" it just shows how prepared you were on some specific type of problems ( in this case math ), so yeah, maybe it's just time for both of us to learn some more math tricks on cf, not to give up <3
thank you. youre right, of course. if youre bad at something i guess that means you can only get better so thats nice
chill, it isn't that deep, just understand the solutions and learn from your mistakes
Just do CSES? You're probably lacking foundational skill, Codeforces teaches a lot of dumb tricks, it's inefficient to just do a bunch of questions on CF. I'd do something like CSES and USACO Guide if I had to start over, since that's what got me to 1200 in like 4-5 months. You need to categorically learn every technique, not just do a bunch of questions and hope for the best. Grinding CF can help, but it's mostly about learning to discover insights faster, it's very tough to learn all the fundamentals from just CF.
For problem 2184C — Huge Pile, any way to avoid tle here? ~~~~~ const ll mx = 1e7+123; ll dp[mx]; ll f(ll n, ll k) { if (n == k) return 0; if (n < k) return inf; if (n < mx && dp[n] != -1) return dp[n];
if (n % 2 == 0) { ll z1 = f(n / 2, k); if (z1 == inf) { if (n < mx) return dp[n] = inf; else return inf; } else { if (n < mx) return dp[n] = 1 + z1; else return 1 + z1;; } } ll z1 = f(n / 2, k); ll z2 = f(n / 2 + 1, k); if (z1 == inf && z2 == inf) { if (n < mx) return dp[n] = inf; else return inf; } if (z1 == inf) { if (n < mx) return dp[n] = 1 + z2; return 1 + z2; } else if (z2 == inf) { if (n < mx) return dp[n] = 1 + z1; return 1 + z1; } if (n < mx) return dp[n] = min(1 + z1, 1 + z2); return min(1 + z1, 1 + z2);}
void solve() { ll n, k; cin >> n >> k; // dbg(f(3, 4));
} ~~~~~
n can go till 1e9, you need to think better
I solved like this, avoided tle:
Liked B
Same, I wrote down some simulations and got the answer quite quick.
I hated A's phrasing though, solved all the way through D before finally understanding what A was asking for (then promptly solving it in one-shot) :<
357546787
Did I get a wrong TLE here? I submitted pretty much the same with just making the values very marginally smaller, and I'm pretty sure this shouldn't be close to TLE. (This worked: 357553381)
undefined behavior index out of range dp[31][32]
Ohh, I was confused because it was TLE, and locally it went fine so I didn't check for indexing errors, but since it's undefined behavior anything can happen ig. I see my mistake now, thanks!
Problem F and G felt more like an educational round problem. I liked the idea of the query always being 0 or 1.
Can anyone post similar problem like F ... just need more problems on the topic of dp on trees
There was one Korean problem (from early 2025) that came to mind when I solved F.
link to problem: https://www.acmicpc.net/problem/33149
editorial (in case you need it): https://www.acmicpc.net/board/view/154753
Thanks but I can't read Korean T_T ... Anyone plz give some other dp on trees problem.
E1. PermuTree (easy version)
I t think you can alos count C, D, E.
C normal DP
D digit DP
E DUS.
using dsu for merging segments in E is a nice trick which I learned, v elegant!
iam i the only one who found B really hard (kinda impossible) i couldn't even understand it it feels bad tbh iam the only one who thinks its problem statement is poorly typed
for example i couldn't solve problem C but at least i get that it is on my skill that i couldn't figure the math idea behind it but for problem B i couldn't even figure out what is it asking me to do !
357562263
Problem G's tests can be done with O(NQ) (when it's not supposed to) with proper breaking after cumulative minimum values — wish the testcases there were stronger on that one since the very reason why we implemented the segtree in the first place was to stop Naive simulation
I think I got pretty close to D, but I can't figure out where my code's going wrong- I'd be grateful if anyone took a peek at it. 357620086
Idk man
Edit: Solved it:)
After looking at the code, I managed to locate the issue: it was in my combination logic, namely, the line:
res *= (n-k+i)/i. After changing it tores = res * (n-k+i)/iit worked for me as well.Thanks for the help :)
Why is that an error, is it coz of some long long -> int, issue?
In the first version, it did the division before doing the final multiplication; it was as if I had written
res = res * ( (n-k+i)/i ), which caused the rounding errors to appear. In the second version, the operations are done from left to right, and thus the multiplication happens first, making an exact integer division possible.Oh bruh lol, I missed that.
I had fun trying to solve A for 2 hours with my limited knowledge
For some reason i was really convinced that bfs would give tle in C, so i tried to come up with some solution using the bits in n and k.
First, there was a special cases: $$$k=2^d$$$ for some d, and there were a prefix of $$$n$$$, $$$n'$$$, in which $$$n'= 2*2^d -1$$$ then it can be done in $$$log_2(n)-log_2(n')+1$$$ operations, the cost of transforming $$$n$$$ into $$$n'$$$ with floor operations and then making a ceil operation for clearing the ones in $$$n'$$$.
Now, analyzing the binary representation of $$$n$$$ and $$$k$$$, and their prefixes:
If $$$k$$$ is a prefix of $$$n$$$ in their binary representation, then it can be done in $$$log_2(n)-log_2(k)$$$ operations.
Now, if they differ in some bit
bin whichbis 1 in $$$n$$$ and 0 in $$$k$$$, we would need to turn this bit off in $$$n$$$, which is not possible with our operations while maintaining it in the final result.But if
bis 0 in $$$n$$$ and 1 in $$$k$$$, we can only turnbinto a 1 in $$$n$$$ if we "borrow" some less significant bit of $$$n$$$ that is 1, but this borrowing forces all bits that are less significant thenbto be 0 (if they can still be present after the borrowing). So for this last case, we need to check if all bit less significant thenbin $$$k$$$ are 0. Also, let $$$c$$$ be this number of 0s in $$$k$$$, so $$$n$$$ needs to have a sequence of ones of size $$$k$$$ right after the bitband also have an additional 1 to be borrowed. If all of these conditions are valid, then it can also be done in $$$log_2(n)-log_2(k)$$$.Thank god, I thought I was the only one who thought BFS will TLE.
For me B > C C is stright forward but B needs some good thinking...
B is just casework my g
dsu fucker ah
(y is ts wrong)
that's insane I just did it with sets
There was a much simpler solution with dsu ;-;
My first CF contest able to solve 2 questions (A and C) .
Just B took me a whole hour... I really liked it though, but my solution wasn't as elegant as the editorial's
Any tips for avoiding min/max stuff and finding the elegant "shortcuts"? I always end up with verbose "unminimized" code.
Dude Contest was actually hard. B was literally tougher than C. C was kinda straightforward could've accepted in one submission but i missed edge case of n==k. I need to practice so much :(
I need to up solve more. B made me have a stroke. That Div 3 B question was harder than the previous Div 1/Div 2 questions: A, B, C of the Blacksled contest.
yeah, agree
Unintentionally, skipped the fact that $$$n = 2^x$$$ in problem D and was trying to solve the bonus version the whole time... feels so bad :(
Oh god ahhh same;(
I even solved it during upsolving and just when I read your comment I noticed oh shit the hell i was doing;)
Pretty bad contest for me, but I guess it’s a good time to pick up some cool math tricks.
I solved D using a completely different approach. It’s a somewhat unconventional math/pattern-based enumeration solution, ofc not the intended one, but it works and it shows the beauty of Fibonacci sequence.
Dropping my accepted submission here just in case anyone is curious about an alternative way of thinking. Not for learning purposes! For that the editorial approach is far better ig. Submission: 357624461
For C, I had a different solution based on bitwise.
If we have the desired value K, it will require either 2*K-1, 2*K or 2*K+1 to be formed before K can be formed, as any one of 2*K-1, 2*K, 2*K+1 divides into K. This means we are looking for a way to make N with 2^x * K + A[x-1] * 2^(x-1) + A[x-2] * 2^(x-2) + ... + A[0] * 2^0, where A[i] has value -1, 0 or 1. This is a trope I recall seeing in another problem, just that I can't remember exactly which one it is now.
Now, how do we test for this? We iterate i=0 to 64 until N — (2^i * K) is equal to or smaller than 2^i — 1 (because this is the max we can form as the A[i] * 2^i sum). If N is greater than (2^i * K) — (2^i — 1), since that is now the minimum sum we can achieve with 2^i * K, then K will be formed from N in exactly i operations, otherwise, there is no solution.
Time O(1), memory O(1)
Code:
d can be also done using dp
Is $$$nlog^2n$$$ supposed to TLE in G? I solved without using 'walk on segment tree', but my solution got hacked.
Can someone try hacking my code as well please.I believe it should work fine as constraints are 2e5.(why using walk un-necessarily) It is n((logn)^2) only. Here is my 357542232.
I realized the issue, problem wasn't with $$$log^2$$$ factor but I had a high constant term which is why my solution TLEd. On writing a cleaner $$$nlog^2n$$$ solution, it passes in 1 second.
Yes if you use Python. Using C++ is able to pass the tests.
My solution for C is very different
Pretty difficult contest, B was quite annoying.
Problem F and G felt too standard.(I am not really complaining) But I think particulary G should involve something more tricky(even if educational) than just using one simple observation and bam segment tree.....AC. overall I enjoyed solving problem E the most.Used segment tree for E as well as I couldn't come up with the merging thing.
G is cool task
For problem D , The number of integers $$$0 \leq m \leq 2^d$$$ such that $$$\text{maxBit}(m) + \text{cntBit}(m) = k$$$ is on A027926 on oeis. Interestingly, the number of unbounded integers $$$m$$$ such that $$$\text{maxBit}(m) + \text{cntBit}(m) = k$$$ is the k'th fibbonacci number.
I only found this because I misread the problem to say alice divides by the largest power of 2 in the prime factorization of n when n is even instead of just dividing by 2. The answer for this different problem comes out to $$$\sum_{i=k+1}^{n} {{d-1}\choose{\lfloor \frac{i}{2} \rfloor}}$$$. When I realized my misread I found the oeis sequence when adapting the solution.
Thanks for fast editorial and beatiful contest. Problem D was amazing! It actually blew my mind.
Also, I think C was much easier than B
great problem setting, absolutely loved it!
i didnt expect to solve only 2 questions in div3 . looking at the edi now the problems seem so interesting
G would be C if it wasn't for data structures
how long does it take for ratings to change since I am new at code forces , I have solved a lot in CodeChef and lc and other platforms bt I dont know about this , if anyone can help it will mean a lot
The ratings will be updated soon after the hacking phase (12 hours long) gets over.
D can be solved in $$$O(1)$$$ each query
I couldn't submit it in the contest because my computer finished brute-forcing the answer matrix 3 minutes after the contest was over. HAHAHA xD
XD
D can also be solved in O(1) per query without a lookup table.
Since I solved fewer problems in div3 than in div2, f**king!
D can be solved using digit dp ,first convert the number into its bits form and then use the condition that 2*setbits-1+unsetsbits<=k 357599309 ,you can check my last submission
my solution also used digit DP, here my code:
357551501
it works for any n
B was quite tricky!
Problem B.
why for test case
16 7 7 answer is 7? (not 9)
There is only one flip. After flip sand minute s — k = 9. No one does flip anymore.
bcoz in that flip time remaining will be 7 not 9 and leaving time is also 7 so 7 minutes will be left
Tho I didn't perform well, one of the best div3s I have given so far
E can be solved using two maps , one for left and one for right , and then counting contribution for each k , and updating left and right ranges in map . B was tricky .
This was my First contest, Im happy that I've solved 3 Questions, I hope that Ill improve.
another sol for C
link: https://codeforces.me/contest/2184/submission/357635822
Solved B in 5 minutes, C in 10 minutes, but didn't solve A in a whole contest lol. The weirdest performance ever
Ratings are out?
I am not able to figure out why my solution for D, 357586842 got hacked please help
Your text to link here... I don't understand why my code failed in Test 2. Could some expert help me find the bug? Thank you.
B was extremely weird
Alternative solution for C:
We can greedily select the next value.
If we can just construct the k with the current n (1 step) we just end the loop.
if n % 2 == 0 it is obvious that we will go to n / 2
if n % 4 == 1 we should go to n / 2 + (n % 2) because it is obviously a better choice than n / 2.
if n % 4 == 3 vice versa
Hey, that's a good method to pull in. I too did the same approach finding whether k is achievable from the set of possible quotients.
I saw many submission who used a segment tree in problem E.
Can anyone explain how to do it using a segment tree?
Why is it showing as unrated competition for me?
In my sleep deprived mind I thought of just checking for half population one side and another half another side for A, but I was too frustrated with my failed submissions and I gave up in between. Should have tried it.
What is "rnk" in solution of problem E
E can be solved without dsu, set or stack. I solved it just using arrays. 357749120 I follow the same strategy as mentioned in the editorial. It can be noted that when we arrive at an index to merge two segments, we only need the left and right segment lengths about that index. So we can maintain a segment_start array and a segment_end array. segment_start[i] = length of segment which starts at i. segment_end[i] = length of segment that ends at i. We can update the arrays as we merge two segments using the lengths. Check my submission for understanding.
How does the suggested solution for G (descent approach) has the time complexity of $$$O(n + qlogn)$$$ ? I think, it should still be $$$O(n + qlog^2n)$$$. Because one $$$logn$$$ factor comes from the fact that we are doing binary search and the second $$$logn$$$ factor will be used for checking the sign of the $$$h(d)$$$ function at the points $$$c_l$$$ and $$$c_r$$$ at each point during the binary search.
Here's an alternate soln of D, O((logn)^3)
Hey everyone ! can anyone please say where to practice problems for improving my problem solving efficiency in contests . and practicing methods which u felt good .currently my rating is 1000 .i wish to improve it kindly help me out .
Hey, a sophomore here!
I have been relatively active in the platform for multiple months and I believe this might help you out.
Problems to practice can be found across multiple websites. I recommend you to try Hackerrank, CSES problem set(highly recommended) and leetcode(standard across Indian engineering institutes to practice for placements and a lot more).
Problem efficiency doesn't arise from sheer talent or the number of problems you have solved in the past for your future. It's the underlying maths which you're able to apply on that carries you forward.
Here's an extra suggestion for you: Write formal math proofs for problems you come across especially for datastructures.
it was tuff asf..could not solve B..also got A wrong coz of panic and language problem...i think framing of question language is better in div 2
I felt that the previous Div 2 a,b questions were much easier than this Div 3 contest.
The author's solution to G by method of descending is really elegant.
For me it was great contest and first oroblem is soososooooooooooo easy
I checked EFG and it's not very difficult. Is ABCD more difficult than EFG?
can someone provide the ratings of each ques
my approach for problem c
whenever i decompose a number i check if decomposed number is my target,and if not among the decomposed number i take the odd number because on decomposition of these i will get all the possible factor and can ignore the other number please take a example you will understand,although i am sillly mistake person i was not able to solve them in contest,for one hour i was struggling to find the mistake i made,i found the mistake in b but was not able to find in problem c
can someone please tell we why this approach is wrong for C problem. ~~~~~ 358167776
~~~~~
For problem F, the problem statement says:
"You choose any vertex of the tree v (including the root or a leaf) and "shake" it. After that, cherries fall from all the leaves that are descendants‡ of vertex v (if vertex v itself is a leaf, then a cherry falls from it). If cherries have already fallen from any leaf before, the tree will break, so such a situation must be avoided."
And it identifies "Descendants of vertex v" as follow:
"‡The descendants of vertex v are all vertices u≠v such that on the shortest path from the root to u, vertex v is encountered."
Which I guess it is obvious enough (at-least for me & that I'm not missing anything) that if I for example choose any node to shake: then I can't shake it again or any other node below it. Why? because from my understanding if I shake a node then all cherries in its children will fall, if I then shake it again or any other node below it, it will also affect the leaves and the rule "If cherries have already fallen from any leaf before, the tree will break, so such a situation must be avoided." would apply. However in the editorial of the analytical solution for F, it claims that I should initially shake the root node, then I can shake anything I want as long as it's not a leaf, how so? Shouldn't the rule still apply?
INDEED, THOUGH AS A WISE MAN ONCE SAID...YOU DO NOT GET EVERYTHING YOU WAN IN LIFE, THAOU BE LIMIT THE EXCEPTIONAL TO CONTROL THE INEVITABLE
in problem G, how does the segment tree descent work, can someone explain
I would like to clarify regarding the similarity flag on my submission.
I solved the problem independently during the contest. My approach was based on modeling the tree using a DFS and maintaining a bitmask representing possible values modulo 3 from each subtree. For each child, I merged masks by combining possible residues and updating the current node’s mask. Leaf nodes returned the base mask, and finally I checked whether residue 0 was achievable at the root.
I did not share my code, discuss implementation during the contest, or use any public code-hosting or collaborative platform. The similarity may be because this problem leads to a very standard tree-DP-with-bitmask approach, where transition logic and structure naturally become similar across solutions.
I respect Codeforces rules and am willing to provide any clarification if needed.
Another approach for problem F.
Think about DP, but in the flattened tree.
How do you solve the bonus for D..
E was such a beautiful Problem..
In problem c according to the given solution, if we give next iteration just a odd number then also it will work.
i got goomba stomped in virtual ;-;
Problem E is really nice! I first tried using a difference array plus a monotonic queue to track the minimum difference, but it bombed — O(n²) time complexity, got TLE on test case 7 straight up. So I switched things up: still stuck with the difference array, but swapped the monotonic queue for a monotonic stack to keep track of the maximum valid interval length. After that, the inclusion-exclusion principle made it a piece of cake, and it’s O(n) time overall. Here’s my submission if anyone wants to check it out: 363405796
There's also an alternative solution to F that i found which is quite elegant. Instead of working top-down, imagine we start by just choosing to shake all the leaves in the tree. Let L be the total number of leaves. If L mod 3 is 0, we can just choose all the leaves and the answer is yes. If L mod 3 is not 0, we need to adjust our chosen set by picking a parent vertex instead of its leaf descendants, which removes S leaves (where S is the number of leaves in that subtree) and adds 1 parent vertex, making the net change in our chosen count exactly 1 minus S. If our initial L mod 3 is 1, we need an overall change of 2 mod 3 (or -1), which means we either have to find one vertex where the number of leaves in its subtree is 2 mod 3 (since 1 minus 2 is -1), or find a pair of disjoint vertices that each have 0 mod 3 leaves (since 1 minus 0 plus 1 minus 0 is 2). Conversely, if L mod 3 is 2, we need an overall change of 1 mod 3, so we just find 1 vertex with 0 mod 3 leaves (since 1 minus 0 is 1), or find 1 pair of disjoint vertices that each have 2 mod 3 leaves (since 1 minus 2 plus 1 minus 2 is -2, which is equivalent to 1 mod 3). It works out every time, and you cant have more than 2 subtrees to change parities because adding three of the same modulo changes would just add up to a multiple of 3 and cancel each other out, meaning it always strictly reduces to one of these exact cases.
i think it is a good contest. but C is 1300(
I can't understand how the descent on the segment tree in G works. It involves the minimum number in a given segment. Could anyone help me?