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

Разбор

Решение

#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()
#define all(v) v.begin(),v.end()
#define eb emplace_back
 
 
void ct(char c) {
    cout << c << '\n';
}
 
void solve() {
    string a,b; cin >> a >> b;
    char ca = a.back();
    char cb = b.back();
    if (ca == cb) {
        if (sz(a) == sz(b)) cout << '=';
        else if (ca == 'S') {
            cout << (sz(a) < sz(b) ? '>' : '<');
        } else {
            cout << (sz(a) < sz(b) ? '<' : '>');
        }
    }else cout << (ca < cb ? '>' : '<');
    cout << '\n';
}
 
int main() {
    int t;
    cin >> t;
 
    forn(tt, t) {
        solve();
    }
}

1741B - Смешная перестановка

Идея: MikeMirzayanov

Разбор

Решение

#include "bits/stdc++.h"
using namespace std;

void solve(){
    int n;
    cin >> n;
    if(n == 3){
        cout << -1 << endl;
    }
    else{
        for(int i = 3; i <= n; i++) cout << i << ' ';
        cout << 2 << ' ' << 1 << endl;
    }
}

int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}

1741C - Минимизируй толщину

Идея: MikeMirzayanov

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2020;

int n;
int arr[MAXN];

int go(int i, int sum) {
	if (i == n) return 0;
	for (int j = i + 1, cur = 0; j <= n; ++j) {
		cur += arr[j - 1];
		if (cur > sum) return n;
		if (cur == sum) return max(j - i, go(j, sum));
	}
	return n;
}

int solve() {
	int ans = n;
	for (int len = 1, sum = 0; len < n; ++len) {
		sum += arr[len - 1];
		ans = min(ans, go(0, sum));
	}
	return ans;
}

int main() {
	int t; cin >> t;
	while (t--) {
		cin >> n;
		for (int i = 0; i < n; ++i)
			cin >> arr[i];
		cout << solve() << endl;
	}
}

1741D - Маша и красивое дерево

Идея: Gornak40

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

const int MAXM = 300300;

int n, m;
int arr[MAXM];

int solve(int l, int r) {
	if (r - l == 1) return 0;
	int mid = (l + r) >> 1;
	int mal = *max_element(arr + l, arr + mid);
	int mar = *max_element(arr + mid, arr + r);
	int ans = 0;
	if (mal > mar) {
		++ans;
		for (int i = 0; i < (mid - l); ++i)
			swap(arr[l + i], arr[mid + i]);
	}
	return solve(l, mid) + solve(mid, r) + ans;
}

int solve() {
	int ans = solve(0, m);
	if (is_sorted(arr, arr + m))
		return ans;
	return -1;
}

int main() {
	int t; cin >> t;
	while (t--) {
		cin >> m;
		for (int i = 0; i < m; ++i)
			cin >> arr[i];
		cout << solve() << endl;
	}
}

1741E - Передача последовательности по сети

Идея: 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()
#define all(v) v.begin(),v.end()
#define eb emplace_back



void solve() {
    int n; cin >> n;
    vector<int> a(n+1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    vector<bool> dp(n+1, false);
    dp[0] = true;
    for (int i = 1; i <= n; ++i) {
        if (i + a[i] <= n && dp[i-1]) dp[i + a[i]] = true;
        if (i - a[i] - 1 >= 0 && dp[i - a[i] - 1]) dp[i] = true;
    }
    cout << (dp[n] ? "YES" : "NO") << '\n';
}

int main() {
    int t;
    cin >> t;

    forn(tt, t) {
        solve();
    }
}

1741F - Разноцветные отрезки

Идея: MikeMirzayanov, senjougaharin

Разбор

Решение

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>

using namespace std;

int n;

vector<int> calc(vector<vector<int>> a) {
    vector<pair<int, int>> l(n), r(n);
    for (int i = 0; i < n; ++i) {
        l[i] = {a[i][0], i};
        r[i] = {a[i][1], i};
    }
    sort(l.begin(), l.end());
    sort(r.begin(), r.end());
    vector<vector<pair<int, int>>> suf(n);
    vector<pair<int, int>> curr;
    for (int i0 = n - 1; i0 >= 0; --i0) {
        int xr = r[i0].first;
        int i = r[i0].second;
        int xl = a[i][0];
        int c = a[i][2];
        if (curr.empty()) {
            curr.emplace_back(xl, c);
        } else if (curr.size() == 1) {
            if (curr[0].second == c) {
                curr[0].first = min(curr[0].first, xl);
            } else {
                curr.emplace_back(xl, c);
            }
        } else {
            if (curr[0].second == c) {
                curr[0].first = min(curr[0].first, xl);
            } else if (curr[1].second == c) {
                curr[1].first = min(curr[1].first, xl);
            } else {
                curr.emplace_back(xl, c);
            }
        }
        sort(curr.begin(), curr.end());
        if (curr.size() == 3) {
            curr.pop_back();
        }
        suf[i0] = curr;
    }
    vector<int> ans(n, 1e9);
    int j = 0;
    for (int i0 = 0; i0 < n; ++i0) {
        int xl = l[i0].first, i = l[i0].second;
        int xr = a[i][1], c = a[i][2];
        while (j < n && r[j].first < xl) {
            j++;
        }
        if (j < n) {
            vector<pair<int, int>> s = suf[j];
            if (s[0].second != c) {
                ans[i] = min(ans[i], max(0, s[0].first - xr));
            } else if (s.size() == 2) {
                ans[i] = min(ans[i], max(0, s[1].first - xr));
            }
        }
    }
    return ans;
}

const int K = 1e9 + 1;

void solve() {
    cin >> n;
    vector<vector<int>> a(n, vector<int>(3)), b(n, vector<int>(3));
    vector<pair<int, int>> l(n), r(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 3; ++j) {
            cin >> a[i][j];
            if (j == 2) {
                b[i][j] = a[i][j];
            } else {
                b[i][1 - j] = K - a[i][j];
            }
        }
    }
    vector<int> ans1 = calc(a), ans2 = calc(b);
    for (int i = 0; i < n; ++i) {
        cout << min(ans1[i], ans2[i]) << ' ';
    }
    cout << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    for (int it = 0; it < t; ++it) {
        solve();
    }
    return 0;
}

1741G - Кирилл и компания

Идея: Vladosiya

Разбор

Решение

from collections import deque
 
 
def solve():
    n, m = map(int, input().split())
    sl = [[] for _ in range(n)]
    for _ in range(m):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        sl[u] += [v]
        sl[v] += [u]
    f = int(input())
    h = [int(x) - 1 for x in input().split()]
    mask = [0] * n
    k = int(input())
    p = [int(x) - 1 for x in input().split()] + [-1]
    for i in range(k):
        mask[h[p[i]]] += 1 << i
    vars = [set() for _ in range(n)]
    dist = [-1] * n
    dist[0] = 0
    vars[0].add(mask[0])
    q = deque([0])
    while len(q) > 0:
        v = q.popleft()
        for u in sl[v]:
            if dist[u] == -1:
                dist[u] = dist[v] + 1
                q.append(u)
            if dist[u] == dist[v] + 1:
                for msk in vars[v]:
                    vars[u].add(msk | mask[u])
    backpack = [False] * (1 << k)
    backpack[0] = True
    j = 0
    for i in range(f):
        if i == p[j]:
            j += 1
            continue
        nw = backpack.copy()
        for msk in range(1 << k):
            if not backpack[msk]:
                continue
            for var in vars[h[i]]:
                nw[msk | var] = True
        backpack, nw = nw, backpack
    mn = k
    for msk in range(1 << k):
        if not backpack[msk]:
            continue
        ans = 0
        for b in range(k):
            if msk & (1 << b) == 0:
                ans += 1
        mn = min(mn, ans)
    print(mn)
 
 
t = int(input())
for _ in range(t):
    solve()

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

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

hkonvict

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

another opportunity to feel dumb

→ Ответить

abcsumits

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

*_*

xzyxzy

G is good and can be extended to weighted graph

Zeus_009

One of the best editorial thanks for this....****

Tom66

← Rev. 2 →

Nice contest and great editorial!

F a little harder

Nice G

fomo_fame

If we replace mar = *max_element(...) with *min_element(...) in problem D, we are getting AC in both cases. I did min element there so someone can just give example or any explanation why is it working? Thanks in advance :)

chromate00

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

If the tree should pass the sanity check (i.e. Answer is not $$$-1$$$), then any comparison between the left subtree and the right subtree should return the same result. You can observe this by trying to construct the input from the sorted order $$$[1,2,\cdots,m]$$$. You can see that there is no way to move elements from the left subtree to the right subtree (or vice versa), other than to swap the two subtrees entirely. Therefore, the comparison returns $$$L<R$$$ if the two subtrees didn't swap, and $$$L>R$$$ if they did swap.

The_Alchemist

Can someone explain F editorial? Thanks.

deneribeiro10

Imagine a segment $$$S$$$ with left and right points being $$$S_l$$$ and $$$S_r$$$. Now, think about all different segments that have it's left points before (or exactly equals) $$$S_r$$$. You will notice that all those segments (including $$$S$$$) are candidates to be the closest to the left point of $$$S$$$ aka $$$S_l$$$. Or even intersecting with $$$S$$$.

When you realize that, the solution that comes in mind is: for every segment $$$S$$$, search among all segments with left points smaller than or equals to $$$S_r$$$ with different color, the one with highest right point $$$R_{max}$$$. After that, check if $$$R_{max} < S_l$$$ (some distance) or $$$R_{max} \ge S_l$$$ (intersecting segments).

Of course this solution gives you a TLE. However, as we want to know all segments with left points smaller than or equals to our current right point $$$S_r$$$, the idea is iterate over all segments $$$S$$$ in increasing order of right points. Also, keep a pointer to the segments with left points $$$\leq S_r$$$ already considered (to find $$$R_{max}$$$). Update this pointer as you walk through values of $$$S_r$$$.

The remaining part of the solution is explained in the editorial. That is the part that was difficult for me to understand as well. Hope it heps.

aviralarpan3301

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

thanks

OMG_wc

+14

Video Editorial for Chinese：

Bilibili

pribic

Is there an english version of this?

you know，because my poor English

saquib2508

Wanted to reach specialist using div3 as a ladder, instead got negative delta. bleh. Need to grind more.

rurixx

Problem D. To decide to swap or not we do not need to calculate maximum. Enough to compare the first element with middle value.

Gornak40

Yes, it's true, thanks

LessThanExpert

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

Sorry For bad English. Another Solution For D. We don't need to swap or check sorted. because we can not make array sorted if we have abs(maxElementOfLeftSubtree — maxElementOfRightSubtree) != 2^(levelnum from bottom on taking level of leaf node is zero).

Here is my solution (https://codeforces.com/contest/1741/submission/208681460)

vitosevskich

$$$C$$$ and $$$D$$$ could've been swapped, at least in my opinion $$$D$$$ is way easier than $$$C$$$.

Saucemaster102

hmm, idk, I found C to be easier, since constraints were small thus O(n^2) was possible.

re_titled

← Rev. 12 →

I have another solution for C:

We calculate the sum of the whole sequence, and consider its divisors: For every divisor $$$x$$$, we check whether we can divide the sequence into segments of sum $$$x$$$, and calculate the length of the longest segment. Doing that for every divisor gives us the time complexity of $$$O(1344\times n+\sqrt{n\times a_i})$$$, which is still good enough to get AC.

Solution: 175584583

nishu2002

What is wrong in my submission for problem D? 175630153

makuwa

There's another solution to B, which I believe to be more intuitive.

If n equals 3 print -1.

If n is even, then the permutation looks like this:

$$$p = {(n), (n - 1), ...(n / 2 + 1), (1), (2), ... (n / 2)}$$$

If n is odd, just print the permutation for n + 1, but without the first element, which will always be equal to n + 1, so the permutation is valid.

Solution: 175595206

PMiguelez

In my opinion your solution seems a little bit more complicated than necessary and than the one given in the editorial.

I did something similar, but instead of doing

p = n, n-1, ..., n/2+1, 1, 2, n/2

I just did

p = n, n-1, 1, 2, ..., n-2

That way it's easier to implement and this works for both even and odd values of n, so you don't need to handle those cases separately

Solution: 175582981

Anyways, it really doesn't matter much...

tgp07

Does anyone know what the 17th test case of test case 3 for F is? 175777495

adityagamer

This is not the 17th test case but here is a failing test case:

Expected Output: 0 0 25 0 9 0

Obtained Output: 0 0 25 0 43 0

Thanks

EasonCookie197

I have another solution for G. It got AC but I'm not sure if it is actually correct.

Spoiler

UNRULY_HORSE

For problem D, we can first check all leaves. Start from a1, we consider every pair (ai,ai+1), it must be like (x,x+1) or (x+1,x), if not, we cannot sort it. Otherwise, when the form is (x+1,x) we are supposed to swap it. Put (x+1)/2 to its father node. After do this we get a new array which length is n/2. And repeat it until the array length is 1. link

shashank5013

Wouldn't the complexity remain O(mn) for D even after pre-calculating min and max for each vertex since we are swapping elements at each level?

-6

We do not necessarily have to swap all elements of the left/right subtree. I used a bottom-up iterative approach for this. We enumerate $$$k$$$ as powers of two (including one) less than $$$m$$$. And starting from $$$k=1$$$, we try to fix the order of $$$A_{2kx}$$$ and $$$A_{2kx+k}$$$. Now we can see that the indices we wil be comparing on the next step will be a subset of the current step. (Think of it as arithmetic progressions of $$$d=1,2,4,\cdots$$$) This is due to the fact that if the subtrees below are sorted, then we can compare the leftmost element to see whether we need a swap or not. And as we will refer to a subset of the current step on the next step, just swapping the two elements suffices for counting the swaps. The sanity check is done by checking a certain invariant property which is true when the subtrees below are sorted and the tree is made from a perfect binary tree: $$$|A_{2kx}-A_{2kx+k}|=k$$$. This solution is $$$O(m)$$$, you can check my submission (Python:175604510, C++:175815111) for further details.

General_Relativity

Can anyone explain why 175793640 gives MLE on test 24 (problem G)? It works for other test cases which have higher n and m.

prabhu_2020

6 недель назад, # ^ |

Bro How did optimize it ?

nonrice

I like E, pretty standard and good

par4dox

2 недели назад, # ^ |

Is there any way to do E recursively because when doing DP one initially think of recursive solution atleast I do and then convert it into iterative and I am unable to think of it recursively

And if there is no way to do so how to come up with this solution thought process of it

nsqrtlog

← Rev. 5 →

Here's an alternative solution to F w/ $$$O(n\log n)$$$ time complexity and less code.

As done in the editorial, traverse the segments after sorting by left coordinate, and again after transforming $$$(l,r)$$$ to $$$(-r,-l)$$$. Instead of keeping track of 2 maximal segments, though, we keep track of the rightmost endpoint of each color with a max segment tree, and when we are processing segment X, if the query result is to the right of X's left endpoint, we can set $$$ans[X]$$$ to 0, otherwise set $$$ans[X]$$$ to the distance between the left endpoint and the query result.

The above algorithm nearly works, except for when a segment is only adjacent to differently colored segments inside itself. Though, we can then use one additional check: the fact that if segment X contains the midpoint of segment Y, then segments X and Y intersect. This is also insufficient standalone as the converse is false, but kills the edge case. Using a std::multiset, we can perform it in $$$O(n\log(n))$$$.

Implementation: https://codeforces.com/contest/1741/submission/175824953

Alternative implementation, with an additional factor of $$$O(\log c)$$$ in space and time complexity, but uses no data structures outside std::set<int>: https://codeforces.com/contest/1741/submission/175826713

(EDIT: the use of a segtree can be circumvented in my original solution with the bitwise maximum technique in this implementation, which should also improve execution time. Though, that is something one would be far less likely to come up with in contest.)

Can someone help me understand the editorial for problem G? I'm not sure what the editorial is trying to say, and I'm finding it difficult to decipher the code in the given solution.

freehandle

For each vertex, find all possible sets of friends with no cars to which it can give a ride via bfs.
For each set of friends with no cars, determine if it is possible to give rides to them via dp.

aditya_01

Can u pls elaborate your second point. Thank you .

We make a dp on friends with cars as follows: if a set A of friends with no cars could be given rides and a new friend with a car can give ride to a set B, then A union B can be given rides.

ok thanks got something will figure out the rest myself.Thank you for the explanation.

drinkWater.

I would like to share my DFS solution approach for problem E. There can be at most O(2*n) valid subarrays. Each segment is consisted of 2 parts length and numbers. In a segment the length can be either on left or on right. Now, if we consider a[i] as one segment's length indicating cell, then the segment will be either of [i-a[i],i] range or of [i,i+a[i]] range. Let's consider each index as a node. If there are two nodes(segments) having range [i,R1] and [j, R2] where R1+1==j, then we will put an edge between them. Now, lets run a dfs from node 1. If we can reach the node (n+1), then answer is "YES", otherwise "NO". (n+1) is just a dummy node at additional index (n+1). My submission: https://codeforces.com/contest/1741/submission/175659624

-8

Did the same. I do think the DP solution is practically equivalent to the DFS solution though. If we model the DP solution as a DAG, we should get the DFS solution, therefore the two solutions are equivalent.

komi_

You have used directed graph. I tried to do it using undirected graph and I was getting WA (my submission). Can you explain the difference??

$$$[2,2,2,1,1,1]$$$ is a counterexample to the undirected graph approach.

a.rjput

why running DFS from only FIRST node giving the correct solution? I thought the same approach but running DFS running for each node as source.

Actually, we are checking if there is a path between the first node and the last node [It only exists when every index belongs to some node of the path]. And it is easier to code talking first node as the source of dfs.

devesh08

Problem C can also be solved by considering all factors of the sum (sum of all elements of array), and trying to split the array for each factor. There can be maximum of log2(sum) factors making the complexity O(NlogN).

Here is my solution: https://codeforces.com/contest/1741/submission/175841633

Actually the number of divisors of $$$N$$$ is not bound to be lower than $$$\log N$$$. We can use a number which is a product of many different primes for an example of this. Your statement is true for prime factors, but it is nowhere close to the truth for all factors. $$$d(N)\le N^{\frac{1.5379 \log(2)}{\log(\log(N))}}$$$ is a known upper bound for the divisor function for $$$N \le 3$$$, though. ($$$\sqrt[\leftroot{-2}\uproot{2}3]{N}$$$ is not a precise upper bound either, it is just an estimate)

Yes, it was my bad. The numbers of factors do not have a log2N upper bound.

Also if the sum of elements are low, my solution can be faster than O(N^2) solution.

Does anyone know subcase 26 in test case 3 for G? 176090403

mixalowski

176213193 which is my way to solve D using sparse table :)

thanhdno

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

Rushdi

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

how you can do a lazy segment tree on ranges l[i] <= r[i] <= 1e9

isn't 1e9 too big for memory?

← Rev. 3 →

B_Consistent

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

For $$$G_i$$$ thought we need to remove each vertex and do bfs on graph $$$G$$$ for each permutation of friends with no cars. so dumb of me, somehow I thought $$$\sum{distance}$$$ doesn't work

szh_DNCB

6 недель назад, # |

Nice contest!

№	Пользователь	Рейтинг
1	tourist	3690
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	163
4	TheScrasse	159
5	nor	157
6	maroonrk	155
7	-is-this-fft-	152
8	Petr	146
8	orz	146
10	BledDest	145

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