Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
void I_love_feblokas();
int32_t main() {
int32_t tc = 1;
cin >> tc;
while (tc-->0) {
I_love_feblokas();
}
return 0;
}
void I_love_feblokas() {
int32_t ans = 0, cnt = 0;
int n;
cin >> n;
string s;
cin >> s;
for (auto &c : s) {
if (c == '*') {
cnt = 0;
} else {
cnt++;
}
ans = max(ans, (cnt + 1) / 2);
}
cout << ans << '\n';
return;
}
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
void I_love_feblokas();
int32_t main() {
int32_t tc = 1;
cin >> tc;
while (tc-- > 0) {
I_love_feblokas();
}
return 0;
}
void I_love_feblokas() {
int n;
cin >> n;
vector<ll> a(n);
for (auto &x : a) cin >> x;
ll cur = 0;
bool ok = true;
for (ll i = 0; i < n; ++i) {
cur += a[i];
ll need = (i + 1) * (i + 2) / 2;
if (cur < need) {
ok = false;
}
}
if (ok) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
void I_love_feblokas();
int32_t main() {
int32_t tc = 1;
cin >> tc;
while (tc-- > 0) {
I_love_feblokas();
}
return 0;
}
void I_love_feblokas() {
int n, x, y;
cin >> n >> x >> y;
vector<int> p(n);
for (auto &val : p) cin >> val;
int g = gcd(x, y);
bool ok = true;
for (int i = 0; i < n; ++i) {
if ((p[i] % g) != ((i + 1) % g)) {
ok = false;
break;
}
}
if (ok) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
2244D - Ярослав и продуктивность
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
void I_love_feblokas();
int32_t main() {
int32_t tc = 1;
cin >> tc;
while (tc-->0) {
I_love_feblokas();
}
return 0;
}
void I_love_feblokas() {
int n, m;
ll ans = 0;
cin >> n >> m;
vector<ll> a(n), b(m);
for (auto &x : a) cin >> x;
for (auto &x : b) cin >> x;
b.push_back(0);
sort(b.begin(), b.end());
vector<ll> pref(n + 1);
for (ll i = 0; i < n; ++i) {
pref[i + 1] = pref[i] + a[i];
}
for (ll i = 1; i < b.size(); ++i) {
ans += abs(pref[b[i]] - pref[b[i - 1]]);
}
ans += pref[n] - pref[b.back()];
cout << ans << '\n';
return;
}
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, q;
cin >> n >> q;
string s;
cin >> s;
vector<int> pref(n, 0);
for (int i = 0; i < n — 1; ++i) {
pref[i + 1] = pref[i] + (s[i] == s[i + 1] ? 1 : 0);
}
for (int i = 0; i < q; ++i) {
int l, r, k;
cin >> l >> r >> k;
if (l == r) {
cout << "YES\n";
continue;
}
int c = pref[r — 1] — pref[l — 1];
int needed = (c + 1) / 2;
if (needed <= k) cout << "YES\n";
else cout << "NO\n";
}
}
int main() {
int t;
cin >> t;
while (t--) solve();
return 0;
}
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
vector<vector<int>> g;
vector<int> leaf;
bool ok;
void I_love_feblokas();
pair<int, int> dfs(int u, int p);
int32_t main() {
int32_t tc = 1;
cin >> tc;
while (tc-- > 0) {
I_love_feblokas();
}
return 0;
}
pair<int, int> dfs(int u, int p) {
if (!ok) return {0, 0};
if (leaf[u] != 0) {
for (int v : g[u]) {
if (v != p) {
ok = false;
return {0, 0};
}
}
return {leaf[u], leaf[u]};
}
vector<pair<int, int>> segs;
for (int v : g[u]) {
if (v != p) {
segs.push_back(dfs(v, u));
if (!ok) return {0, 0};
}
}
if (segs.empty()) {
ok = false;
return {0, 0};
}
vector<pair<int, int>> sorted_segs = segs;
sort(sorted_segs.begin(), sorted_segs.end());
for (size_t i = 0; i < sorted_segs.size() — 1; ++i) {
if (sorted_segs[i].second + 1 != sorted_segs[i + 1].first) {
ok = false;
return {0, 0};
}
}
int start_pos = -1;
for (size_t i = 0; i < segs.size(); ++i) {
if (segs[i] == sorted_segs[0]) {
start_pos = i;
break;
}
}
if (start_pos == -1) {
ok = false;
return {0, 0};
}
for (size_t i = 0; i < segs.size(); ++i) {
if (segs[(start_pos + i) % segs.size()] != sorted_segs[i]) {
ok = false;
return {0, 0};
}
}
return {sorted_segs[0].first, sorted_segs.back().second};
}
void I_love_feblokas() {
int n;
cin >> n;
g.assign(n + 1, vector<int>());
leaf.assign(n + 1, 0);
ok = true;
for (int i = 2; i <= n; ++i) {
int p;
cin >> p;
g[p].push_back(i);
g[i].push_back(p);
}
int k = 0;
for (int i = 1; i <= n; ++i) {
cin >> leaf[i];
k = max(k, leaf[i]);
}
if (n == 1) {
cout << "YES\n";
return;
}
pair<int, int> res = dfs(1, -1);
if (ok && res.first == 1 && res.second == k) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Fenwick {
int n;
vector<ll> t;
Fenwick(int n) : n(n), t(n + 1, 0ll) {}
int f(int x) {
return x & -x;
}
void upd(int pos, ll val) {
for (; pos <= n; pos += f(pos)) t[pos] = max(t[pos], val);
}
ll get(int pos) {
ll ans = 0;
for (; pos > 0; pos -= f(pos)) ans = max(ans, t[pos]);
return ans;
}
};
void I_love_feblokas() {
int n;
cin >> n;
vector<ll> a(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
Fenwick t(n);
vector<vector<pair<int, ll>>> ev(n + 1);
ll ans = 0;
for (int i = 1; i <= n; ++i) {
for (auto& ev : ev[i]) {
t.upd(ev.first, ev.second);
}
int lim = i - a[i] - 1;
ll mx = 0;
if (lim > 0) {
mx = t.get(min(n, lim));
}
ll dp_i = a[i] + mx;
ans = max(ans, dp_i);
ll act = i + a[i] + 1;
if (act <= n) {
ev[act].push_back({i, dp_i});
}
}
cout << ans << "\n";
}
int main() {
int t;
cin >> t ;
while (t--) {
I_love_feblokas();
}
return 0;
}
Автокомментарий: текст был обновлен пользователем itz_pabloo (предыдущая версия, новая версия, сравнить).
The solutions for B, E, F and G are not formatted properly
Fixed
Am I missing some new C++ syntax updates? What is this line in the solution for $$$G$$$?
If you see &mdash. Its just error in the showing the code or a typo made by the writer of the tutorial(not likely).
These things are HTML symbols and have nothing to do with c++.
Yep, those are HTML entities not c++
"
—" means "-" minusyou can even see that in action on CF itself, just type
—and you will see — after postinghere , &mdash is an HTML entity that represents a long dash (—), called an em dash.
Автокомментарий: текст был обновлен пользователем itz_pabloo (предыдущая версия, новая версия, сравнить).
Honestly a decent contest, I just haven't seen E before so I didn't know how to do it.
you saw all the other problems before?
No I didn't "see" them before, but I kind of have.
A — find longest continuous sequence, done that before.
B — greedily place the books in a consecutive sequence 1,2,3... I have seen similar greedy problems where you have to place everybody consecutively.
C — fun little graph problem — there was a similar usaco problem where you had to check if a cow and the position of the cow were in the same connected component.
D — I listed out the array and the array times -1, realized you had to select the intervals according to the posts + Pref sums (aka DP) to speed up the solution — this problem was similar to We Be Flipping (Problem C from Spectral Cup Round 2)
E — somebody help me here, I hate flipping subarrays in order to get it to alternate, I've never done this alternating shit before. It's obvious, but if you've never seen it — it's not, and I wasn't bothered enough to actually bash out the greedy approach?
My approach to E:
Define $$$eqCnt$$$ as the count of $$$s[i] == s[i + 1]$$$. Clearly a string is alternating iff $$$eqCnt = 0$$$.
Now consider what happens when you invert the range $$$[l, r]$$$. The only change in $$$eqCnt$$$ will come from neighbours $$$(l - 1, l)$$$ and $$$(r, r + 1)$$$, where one part is flipped, and the other is left alone. The inside of the region $$$[l, r]$$$, will have flips like $$$00$$$ to $$$11$$$ or $$$01$$$ to $$$10$$$, none of which will affect $$$eqCnt$$$.
An optimal approach to make a string alternating is to iteratively fix the leftmost and rightmost occurences of equal neighbors. Suppose $$$s[l] = s[l + 1]$$$ and $$$s[r] = s[r + 1]$$$ then inverting $$$s[l : r]$$$ will reduce $$$eqCnt$$$ by $$$2$$$.
A case to consider is when you only have $$$eqCnt = 1$$$. i.e. $$$01001$$$. In this case (given $$$s[i] == s[i + 1]$$$) you can just invert $$$s[i + 1 : n]$$$ and reach $$$eqCnt = 0$$$.
This process can clear $$$eqCnt$$$ equal neighbors using $$$ \lceil \frac{equalCnt}{2} \rceil$$$ operations.
Thus for a $$$query(l, r, k)$$$, use prefix sums to get the $$$eqCnt$$$ of $$$s[l : r]$$$ and check if $$$\lceil \frac{equalCnt}{2} \rceil \leq k$$$.
Thank you mgranger22 — great explanation, way better than the editorial's by a mile! I didn't think about counting equalities, I was too distracted by counting alternations.
It makes sense that the eqCnt of the interval from [l, r] always stays the same because you invert everything, some if 2 adj elements were equal they still are equal and vice versa.
The only thing that changes the eqCnt is the relationship between l — 1 and l and r and r + 1, since l got flipped and r got flipped the eqCnt gets reduced by 2. Wow!
And you can also reduce the last one (if eqCnt was originally odd) easily.
Dang, well played. Now I know to look for equalities when you have alternating problem.
I have a doubt in Question E, I was hoping you could help me,
If k is equal to 0 and the string is not already alternating then shouldn't the answer automatically be NO
Yes, I think so.
Yes. This will be handled correctly by the above approach as $$$eqCnt \gt 0$$$ implies $$$ \lceil \frac{eqCnt}{2} \rceil \gt 0$$$ which is not less than or equal to $$$k = 0$$$
My bad, I have understood it now
Thank you!
Why did you use pre[r] — pre[l] rather than pre[r] — pre[l-1] in your code. dont we get the eq count by the latter formula?
$$$pref[i]$$$ counts equal adjacent pairs up to the pair $$$(i-1, i)$$$, not characters up to index $$$i$$$.
For substring $$$s[l,r]$$$, the internal adjacent pairs are $$$(l,l+1), (l+1,l+2), \dots, (r-1,r)$$$, which correspond to prefix indices $$$l+1$$$ through $$$r$$$.
So the count is $$$pref[r] - pref[l]$$$; using $$$pref[r] -pref[l-1]$$$ would incorrectly include the outside pair $$$(l-1,l)$$$.
A good way to avoid such off by $$$1$$$ confusion is to consider the full array query $$$[0, n-1]$$$ and make sure the formula matches the total count.
Okay, Thanks for the clarification.
literally my approach, couldn't have said it better tho
Nice approach.
I tried that appraoch first when solving this problem but Idk why I thought that I can reduce the eqCnt by two only if the interval I choose is 0011 (the interval here is [2,3]) . Because of that I didin't continue with my appraoch and went into a much harder one.
cool man, ur able to connect the dots, i like the way u described it... btw u dont need dp for D
Yeah even i felt part D was similliar to one of the latest problems i have solved , thanks for mentioning the name of the problem . I was trying to find that problem for hours .
Here is a similar problem to E from CP31 sheet of TLE Eleminators — 1600 rated.
Similarity: There also target string can have 6 configuration and here binary string has two different configuration
0101..or1010... So we can precompute operations for both of them. My submissionThanks for pointing that out, I've never tried CP31 before, but I will definately take a look at that problem after upsolving C from the Spectral Cup Round 3.
lol
deleted
For F
A tree can be good when all its subtree are good individually --> part1
and
all the leaf node values of all subtree can be arranges in increasing order by doing any no of ops --> part2
part1 is recursion on tree
part2 :
**when all subtree are individually good**, each subtree has min and max value of leaf node and we want to form a strictly increasing sequecne each subtree have min and max value of leaf node : ( **min** , max ) Ex : ( a , b ) , ( c , d ) , ( e , f ) , ...... , ( q , r ) find index with min value of **min**, from there check if next interval follows the condition : curMax < nextMin . When this condition is true for all pairs, the tree is good To check this, min and max leaf node values are needed from all good subtrees.Both parts can be handled in the same recursion.
I tried to explain in the best and easy to understand way as far as I know. Hope this help someone.
AC Implementation
ngl idgaf fr
spasibo for fire round
btw, problem E can be solved also using MO’s algorithm check out code in my submissions
Автокомментарий: текст был обновлен пользователем itz_pabloo (предыдущая версия, новая версия, сравнить).
Auto comment: topic has been updated by itz_pabloo (previous revision, new revision, compare).
wonderful F
Problem C is just beatifull!
Can Anyone explain in detail the solution and intuition for Problem D.
The key idea the editorial is trying to get across is that we can freely choose whether or not to negate each region between posts (except for the last one for obvious reasons).
Denote the posts (in sorted order) as $$$p_1, p_2, ... , p_n$$$.
Also insert a sentinel post $$$p_0 = 0$$$ to account for the first region.
Suppose we decide to use $$$p_3$$$ and $$$p_2$$$. All $$$i \leq p_2$$$ will be negated twice (once by $$$p_2$$$, once by $$$p_3$$$), thus cancelling out and leaving the indices as they were originally. All $$$p_2 \lt i \leq p_3$$$ will be negated once.
Basically, by selecting $$$p_i$$$ and $$$p_{i + 1}$$$ we can negate the region $$$(p_i, p_{i + 1}]$$$.
Work from right to left considering each region $$$(p_{i} p_{i + 1}]$$$. If the region's sum is non-negative then leave it as is. Otherwise, we should negate this region to make the negative sum contribute a positive amount.
To do this, activate $$$p_{i + 1}$$$. This will negate our target region, but it will also negate all regions before it. However, this is of no concern, as later $$$p_i$$$ to the left can leave/undo this.
Now you don't fully need to simulate this process. Just observe that we can take the absolute value of each region (besides the last).
No better strategy exists since it's impossible for us to get any more granular in the segments we do/don't negate given we only have control of $$$p_i$$$'s.
Can someone explain the x+y <= n for C?
Basically you can just form groups where position is separated by gcd(x,y) and can swap elements of these group within this group only and at any position within group, but can't swap with other group, so problem narrow down to see if element belong to the same group as its final Postion group or not because final array has position equal to value at position, so just see if element modulo gcd is equal to its current position modulo gcd or not.
The claim is that indices of the same remainder mod $$$gcd(x,y)$$$ are connected via jumps of size $$$x$$$ and $$$y$$$ while staying in $$$[1, n]$$$. That is to say that from any $$$i \equiv rem$$$ $$$(\text{mod } gcd(x, y))$$$ you can reach any other $$$j \equiv rem$$$ $$$(\text{mod } gcd(x, y))$$$
Now consider the case $$$n = 5$$$, $$$x = 3$$$, and $$$y = 4$$$ (note that $$$x + y \gt n$$$).
$$$gcd(x, y) = 1$$$, so all indices should be reachable from one another.
However, if we start at $$$i = 3$$$, all possible jumps of size $$$x$$$ or $$$y$$$ land outside of $$$[1, n]$$$.
The condition that $$$x + y \leq n$$$ ensures that for any start position has some legal move. Proving that all positions of the same residue class are reachable is a bit more work, but hopefully this helped demonstrate the necessity of the condition.
Q1. Why is it necessary that all paths would consist of steps of length $$$x$$$ and $$$y$$$? If a graph was constructed with only differences of $$$x$$$ in the positions, it would only have steps of length $$$x$$$.
Q2. Why can we change the position index by a multiple of $$$g$$$? If $$$x=2$$$ and $$$y=3$$$, then the $$$\gcd{(x, y)}=1$$$. In this case, if we change the positions by a multiple of $$$g=1$$$, then we are violating the rules of the problem itself, where it is saying that we can only reach positions where the difference in the positions is either $$$x$$$ or $$$y$$$.
Q3. Didn't understand this part at all. How would you replace all the "out-of-bound" steps with equivalent ones? How come each connected component consists exactly of all positions with the same remainder modulo $$$g$$$.
Travel as in reach using a sequence of allowed moves.
Problem E doesn't seem easy to understand at all.
I have never written explantion to code in details and my first time posting here. so i will submit the code. This is my solution to E:
problem G is identical to Bouqet, an EGOI problem from 2024.
Damn D cooked me, ive done DP and got it wrong for an hour XD nice problem-set tho- really impressive for a solo writer!
for problem C, could someone please share a rigorous proof of why, when x+y<=n, any two indices with the same remainder mod gcd(x,y) are guaranteed to be connected by jumps of size x and y without ever leaving the range [1,n]?
i understand the intuition behind the editorial's statement, but I'm struggling to turn it into a formal proof
I will explain my approach for it.
First, why the condition $$$x+y \lt =n$$$ exists in the first place. This condition will allow you to always swap any element whatever its position in the array.
Now, let's assume that we moved $$$A$$$ times using step $$$x$$$, and we moved $$$B$$$ times using step $$$y$$$.
both $$$A,B$$$ can be negative, which means moving in the other direction. For the array to be sorted, you need to move each element to its right place.
lets assume this array: $$$[3,2,1]$$$ The number 1 needs to move -2 in the index. 2 needs to move 0. 3 needs to move 2.
the question now is, can we achieve these moves? The distance $$$D$$$ moved can be represented by this formula. $$$x\times A + y\times B = D$$$
There is a well known theory (Diophantine equation) that says, these kinds of equations only have solutions if and only if: $$$gcd(x,y)$$$ divides $$$abs(D)$$$.
So, the solution will be just to iterate on the array, and see the distance that we need to move so we can put each element at its right index. and for each element, we check if gcd(A,B)%dist == 0
if there exists an element that this condition doesn't hold, then the answer will be NO. Otherwise, the answer is YES.
My solution
https://ideone.com/nS8b1z
This is correct but it misses a final piece of the proof: how do you know that all permutations are reachable in this way?
Your argument shows for any pair of indices (i, j) where i = j mod gcd(x,y) there is a sequence of swaps that moves the element from index i to index j. But in the process, you shift a bunch of other elements too.
To complete the proof, you also need to show that you can swap the element at i and j without moving the other elements. To show that, consider the sequence of indices i=i1, i2, i3, .. ik=j that the element moves to when we perform swaps (i1, i2), (i2, i3), etc. Then the element that started at index i ends up at index j, and the element at i2 ends up at index i1, the element at i3 ends up at index i2, etc. each element being moved backward one place in the sequence of indices.
To restore them, we can perform the swaps in reverse except for the last: swap (i{k-1}, i{k-2}), (i{k-2}, i{k-3}), etc. This moves the element at i{k-1} which was originally at ik = j to i1 = i, and all other elements are moved forwards, back to their original position, so the final effect is that only the elements at index i and j are swapped.
So now we know how to swap any pair of elements (provided their distance is a multiple of gcd(x, y)) we can use any sorting algorithm to sort the array.
Thank you!
I'd go a step further and argue that the proof is also missing a justification that the sequence of swaps described is always possible while staying in $$$[1, n]$$$ for $$$x + y \leq n$$$. It's not as if you can just take $$$A$$$ steps of $$$x$$$ then $$$B$$$ steps of $$$y$$$, as this will often lead you out of bounds.
You're right, the comment I replied to wasn't super clear. Other comments invoked Bézout's identity which hints at the proof. I was hesitant to repeat it but I can spell out the argument explicitly to make the proof really airtight.
Bézout's identity guarantees that if $$$gcd(x, y) = d$$$, then we can write $$$d = ax + by$$$ for some pair of integers (a, b) and it follows that any multiple of $$$d$$$ can be written like that as well. Actually calculating the Bézout coefficients requires the extended Euclidean algorithm, but for the proof it is enough to know that a solution exists.
That means for any pair of indices (i, j) ($$$1 \le i, j \le n$$$ and $$$j - i$$$ is a multiple of $$$d$$$) we have some (a, b) such that $$$j = i + ax + by$$$, implying we can move from $$$i$$$ to $$$j$$$ taking $$$a$$$ steps of size $$$x$$$ and b steps of size $$$y$$$. Note that $$$a$$$ and/or $$$b$$$ may be negative but they are integers.
When $$$a$$$ and $$$b$$$ have the same sign (or one of them is zero) then trivially we can just take all the steps in the same direction without going out of bounds since all intermediate steps lie strictly between $$$i$$$ and $$$j$$$.
Otherwise, $$$a$$$ and $$$b$$$ have opposite signs. W.l.o.g. assume $$$a \lt 0$$$ and $$$b \gt 0$$$ (otherwise just swap $$$x$$$ and $$$y$$$ and $$$a$$$ and $$$b$$$). We have to take $$$-a$$$ steps backward (decreasing $$$i$$$ by $$$x$$$ each step) and $$$b$$$ steps forward (increasing $$$i$$$ by $$$y$$$ each step) to reach the goal for a total of $$$b - a$$$ steps.
The claim is that at any intermediate index $$$i$$$ ($$$1 \le i \le n$$$) either $$$i - x$$$ or $$$i + y$$$ is in bounds so we can always take one more step, reducing the absolute value of either $$$a$$$ or $$$b$$$ by one, until $$$a = b = 0$$$ and we arrived at the desired $$$j$$$. This follows from the guarantee that $$$x + y ≤ n$$$ as follows:
So when $$$i - x$$$ is out of bounds, $$$i + y$$$ must be in bounds. The reverse can be proven similarly. Either way, we can always take one step closer (reducing $$$|a| + |b|$$$ by 1) until we end at the destination without ever stepping out of bounds.
Nice. I made another argument a bit down in the comments, but I think I prefer yours.
I solved problem G slightly differently (maybe overcomplicating it?) by using a
monotonic stack of pairs (i, v), where (i, v) denotes a sequence that ends at index i and has maximum value v. Clearly if we have two pairs (i, v) ≠ (j, w) such that i ≤ j and v ≥ w, then the first pair is strictly better than the second, because any element that can be appended to the second sequence can also be appended to the first for an equal or better total value, so we can erase the second pair.
We then end up with a sequence of pairs (i1, v1), (i2, v2), .. so that i1 ≤ i2 ≤ .. and v1 ≤ v2 ≤ .. which can be stored in a std::map which maps indices (keys) to values and can be queried efficiently with std::lower_bound.
The idea is a little similar to the standard solution to the longest increasing subsequence (LIS) problem. The difference is that we have to insert in the middle of the "stack" which is why std::map is needed instead of a simple std::vector for the LIS problem.
The upside is that you can implement this with just std::set/std::map without needing Fenwick arrays or segment trees.
(Ugly) code here: 382685473
Can I ask about this approach? This was actually the first thing that came to mind for me but I didn't think it would work.
Because if we are considering doing the assignment at index i and before it an assignment at index j, we need both: - i — a[i] > j - j + a[j] < i
so I thought we also need to care about the index at which an assignment starts (i.e. we care about index j as well as index j + a[j]).
So I thought we'd somehow need to store (s, e, v) where v is value, s is start (i.e. j) and e is end (i.e. j + a[j]) in our monotonic stack, but as far as I can see this can't be done.
What am I missing?
Thanks very much
Yes, there are two constraints, which are handled differently. When we are at index $$$i$$$, the monotonic stack is only used to find a maximal index $$$j \lt i - a_i$$$ which satisfies the constraint $$$i - j \gt a_i$$$.
To satisfy the other constraint, $$$i - j \gt a_j$$$, we don't insert the sequence found at index $$$i$$$ into the monotonic “stack” immediately, but delay that until we arrive at index $$$i + a_i + 1$$$, which is the earliest time where it could possibly be used. In my code, this is what
queueis for: to delay the insertion intoindex_to_value.So at any index $$$i$$$,
index_to_valuecontains (at most) the sequences ending at indices $$$j$$$ such that $$$j + a_j \lt i$$$ or equivalently $$$a_j \lt i - j$$$.Ahhh ok so you still use the delay idea. That makes sense then, thank you very much for your reply :)
PROBLEM(C) - DSU Graph Approach - O(N α(N))This problem can be elegantly solved by modeling it as a graph and using Disjoint Set Union (DSU).
The Core ObservationThink of the array indices (from 1 to n) as nodes in an undirected graph. A valid swap operation connects two indices. If two indices belong to the same connected component in this graph, we can always route an element from one index to the other through a sequence of valid swaps.
Therefore, for the permutation to be sortable, every element's starting index must be in the same connected component as its final sorted index.
Core Logic Snippetexact same solution!! crazyy
A simpler way of performing the check in F would be to just rotate the segs array defined in the author's solution such that the min element is at the first place. Then just check the adjacent elements.
https://codeforces.me/contest/2244/submission/382719882
Yes,I did the same.As leaf's value form permutation,its necessary and the sufficient condition.
I also conducted the same check. All that was needed was to rotate the sub-tree and check the adjacent elements. There was no need to sort the sub-tree.
I did it by checking for each child node lengths the number of nodes for which
c[i]>c[i+1]. If this number is greater than 1, then it means it cannot be cyclically brought to the ideal state.My submission
Can someone provide a proof of why the condition $$$x + y \le n$$$ is sufficient?
if you use DSU, then this condition doesn't matter anymore
I know a DSU solution works. My question is specifically about the proof in the editorial. I'm curious why the condition $$$x + y \le n$$$ guarantees that we can always move from $$$i$$$ to $$$i \pm \gcd(x, y)$$$ without leaving the array.
see essentially we are solving Ax+By=c*gcd(x,y) where c*gcd(x,y)=abs(i-j). now say the soln you get has a positive A and negative B, meaning you move forward A times and backward B times. say you are at i and want to move x position forward but i+x>n meaning if you do so you move out of array bounds itself which isnt possible. x+y<=n ensures that if ever your i+x>n then i-y>=1 meaning if you cannot move forward then you can always move backward vis-a-vis for opps direction aswell. It ensures that finding a soln to ax+by=abs(i-j) is enough and you need not worry about going beyond array bounds.
OMG, that's such a nice proof, thank you!!
Not to be that guy, but I don't feel this is a very complete proof. These observations only show that some opposite move is available at any moment, but it does not show that taking it is compatible with the chosen Bézout solution or that the remaining moves can still be chosen to reach the target destination.
If in a valid path you stepped out of the array by a $$$+x$$$ move, you must step back into it with $$$-y$$$ at some point in the future. So let's do $$$-y$$$ right now — we can because $$$x+y\leqslant n$$$.
Here's a construction using the euclidean algorithm:
Suppose wlog that $$$x \gt y$$$ and let $$$r = x \% y$$$. It is possible to go from any position $$$p$$$ to $$$p + r$$$ via some series of $$$x$$$ and $$$y$$$ jumps.
Notice that $$$x + y \leq n$$$ implies $$$n - x \geq y$$$, and thus the range $$$[1, n - x]$$$ contains every remainder mod $$$y$$$ (this is NOT guaranteed when $$$x +y \gt n$$$).
To go from $$$p$$$ to $$$p + r$$$ follow this process:
Select some $$$s \in [1, n - x]$$$ where $$$s \equiv p$$$ (mod $$$y$$$).
Jump to $$$s$$$ via $$$\pm y$$$ jumps.
From $$$s$$$, jump $$$+x$$$ (this will stay in bounds), then jump $$$-y$$$ as much as possible while staying above $$$s$$$.
Following this process you will end at $$$s + r$$$, and since $$$s + r \equiv p + r$$$ (mod $$$y$$$) we can reach $$$p + r$$$ via more $$$\pm y$$$ jumps.
Thus, the jump pair $$$(y, r)$$$ can be represented using the jump pair $$$(x, y)$$$.
Now iteratively apply this argument, and you'll follow jump pairs $$$(x, y), (y, r), ... , (gcd(x, y), 0)$$$. This is the typical euclidean algorithm.
Since each jump pair can be represented via the previous jump pair (while staying in bounds), by transitivity it follows that jumps of $$$gcd(x, y)$$$ can be represented by a series of $$$x$$$ and $$$y$$$ jumps while staying in $$$[1, n]$$$.
please can someone explain that in B problem
author used (i + 1)*(i + 2)/ 2 this formula instead of (i + 1)*i /2 formula ????
since index is starting from 0 , and we need to start our series from 1. We are adding +1
ya thxk arnav , i got it now
Decent problem for div 3 . Rep++
this contest is very kind to we newbie! I solved A ~ E(smile emoji) ah ha
this was my first ever contest and i wasted so much time in question 1 because i misread the question , rather then reading one line i read like each line and interpreted it as string which made me use two pointer checking front and back indices with condition and wasted so much of my time and was only able to solve around first 2 question , in 2nd question i only took 30 mins and during 3rd question contest ended, I think is preety good for starters maybe . Any tips guys for a new guy like me because reading that big para is a bit tricky for me because on leet the problem doesnt have the story and all.
Read more carefully and typing quickly(I don't think B needs to cost 30min)
You can do some simple problems(around 800) to improve yourself
ok thnx bud
I think that problem C is interesting but it's harder than D.Maybe my math is soo bad.
Great contast Thanks
my rating is not updated till now and, this contest is showing unrated in my contest list, even i registered for the rated, can you tell me why?
Me too, and the same thing happened to my friends. Also, the problem I solved doesn't show up. I think we should just wait.
I'm pretty sure it's because of system testing all submissions against successful hacks. The entire process is taking 5+ hours, but once it's done final contest results should show up and correctly solved problems will be properly marked.
Man, I feel so stupid after not being able to solve C and D.
In the D problem , how are we telling this — "Since the posts can be chosen arbitrarily, y1,…,ym can be anything." ? I mean doesnt it depend on the given set of b[i]'s ? how are we drawing this conclusion ? Is there a sound proof for this assumption?
This problem can be considered from the perspective of the greedy algorithm. Suppose $$$(b_1, b_2]$$$ needs to be flipped and has already been flipped. When it is necessary to flip $$$(b_k, b_{k+1}] (k \gt = 2)$$$, simply cancel the flipping of $$$(b_1, b_2]$$$ (this is always feasible, as the previous b elements do not need to be selected).
Consider iterating backwards through segments of the form
(b_k, b_k+1]starting from(b_m-1, b_m]. We can always greedily choose to include/not include the postb_kto flip the parity of the segment(b_k, b_k+1]regardless of any sequence of posts chosen greater thank.Helps. Thanks!
can we do D by backtracking and recusrsion, or will the tc not allow
wdym by backtracking, the time complexity would be O(2^m), your code would still be running even after the earth is gone lol
But you can use memory search(search but like dp)
the solution is quite long can it be shortened . i wrote using template . i am trying to make my code less bloated btw . "Bad Taste"
When I realized that G was eazy the contest ends.
I think I spend to much time on F(It strucked me 1h and my code can't even pass the sample)
G was the only problem I couldn't solve (idk segment trees and barely know fenwick trees). But yeah F was definitely the most time consuming, though it is a fairly standard problem. I just haven't practiced dfs/graph problems enough.
You can learn some data structures. Such as segment trees and Binary Search Trees.
It's easy to understand and useful. I solved E by using segment trees and passed it in O(nlogn).
I'm finally learning segment trees now, but using it for problem E is definitely overkill since you can just use prefix sums. I don't have any issues solving easy problems like those, the ones that require these kinds of advanced data structures are where I need to learn more.
You are right. But I solved lots of problems about using segment trees to get subsegment's mergable information. So thats simple for me.
itz_pabloo my solution for B was accepted during contest and i was aware that it will give integer overflow without long long but still it got accepted at that time. the tests were weak for the contest.
Well,for E,I set f[i]=a[i] xor a[i-1],and for each operation,changes two of f,then it is solved
Thank you，very interesting idea！
Given: A permutation $$$p$$$ of size $$$n$$$ and positive integers $$$x, y$$$ such that $$$x + y \leq n$$$. An operation allows swapping elements $$$p[i]$$$ and $$$p[j]$$$ $$$(1 \leq i, j \leq n)$$$ if at least one of the following conditions holds: $$$|i - j| = x$$$; $$$|i - j| = y$$$. Prove: Whether the permutation $$$p$$$ can be sorted using this operation (with unlimited number of applications). Proof: Consider for position $$$i$$$ all positions reachable for swapping: $$$i + x, i + 2x, i + 3x, \ldots$$$ $$$i + y, i + 2y, i + 3y, \ldots$$$ $$$i + x, i + x + y, \ldots$$$ This means we can take distance $$$y$$$ some number of times and then $$$x$$$ some number of times. Let $$$a$$$ be the number of times we took distance $$$x$$$, and $$$b$$$ be the number of times we took distance $$$y$$$. The numbers $$$a$$$ and $$$b$$$ can be negative (if we go backwards). Then for position $$$i$$$ we need to move to position $$$j$$$. Then we have: $$$j = i + ax + by.$$$ Moving $$$i$$$ to the left: $$$j - i = ax + by.$$$ Notice that $$$ax + by$$$ is a Diophantine equation! A Diophantine equation of the form: $$$ax + by = c$$$ where $$$a, b, c \in \mathbb{Z}$$$, and $$$x, y$$$ are the numbers to be found. In our case we need to find $$$a$$$ and $$$b$$$. Then solutions exist only when $$$(j - i)$$$ is divisible by $$$\gcd(x, y)$$$ (from the classical criterion for Diophantine equations).
And the question arises: how does this relate to sorting? In a permutation sorted in non-decreasing order, at position $$$i$$$ the value is $$$p[i]$$$ and vice versa. Using these movements we can determine whether it is possible to move from position $$$i$$$ (where the value of the $$$i$$$-th element is $$$p[i]$$$) to position $$$p[i]$$$ (where it should be in the sorted permutation). This can be determined by the previous fact: is $$$j - i$$$ divisible by the greatest common divisor of $$$x$$$ and $$$y$$$? By the criterion for congruences, if $$$(j - i)$$$ is divisible by $$$\gcd(x, y)$$$, then: $$$j \equiv i\pmod{\gcd(x, y)}.$$$ Then, if $$$j$$$ is not congruent to $$$i$$$ modulo $$$\gcd(x, y)$$$, it is impossible to move, and the array cannot be sorted in non-decreasing order.
Then the criterion is as follows: if there exists an $$$i$$$ such that $$$j$$$ is not congruent to $$$i$$$ modulo $$$\gcd(x, y)$$$, where $$$j = p[i]$$$ (we need to move to this position), then the array cannot be sorted in non-decreasing order. If no such $$$i$$$ exists, then it can be sorted in non-decreasing order. $$$\boxed{\forall i: p[i] \equiv i \pmod{\gcd(x, y)}}$$$ If this holds, the answer is YES; otherwise, NO. Q.E.D.
You did not show the following fact: that when moving along edges, we always change the position number by a multiple of g. In the solution above, this fact is rigorously examined.
Much better explanation than the editorial. Thanks a lot for such a good explanation <3
I'm very glad. Thank you. I think about your proposal.
382644154
why is this wrong for D
first time participant here. when will the contest standings be finalized to get a rating?
usually it takes some hours after system testing has finished
itz_pabloo, could you please check the failing test for my submission 382619643 for D? I'm getting Runtime Error on test 8, but I can't reproduce it locally and I really feel there is a problem in that test case. Even a hint about the test or the reason for the runtime error would be greatly appreciated. Thanks!
382644154
plzz check this one also, got wa on test 8 in system testing
Hey itz_pabloo, I found the mistake in the test case. The question states that all bi are distinct, but in test case 8 there are some bi which are duplicate see the submission 382776734, there I have printed the bi which are duplicate in test case 8.
crazzy bro, I did not even think that the test case could be wrong
382633028
I am also getting Wrong Answer on Test-8 due to duplicate b[i] in test case while the question clearly states that all b[i] are distinct
Why is below solution to C incorrect? ~~~~~ void solve(){ int n,x,y; cin>>n>>x>>y; if(x > y)swap(x, y); vector v(n), p(n+1); for(int i=0;i<n;i++){ cin>>v[i]; p[v[i]] = i+1; } int g = gcd(x, y); for(int i=0;i<n;i++){ int t = abs(p[i+1] — i+1); if(t % g != 0){ cout<<"NO"<<endl; return; } } cout<<"YES"<<endl; } ~~~~~
can anyone help me how to get pupil without cheating in contests, yesterday i stuck at C problem i cant understand the solution also.
How can I write a contest?
I would like to contribute!
So for https://codeforces.me/contest/2244/submission/382666246 (problem D) I could've not sorted in reverse and it would've worked too?
Can anyone help me why this solution is wrong for B question —
I also have the same issue but the solution was to multiply 1LL with this
ll temp = 1LL*(i+1)*(i+2))/2;
Its giving W.A. for Integer Overflow.
In C++, the GCC header <bits/stdc++.h> includes almost all standard library headers, so you don't need to include them individually.
Can anyone help me find the test case where my code fails? I'm getting a Wrong Answer on test 2, but I can't figure out which input is causing it.
You inititialized r as an integer, but it could (and would in many cases, since you're piling the excess books onto the last pile) cause integer overflow. Changing r into a long long type fixes the error.
thank you , @andrew2028
Hello Everyone, Can somebody Please tell me why is this a ** Wrong Submission** 382822764
Edit : I found the error It was I am not multiplying 1LL inside the bracket , Thanks for reading my comment.
Я новичок на (Codeforces), раньше программировал на других сайтах. Я сам решил задачу (E), не могли бы вы сказать, почему я получил предупреждение за похожие ответы? Вопрос был простым, не могли бы вы его проверить?
I don't understand the tutorial of E at all. How do they merge? Also, the code seems to be totally different then the approach mentioned in the tutorial.
can anyone help me with problem f,like how are we comparing globally.
the solution of $$$F$$$ in editorial seems overcomplicated , what I did was I calculated $$$dp[i]$$$ for each node which means minimum value among leaves in the subtree rooted at $$$i$$$ , then for each vertex I kept doing cycling shifting in it's children until the child with minimum $$$dp[i]$$$ value comes to the left , then I ran a simple dfs and kept pushing the leaves in a vector by their order in the dfs , if that vector is sorted answer is YES otherwise NO
It took me some time to come to the conclusion that the parities y1, y2, ..., ym can be chosen arbitrarily, so this is if you want the proof:
It is easier to reason from right to left.
Therefore, every parity vector (y1, y2, ..., ym) is achievable by an appropriate choice of posts. Hence, the sign of every segment can be chosen independently.
Is it essential to add so much (ok test) for question F. XD It takes actually a very while to understand them.
F. Anya Loves Trees Video Editorial link (dfs solution): https://youtu.be/cR1qc2FcnuU?si=NekZjE2B3wPKHN_y
Thanks a lot for C: the fact that $$$x + y \leqslant n$$$ means we can persistent inbounds is nice.
Also wanted to mentition that for G,
std::setis sufficient: https://codeforces.me/contest/2244/submission/385405936 We just need to to keep both the index and the value in increasing order, dropping useless options.What i did in problem E:
I first created 2 beautiful strings (one that starts with 0 and the other with 1), then created 2 vectors to store the segments in which the string's characters differ from the beautiful strings. To find the answer, what i basically did was use lower_bound for (l, 0) and (r, 0) to get the number of segments that i need to invert.
well, i think it's more complicated than the tutorial's solution, but i think this pattern is good to know.
This is my submission: 385693132
C is just way easier with DSU, man.