Codeforces Round #756 (Div. 3) Разбор

№	Пользователь	Рейтинг
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	162
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	147
9	orz	146
10	pajenegod	145

Разбор

Решение

#include<bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while(t--) {
        string n;
        cin >> n;
        if((n.back() - '0') % 2 == 0) {
            cout << "0\n";
            continue;
        }
        if((n[0] - '0') % 2 == 0) {
            cout << "1\n";
            continue;
        }
        int count_2 = count(n.begin(), n.end(), '2');
        int count_4 = count(n.begin(), n.end(), '4');
        int count_6 = count(n.begin(), n.end(), '6');
        int count_8 = count(n.begin(), n.end(), '8');
        if(count_2 > 0 || count_4 > 0 || count_6 > 0 || count_8 > 0) {
            cout << "2\n";
            continue;
        }
        cout << "-1\n";
    }
    return 0;
}

1611B - Team Composition: Programmers and Mathematicians

Идея: MikeMirzayanov

Разбор

Решение

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
void solve() {
    ll a, b;
    cin >> a >> b;
    cout << min(min(a, b), (a + b) / 4) << '\n';
}
 
int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }
    return 0;
}

1611C - Polycarp Recovers the Permutation

Идея: MikeMirzayanov

Разбор

Решение

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        int n;
        cin >> n;
        vector<int> a(n);
        forn(i, n)
            cin >> a[i];
        if (a[0] != n && a[n - 1] != n)
            cout << -1 << endl;
        else {
            for (int i = n - 1; i >= 0; i--)
                cout << a[i] << " ";
            cout << endl;
        }
    }
}

1611D - Weights Assignment For Tree Edges

Идея: MikeMirzayanov

Разбор

Решение

#include <bits/stdc++.h>
 
using namespace std;
 
void solve(){
    int n;
    cin >> n;
    vector<int> b(n + 1), p(n + 1), dist(n + 1, -1);
 
    for(int i = 1; i <= n; i++)
        cin >> b[i];
    for(int i = 1; i <= n; i++)
        cin >> p[i];
 
    if (b[p[1]] != p[1]){
        cout << -1 << '\n';
        return;
    }
 
    dist[p[1]] = 0;
    for(int i = 2; i <= n; i++){
        if(dist[b[p[i]]] == -1){
            cout << -1 << '\n';
            return;
        }
        dist[p[i]] = dist[p[i - 1]] + 1;
    }
 
    for(int i = 1; i <= n; i++) {
        cout << dist[i] - dist[b[i]] << ' ';
    }
    cout << '\n';
}
 
int main() {
    int t;
    cin >> t;
    while(t-- > 0) {
        solve();
    }
}

1611E1 - Escape The Maze (easy version)

Идея: Vladosiya

Разбор

Решение

//
// Created by Vlad on 16.11.2021.
//
 
#include <bits/stdc++.h>
 
#define int long long
#define mp make_pair
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
 
typedef long double ld;
typedef long long ll;
 
using namespace std;
 
mt19937 rnd(143);
 
const int inf = 1e10;
const int M = 998244353;
const ld pi = atan2(0, -1);
const ld eps = 1e-4;
 
void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> color(n, -1);
    deque<int> q;
    for(int i = 0; i < k; ++i){
        int x;
        cin >> x;
        color[--x] = 0;
        q.push_back(x);
    }
    color[0] = 1;
    q.push_back(0);
    vector<vector<int>> g(n);
    for(int i = 0; i < n - 1; ++i){
        int u, v;
        cin >> u >> v;
        g[--u].push_back(--v);
        g[v].push_back(u);
    }
    while(!q.empty()){
        int v = q.front();
        q.pop_front();
        for(int u: g[v]){
            if(color[u] == -1){
                color[u] = color[v];
                q.push_back(u);
            }
        }
    }
    for(int v = 1; v < n; ++v){
        if(g[v].size() == 1 && color[v] == 1){
            cout << "YES";
            return;
        }
    }
    cout << "NO";
}
 
bool multi = true;
 
signed main() {
    int t = 1;
    if (multi) {
        cin >> t;
    }
    for (; t != 0; --t) {
        solve();
        cout << "\n";
    }
    return 0;
}

1611E2 - Escape The Maze (hard version)

Идея: Vladosiya

Разбор

Решение

#include <bits/stdc++.h>
 
#define int long long
#define mp make_pair
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
 
/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")
*/
typedef long double ld;
typedef long long ll;
 
using namespace std;
 
mt19937 rnd(143);
 
const int inf = 1e10;
const int M = 998244353;
const ld pi = atan2(0, -1);
const ld eps = 1e-4;
 
vector<vector<int>> sl;
vector<int> nearest;
 
int count(int v, int dist, int p = -1){
    bool children = true;
    int s = 0;
    for(int u: sl[v]){
        if(u == p) continue;
        int c = count(u, dist + 1, v);
        if(c < 0) children = false;
        nearest[v] = min(nearest[v], nearest[u] + 1);
        s += c;
    }
    if(nearest[v] <= dist) return 1;
    if(s == 0 || !children) return -1;
    return s;
}
 
void solve() {
    int n, k;
    cin >> n >> k;
    sl.assign(n, vector<int>(0));
    nearest.assign(n, n);
    for(int i = 0; i < k; ++i){
        int x;
        cin >> x;
        --x;
        nearest[x] = 0;
    }
    for(int i = 1; i  < n; ++i){
        int u, v;
        cin >> u >> v;
        --u, --v;
        sl[u].emplace_back(v);
        sl[v].emplace_back(u);
    }
    cout << count(0, 0);
}
 
bool multi = true;
 
signed main() {
    //freopen("in.txt", "r", stdin);
    //freopen("in.txt", "w", stdout);
    /*ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);*/
    int t = 1;
    if (multi) {
        cin >> t;
    }
    for (; t != 0; --t) {
        solve();
        cout << "\n";
    }
    return 0;
}

1611F - ATM and Students

Идея: Gol_D, MikeMirzayanov

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define forn(i, n) for (int i = 0; i < int(n); i++)

vector<ll> t, a;
ll s, tl;

const ll MAX = 1'000'000'000'000'000LL;

void build(int v, int l, int r) {
	if (l == r)
		t[v] = a[l];
	else {
		int m = (l + r) / 2;
		build (v * 2, l, m);
		build (v * 2 + 1, m + 1, r);
		t[v] = min(t[v * 2], t[v * 2 + 1]);
	}
}

void update(int v, int l, int r) {
	if (l == r)
		t[v] = MAX;
	else {
		int m = (l + r) / 2;
		if (tl <= m)
			update(v * 2, l, m);
		else
			update(v * 2 + 1, m + 1, r);
		t[v] = min(t[v * 2], t[v * 2 + 1]);
	}
}

int lower_bound_s(int v, int l, int r) {
	if (r < tl || (l == r && s < -t[v])) {
		return -1;
	}
    if (l == r || -t[v] <= s) {
        return r;
    }
	int m = (l + r) / 2;

	if (m < tl) {
        return lower_bound_s(2 * v + 1, m + 1, r);
	}
	if (s < -t[2 * v]) {
        return lower_bound_s(2 * v, l, m);
	}
	int res = lower_bound_s(2 * v + 1, m + 1, r);
	return (res == -1) ? m : res;
}


int main() {
    int tests;
    cin >> tests;
    forn(tt, tests) {
        int n;
        cin >> n >> s;
        t = vector<ll>(4 * n);
        a = vector<ll>(n);
        forn(i, n) {
            cin >> a[i];
        }
        for (int i = 1; i < n; ++i) {
            a[i] += a[i - 1];
        }
        build(1, 0, n - 1);
        int first = -1, second = -2;
        for (tl = 0; tl < n; ++tl) {
            int v = lower_bound_s(1, 0, n - 1);
            if (v != -1 && v - tl > second - first) {
                first = tl + 1;
                second = v + 1;
            }
            s -= a[tl];
            if (tl != 0) s += a[tl - 1];
            update(1, 0, n - 1);
        }
        if (first == -1) {
            cout << -1;
        } else {
            cout << first << " " << second;
        }
        cout << endl;
    }
}

1611G - Robot and Candies

Идея: MikeMirzayanov

Разбор

Решение

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define sz(v) (int)v.size()
 
const int N = 1e6 + 50;
string a[N];
 
int n,m;
int ans;
 
void solve(int sum0) {
    vector<int> v;
    for (int sum = sum0, ad = 0, pref = 0; sum < n + m; sum += 2, ad++) {
        vector<int> cur;
        int li = max(0, sum - m + 1), ri = min(n - 1, sum);
        if (li > ri) continue;
 
        for (int i = li; i <= ri; i++) {
            int j = sum - i;
 
            if (a[i][j] == '1')
                cur.emplace_back(i);
        }
 
        while (pref != sz(v) && v[pref] + ad > ri) {
            pref++;
        }
        for (int i = pref; i < sz(v); i++) {
            int new_val = v[i];
            while (!cur.empty() && cur.back() - ad >= v[i]) {
                new_val = max(new_val, cur.back() - ad);
                cur.pop_back();
            }
            v[i] = new_val;
        }
        if (!cur.empty()) {
            v.emplace_back(cur.back() - ad);
            ans++;
        }
    }
}
 
int main() {
    int t;
    cin >> t;
 
    forn(tt, t) {
        cin >> n >> m;
 
        forn(i, n) {
            string s; 
            cin >> a[i];
        }
 
        ans = 0;
        solve(0);
        solve(1);
        
        cout << ans << '\n';
    }
}

Комментарии (50)

Показать архивные | Написать комментарий?

Gol_D

2 года назад, # |

Автокомментарий: текст был обновлен пользователем Gol_D (предыдущая версия, новая версия, сравнить).

→ Ответить

By the way, in F many of you have written a two-pointer solution and I liked it. If anyone wants to write a proof, please.

mon0pole

2 года назад, # ^ |

← Rev. 4 →

Correct me if I am wrong

Proof

The problem is similar to problems where size of sliding window changes depending on some condition
Here the condition is we should always have enough money to perform next transaction.
In this explanation assume that we are always maintaining a $$$sum$$$ variable for the current amount of money in the ATM (initially $$$s$$$) and here $$$l$$$ signifies left pointer (initially 0) and $$$r$$$ right pointer (initially 0)
There are four changes possible

Change 1

Change 2

Change 3

Change 4

0-based indexing
Lets suppose we start from $$$0$$$ and we are able to perform all transactions upto $$$i$$$
Now obviously, the transaction at point $$$i+1$$$ has to be of withdrawal as we are always able to perform credit operation.
So , at $$$i+1$$$ we are unable to provide the required amount as ATM doesn't have that much
So we will rollback our previous operation upto a smallest (nearer to 0) point where we have enough money to perform the given operation
Now the $$$0th$$$ operation can be

1) Withdrawal

2) Credit

So if we are unable to have enough amount of money even if we rollback all previous operations then our left pointer will be $$$i+2$$$
Otherwise we will increment the right pointer by $$$1$$$.
So we can just keep doing this until the right pointer reaches the end of array and while extending our right pointer we will keep track of the max number of operations($$$[l,r]$$$) performed for answer.

sdssudhu

← Rev. 2 →

Let us assume the max possible index(MPI) for some index L is R. Now for L+1, there are 2 possibilities:

The MPI for L+1 >= R, which means 2 pointers would work normally.
The MPI for L+1 < R. The reason 2 pointers work in this case is the fact that if MPI for L+1 is < R, it doesn't even matter to us because we need the max interval and this will definitely be less than the size of [L,R]. Thus for any useful range with start index > L, MPI must be greater than R.

Olympia

I didn't realize 2 pointers solution worked, so I wrote segment tree + binary search. 2 pointers is much cleaner :)

devanshmishra111

how would you solve it if the problem were to find largest subsequence instead of contiguous subsequence ??

Several observations:

If we fix the leftmost position of the contiguous subsequence we chose to employ, we can binary search on our rightmost position. This is because choosing to help one more person on the right is always more expensive than not choosing to help that person.
How do we know if we can help a contiguous subsequence $$$[a_l, a_{l + 1} \dots a_{r - 1}, a_r]$$$? We can only help if $$$a_l, a_l + a_{l + 1}, a_l + a_{l + 1} + a_{l + 2} \dots a_l + a_{l + 1} + \dots + a_r$$$ are all positive. That is, if all the prefix sums are positive, or alternatively that our minimum prefix sum is $$$\ge 0$$$.
How do we quickly calculate minimum prefix sums which have some left offset? Just notice that prefix sums starting at $$$a_l$$$ are exactly the same as prefix sums starting at $$$a_0$$$, except we subtract off $$$pref[l - 1]$$$.
So in short, we can find the minimum prefix from $$$a_l \dots a_r$$$ by computing prefix sums $$$a_0 \dots a_r$$$, finding the minimum on the interval $$$[l, r]$$$, and subtracting off $$$pref[l - 1]$$$.

You can check out my submission here: 136938974 if you are still confused. Also, there's no need to cheese in this problem, but if you did need to cheese, you could be sparse table instead of segment tree for minimum, since the prefix sum array is static.

yeah i understood this one, but i asked a different question..i asked if we could solve this problem in O(NlogN) when we are asked to find longest subsequence instead of longest contiguous subsequence

Pi61

I assume what you meant is creating the longest subsequence by removing some elements in the original sequence.

In this case, we can try to solve the problem greedily.

First we construct a minheap.

Then we will iterate through the original sequence using a pointer i.

If the ith element is negative, put it in the heap.
When the sum of all elements from 1 to i becomes negative, we will remove the element with the smallest value using the minheap we just constructed. Since the removed elements will have the smallest possible value, I think the resulting sequence will be the longest possible sequence.

I couldn't prove/disprove this idea, but it seems to work.

liuxiangbin

In China we call this solution "Monotone queue", maybe you can get some information by searching this word.

ibrahimwq

10 месяцев назад, # ^ |

← Rev. 3 →

let's say p[i] is a prefix sum from L to i, by definition every i for p[i] must be greater or equal to -s

suppose we want to add a[R+1] to our subsequence

1.if p[R] + a[R+1] < -s, we must move our L pointer, it means we will remove some p from L to R let's say it p[j], then (p[R] + a[R+1]) — p[j] must be greater or equal to -s.

(p[R] + a[R+1]) — p[j] >= -s

(p[R] + a[R+1]) + s >= p[j] -> means p[j] < 0

what will happen with other p where j < i <= R when we removing p[j], by definition every p >= -s, since we are removing p[j] and p[j] < 0 and p[j] >= -s, then every p where j < i <= R will lose p[j],so it means any p from our new subsequence won't be less than -k

2.if p[R] + a[R+1] >= -s we can just move our R pointer to R + 1

solution: here

peti1234

+38

Alternative solution for G:

We have to cover the candies with chains. According to Dilworth's theorem it is enough to find the longest antichain. (set of candies, where it is impossible to collect two of them in the same turn).

Two candy $$$a$$$, $$$b$$$, (with the same parity) can be in the antichain if their width differnce is strictly larger than their height difference ($$$|y[a]-y[b]|>|x[a]-x[b]|$$$)

This motivates a dp solution $$$dp[i][j]$$$ — the longest anticahin from the first column ends $$$(i, j)$$$. The transitions are easy: $$$dp[i][j]$$$=max($$$dp[i-1][j-1]$$$, $$$dp[i+1][j-1]$$$) and $$$dp[i][j]$$$=$$$dp[i][j-2]+1$$$ (if there is a candy in (i, j).

The time and memory complexity is $$$O(n*m)$$$.

Deepesson

That was what I did in the contest. I was just a bit dumb and didn't realize that I could've just done a bit of dp. Instead, I solved with LIS, so the code got much longer than needed. Well, the final code was really similar to Baltic OI — 2009 — Candy.

hydroshiba

Did anyone else solve E1 using LCA?

I solved E1 using LCA and a bruteforce-ish approach. For every leaves, I brute through all the enemy vertices in the list and then used LCA to calculate the distance from the leaf to the enemy and from the leaf to the root in $$$O(logN)$$$. I did a little optimization that if the leaf is an enemy vertex, I skip it.

In the worst case the complexity should be something around $$$O(N * k * logN)$$$ with $$$k$$$ is the number of enemies, since it is possible to build a tree with $$$N - 1$$$ leaves. Still not sure why my code didn't got FST, probabilistic magic maybe?

r-tron18

I did simple dfs two times. That is a O(n), check my submission here

https://codeforces.com/contest/1611/submission/136941781

Ryu204

Can you show me how did you do LCA with $$$O(logN)$$$?

kanisht_09

my simple two pointer solution for problem F:

solution for F

shubham84

Thanks for this, it was helpful.

joecai

thanks,dude,it's helpful!

adiagr

Great

visheshgautam.official

your timecomplexity is O(n^2) right??

No its O(N)

maxn1e5

Please, help me. Why my solution for F get WA: https://codeforces.com/contest/1611/submission/136894757 ?

UPD: fixed: https://codeforces.com/contest/1611/submission/137155268

AdnanShamsi

1
2 0
-1 5
correct output: 2 2
your output : 1 2

Thank you!

Your_Bunny_Wrote

Can someone help me,please https://codeforces.com/contest/1611/submission/137113575

doraty228

this test

1
8
1 1 2 3 4 5 1 7
1 7 2 3 4 5 6 8

get wrong answer distant to 8 is 7, distant to 5 is 8, but 5 earlier then 8 it's solution don't work because you don't check distant from root of tree.

dedsec_29

Is this a bug? The editorials to the problems aren't linked in "Contest Materials" yet, only the Announcement is linked.

d0t_d0t

-10

I think, my solution for F is easier than editorial's.

Time complexity: O (n * log ^ 2 (n))

Link: 137119559

P.S. you can use sparse table instead of segment tree.

MrOtter

You can use sliding window which is O(N)

notwatermango

how do we decide which one to slide?

deneribeiro10

use a prefix sum (or just a sum), try taking next value at j. if S + range_sum(i, j) < 0, then its not possible to take elements up to j starting at i, then move i until it is possible to do so. At this point, you then increment j and repeat the process.

something lile this:

while(j < N) {  
   while(i <= j && S + range_sum(i, j) < 0) i++;  
   ans = max(ans, j-i+1);  
   j++;  
}

using this idea, you know that every i already tested cannot excede the current j, (because at some point S + range_sum was less then 0). At the meantime, we are removing all i that is not usefull (doesn't get to j).

I think that the last question is: "Given an invalid window (i, j), what if I test an new_i (new_i > i) that can get to j, but there is some point x (new_i <= x < j) such that S + range_sum(new_i, x) < 0??", that is not possible because, initially our current window was invalid and:

if we remove a positive prefix of our window (i, j), then S + range_sum(new_i, j) is also invalid (less then an invalid range). That is the case explained before.
if we remove a negative prefix of our window (i, j), as S + range_sum(new_i, x) < 0, adding the removed negative prefix + S + range_sum(new_i, x) is also less then 0. Which means that S + range(i, x) is negative, therefore, j shoud never be greater then x, as j is the first invalid point. This is a contradiction.

thanks, i succesfully implemented this with a sum and two pointers

vaal

I think it should come like "Consider a vertex p[i], (2≤i≤n)" instead of "(2≤p[i]≤n)" in the editorial for D.

arpitP

I did same as it written in the editorial.

By running a breadth-first search at the same time from each vertex with a friend, we can find the shortest distance to any friend from each vertex and by running from the root — the distance to the root. Now let's just go through all the leaves and check if there is one among them that the distance to the root is less.

Here is my implementation

What I did in my implementation is that

First I found the distance of every vertex from the root and stored it in the vector distance_from_root.

second, I found the minimum distance of every vertex from every friend, What I mean is that if the distance of a vertex x is 1,2,3 from friend x1,x2,x3 respectively then I stored the minimum of it i.e., 1 for vertex x in the vector distance_from_friend and then I checked for this condition as it is given int the editorial. Thus, Vlad can win if there is such a leaf (which, by condition, exits) for which the distance to the root is less than the distance to any of the friends.

But it is showing TLE. Please Help!

Vladosiya

You run bfs from each friend, it's O(n*k). In the editorial, It was meant to run one bfs which uses all friends as start vertices like it is in solution.

sw_enthusiast

I tried to solve "1611E1 — Escape The Maze (easy version)" using approach of traversing from friends up (parents) and from root (Vlad) down (to leaves) and at the same time. When friends visit some node I mark it as visited and that prevents Vlad to traverse through that node down. This approach gives me incorrect solution and I don't know why. Any ideas? Submission: https://codeforces.com/contest/1611/submission/136924541

practice_52

11 месяцев назад, # ^ |

Hi, I know its a long time ago but did you find the mistake in your solution?

My code 208031894 is giving wa on a test case too using the same approach.

variety-jones

Take a look at Ticket 16861 from CF Stress for a counter example.

Thankyou so much cfstress is a great tool.

bergus

I had the same idea, but I got TLE 213292785 I think that's because traversing from friends up may lead to O(n^2) if the tree is a bamboo.

max0n

Can someone explain to me my own approach for C xD? During the contest this seemed natural to me, but now I cannot convince myself why this actually works. In short, I compare leftmost and rightmost elements of a and whichever is smaller goes to the corresponding side in p (if a[left] is smaller, a[left] goes to beginning of p, otherwise a[right] goes to end of p)

mage111

Can someone explain solution of E1?

agobeaux

Here is my solution for E1: https://codeforces.com/contest/1611/submission/137730474 I did not use the color thing, even though I can understand it now.

For my solution, I used a queue, a distance array, and simply made 2 BFS. The first BFS helps to know the distance between any vertex and Vlad's friends. This is feasible by putting all the friends' nodes as the sources (you put them in the queue and put the distance as 0). Why is that useful? Because we want to know whether a friend will be able to catch Vlad on a certain node. This is the case if the distance from the node to Vlad is bigger or equal to the distance from the node to the closest friend. Now that we have this distance array, we simply make a BFS with Vlad as the source, and verify that the distance from Vlad to each node is strictly smaller than the distances previously computed. If we end up on a node verifying this condition and this node appears to be a leaf, we know Vlad can escape without being caught!

I hope my explanation is clear, I had also put some comments in the code to make it understandable.

P.S.: for the color solution, it is basically the same but more optimized: we simulate both DFS at the same time. Vlad and his friends are the sources. Every node visited is colored with Vlad's color or his friends' color, IF it was not already colored. An important detail here is that we do not want Vlad to end up on a node that is at the same distance from one of his friends. To take this into account, we put Vlad's friends in the queue before him, so that they get to move before he does (color of friends has a higher priority than Vlad's color).

Let me know if something is not clear!

SSGJ_Goku

Can anyone spot the mistake in my code .. I am getting a runtime verdict on this code https://codeforces.com/contest/1611/submission/137548112

Thanx in advance

dhruv7888

Can someone explain me the editorialist's Solution for G or anyother solution . It's been 1 day me trying to understand that . I did understood the solution provided by peti1234 in comments section .

SaoST

← Rev. 11 →

I can solve problem G in O(n*m) by find path for each robot.

I divide robot into 2 parts, the same as MikeMirzayanov's solution.

With each part, while cell 1 exist, i go from top to bottom, with each row:

Get the first cell is 1, let's say p[i].
If robot can go to this cell, add i to list Q.
Else if column that robot exist smaller than this cell, skip this row, that mean p[i] < p[Q.back()].
Else, remove Q.back() from list, until robot can go to this cell.

After, make all cell in list to 0.

If we save p[i], p[i] always increase, and the loop is not overate m times, so complexity is O(n*m).

P/s: Sorry for my bad english.

tgp07

Multi-Source BFS is amazing

vd__coder

In problem F,as per the equation in editorial,for each l in prefix array there would be value for right index in prefix array, given by p[r]<p[l-1]-s,so cant this this be implemented with a method of finding next greater element,with a little modification?

anuj_pandey0

10 месяцев назад, # |

why my solution is not correct... WA at TC-2

210089349

Блог пользователя Gol_D