1694A - Creep
Idea: AmShZ
Solution
Tutorial is loading...
Implementation
# include <bits/stdc++.h>
using namespace std;
int t, A, B;
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> t;
while (t --){
cin >> A >> B;
for (int i = 0; i < min(A, B); ++ i)
cout << "01";
for (int i = 0; i < abs(A - B); ++ i)
cout << (A < B ? 1 : 0);
cout << '\n';
}
return 0;
}
1694B - Paranoid String
Idea: AmShZ
Solution
Tutorial is loading...
Implementation
# include <bits/stdc++.h>
using namespace std;
int t, n;
string S;
long long ans;
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> t;
while (t --){
cin >> n >> S, ans = n;
for (int i = 1; i < n; ++ i)
if (S[i] != S[i - 1])
ans += i;
cout << ans << '\n';
}
return 0;
}
1693A - Directional Increase
Idea: alireza_kaviani
Solution
Tutorial is loading...
Implementation
//In the name of God
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 100;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n, t, a[maxn];
long long ps[maxn];
int main(){
fast_io;
cin >> t;
while(t--){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
ps[i] = ps[i - 1] + a[i];
}
if(ps[n] != 0){
cout << "No\n";
continue;
}
bool ok = 1;
for(int i = 1; i <= n; i++){
if(ps[i] < 0) ok = 0;
}
bool visited_zero = 0;
for(int i = 1; i <= n; i++){
if(ps[i] == 0) visited_zero = 1;
else if(visited_zero) ok = 0;
}
if(ok) cout << "Yes\n";
else cout << "No\n";
}
return 0;
}
1693B - Fake Plastic Trees
Idea: AmShZ, alireza_kaviani
Solution
Tutorial is loading...
Implementation
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int t, n, l[N], r[N], ans;
vector <int> adj[N];
ll DFS(int v){
ll sum = 0;
for (int u : adj[v]){
sum += DFS(u);
}
if (sum < ll(l[v])){
++ ans;
return r[v];
}
return min(ll(r[v]), sum);
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> t;
while (t --){
cin >> n;
for (int i = 2; i <= n; ++ i){
int par;
cin >> par;
adj[par].push_back(i);
}
for (int i = 1; i <= n; ++ i){
cin >> l[i] >> r[i];
}
ans = 0;
DFS(1);
cout << ans << "\n";
for (int i = 1; i <= n; ++ i){
adj[i].clear();
}
}
return 0;
}
1693C - Keshi in Search of AmShZ
Idea: AmShZ
Solution
Tutorial is loading...
Implementation
# include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, d[N], dist[N];
priority_queue <pair <int, int> > pq;
vector <int> adj[N];
bool mark[N];
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
fill(dist, dist + n + 1, m);
while (m --){
int v, u;
cin >> v >> u;
adj[u].push_back(v);
++ d[v];
}
dist[n] = 0;
pq.push({0, n});
while (!pq.empty()){
int v = pq.top().second;
pq.pop();
if (mark[v])
continue;
mark[v] = true;
for (int u : adj[v]){
if (dist[v] + d[u] < dist[u]){
dist[u] = dist[v] + d[u];
pq.push({- dist[u], u});
}
-- d[u];
}
}
cout << dist[1] << '\n';
return 0;
}
1693D - Decinc Dividing
Idea: AmShZ
Solution 1
Tutorial is loading...
Thanks to Koosha_Mv
Solution 2
It can be proven that a permutation is Decinc if and only if it's $$$3412$$$-avoiding and $$$2143$$$-avoiding.
Implementation 1
# include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, a[N], dp[N], pd[N], f[N];
long long ans;
inline void upd(int i){
if (n < i)
return;
int inc = 0, dec = n + 1;
if (pd[i - 1] < a[i])
inc = max(inc, a[i - 1]);
if (a[i - 1] < a[i])
inc = max(inc, dp[i - 1]);
if (a[i] < dp[i - 1])
dec = min(dec, a[i - 1]);
if (a[i] < a[i - 1])
dec = min(dec, pd[i - 1]);
if (inc == dp[i] && dec == pd[i])
return;
dp[i] = inc, pd[i] = dec;
f[i] = 0;
if (dec <= n || inc){
upd(i + 1);
f[i] = f[i + 1] + 1;
}
return;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++ i)
cin >> a[i];
for (int i = n; 1 <= i; -- i){
dp[i] = n + 1;
pd[i] = 0;
upd(i + 1);
f[i] = f[i + 1] + 1;
ans += f[i];
}
cout << ans << '\n';
return 0;
}
Implementation 2
# include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, a[N], min_r[N], fen[N];
long long ans;
stack <int> sk;
vector <int> vec[2][N];
void mofen(int pos, int val){
for (pos += 5; pos < N; pos += pos & - pos)
fen[pos] = min(fen[pos], val);
}
int gefen(int pos){
int res = n + 1;
for (pos += 5; 0 < pos; pos -= pos & - pos)
res = min(res, fen[pos]);
return res;
}
void find_3412(){
fill(fen, fen + n + 10, n + 1);
while (!sk.empty())
sk.pop();
for (int i = 1; i <= n; ++ i){
while (!sk.empty() && a[i] < a[sk.top()])
sk.pop();
if (!sk.empty())
vec[0][sk.top()].push_back(i);
sk.push(i);
}
while (!sk.empty())
sk.pop();
for (int i = n; 1 <= i; -- i){
while (!sk.empty() && a[sk.top()] < a[i])
sk.pop();
if (!sk.empty())
vec[1][sk.top()].push_back(i);
sk.push(i);
}
for (int i = n; 1 <= i; -- i){
for (int ind : vec[0][i])
mofen(a[ind], ind);
for (int ind : vec[1][i])
min_r[ind] = min(min_r[ind], gefen(a[ind] - 1));
vec[0][i].clear(), vec[1][i].clear();
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++ i)
cin >> a[i];
fill(min_r, min_r + n + 2, n + 1);
find_3412();
for (int i = 1; i <= n; ++ i)
a[i] = n + 1 - a[i];
find_3412();
for (int i = n; 1 <= i; -- i){
min_r[i] = min(min_r[i], min_r[i + 1]);
ans += min_r[i] - i;
}
cout << ans << '\n';
return 0;
}
1693E - Outermost Maximums
Idea: Keshi
Solution
Tutorial is loading...
Implementation
//In the name of God
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll maxn = 2e5 + 100;
const ll mod = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
#define lc (id << 1)
#define rc (lc | 1)
ll pw(ll a, ll b){
ll c = 1;
while(b){
if(b & 1) c = c * a % mod;
a = a * a % mod;
b >>= 1;
}
return c;
}
struct cost{
int c[2][2];
cost(){
memset(c, 0, sizeof c);
}
};
cost cst[2][2];
int n, a[maxn], dp[maxn], cnl[maxn], cnr[maxn];
ll s, ans, ans2;
cost seg[maxn << 2];
inline cost mrg(cost l, cost r){
cost mid;
for(int i = 0; i < 2; i++){
for(int j = 0; j < 2; j++){
mid.c[i][j] = min(r.c[i][0] + l.c[0][j], r.c[i][1] + l.c[1][j]);
}
}
return mid;
}
void bld(int id, int s, int e){
if(e - s == 1){
seg[id] = cst[int(cnl[s] > 0)][int(cnr[s] > 0)];
return;
}
int mid = (s + e) >> 1;
bld(lc, s, mid);
bld(rc, mid, e);
seg[id] = mrg(seg[lc], seg[rc]);
return;
}
void upd(int id, int s, int e, int l, int r){
if(r <= s || e <= l) return;
if(l <= s && e <= r){
seg[id] = cst[int(cnl[s] > 0)][int(cnr[s] > 0)];
return;
}
int mid = (s + e) >> 1;
upd(lc, s, mid, l, r);
upd(rc, mid, e, l, r);
seg[id] = mrg(seg[lc], seg[rc]);
return;
}
cost get(int id, int s, int e, int l, int r){
if(r <= s || e <= l) return cost();
if(l <= s && e <= r) return seg[id];
int mid = (s + e) >> 1;
return mrg(get(lc, s, mid, l, r), get(rc, mid, e, l, r));
}
int main(){
fast_io;
srand(time(NULL));
cst[0][0].c[0][0] = cst[0][0].c[1][1] = 0;
cst[0][0].c[0][1] = cst[0][0].c[1][0] = inf;
cst[0][1].c[1][0] = cst[0][1].c[1][1] = 1;
cst[0][1].c[0][0] = 0;
cst[0][1].c[0][1] = inf;
cst[1][0].c[0][1] = cst[1][0].c[0][0] = 1;
cst[1][0].c[1][1] = 0;
cst[1][0].c[1][0] = inf;
cst[1][1].c[0][0] = cst[1][1].c[1][1] = 1;
cst[1][1].c[0][1] = cst[1][1].c[1][0] = 1;
cin >> n;
cnr[0] = cnl[0] = 1;
for(int i = 1; i <= n; i++){
cin >> a[i];
cnr[a[i]]++;
s += a[i];
}
bld(1, 0, n + 1);
for(int i = 1; i <= n; i++){
cost cs = get(1, 0, n + 1, 0, a[i]);
cnr[a[i]]--;
cnl[a[i]]++;
upd(1, 0, n + 1, a[i], a[i] + 1);
dp[i] = min({cs.c[0][0], cs.c[0][1], cs.c[1][0], cs.c[1][1]});
ans += dp[i];
}
cout << ans << "\n";
return 0;
}
Check out this solution by ecnerwala
1693F - I Might Be Wrong
Idea: AmShZ
Thanks to antontrygubO_o for proof
Solution
Tutorial is loading...
Implementation by Um_nik
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
#ifdef LOCAL
#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
#define eprintf(...) 42
#endif
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
clock_t startTime;
double getCurrentTime() {
return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
const int N = 200200;
int n;
char s[N];
int bal[N];
int pos[N];
void solve() {
scanf("%d %s", &n, s);
int b = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '0')
b++;
else
b--;
}
if (b < 0) {
for (int i = 0; i < n; i++)
s[i] ^= 1;
reverse(s, s + n);
b *= -1;
}
bal[0] = (n + b) / 2;
for (int i = 0; i < n; i++)
bal[i + 1] = bal[i] + (s[i] == '0' ? -1 : 1);
assert(bal[n] == (n - b) / 2);
for (int i = 0; i <= n; i++)
pos[i] = -1;
for (int i = 0; i <= n; i++)
pos[bal[i]] = i;
int ans = 0;
int l = 0;
while(l < (n + b) / 2) {
if (bal[l + 1] < bal[l]) {
l++;
continue;
}
if (bal[l] <= (n - b) / 2) {
ans++;
break;
}
int r = pos[bal[l]];
assert(r > l);
ans++;
for (int i = l + 1; i < r; i++) {
if (2 * i > l + r) {
bal[i] = bal[l] - (r - i);
} else {
bal[i] = bal[l] - (i - l);
}
pos[bal[i]] = max(pos[bal[i]], i);
}
}
printf("%d\n", ans);
}
int main()
{
startTime = clock();
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int t;
scanf("%d", &t);
while(t--) solve();
return 0;
}
Thanks to Um_nik
fastest editorial, epiq round, ORZ
I'm a simple man, I upvote this post
In the consequence, you get upvotes too. Hee...hee ..You're amazing and smart both :-)
You commented right under my comment. Hee...hee...you're amazing and smart both :-)
I'm simple man, I will just upvote you're comment right under my comment. :-D
.
Great, thoughtful problems. Good job.
Great job! Loved the problems, thank you!
Is there a proof for Div1C / Div2Е that all edges with min dis are equally beneficial ? I think it is not. In some case it's better to block a way with dis = min if we have another way with the same dis and less count of elements to block in future.
Note that, in the definition of "dis[u]", we are already including the cost of the edges we have to block to get from u to N. So all edges with the same minimum dis are equally beneficial.
why to decrease the degree of a node after visiting it. And why every one doing it in backwards. In the contest i did it from the front and didn't have any intuition on decreasing the degree and ended up getting wrong answer on pretest 16.
Maybe you can think the DAG solution first(aka invent subtask), then it is quite intutive to do it backward.
I agree with this but I don't get why dijkstra works.
What I wanted to do was to compute the SCC, compress the graph as a DAG and then iterate over the compressed top-sort to do the dp and in each SCC I should propagate the dp value all over the cycles by running the dp n times in each SCC. This will give some $$$O(n^2)$$$ algorithm.
I think the fact that makes dijkstra work is that each cycle will become "directed", like if we add an edge from each node to the node it gets the answer, there will be no cycles so propagating from the smallest value first should work I guess ?
Can anyone tell me if I'm correct or provide some better intuition of why it works please ?
First define $$$distance[v]$$$ be the minimum number of operation need to be done to reach vertex $$$n$$$, then every vertex have some non-negative distance.
Let consider for a vertex $$$v$$$, how do we find the $$$distance[v]$$$?
assume vertex $$$v$$$ can reach $$$v_1, v_2, v_3, ..., v_k$$$(sorted by distance in increasing order), then it is obvious that if you want to reach $$$v_i$$$, you need to block all vertex whose distance is greater than $$$v_i$$$, so you need to block $$$k - i$$$ edges to guarantee reaching $$$v_i$$$.
So you can think this as there has an edge whose weight is $$$k - i + 1$$$ from $$$v$$$ to $$$v_i$$$, then the problem can be reduced as a well-known problem: "Given a directed graph, all edge have some positive weight, find the minimum distance from $$$n$$$ to $$$1$$$", but with a little twist: "you won't know the weight of edges until you calculate it."
Thanks a lot ! That's super clear :D
But I saw this problem as follows "when ever u want to move forward in original graph(not in rev_graph) let's say from u-v , then you need to remove all the edges that are going from 'u' to some other node except all the multiple edges that are between u-v because we can use a random operation once to get there and I did it untill I reach node n without removing any edge. It seems intuitive to me but I saw this is not optimal why it is happening.here is the link to my solutionYour text to link here... . Here dp[i] stores min op to reach I from 0 and dp[n-1] is the ans.
you don't need to block edges that make you reach some vertex whose distance to $$$n$$$ is shorter than $$$v$$$, because reaching these vertex will only make the answer better.
Ohh, while moving forward if we know any forward edge has less dp val we use it first so while moving forward let's say if we go from u-v we have to know dp values of all 'v' nodes and their order based on dp values. That is reason why we do it from backwards, And we use dijkstra because it gives order of nodes 'v' based on lower dp values, And the reason to remove edges was to, while moving from lesser dp values to higher of all 'v' nodes we don't consider previous edges in this operation because it gives min ans.you( __Shioko ) explained that it in very nicely with one simple observation very very thankful to you. I explained it elaborately because someone having similar idea like me and struggling to understand probably would get some help.
multiple edges,and you can't use set to delete it.
Could you please elaborate with an example. I still don't get idea of why removing edges benefits us.
in the sample input 2 , if you try to expand from node 4 you will first go to node 1 with dist 3 .and you decrease the degree of node 1, then you can go to node 1 in another edge from 4 to 1 with dist 2.
Thanks to your efforts, I understood my errors and explained my wrong thought process and explained how to correct it, to get it accepted in my comment above this one.
woah! thanks for super-fast tutorial!
I originally posted this under the round announcement but perhaps it's better to post it here:
Thanks for this great div2 round !
I think the difficulty curve was a bit messy BUT the problems were interesting
Here is my feedback on each of the problems because I think it can be valuable to authors to know what people thought about the problems
Good problem A, not an a+b problem but not an impossible problem either.
I had the right observation instantly (that there is some sort of "eating" relation that is directed from right to left but I spent a lot of time to actually see that it worked. The problem was great but it could have been better as a div2 C (I think the C was better as B) ? Anyway, I liked B a lot, very cute observation
The samples kinda spoil the problem (the explanations on how to get the 2 -1...sequence shows that you can do everything with "left/right" moves and then it's just about simulating the process). That's why I think it would have been a better problem as div2 B. Still a nice problem though (but not as good as the others).
The problem is really interesting and educative but it's perhaps a bit too easy as a div2 D. I think it would fit nicely as div2 C or edu D (but my advice might be completely fucked up).
I didn't success in making my DP work for cycles (I had some O(N^2) by splitting in strongly connected components though). Some people said that using dijkstra to do "implicit topsort" or whatever it's called is standard but I never saw this after solving a lot of standard problems (including some more OI style problems)...In my opinion, it's a beautiful problem showing an interesting trick, congrats to the authors!!
Can someone explain the last statement in Div2B solution to me in simpler worda? Im unable to understand why we should add r-1 to the answer
Let's introduce the "eating" idea
01 -> 1, that means 1 can eat 0 (the 1 is kinda "eating" the 0 to its left)
10 -> 0, that means 0 can eat 1 (the 0 is kinda "eating" the 1 to its left)
Say you consider the blocks of consecutive same numbers
[0...0][1...1][0...0][1...1]
Each block can eat the block right to its left. This way, only the last block will survive at the end of the process. So we need the last block to be of size 1
What they say in the editorial is that they fix the right border of the substring (call it $$$r$$$), now if the char is the first of its block, all the substrings having their left border to the left of $$$l$$$ will be paranoid (because of what I explained earlier) and there are $$$r - 1$$$ such left border (we do $$$-1$$$ because we don't want to consider the case $$$l = r$$$ as we handle it separately by adding $$$n$$$ to the answer).
For example if you fix $$$r$$$ to be 3, the left border can be $$$1$$$ or $$$2$$$ so you have $$$3 - 1 = 2$$$ ways of choosing it.
I tried this 'eating' approach (160867965). While I don't understand it completely, it seemed to work with the testcases in the problem and few others that I made. It failed the longest testcase so I'm assuming it's overflowing? I tried to find small counterexamples on cfstress but it didn't help. Could you kindly tell me if my approach is correct or not?
does not prevent overflows.
it gets AC by using long long everywhere 160900072
If you have any question about things that aren't clear don't mind to ask me
Can you give some problems that uses this eating concept
Hey! I think that's not some general concept, the key idea is just to try to get familiar with the operations described and to see them in some intuitive way.
I suggest you to read this amazing blog by Everule. I solved the 2nd problem of the blog using that kind of intuition.
Really nice explanation. I was not able to understand the solution when I read the editorial but after reading your comment I completely understood the approach. Thanks
If it ends on different numbers, then it works. So, all substrings starting from $$$i=1$$$ to $$$r-1$$$ and ending in $$$r$$$ need to be counted, and we add the $$$r-1$$$ options to $$$ans$$$.
Loved this round!
Here's my solution for div1E (could be the same, but the interpretation seems different). Consider numbers by increasing, suppose we have considered all numbers up to $$$x$$$ (all the rest are $$$0$$$ for now). Suppose we now place $$$a_i = x + 1$$$ at an empty position. We define $$$L_i$$$ and $$$R_i$$$ as the smallest number of operations to get $$$a_i$$$ to zero if we start with the left/right relaxation respectively. At this stage we can consider all $$$i$$$ such that $$$a_i$$$ is actually $$$x + 1$$$, and add $$$\min(L_i, R_i)$$$ to the answer. Note that initially $$$L_i = R_i = 1$$$.
How do $$$L_i$$$ and $$$R_i$$$ change when going $$$x \to x + 1$$$? If there are no $$$x + 1$$$'s, we do nothing. Otherwise, for a position $$$i$$$:
These updates can be done via a segment tree with lazy $$$(\min, +)$$$ matrix multiplication.
I couldn't prove the complexity of my accepted solution for div 1D, which seems to be quite different from the official implementations. (Editorial for the task still not out as i write this)
What I did:
First, note that if $$$(x,y)$$$ is a valid pair, then all $$$(a,b)$$$ such that $$$x \le a \le b \le y$$$ are valid, as you can simply remove prefixes and suffixes from the increasing/decreasing subsequences.
Next, we can find the largest $$$y$$$ such that $$$(x,y)$$$ is valid for some $$$x$$$ in $$$\mathcal O(n)$$$ using this. We also note that we can do the same in reverse (i.e. find the smallest $$$x$$$ such that $$$(x,y)$$$ is valid for some $$$y$$$, by simply flipping increasing and decreasing).
Now, we first let $$$x_0 = 1$$$, and find the corresponding maximum $$$y_0$$$. Then we do the reverse starting on $$$y_0+1$$$ and find the least $$$x_1$$$ such that $$$(x_1,y_0+1)$$$ is a valid pair. Note that here $$$x_1 > x_0$$$ must hold as $$$(x_0, y_0+1)$$$ is not valid. Then we just repeat this process, each time finding maximum $$$y_i$$$ for $$$x_i$$$, then finding minimum $$$x_{i+1}$$$ for $$$y_i+1$$$. Do this until $$$y_k=n$$$ eventually and we can simply add up the answer using a loop.
This solution looks like $$$\mathcal O(n^2)$$$ and I could neither prove a better complexity nor come up with any construction that leads to TLE, I wonder if anyone can help think of one (proof or counterexample), thanks a lot :D
160875853 (Ignore the few lines of template)
I can't prove it very formally.But I have an idea. Assume every time the y become to y + 1, the average mount of x you should calculate is p, such that the answer would be about p*(n-p)*(p+1)*p/2, and this number is less than the situation which all of the array is a Dicinc array, that would have n * (n + 1)/ 2 subarrays. Then it is very easy to find that p would not bigger than n^(1/3), and your algorithm's complexity would be like O(n^(4/3)).I think it is very fast.
Could you explain more on “the answer would be about p*(n-p)*p*(p+1)/2”? Thanks a lot.
What I had wrote is wrong here, and I should removed it but I can't. Sorry for that. The value I shoudl write is (n — p) *(p (p + 1)) / 2, which means you should calculate a p length array for (n — p) times ,and the mount of subarrays of every array is p * (p + 1) / 2.
When we try to generate the Decinc decomposition of an array going left-to-right (or backwards), it is enough to store the following values from the previous position: the minimum possible last value of the $$$inc$$$ if the previous element was placed in the $$$dec$$$, and the maximum possible last value of the $$$dec$$$ if the previous element was placed in the $$$inc$$$ ($$$0$$$/$$$\inf$$$ in cases where the other sequence wasn't started yet, $$$\inf$$$/$$$0$$$ if the previous element couldn't be placed in that sequence). my implementation of this approach
Let's look at some three consecutive elements such that $$$a < b > c$$$ and at the state of calculating the decomposition left-to-right after $$$c$$$. If $$$c$$$ is in the $$$dec$$$, then the minimum possible last value of the $$$inc$$$ is either $$$a$$$ or $$$b$$$ or $$$\inf$$$ (since it's impossible to place both of them in the $$$dec$$$ and have $$$inc$$$ ending in some different value). If $$$c$$$ is in the $$$inc$$$, then the maximum possible last value of the $$$dec$$$ is either $$$b$$$ or $$$0$$$. So there is a limited number of possible states giving full information on the decomposition up to $$$c$$$ — $$$6$$$, actually less. So there are $$$O(1)$$$ possible right ends for the maximal Decinc segments enclosing $$$a$$$, $$$b$$$, $$$c$$$. Similarly for $$$a > b < c$$$. But when we extend a maximal segment to the right by $$$1$$$, the new maximal segment gets a new such chainsaw point (otherwise it's trivial to show that the previous segment wasn't maximal to the right), which will be traversed $$$O(1)$$$ times before going out of scope of another maximal segment. Hence the solution works in $$$O(n)$$$.
1693A — Directional Increase
I think in the second condition bj==0 should be there instead of bj!=0.
Thanks!
I ACed problem D at $$$01:59:45$$$ . The adrenaline rush was real, I have never felt the the flow of time like today, I could feel every second ticking inside my mind near the end. Thank you for this round.
160885850
Alternate (I think) solution for 1D briefly:
An array is decinc if there is some $$$(k, x)$$$ such that when you split the array into quadrants based on whether $$$j \leq k$$$ and on whether $$$p_j \leq x$$$, then the quadrant with $$$j \leq k$$$ and $$$p_j \leq x$$$ and the quadrant with $$$j > k$$$ and $$$p_j > x$$$ is increasing, and the other two quadrants are decreasing.
For a fixed $$$k$$$, we can see that there are basically three choices of $$$x$$$ we need to consider: two where $$$p_k$$$ and $$$p_{k + 1}$$$ are on the same side of $$$\leq x$$$, and one where they're on the different side.
The value from this approach is that for a certain $$$(k, x)$$$, the furthest to the left of $$$k$$$ you can go is independent from the furthest to the right of $$$k$$$ you can go. So for each $$$(k, x)$$$, we want to calculate these furthest left and right endpoints based on the increasing/decreasing constraints.
I did this by maintaining binary search trees containing points where the increasing/decreasing constraints are violated for each of the halves $$$\leq x$$$ and $$$> x$$$, moving $$$x$$$ from $$$0$$$ to $$$n$$$. Unfortunately this part had very high constant factor and TLEd in Kotlin. My C++ solution ran in about 1 second.
After finding the furthest to the left and right you can get from each $$$(k, x)$$$, we can simply calculate for each left endpoint what the farthest right endpoint we can get is using a linear scan. The overall complexity is $$$O(n\lg n)$$$ (with high constant factor).
Div 1 A ~ D are good problems compared to some previous rounds, really satisfied with solving them!
Is your comment related to your rating changing?
Can you explain Div2E in a bit more detail? I don't understand why always choosing the maximum dis_n is correct. It seems possible that dis_n can be updated later by dis_{n'}, where dis_{n'} < dis_{n}.
Is it crucial that all edges are length 1? If the edges are not length 1, would a dijstra-like solution still work?
[update: For the first part I misunderstood the use of priority_queue. For the second part I think the answer is yes, but am interested in solving this variation.]
There seems to be a simple solution: split each edge (u,v,w) (where w is the length) into two segments by introducing an extra vertex y, so that (u,v,w) -> (u,y,0) and (y,v,w). We can run the same dijkstra on this new graph. But since each y has out degree 1, the update for these are trivial. By doing this, it is guaranteed that y will be considered in increasing order of dis_y.
If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.
Divison 2
Divison 1
If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).
Great job! Loved the problems, thank you!
Is this contest unrated?
Just wait. If it was, they would announce it.
Can anyone explain div2D/div1B?
I solved it but I couldn't get Lemma 1 in editorial...
Let's look at example:
I.e. we have a root with two children. Children are required to be in range (1, 1) and the root in range (2, 2).
The minimum number of operations is 2:
Increase by 1 values at vertexes 1 and 2
Increase by 1 values at vertexes 1 and 3
It looks to me that for optimum solution value at root should be increased twice. So it seems to me the Lemma 1 is not hold.
It would be great to get clarification.
I think it means that each node will only be the end of a single path (but may be in the middle of multiple paths)
The way I solved it was to realise that every leaf node will have a single path back to the root and each of those paths would start by returning leafenode.r. Any nodes in the middle of the path will return as much as possible (node.v = min(node.r, sum(node.children.v))) towards the root. If sum(node.children.v) is less than node.l then we need to add an extra path from the root to that node and return node.r towards the root.
Great problems! Credits to authors
In div1 C I don't get why you can't do dijkstra starting from node 1? I am getting WA on testcase 16 when doing it. It seems also that most people have solved it staring from n..
Consider the following test:
The answer is 2, by using the move operation two times, but your code outputs 3.
I see. Thanks!
Could you plz explain why starting from 1 will get WA, while starting from n can find out the correct answer? I didn't get that :(
Actually, I made some testcases that can hack my program(starting from 1). But I don't know why it can be correct to start from n.
Can someone explain the proof of the claim "It's trivial that we only sort with segments with balance 0" in the editorial of Div1 F? This does not seem trivial to me. Apologies if I am missing something very simple.
proof of this: suppose that 0s are more than 1s. if the first character of the interval is 0, delete it, otherwise we have a prefix with equal 0s and 1s, and after performing a operation on it, the first character will be 0, and we can delete it. so we can reach our goal by operations with equal numbers 0 and 1.
I understand now, thank you! By the way, I think this is definitely a nontrivial (and interesting) proof. Maybe you should consider adding this to the editorial?
Yes, it's better to add.
It seems the construction is also the final solution
I believe you mean 2143-avoiding permutations for D problem, not 2134
You are right. Will be fixed.
In div1 C $$$\newline$$$ Why bottom up dp on dfs doesn't work 160881231
Take a look at Ticket 12523 or Ticket 12520 from CF Stress for a counter example.
Thanks found my mistake. $$$\newline$$$ What i was doing was applying dp on dfs of directed graphs which is nothing more than dp on the topological sort of the directed graphs. Since topological sort does not exist on directed graphs with cycles hence we can't apply this. Dijkstra is the only option left.
Could you please explain why dijkstra works here ? I don't clearly see why it would work and the editorial doesn't seem to explain it.
At each step keshi would choose worst possible road, so optimal solution should be keeping minimum distance roads and blocking the rest, as stated in the editorial. $$$\newline$$$ So let's look from the perspective of the cities to which keshi will reach, any particular cities will be chosen only if it's distance is minimum compared to other cities. $$$\newline$$$ So we essentially want to sort them according to their distance, which is exactly what dijsktra does. $$$\newline$$$ Instead of 1 as source node, n can be taken as source node and dijsktra can be used to search for shortest path to 1st node.
Can I get more explanation about find_3412?
an $$$O(n\log n)$$$ approach:
for each $$$l$$$ , find maximum $$$r$$$ within $$$[l, r]$$$ is decinc using two-pointers
for 3412 case, if $$$[l, r - 1]$$$ is already decinc, then the situation of $$$[l, r]$$$ only depends on whether it's possible to find a 3412-tuple which the 2-element corresponds to $$$a_r$$$
suppose $$$f_r$$$ represents the largest index $$$i < r$$$ which $$$a_i < a_r$$$ ，it's optimal to choose $$$a_{f_r}$$$ as the 1-element
suppose the 3-element is fixed with some element $$$a_k$$$, then it's optimal to choose $$$a_{g_k}$$$ as the 4-element where $$$g_k$$$ represents the smallest index $$$i > k$$$ which $$$a_i > a_k$$$
if in the range $$$[l, r]$$$ there exists some element $$$a_k > a_r$$$ and $$$g_k < f_r$$$ ，then $$$[l, r]$$$ is not decinc since $$$a_k, a_{g_k}, a_{f_r}, a_r$$$ form a 3412-tuple
to check the existence of $$$a_k$$$ ，for each $$$a_k$$$ we put a pair $$$(a_k, g_k)$$$ into a sequence , sort all the pairs by $$$a_k$$$ increasing and check whether the minimum $$$g_k$$$ among a suffix of the pair sequence is smaller than $$$f_r$$$
arrays $$$f$$$ and $$$g$$$ could be pre-computed
during the tow-pointers process ， using some data structures like segment trees to maintain the sorted sequence to support insertion/deletion of elements while moving pointer $$$[l, r]$$$
Thanks, this is my understanding: 161348650
Here is a solution to E that only involves binary indexed tree/order statistic set (insert-value and range-count).
As the editorial states, we can greedily move each maximum to the smaller of the max on the left and the max on the right. Let's simulate this process efficiently. We'll go from highest values downwards. Note that, at a single current max value, there may be several different values that our maxes get set to, so we can't naively simulate this process. Instead, we'll instead just mark all current values as "to set to smaller of left-max or right-max".
Then, as we continue processing, when we process a current value which occurs to the right of something marked as "to set to smaller of left-max or right-max", we change the mark to "to set to left-max" (and likewise on the left side). If we process a current value which occurs to the left of something marked as "to set to left-max", then, we must set it to exactly the current value; then, we can add it to the cost and treat it as "to set to smaller of left-max or right-max".
At any point in this process, the "active" elements (ones with marks) are just all elements bigger than the current value. Also, we can verify that the elements marked "to set to left-max" are a prefix, and the elements marked "to set to right-max" are a suffix. Thus, we can just maintain the cutoff indices between our three types of marked elements, and use a BIT/order statistic set to count how many "active" nodes need to move.
This solves the whole problem in $$$O(n \log n)$$$ with very little code. 160890042
Got Stuck in 'B' after a long time. The problems were great!✔️
div1D можно решать двумя указателями. Если отрезок [l, r] хороший, то [l + 1, r] и [l; r — 1] тоже. Будем поддерживать up/down подпоследовательности возрастания и убывания соответственно в set(pair(int, int)), где пары внутри равны (i, p[i]). Когда смогли найти правый r для заданного l, то добавим r — l + 1 к ответу. Чтобы поддерживать эти два сета надо посмотреть, сильно ли они меняются при добавлении нового элемента. Мы не можем взять 2 элемента из одного множества и вставить в другое, потому что нарушим относительный порядок, а значит только один элемент можем перекинуть, и возможно еще один из другого. Если хотим перекинуть из up в down, то возможно в down будет несколько элементов слева, которые меньше, их нужно перекинуть в up (их может быть не более одного по предыдущему) (down->up аналогично). Если мы можем дополнить хотя бы в один сет сразу, то сделаем и продолжим. Иначе мы обязаны взять самый правый элемент из какого-то сета и перекинуть (иначе все еще не сможем вставить). Реализовать можно просто перебором всех элементов и все вставки, а это 2^4 вариантов по 4 вставки/удаления(при откате) (<= 2 элемента при up->down, <= 2 элемента при down->up). Итого NlogN
Why are we using dijkstra in Div2E. can anyone please give point by point explanation for div2E.
The proof idea of div1D/div2F solution2:
It's trivial that if an array is Decinc, it must be $$$3412$$$-avoiding and $$$2143$$$-avoiding.
To prove the other side, we can use strong induction on the number that the array has by considering the biggest element in the array.
Isn't it Div1D?
Thanks, it's correct now.
Interesting 1C and 1D,tks.
For 1963C,I try to use an algorithm we called SPFA to solve it.SPFA can be so slow and what i have written cound be much slower.But unexpectedly,it was accepted.MAybe the data should be much stronger.Looking forward to a hack or a proof of its correctness.
See my submission here! 160873008
Div2E is kinda awesome. I really liked this problem.
Why are we using dijkstra in Div2E. can u please give point by point explanation for div2E.
Let $$$dist(u)$$$ be the minimum operations needed to reach node $$$n$$$. Obviously, $$$dist(n)=0$$$ (As in editional). Now consider we want to go node $$$n$$$ from $$$u$$$ via some adjacent node $$$v$$$, then we have to block every edge which leads to the node $$$w$$$ whose distance value is larger than that of $$$v$$$, i.e. $$$dist(w)>dist(v)$$$. In this case, the number of operations needed to reach node $$$n$$$ from $$$u$$$ is $$$dist(v)+f_u(v)+1$$$ where $$$f_u(v)$$$ is the number of adjacent edges which leads to nodes whose distance value larger than that of $$$v$$$. Additional plus one is the cost of going through the edge. Considering every adjacent node of $$$u$$$, we can derive the formula:
If we think the term $f_u(v)$ as weight of edge passing through $$$u$$$ to $$$v$$$, we can reduce the problem to find single source shortest path in the weighted reversed digraph $$$G$$$ but the weights are unknown (but fixed). So we can use the dijkstra algorithm. But how do we know the shortest path length when we don't know the weight of edges until we actually investigate them? Actually, we know in the action of the algorithm. Suppose we are at the $$$i$$$th iteration of the dijkstra algorithm and we already know the distance values of marked nodes. Suppose we picked some unmarked node $$$v$$$. Of course we know that $$$dist(v)$$$ is minimum among unmarked nodes. Now we want to efficiently calculate contributions of $$$dist(v)$$$ to the nodes adjacent to $$$v$$$ (Note that we are considering reversed digraph). But how do we know the value of $$$f_u(v)$$$ for each adjacent nodes of $$$v$$$? If we maintain for each node $$$u$$$ how many edges are there which leads to the unmarked node so far (let us call them $$$d_{+}(u)$$$), we can easily calculate the value of $$$f_u(v)$$$ because it is just equal to $$$d_{+}(u)$$$. Why this is true is that every node we marked so far obviously has smaller distance value than $$$dist(v)$$$ and every unmarked node we will mark in next iterations can never have distance value less than $$$dist(v)$$$. Thus, all we have to do is maintain $$$d_{+}(u)$$$ and decrease by one if we investigate it in relaxation step. (Sorry my English is poor so it can be very hard to read 0_0)
Can someone please suggest a simpler solution to div1B or the solution in the editorial is the simplest one? I didn't get why a 1k7-rated problem could be such hard, or maybe it requires using some popular ideas that I haven't known yet. Tysm
shouldn't be ...?
Let $$$i$$$ be the smallest such that numbers from a_i to $$$a_n$$$ increase.
Thanks!
Is there any way to solve Div2 E with SCC, (after compressing graph with strongly connected component)
In Div2 E, why to decrease the degree of a node after visiting it??
This is problem C.Can anyone tell me which test case is failing
include<bits/stdc++.h>
define ll long long
define ld long double
using namespace std; /* " I AM VENGEANCE , I AM THE NIGHT , I AM THE BATMAN ! " ____ __ __ __ __ __ ___ _ __ __ __ __ __ ____
-._: .:'::: .:\ |__/| /:: .:'::: .:.-' \ : \ |: | / : / \ :: .-_____/ :: _______-' . :: . / | : :: ::' : :: ::' : :: ::' :: ::' : :: :| | ;:: ;:: ;:: ;:: ;:: | | .:'::: .:'::: .:'::: .:'::: .:':| / : : : : : \ /______::_____ :: . :: . :: _____._::____\----._:: ::' : :: ::' _.----'--. ;:: .--'-. .:' .-' \ / \ / \/ */ //Number to string-->string s=to_string(a); //String to number-->ll a=atoi(s.c_str());//3D vector of dimension 2*2*3 with all elements as 1 // vector<vector<vector > > vect3d(2, vector<vector > (2,vector(3,1)));
//Binary Search for desired position
// int BinSearch(ll *arr,int n,ll k){ // int beg=0; // int end=n-1; // int mid; // while(beg<=end){ // mid=beg+(end-beg)/2; // if(arr[mid]==k){ // return mid; // } // else if(arr[mid]>k){ // end=mid-1; // } // else{ // beg=mid+1; // } // } // return -1; // }
//Binary Search for index of first occurance of k
// int BinSearch(ll *arr,int n,ll k){ // int beg=0; // int end=n-1; // int mid; // while(beg<=end){ // mid=beg+(end-beg)/2; // if(arr[mid]==k && (mid==0||arr[mid-1]!=k)){ // return mid; // } // else if(arr[mid]>=k){ // end=mid-1; // } // else{ // beg=mid+1; // } // } // return -1; // }
//Binary Search for index of last occurance of k
// int BinSearch(ll *arr,int n,ll k){ // int beg=0; // int end=n-1; // int mid; // while(beg<=end){ // mid=beg+(end-beg)/2; // if(arr[mid]==k && (mid==n-1||arr[mid+1]!=k)){ // return mid; // } // else if(arr[mid]>=k){ // end=mid-1; // } // else{ // beg=mid+1; // } // } // return -1; // }
// bool comp(pair<ll,ll>p1,pair<ll,ll>p2){ // if(p1.first<p2.first){ // return true; // } // if(p1.first==p2.first){ // if(p1.second<p2.second){ // return true; // } // } // return false; // }
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll t; cin>>t; while(t--){ ll n; cin>>n; ll sum=0; ll arr[200003]; for(int i=0;i<n;i++){ cin>>arr[i]; sum=sum+arr[i]; } if(sum!=0){ cout<<"No"<<endl; continue; } if(arr[0]<0){ cout<<"No"<<endl; continue; } ll point=n; //Do check if all are zeros or not(Boundry Condition) bool snake=false; for(int i=0;i<n;i++){ if(arr[i]!=0){ snake=true; } } if(!snake){ cout<<"Yes"<<endl; continue; } for(ll i=n-1;i>=0;i--){ if(arr[i]!=0){ point=i; break; } } for(ll i=1;i<=point;i++ ){ arr[i]=arr[i]+1; } bool poke=true; ll c=-arr[0]+2;
for(ll i=1;i<point;i++){ if(arr[i]<c){ poke=false;
} else{ c=-(arr[i]-c)+1;
} }
if(poke){ cout<<"Yes"<<endl; } else{ cout<<"No"<<endl; } } }
Can't read this. Can you post it better in the form of a donut?
In 1694B-Paranoid string why should we add i when s[i]!=s[i-1]?