1741A - Сравни размеры футболок
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#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();
}
}
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#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();
}
}
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#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
Разбор
Tutorial is loading...
Решение
#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
Разбор
Tutorial is loading...
Решение
#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();
}
}
Идея: MikeMirzayanov, ibraevdmitriy
Разбор
Tutorial is loading...
Решение
#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;
}
Идея: Vladosiya
Разбор
Tutorial is loading...
Решение
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()
another opportunity to feel dumb
*_*
G is good and can be extended to weighted graph
One of the best editorial thanks for this....****
Nice contest and great editorial!
F a little harder
Nice G
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 :)
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 \lt R$$$ if the two subtrees didn't swap, and $$$L \gt R$$$ if they did swap.
Can someone explain F editorial? Thanks.
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} \lt 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.
thanks
Video Editorial for Chinese：
Bilibili
Is there an english version of this?
you know，because my poor English
Wanted to reach specialist using div3 as a ladder, instead got negative delta. bleh. Need to grind more.
Problem D. To decide to swap or not we do not need to calculate maximum. Enough to compare the first element with middle value.
Yes, it's true, thanks
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://mirror.codeforces.com/contest/1741/submission/208681460)
$$$C$$$ and $$$D$$$ could've been swapped, at least in my opinion $$$D$$$ is way easier than $$$C$$$.
hmm, idk, I found C to be easier, since constraints were small thus O(n^2) was possible.
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
What is wrong in my submission for problem D? 175630153
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:
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
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...
Does anyone know what the 17th test case of test case 3 for F is? 175777495
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
I have another solution for G. It got AC but I'm not sure if it is actually correct.
First of all, we do a BFS from the node 1 to calculate the shortest distance from 1 to all the other nodes, call it $$$dist[i]$$$.
Next, we want to know if we can go from node $$$a$$$ to node $$$b$$$ by traversing shortest paths, call it $$$ok[a][b]$$$. We do a DFS starting from every node $$$a$$$, but only use the edge $$$(u,v)$$$ if $$$dist[u] + 1 = dist[v]$$$. The nodes that encounter on this DFS is reachable from $$$a$$$.
There are only at most 6 friends without cars. There must be some permutation that matches the order of these friends getting home. So we enumerate all $$$6!$$$ permutations. For each permutation, we assume that the friends without cars reach home in the specific order of the permutation. Then we go through all the friends with cars and we try to send as many friends home as possible, in that specific order. We check if it is possible by using $$$ok[a][b]$$$. For example, let the permutation be $$$p$$$. If the first friend with a car is able to send $$$p_1$$$ home (but not $$$p_1$$$ and $$$p_2$$$ at the same time), then we will start checking $$$p_2$$$ for the second friend with a car.
Lastly, the answer is the maximum among all the permutations. The time complexity is $$$O(nm + k!\times f)$$$.
my submission
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
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
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?
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.
Can anyone explain why 175793640 gives MLE on test 24 (problem G)? It works for other test cases which have higher n and m.
Bro How did optimize it ?
I like E, pretty standard and good
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://mirror.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://mirror.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.
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.
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://mirror.codeforces.com/contest/1741/submission/175659624
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.
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.
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.
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://mirror.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
176213193 which is my way to solve D using sparse table :)
.
how you can do a lazy segment tree on ranges l[i] <= r[i] <= 1e9
isn't 1e9 too big for memory?
.
task D : segment tree with dfs
o(n*m*log(n)) https://mirror.codeforces.com/contest/1741/submission/263268380
o(n*log(n)) https://mirror.codeforces.com/contest/1741/submission/263376104
271884281 I got a memory limit exceeded error on case 18, can somebody figure out what can I do to optimally run my code. Thanks !!!
The original solution to problem E is not so intuitive. There is another way to structure the DP. Each index (i) will either represent length of a segment to the right of it (then we can recursively call of f(i+a[i]+1) or will become part of a segment having it's length representation to the right (then we can see which index (j) to the right of it satisfies (j — a[j] == i).
Here is the Java code:
The arraylist (b) is used for precomputation so that we don't have to loop for every single index. It might look like O(N*N) time but it's actually O(N).
Problem Number D can be solved using Divide and Conquer..while merging the two subparts...we just have to check that the diff of the minimum of the two should be less than the size of the subproblem...if not return -1 which signifies that we it is not possible...like if the subarrays are — [1,2] and [7,8] then we cannot make it increasing in any number of operations..if it was [5,6] as left and [7,8] as right then it is correct if otherways return 1+left+right in recursive manner.... here is my code 323823012
time constraints for E is really tight.
topdown dp of the exact same implementation doesn't work. im getting TLE on test 20, i copy pasted that test and it runs 3ms on my laptop! how does that take more than 1 sec on your servers ?!