Idea: soullless
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while(t--) {
int x;
cin >> x;
int mn = 9;
while(x > 0) {
mn = min(mn, x % 10);
x/=10;
}
cout << mn << endl;
}
}
2126B - No Casino in the Mountains
Idea: soullless
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while(t--) {
int n,k;
cin >> n >> k;
int a[n + 1];
for(int i = 1;i <= n;i++) cin >> a[i];
int ans = 0;
int cnt = 0;
for(int i = 1;i <= n;i++) {
if(a[i] == 1) {
ans+=(cnt + 1)/(k + 1);
cnt = 0;
continue;
}
else {
cnt++;
}
}
ans+=(cnt + 1)/(k + 1);
cout << ans << endl;
}
}
2126C - I Will Definitely Make It
Idea: soullless
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while(t--) {
int n,p;
cin >> n >> p;
int a[n + 1];
for(int i = 1;i <= n;i++) cin >> a[i];
int cur = a[p];
int dist = a[p];
sort(a + 1,a + n + 1);
bool ans = true;
for(int i = 1;i <= n;i++) {
if(a[i] < cur) continue;
if(a[i] — cur > dist) {
ans = false;
}
cur = a[i];
}
if(ans) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
Idea: soullless
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while(t--) {
int n,k;
cin >> n >> k;
pair <int,pair <int,int> > p[n + 1];
for(int i = 1;i <= n;i++) cin >> p[i].first >> p[ыi].second.first >> p[i].second.second;
sort(p + 1,p + n + 1);
int cur = k;
for(int i = 1;i <= n;i++) {
if(p[i].first > cur) break;
cur = max(cur,p[i].second.second);
}
cout << cur << endl;
}
}
Idea: Away_in_the_heavens
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
long long a[n + 1];
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
long long b[n + 1];
for (int i = 1; i <= n; i++) {
cin >> b[i];
}
long long ans[n + 1];
for (int i = n; i >= 1; i--) {
ans[i] = lcm(a[i], b[i]);
}
bool ch = 1;
if(ans[1] != a[1]) ch = 0;
if(ans[n] != b[n]) ch = 0;
for (int i = 2; i <= n; i++) {
if (__gcd(a[i — 1], ans[i]) != a[i]) {
ch = 0;
}
}
for (int i = n — 1; i >= 1; i--) {
if (__gcd(b[i + 1], ans[i]) != b[i]) {
ch = 0;
}
}
if (ch) {
cout << "YES" << "\n";
} else {
cout << "NO" << "\n";
}
}
}
Idea: soullless
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int B = 2e5 + 100;
int n;
int col[B];
long long costt = 0;
vector <pair <int,int> > reb[B];
bool was[B];
map <int,long long> cnt[B];
int pred[B];
long long zn[B];
void dfs(int v) {
was[v] = true;
for(auto u:reb[v]) {
if(was[u.first]) {
pred[v] = u.first;
continue;
}
if(col[v] != col[u.first]) costt+=u.second;
dfs(u.first);
zn[u.first] = u.second;
cnt[v][col[u.first]]+=zn[u.first];
}
}
void update(int v,int x) {
if(v != 1) {
cnt[pred[v]][col[v]]-=zn[v];
if(col[pred[v]] == col[v]) costt+=zn[v];
cnt[pred[v]][x]+=zn[v];
if(col[pred[v]] == x) costt-=zn[v];
}
else {
}
costt+=cnt[v][col[v]];
costt-=cnt[v][x];
col[v] = x;
}
void clr() {
for(int i = 1;i <= n;i++) {
reb[i].clear();
was[i] = false;
cnt[i].clear();
zn[i] = 0;
}
costt = 0;
}
int main() {
int t;
cin >> t;
while(t--) {
int q;
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> col[i];
for(int i = 1; i < n; i++) {
int u, v, c;
cin >> u >> v >> c;
reb[v].push_back({u,c});
reb[u].push_back({v,c});
}
dfs(1);
while(q--) {
int pos,x;
cin >> pos >> x;
update(pos,x);
cout << costt << "\n";
}
clr();
}
}
2126G1 - Big Wins! (easy version)
Idea: soullless
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int B = 2e5 + 100;
int main() {
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
int a[n + 1];
for(int i = 1;i <= n;i++) cin >> a[i];
int ans = 0;
for(int i = 1;i <= 100;i++) {
int b[n + 1] = {};
for(int j = 1;j <= n;j++) {
if(a[j] >= i) b[j] = 1;
else b[j] = -1;
}
int pref[n + 1] = {};
for(int j = 1; j <= n; j++) {
pref[j] = pref[j - 1] + b[j];
}
int prefmn[n + 2] = {},suffmx[n + 1] = {};
prefmn[0] = 0,suffmx[n] = pref[n];
for(int j = 1; j <= n; j++) {
prefmn[j] = min(prefmn[j - 1],pref[j]);
}
for(int j = n - 1; j >= 1; j--) {
suffmx[j] = max(suffmx[j + 1],pref[j]);
}
for(int j = 1; j <= n; j++) {
if(prefmn[j - 1] <= pref[j] || pref[j - 1] <= suffmx[j]) {
ans = max(ans,i - a[j]);
}
}
}
cout << ans << endl;
}
}
2126G2 - Big Wins! (hard version)
Idea: soullless
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
int n;
int a[200005 + 2];
array<int, 4> t[800005];
array<int, 4> merge(array<int, 4>a, array<int, 4>b) {
int ans = max(a[0], b[0]);
int mxpref = max(a[1], a[3] + b[1]);
int mxsuff = max(b[2], a[2] + b[3]);
ans = max({ans, mxpref, mxsuff});
int sum = a[3] + b[3];
return {ans, mxpref, mxsuff, sum};
}
void update(int v, int tl, int tr, int pos, int val) {
if (tl == tr) {
t[v] = {max(val, 0), max(val, 0), max(val, 0), val};
} else {
int tm = (tl + tr) >> 1;
if (pos <= tm) {
update(v * 2, tl, tm, pos, val);
} else {
update(v * 2 + 1, tm + 1, tr, pos, val);
}
t[v] = merge(t[v * 2], t[v * 2 + 1]);
}
}
array<int, 4> get(int v, int tl, int tr, int l, int r) {
if (tl == l && tr == r) {
return t[v];
} else if (l > r) {
return {0, 0, 0, 0};
} else {
int tm = (tl + tr) >> 1;
return merge(get(v * 2, tl, tm, l, min(r, tm)), get(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
}
}
int solve(int n, vector<int>A) {
int m = 0;
for (int i = 1; i <= n; i++) {
a[i] = A[i — 1];
m = max(m, a[i]);
}
vector<int>ind[m + 1];
for (int i = 1; i <= n; i++) {
ind[a[i]].push_back(i);
}
stack<int>s;
s.push(0);
a[0] = -INT_MAX;
int l[n + 1];
for (int i = 1; i <= n; i++) {
while (a[s.top()] >= a[i]) {
s.pop();
}
l[i] = s.top() + 1;
s.push(i);
}
a[n + 1] = -INT_MAX;
s.push(n + 1);
int r[n + 1];
for (int i = n; i >= 1; i--) {
while (a[s.top()] >= a[i]) {
s.pop();
}
r[i] = s.top() — 1;
s.push(i);
}
int med = 1;
for (int i = 1; i <= n; i++) {
update(1, 1, n, i, 1);
}
for (auto u : ind[1]) {
update(1, 1, n, u, -1);
}
int ans = 0;
for (int mn = 1; mn <= m; mn++) {
for (auto u : ind[mn]) {
int lg = l[u], rg = r[u];
while (med < m && get(1, 1, n, lg, u — 1)[2] + get(1, 1, n, u + 1, rg)[1] + (a[u] < (med) ? -1 : 1) >= 0) {
med++;
for (auto u : ind[med]) {
update(1, 1, n, u, -1);
}
}
}
// cout << med << ' ' << mn << endl;
ans = max(ans, med — mn);
}
return ans;
}
int solveslow(int n, vector<int>A) {
for (int i = 1; i <= n; i++) {
a[i] = A[i — 1];
}
int mx = 0;
for (int i = 1; i <= n; i++) {
vector<int>v;
for (int j = i; j <= n; j++) {
v.push_back(a[j]);
sort(v.begin(), v.end());
mx = max(mx, v[v.size() / 2] — v[0]);
}
}
return mx;
}
int rnd() {
return (rand() + rand() * RAND_MAX);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while(tt--) {
int n;
cin >> n;
vector<int>v;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
v.push_back(x);
}
cout << solve(n, v) << endl;
// cout << solveslow(n, v) << endl;
for(int i = 0;i <= n*4;i++) {
t[i][0] = 0;
t[i][1] = 0;
t[i][2] = 0;
t[i][3] = 0;
}
}
}
solution section for problem C, E and G2 seems to be not formatted well
thanks? edited
F also
I think so jiangly had some different solution for G which is using DSU. If anyone could explain it that would be great.
For G1, I had the same solution in mind but why are we not ensuring the existence of $$$m$$$ in $$$(l, r]$$$? I got confused because of that and left
because lets say for some
m, you found a valid segment(l, r]It may be possible that m doesn't lie in that segment or some value greater thanmmight become the median. In the above mentioned cases, when you eventually move to larger values ofm, the range sum for the same subarray will still be non-negative! (edit: In that case, the answer is BOUND to be greater than the currently computed value)see this case:
lets only operate on index
i=0arr[] = {1, 3, 3, 4}b = [1, 1, 1, 1]Since a valid range exists, my answer will be updated toans = m - a[0] = 1 - 1 = 0b = [-1, 1, 1, 1]Valid range exists for i = 0, soans = m - a[0] = 2 - 1 = 1b = [-1, 1, 1, 1]Valid range exists for i = 0, soans = m - a[0] = 3 - 1 = 2b = [-1, -1, -1, 1]It's pretty clear that no valid subarray exists for i = 0so my final answer become 2, hope this helps..
Fast editorial!!!
Hi, I am new to this platform, I am unable to view others submissions for some reason. In the source section it shows N/A. Not sure what is the reason for this, can anybody help me out with this?
I think that's done to fight bots, you would need to attend at least 5 contents to see the solutions I guess. you can see solutions of past problems at https://github.com/dvaitam/codeforces or https://huggingface.co/datasets/open-r1/codeforces-submissions
Also, it's worth noting that you can't see other people's code during a live contest, even in virtual ones. Try reviewing old submitted problems from the general problemset after LOGGING IN. Once the contest is over, the code is usually visible.
How to solve problem D when the value of "real" is not necessarily between l and r? I spent hours on this version of the problem. One approach is dp but states are too big. Is there any other way?
Here's a testcase:
Output: 100
1 3 100 is wrong.. u missed a condition l <= real <= r
Read the entire comment, I meant when that condition is not true. This version is quite hard, at least for me.
when you are inserting l real and r
check for one condition if l<=real and real<=r then only insert it in vector.
Oh I thought that was the version initially and spent around 15 minutes thinking.
What I thought was we do lower_bound and upper_bound for finding the boundaries which can be reached and then store the maximum value of real and then go on exploring other values. My solution was initially coded for that, but then I just made a minor adjustment to pass this.
what if we create a graph using the real values, and each edge is based on if we can use one casino's real value to visit the other. Then we can recognize the casino's we can initially start from and perform a BFS for finding the largest node
Creating the graph would be the tedious part which will affect time complexity imo.
I believe this is the right approach. Perhaps with an interval tree that supports removal of intervals, it would be possible to run the BFS without actually creating a graph?
what do you mean without actually creating a graph?
I mean that we can use the interval tree to visit all intervals overlapping the current number of coins, $$$k$$$, and erase them from the tree (as they do not need to be visited again). The next iteration of BFS uses the values of $$$k$$$ that have been reached, until there are no more intervals left. In other words, the graph would be implicit.
Since intervals are sparse, we can store them in center-based tree with $$$2n$$$ nodes. Each possible value of $$$k$$$ would perform a $$$O(\log n)$$$ operation on the tree, possibly visiting some number of intervals that would be removed, so the overall time complexity would be $$$O(n \log n)$$$. But perhaps there are more elegant solutions to this problem.
We can use a segment tree instead. Let's sort intervals by their left ends. Node responsible for an interval [l,r] contains a pair {maxR,ind}, where maxR is a maximum right end of intervals in range [l,r], ind is an index where this maximum was reached.
Alternative solution for $$$F$$$ (which I've seen quite a few times and are probably the reason for all the hacks):
Let's fix some $$$X$$$. For all vertices $$$u$$$ with $$$\mathrm{deg}(u) \le X$$$, we can just simulate the change and recalculate the answer in $$$\mathcal O(X)$$$. If $$$\mathrm{deg}(u) \gt X$$$, for all adjacent colors, we will store the sum of edges with that specific color that end in $$$u$$$. A color-update of such vertices can be performed in $$$\mathcal O(1)$$$ (add the contribution of the old color, remove the contribution of the new color).
It remains to update this "color-map". Since each vertex $$$v$$$ can be adjacent to at most $$$\frac{n}{X}$$$ such vertices, these updates can also be performed in $$$\mathcal O(n / X)$$$ time.
The total time complexity is $$$\mathcal O(n + q \cdot \max (X, n / X))$$$. The memory complexity is $$$\mathcal O \left(n + \frac{n}{X} \cdot n \right)$$$ if we remove the unused colors from the map.
If we choose $$$X = \sqrt{n}$$$, the total time complexity is $$$\mathcal O((n + q) \sqrt{n})$$$. Unfortunately, my solution with that choice of $$$X$$$ was hacked (MLE), but setting $$$X$$$ to $$$3500$$$ ($$$~5\sqrt{n}$$$) works.
same :( I had $$$ X = 400 $$$ as a constant and it TLE-ed. Later, I saw Dominater having $$$ X = \frac{\sqrt{n}}{4} $$$ and that worked. a good learning experience but it turned out to be the difference between my current performance and a master performance which would've shot me into expert :)
BTW, I tried $$$ X = \frac{\sqrt{n}}{k} $$$ for all all $$$ 2 \lt = k \lt = 11 $$$ and it works. But I couldn't get a single $$$ X = \sqrt{n} \pm k $$$ to work for some reason.
$$$X = \sqrt n \pm k$$$ is basically $$$X$$$ (especially for such small $$$k$$$ (or do you mean multiplication instead)). And is it possible that your definition of $$$X'$$$ is the opposite of mine, i.e. $$$X' = \frac{n}{X}$$$ 😅
Larger k too. I tried so many values but all tled
Maybe try $$$k = \frac {\sqrt n} 2$$$ xd
$$$X=1600$$$ is quite optimal for static arrays (it balances out the fast $$$adj[]$$$ and the slow $$$ngu[]$$$ (see the code for more information)). Even when I stress tested it, it doesn't exceed 2 seconds. 329522997 (my friend submitted the code for $$$X=1333$$$, it is just barely fitting in ML (I couldn't cause a MLE), and the peak runtime in hacks is only 1.6 seconds).
Hi , Can you please tell why is this submission giving MLE MySolution. I am not using any extra structure as compared to final solution given in solutions.
As mentioned in my comment, setting $$$X = \sqrt n$$$ gives mle, try using
lmt = 3500.My initial idea was similar; I would compare the degree of the vertex with the number of queries until the next time the vertex was painted. If the degree was smaller, I would update all neighbors, else I would update everything between the current query and the next query of v. I believe this comes out to the same time complexity, but it was practically too slow.
Looks like there were many solutions for $$$G2$$$, here's mine using Persistent Segment Trees and maximum subarray sum queries (somewhat similar to the editorial but worse time complexity xd). (This segtree extension was also part of the solution of a recent div 3H).
The general idea is to fix the index $$$i \in [1, n]$$$ of the minimum element and find the largest possible median containing $$$i$$$. We can binary search the median with the same construction of the array $$$b(m)$$$ as in the editorial of $$$G1$$$, i.e. for some fixed $$$m$$$, $$$b_j(m) = a_j \ge m\ ?\ 1 : -1$$$. Any non-negative subarray sum would correspond to a median $$$\ge m$$$. To ensure that $$$i$$$ is included in that subarray, we add a large number to $$$b_i(m)$$$, i.e. $$$b_i(m) = X + (a_i \ge m\ ?\ 1 : -1)$$$. One option would be $$$X = 2n$$$.
We need all the possible arrays of $$$b(m)$$$, which can be stored in a persistent segment tree. Start with $$$b_j = -1$$$ and for all $$$v \in [1, n]$$$ in descending order, do the following:
After doing that for all indices with value $$$v$$$ (and values $$$ \gt v$$$), our persistent segment tree will have the values of $$$b(v)$$$.
While iterating over the $$$i$$$ and doing the binary search, we need to add $$$2n$$$ to $$$b_i$$$. This is easy, since we can simply update $$$b_i$$$ and "forget" about the update.
The total time complexity is $$$\mathcal O(n \cdot \log^2(n))$$$, where the $$$\log$$$ factors come from binary search and persistent segment tree update. The memory complexity is around $$$\mathcal O(n \cdot \log n)$$$, but this has a high constant hidden, since we need to store 4
ints in each vertex of our segment tree for the queries. It is important that we remove the persistent segment tree vertices we create while querying — otherwise, we will need quite a lot of memory ...Submission
Nice.. My first idea was using two different persistent segment trees (one for the normal array, one for reversed) to store max prefix sums but kept getting TLE or MLE.
Later I updated it to a single persistent lazy tree storing a pair of {min, max} prefix sums. That was enough to pass. submission
Memory Limit was quite low (and the intended memory limit is $$$\mathcal O(n)$$$, so makes sense that $$$\mathcal O(n \log n)$$$ will be tight), so even constant factors matter :/
I am sorry if I missed something, but in the proof for the solution of problem E, I think there are times when $$$P_i=\frac{p_i}{g}$$$ and $$$x=\frac{p_{i-1}}{p_i}$$$ are not coprime: For example, if the underlying array is [49, 7, 1], then the prefix array would be [49, 7, 1] and the suffix array is [1, 1, 1]. If we let $$$i=2$$$, then $$$P_i=\frac{7}{1}=7$$$ and $$$x=\frac{49}{7}=7$$$, and they are not coprime.
Is there something I’m missing here? I’d appreciate any clarification.
I came up with another proof. Hope this might help.
Theorem. If the prefix and suffix gcd sequences $$$p_{1:n}$$$ and $$$s_{1:n}$$$ are valid (i.e., there exists an original sequence whose prefix and suffix gcd sequences are $$$p_{1:n}$$$ and $$$s_{1:n}$$$), then sequence $$$a_{1:n}$$$, defined by $$$a_k=lcm(p_k,s_k)=\frac{p_ks_k}{gcd(p_k,s_k)}$$$, has a prefix gcd sequence of $$$p_{1:n}$$$ and a suffix gcd sequence of $$$s_{1:n}$$$.
Proof: First, we can prove $$$gcd(a_1)=a_1=p_1$$$ easily using the fact that $$$gcd(p_1,s_1)=s_1$$$.
Then, we can prove the rest with mathematical induction. Assume that $$$gcd(a_{1:{k-1}})=p_{k-1}$$$, we want to prove $$$gcd(a_{1:k})=p_k$$$.
Therefore, proving $$$gcd(a_{1:k})=p_k$$$ is equivalent to proving $$$\frac{p_{k-1}}{p_k}$$$ and $$$\frac{s_k}{gcd(p_k,s_k)}$$$ are coprime.
Given the validity of $$$p_{1:n}$$$ and $$$s_{1:n}$$$, there exists an original sequence $$$b_{1:n}$$$ such that they are its prefix and suffix gcd sequences. Then, we have:
Because $$$gcd(gcd(b_{1:k-1}),gcd(b_{k:n}))=gcd(b_{1:n})$$$, $$$\frac{gcd(b_{1:k-1})}{gcd(b_{1:n})}$$$ and $$$\frac{gcd(b_{k:n})}{gcd(b_{1:n})}$$$ are coprime, and therefore $$$\frac{gcd(b_{1:k-1})}{gcd(b_{1:k})}$$$ and $$$\frac{gcd(b_{k:n})}{gcd(b_{1:n})}$$$ are coprime, due to the fact that $$$gcd(b_{1:n})|gcd(b_{1:k})$$$.
Now we have proven that the prefix gcd sequence of $$$a_{1:n}$$$ is $$$p_{1:n}$$$, and the proof for the suffix gcd sequence is symmetric.
Corollary. The prefix and suffix gcd sequences $$$p_{1:n}$$$ and $$$s_{1:n}$$$ are valid, if and only if sequence $$$a_{1:n}$$$, defined by $$$a_k=lcm(p_k,s_k)=\frac{p_ks_k}{gcd(p_k,s_k)}$$$, has a prefix gcd sequence of $$$p_{1:n}$$$ and a suffix gcd sequence of $$$s_{1:n}$$$.
Proof: Trivial. Therefore, we can construct $$$a_{1:n}$$$ and see if its prefix and suffix gcd sequence fit with $$$p_{1:n}$$$ and $$$s_{1:n}$$$ to judge if they are valid.
I didn't quite get how you concluded if and only if, because I don't see you proving the uniqueness of the sequence of b. But otherwise, well rounded proof to show why it works.
Sorry for skipping the if and only if part, felt too tired and just slacked off lol.
From the theorem, it is proven that if the prefix and suffix gcd sequences are valid, then our construction is a valid underlying sequence. But conversely, if the construction is a valid underlying sequence for the prefix and suffix gcd sequences, then it means that there exists an underlying sequence to have the given sequences as its prefix and suffix gcd sequences, which means that the prefix and suffix gcd sequences are valid, so it is an iff.
The theorem is proving something like: if there exists a solution to the problem, then X is a solution to the problem. But conversely if X is a solution to the problem, then there exists a solution to the problem.
As for the uniqueness of sequence b, it is just a device to show the properties of the sequences p and s, so I don't need it to be unique, I just need it to exist, which is assured by the definition of validity in the problem.
Yeah lol the 3rd paragraph was what I was wondering about, it felt obvious XD. Yeah but nice proof
did you develop this theorem or it has some source???can you share whats the name of this theorem?
Nah I developed it on my own. I used words like 'theorem' and 'corollary' just for better structure. But it is probable that this conclusion has already been proven in some related textbook (and has its own name) tho, idk.
Yes, I believe there is a mistake, as do you. I'm also trying to understand their proof, but I couldn't get it from yesterday lol. Isn't there an error in step 3? soullless
my g2 sol uses a two pointer approach while using segtree to handle query and updates. you can find nlogn solution here
Your solution is very interesting. At first impression, the merge function seemed to be non-commutative. But when I tried with a bottom-up implementation of segment tree, it worked without any handling of segment order, even when $$$n$$$ was not a power of 2. Would you care to explain why it works in this case?
because when you dont use a build function and build through a "update function", the range a node covers is calculated dynamically. they are calculated at "runtime" and are always the same for same n.
After much pondering over what you said, I decided to investigate what was really happening. I found that, in most implementations, the update function merges nodes $$$2i$$$ with $$$2i+1$$$ into node $$$i$$$, which may not be the correct order for all $$$i$$$ when $$$n$$$ is not a power of 2. However, the query function follows a different pattern, so that problematic nodes will be skipped and correct order is preserved (even if the right pointer falls in a subtree to the left of that of the left pointer). Anyway, thanks for the reply!
catch up to me on discord #hippie4640
Is there a way to use Segment Tree Optimized Graph Construction in problem C?
Typo on code problem C
For E: Should it be "Key arithmetic facts: $$$S_i$$$ and $$$x$$$ are always coprime, because $$$x = \frac{P_{i-1}}{P_i}$$$ and no prime can divide both a number and its own quotient. Symmetrically, $$$P_i$$$ and $$$y$$$ are coprime." ？
Another DSU solution to problem G (inspired by jiangly's): 329775391
Explanation: for each $$$a_i$$$ in descending order, search for the next available index $$$j$$$, both to the left and to the right, such that it can be part of a good segment (according to the prefix/suffix sums of $$$1$$$ and $$$-1$$$).
From my understanding, it works because each minimum need only be visited once (since we are iterating in descending order of median value and flipping values from $$$-1$$$ to $$$1$$$). At each iteration, we need only visit two such indices. Hope this makes sense.
what is the logic behind the increment/decrements? I get why DSU works here but struggling to understand how to actually implement it to solve this problem
The DSU in this case works like a linked list where elements are indices, except that it can identify the next item from a given index (which a linked list cannot do natively). You start with all indices and repeatedly remove them. The increment/decrement is just a way to link an index to its left or right neighbor. (This is not to be confused with the $$$\pm1$$$ used to model the problem.)
doubt solved
Code above is correct solution, 72 is not divisible by 48 so the answer "NO" is correct for given test case.
Thanks man I just realized I was so confused.
Just a question about Part D:
In the problem specification, it said that li <= reali <= ri and x = reali after visiting ith casino.
It make sense to only take ri if reali is not in the range of [li,ri].
But it doesn't make sense when we perform max(x, ri), if reali <= ri, and the specification said that x = reali after visiting ith casino.
max(x, ri) here means we are deciding whether to visit this casino or not
I didn't understand the step 3 part of editorial of Problem E.
gcd(pi−1,A)=pi and gcd(A,si+1)=si<- This is understandableDivide by g everywhere <- g is already factored out from previous pi and si as per step 2 what are we dividing now?
How did we arrive to these
gcd(x,A/g)=1 and gcd(A/g,y)=1equations just based on the fact thatpi-1 = pi * x and si+1 = si * yI have tried a lot to understand this but am not able to understand anything, If somebody can help I would appreciate it a lot.
I have the same question as you.Have you solved it yet?
I solved it but, I didn't get it from this editorial, I saw some video online for the solution.
Thanks for you reply，I solved this problem using another method too and still don't understand this solution.
Problem F is a nice problem, I enjoyed it.
soullless Why didn't you decide to accept $$$O(n\sqrt{n}\cdot logn)$$$ solutions in F?
By the plan, people had to solve problem by using brain, not just by transfering the problem into data structure that they know
Why is there a surge of people doing heavy-light partitioning in Div 3? I mean, was it that hard to do a simple tree-based solution? Look, it's not a 2400-rated D2E.
For real
For the entries of the hidden array A, why is A[i] = lcm(P[i], S[i]).
I would like to have an elementary and simply explanation since I not any good at math, and only understand the proof up until the second line of Step 3. I don't understand the rest.
Thanks in advanced!
...
Hello Codeforces Team,
I’ve received a plagiarism notification regarding my submission for Problem D in Round 1037 (Div. 3). I want to clarify that the solution was completely written by me, and I haven’t copied from anywhere or taken help from anyone.
I don't know how it is happened.I use struct,just because I didn't know about tuple back then.And I used priority_queue just because I couldn't solve in other ways.Using multiple approaces I couldn't even pass the example testcase as I couldn't implemented my idea,that is why I used priority_queue,and it worked.Then I thought if I put all the Real (here in my code which is r) based on l less than equal to current ans,which is initialized by k.After that if I pop the elements less than or equal to current ans,I can get the maximum current ans.That's why I tried this,and got AC.
Now I got this message,I don't know what should I do.I think it's a conincidence. I never face this before.So,I don't know what should I write here. I just can say it's maybe a coincidence from my side,please approve this. I don't know when will you review it.I write the code by my own.This code based on my idea.I always participate fairly in contests and never copied code. Even if you look the code,When I read the problem statement,it was l[i],Real[i],r[i] in this sequence,which I thought mistakenly,as am in time pressure during contest.So I made my custom ds by using struct in this sequence. But I couldn't even passed the example test case.Then I find out I took input in the wrong order which should be l[i],r[i],Real[i].But as it is in contest and time matters,thats why I didn't change the sequence and used r as Real and used Real as r.And my idea was clear to myself.I just came to know that my code matches to others.I don't know how.It's a coincidence maybe.They did this approach also.Here What's my fault?I don't even know.It will be very hurtful,if my submission got skipped.Please review it. And I never used ide.one,I use vscode always. I don't know is it enough to clarify it.But I hope my message can clarify the situation. I am fully aware of the importance of fair participation, and I always code alone during contests. And I assure you I’ve always followed fair practices. I hope you’ll consider my clarification.
Is there an issue with the solution for problem D?
For example, take this test case:
3 5
1 2 100
4 6 9
4 6 9
The reference program outputs 100, but the correct answer should be 9.
Above test case is not valid as per constraint given in problem that
for each $$$i$$$ \begin{equation}l_i \leq real_i \leq r_i\end{equation},
"In the solution to problem G1, I have a different opinion. I believe the correct case should be when the suffix maximum is greater than the prefix minimum."
When I thought carefully about it, I also arrived at this conclusion. Initially, I didn't understand the editorial and even thought it might be incorrect. But after thinking it through, I believe the editorial can be interpreted this way:
We only need to check whether a subarray ending (or starting) at position $$$j$$$ exists because — suppose both intervals $$$[x, j]$$$ and $$$[j, y]$$$ are invalid. What does that imply? It means that whether we extend to the left or to the right, in any such extended subarray, the number of elements greater than or equal to $$$m$$$ is less than half of the total number of elements. In this case, if we try to enlarge the interval from one end, the other end becomes a burden — it won’t help us make the number of elements $$$\ge m$$$ reach or exceed half.
This is why the condition in the editorial — that the suffix maximum is greater than or equal to the prefix minimum — is equivalent to the requirement. That is, either the suffix maximum is at position $$$j$$$, or the prefix minimum is at position $$$j$$$; at least one of these must hold.
From another perspective, $$$a[j]$$$ is at worst $$$-1$$$. If extending in either direction from $$$j$$$ fails to make the sum greater than or equal to $$$0$$$, then the best possible result we can achieve is just $$$-1$$$.
I thought about it more carefully and realized you were right. I forgot to consider that the maximum value of the suffix would also include the maximum value of the prefix, so my approach might not include 'j' in the result.
Problem D: Why does my DSU approach gives TLE on test 28.. it must be O(n.logn) Submission: 330766212
For E, you can also just compute $$$a_i := lcm(p_i,s_i)$$$, and then verify that $$$a$$$ produces $$$p$$$ and $$$s$$$.
I did the same thing
Can you please tell why does that work, i can't think about it intuitively
Because both $$$ p_i $$$ and $$$ s_i $$$ divide $$$ a_i $$$. It is sufficient because the constructed array of lcm will always satisfy the given $$$ p $$$ and $$$s$$$, if they are valid, again as the calculated $$$ p_i$$$ and $$$s_i $$$ from lcm array are the same as given.
332360899 Why is my solution to Problem D correct written like this?
Why solution to problem E not working when i am using the divide method taught in the tutorial. 1. Verify the divisibility chains and pn=s1 ; if something fails, print NO.
For every i=2…n check gcd((pi−1pi),Si)=1 .
For every i=n−1…1 check gcd((si+1si),Pi)=1 . (All divisions are exact by the chain property.)
If every test passes, print YES; otherwise NO.
nice one
2126A — Only One Digit
solution- https://youtu.be/T2g3bK6eNrM?si=d49_BqqFjlu1jTkh
https://mirror.codeforces.com/problemset/problem/2110/C D seems to similar this problem. Could anyone tell me that which algorithm or approach is suitable for these types of problem?
Hi can someone help me write this in text:
https://ibb.co/MwdvhMk
getting this error: The comment contains source code without markup.
Also , how can i inline image in comment
Problem F: why use map instead of unordered_map? The elements don't need to be sorted and map offers worse time complexity for access
If you want to maximize performance, there are custom hash tables or radix sort. It doesn't hurt to do map when you can, and it doesn't endorse others to use unordered_map blindly.
For Problem D:
1 9 20, 1 9 8, 8 8 100
the editorial solution gives answer 20 but the actual answer is 100 right?
In problem F, different heavy-light partition ways will get different verdict(TLE or AC) in spite of all of them is $$$O(\sqrt{n} \cdot logn)$$$ per query. I found a way that can AC(640ms): https://mirror.codeforces.com/contest/2126/submission/350566213
Had an alternative solution to E : https://mirror.codeforces.com/contest/2126/submission/352395496
Tried to create the original array and verify if the pref and sum gcd arrays match for the created array. An element i in the original array at a bare minimum has to have both p[i] and s[i] as factors. So generate an array v where v[i] = (p[i] * s[i]) / gcd(p[i], s[i]). This ensures that v[i] does not have any additional factors and only the bare minimum to be valid for both p[i] and s[i] values simultaneously.
Then to just verify p and s using this array. Can someone help with how to prove that this would work for all cases?
How is F rated 2000. The logic is simple. May be critical edge cases??
I am stucked in a doubt in Problem D. In editorial, it is checking only lower bound. It is not checking if curr value is greater than ri? And, It is clearly given in the question, that we can only enter in the casino, if our coin's value is between li and ri.
can someone explain this to me.
the solution of the problem E is not formatted correctly really difficult to even understand the solution
Problem B has already a neat solution, but other way to think of it in terms of sliding window is as follows.
The idea is to maintain a sliding window of size
kand check two things:0(good weather),To check if a window contains only zeros, maintain a variable
rainwhich stores the number of1s in the current window. Using a sliding window:At any index
i ≥ k-1, the window[i-k+1 ... i]is valid ifrain == 0.Next, we need to enforce the break condition. For this, maintain a variable
nextwhich represents the earliest index where the next hike can start.When we find a valid window:
start = i - k + 1start >= nextSo the condition becomes:
After taking a hike:
[start ... i]i+1is a mandatory breaki+2So we update:
Overall, we iterate once over the array, maintaining the sliding window and greedily taking the earliest possible valid hike.
This greedy works because taking a hike as early as possible always leaves more room for future hikes, and never reduces the total count.
Complete implementation:
Don't get how test case 1 for C is 3->2->1->4->5
shouldn't it be 1->2->3->4->5? as we need to climb in a non-decreasing manner.