Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
t = int(input())
for i in range(t):
l1, r1, l2, r2 = map(int, input().split())
if max(l1, l2) <= min(r1, r2):
print(max(l1, l2))
else:
print(l1 + l2)
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
t = int(input())
for i in range(t):
n, m = map(int, input().split())
s = []
for j in range(n):
s.append(input())
minx = 10 ** 9
miny = 10 ** 9
for x in range(n):
for y in range(m):
if s[x][y] == 'R':
minx = min(minx, x)
miny = min(miny, y)
print('YES' if s[minx][miny] == 'R' else 'NO')
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
def can(pos, m):
k = len(pos)
x = k - m
for i in range(m + 1):
l = pos[i]
r = pos[i + x - 1]
if r - l + 1 - x <= m:
return True
return False
t = int(input())
for i in range(t):
s = input()
pos = []
n = len(s)
for i in range(n):
if s[i] == '1':
pos.append(i)
lf = 0
rg = len(pos)
while rg - lf > 1:
mid = (lf + rg) // 2
if can(pos, mid):
rg = mid
else:
lf = mid
if len(pos) == 0 or pos[-1] - pos[0] == len(pos) - 1:
print(0)
else:
print(rg)
Разбор
Tutorial is loading...
Решение (vovuh)
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
long long k;
cin >> n >> k;
vector<long long> a(n);
for (auto &it : a) {
cin >> it;
}
long long ans = 0;
for (int it = 0; it < n; ++it) {
vector<int> cnt(n);
for (int i = n - 1; i >= 0; --i) {
cnt[i] = (a[i] == 0);
if (i + 1 < n) {
cnt[i] += cnt[i + 1];
}
}
vector<long long> b = a;
long long s = accumulate(b.begin(), b.end(), 0ll);
bool ok = true;
for (int i = 0; i < n; ++i) {
if (b[i] == 0) {
long long x = (i + 1 < n ? cnt[i + 1] : 0);
b[i] = min(k, x * k - s);
if (b[i] < -k) {
ok = false;
}
s += b[i];
}
}
if (ok) {
long long pos = 0, mn = 0, mx = 0;
for (int i = 0; i < n; ++i) {
pos += b[i];
mn = min(mn, pos);
mx = max(mx, pos);
}
if (pos == 0) {
ans = max(ans, mx - mn + 1);
}
}
rotate(a.begin(), a.begin() + 1, a.end());
}
if (ans == 0) {
ans = -1;
}
cout << ans << endl;
return 0;
}
Идея: vovuh
Разбор
Tutorial is loading...
Решение (vovuh)
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int tc;
cin >> tc;
while (tc--) {
int n;
string s[2];
cin >> n >> s[0] >> s[1];
for (int it = 0; it < 2; ++it) {
while (s[0].back() == '.' && s[1].back() == '.') {
s[0].pop_back();
s[1].pop_back();
}
reverse(s[0].begin(), s[0].end());
reverse(s[1].begin(), s[1].end());
}
n = s[0].size();
vector<vector<int>> cost(n, vector<int>(2));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 2; ++j) {
cost[i][j] = (s[j][i] == '*');
}
}
vector<vector<int>> dp(n, vector<int>(2, INF));
dp[0][0] = cost[0][1];
dp[0][1] = cost[0][0];
for (int i = 0; i + 1 < n; ++i) {
dp[i + 1][0] = min(dp[i + 1][0], dp[i][0] + 1 + cost[i + 1][1]);
dp[i + 1][0] = min(dp[i + 1][0], dp[i][1] + 2);
dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + 1 + cost[i + 1][0]);
dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + 2);
}
cout << min(dp[n - 1][0], dp[n - 1][1]) << endl;
}
return 0;
}
1680F - Свободное вершинное покрытие
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
vector<vector<int>> g, h;
vector<int> tin, tout, clr;
vector<vector<int>> sum(2);
int T;
int flip;
int cnt;
bool isp(int v, int u){
return tin[v] <= tin[u] && tout[v] >= tout[u];
}
void init(int v){
tin[v] = T++;
for (int u : g[v]){
if (clr[u] == -1){
clr[u] = clr[v] ^ 1;
h[v].push_back(u);
init(u);
}
else if (tin[u] < tin[v]){
int dif = clr[v] ^ clr[u];
if (!dif){
flip = clr[v] ^ 1;
++cnt;
}
--sum[dif][u];
++sum[dif][v];
}
}
tout[v] = T;
}
int sv;
void dfs(int v){
for (int u : h[v]){
dfs(u);
if (sum[0][u] == cnt && sum[1][u] == 1){
sv = u;
flip = clr[v] ^ 1;
}
forn(i, 2) sum[i][v] += sum[i][u];
}
}
int main() {
cin.tie(0);
iostream::sync_with_stdio(false);
int t;
cin >> t;
forn(_, t){
int n, m;
cin >> n >> m;
g.assign(n, vector<int>());
h.assign(n, vector<int>());
forn(i, m){
int v, u;
cin >> v >> u;
--v, --u;
g[v].push_back(u);
g[u].push_back(v);
}
tin.resize(n);
tout.resize(n);
forn(i, 2) sum[i].assign(n, 0);
clr.assign(n, -1);
cnt = 0;
T = 0;
clr[0] = 0;
init(0);
if (cnt <= 1){
cout << "YES\n";
forn(v, n) cout << (clr[v] ^ flip);
cout << "\n";
continue;
}
sv = -1;
dfs(0);
if (sv == -1){
cout << "NO\n";
}
else{
cout << "YES\n";
forn(v, n) cout << (clr[v] ^ isp(sv, v) ^ flip);
cout << "\n";
}
}
return 0;
}
Can someone share his sliding window approach for problem C ?
Reduce the problem: find the lowest cost substring, cost = max(0's, total 1's — 1's)
The cost of the final optimal substring will either be contributed by 0's or by 1's. Let's binary search on the best answer that can be contributed by 0's and then binary search again on 1's, then we take the minimum of the two.
To check if an answer
g
is possible, we run sliding window. For example, let's say we are currently binary searching on best answer contributed by 0's. We can expand the window until we have more than g 0's in the current window. Then we can shrink it from the left until we have exactly g 0's again.here's my submission: https://codeforces.me/contest/1680/submission/157099290
No need to check for 0's, we can show that if some cost k is achieved we can achieve it using the number of 1's removed = k (and hence the number of 0's left <= k). The proof of this is, suppose on the contrary we get a score of k and remove less than k 1's, then the number of 0's left in the string is k. Now we should not be able to remove more 0's from the string, or we will get a lower score. Hence there should be sufficient 1's surrounding the 0's so that we can bring the count of removed 1's up to k.
Sliding window / two pointers approach without binary search, runs in O(n) time, in C.
Let our window represent the string left after deleting the first
i
elements, and thesize - j
elements from the right.We know that for a window starting at index
i
, if we're increasing the window size, then the best cost we can get is when the number of characters0
in our window is equal to characters1
outside the window. This is because if we keep increasing our window size then the number of character0
in the string will keep increasing, and a smaller window will increase the number of character1
outside the string.Then we just iterate through
i
, the beginning of each window, and keep the maximum window we can get. Wheni
goes to the next iteration, it will find the next possible window starting at the previousi
's max (to keep it O(n)), while also keeping track of the minimum cost as well.Submission: https://codeforces.me/contest/1680/submission/157038960
Great approach !! Understood completely. Thx
Isn't is O(n^2) solution
Can someone share all the approaches to question C as mentioned in the tutorial? It will be nice to see them all at once and compare their complexities
Dynamic programming, Greedy, Two pointers
Has anyone solved problem C with dynamic programming?
dynmaic programming(prefix sum) - Submission
Can you please elaborate your solution. Precisely what the last for loop means.
Refer to this COMMENT for explanation.
Can C be solved using ternary search? If yes, can someone share their solution for the same?
Here is my solution with ternary search.
157125272
I think the solution can be improved and may be done more clearly.
I also tried it using ternary search but got WA as verdict , can you help me finding the test case where it is failing ? 157066350 For every index j in the string , I am finding the optimal i so that cost is minimum using ternary search .
Binary Search Video Solution for C
green !
I used a segment tree.I think I can replace it by a monotune queue.
Problem F looks very similar to https://codeforces.me/contest/19/problem/E
For problem E: a "state machine" approach works, without any DP.
The idea: same as in the editorial, we sweep all the chips from left to right. If we reach a column with a single chip, just move it to the right and add 1 to the answer. What if we reach a column with 2 chips (whether it's 2 chips that are already there, or 1 chip is there and another has been pushed in from the left)? In this case, we push the top chip down or the bottom chip up. But we don't have to consider both possibilities yet. Just put the chip in an "indeterminate" state and resolve the state when you reach a column with exactly one chip.
Of course, this doesn't save much in terms of runtime/space — the dp solution only carries around 2 integers. But I think it's a nice way of looking at the problem.
Hey, can anyone help me with problem C. I've thought of a greedy solution whose basic idea was to remove the max number of zeros by removing min number of ones and repeat this till the string becomes empty from zeros.I tried checking with many edge cases but cannot see what is the mistake ive made. So plz can anyone help me I have commented the code for better understanding https://ideone.com/bBoj0b
Failing testcase: Ticket 7173
I think there is a typo in the editorial of problem E, because the transition $$$dp_{i, 1} \rightarrow dp_{i+1, 1}$$$ is considered twice. It's not really important though because it's easy to understand that the last transition is meant to be $$$dp_{i, 1} \rightarrow dp_{i+1, 0}$$$
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.
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).
Finally an expert after this contest, really liked third problem
Problem F is very nice.
The final part can also be done with LCA. If you want to remove an edge in the tree, which splits it into two subtrees, the edge needs to be so the bad edges not in the original tree (ie. those non-tree edges that connect vertices of the same color) need to be in separate subtrees so we can flip the colors of one subtree.
Then the problem becomes: Given several paths on a tree, find an edge that lies on all of them. This will be the edge we remove. The intersection of two paths is empty, a vertex, or a subpath. It can be checked with a few cases using LCA whether the intersection is another path, and we repeat checking with this newer subpath.
Hey, do you think you could help me understand solution to problem F? I understand when it says we need to remove one edge such that the remaining graph is bipartite but I don't after that I don't really understand anything about how we find this edge. Thanks.
Can anyone help finding which TC my submission fails on? https://codeforces.me/contest/1680/submission/157535516
Edit: Problem E
I did the same! IDK where I am going wrong. If you get it do tell me.
Hello, BARBARIANNNNN , can you please explain your implementation of 157031361, i.e. problem 1680C - Двоичная строка , i am not getting a proper intuition of your code.
And can you please tell me this condition :
while(j<=i && c0>x) { } // my doubt is why we are only comparing c0 with x and not change the loop like this while(j <=i && c1 > x) { } if(c0 <= x && c1 <= x) return true;
changing this is actually giving the wrong answer and giving the bigger cost . Why is it so as we are also considering all the cases in comparing c1 with x ?
In the function check, we use $$$[i,j]$$$ mention the subsegment after our operations. Because we want the max of
the number of characters 0 left in the string
andthe number of characters 1 removed from the string
to be $$$\le x$$$, we should control the c0(the first number in the condition) $$$\le x$$$, while we check whether c1(means the second number in the condition) also $$$\le x$$$. If we change the loop like while(j <=i && c1 > x), then when you add j, the c1 will increase, and it is meanless(never c1<=x because of increasing).Thank you very much BARBARIANNNNN for taking out your time and expalining it clearly. Actually, TBH as a newbie i do not expect so much replies from high rated coders as i am a newbie. But when someone takes out time to resolve my doubt, it just increases my enthusiasm , makes me happy and fills me with a new vigor to practice more.
Really, Thank you again for your time to resolve my doubt BARBARIANNNNN as i have been actually stuck for a long time trying to understand the intuition of your implementation.
I'm unable to understand editorial of problem C. Can someone explain clearly?
I'm unable to understand editorial of problem C. Can someone explain it clearly?
Well, we binary search the number of how much '1's did we delete. Suppose, we have M as the number of deleted '1's. Than we need to find the range with the shortest length of remaining '1's (That's why we need to make an array named pos, where we conserve positions of i-th '1', before binary search). Let's make a loop where we delete first i '1's and last m — i '1's. In this loop we find the shortest length between remaining '1's. After this loop, if the number of '0' in this min-length range of remaining '1's is less then number of deleted '1's, than it's a good answer and we can check lesser answers, Otherwise it's a bad answer and we move to the right. 180966441 — here's my solution
Thank you so much
Hey can someone give me a counter example for this submission of E: https://codeforces.me/contest/1680/submission/197569270
nevermind i got it:
s1 = '*.***'
s2 = '***.*'
Can someone share his DP approach for problem C ?
I am sorry for necroposting but I was solving C by two pointers and sets and I am getting WA on 100 tc on tc 2 I really want to know my mistake. If possible can anyone tell the test case on which it is failing.
void solve() { This is some text.
The rest of the text.
}