1196A - Three Piles of Candies
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
long long a, b, c;
cin >> a >> b >> c;
cout << (a + b + c) / 2 << endl;
}
return 0;
}
Idea: vovuh
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int n, k;
cin >> n >> k;
vector<int> a(n);
int cntodd = 0;
for (int j = 0; j < n; ++j) {
cin >> a[j];
cntodd += a[j] % 2;
}
if (cntodd < k || cntodd % 2 != k % 2) {
cout << "NO" << endl;
continue;
}
cout << "YES" << endl;
for (int j = 0; j < n; ++j) {
if (k == 1) break;
if (a[j] % 2 == 1) {
cout << j + 1 << " ";
--k;
}
}
cout << n << endl;
}
return 0;
}
Idea: MikeMirzayanov and vovuh
Tutorial
Tutorial is loading...
Solution
#include <algorithm>
#include <iostream>
using namespace std;
const int MAXC = 1e5;
int main() {
int q;
cin >> q;
while (q--) {
int n;
cin >> n;
int mnx = -MAXC, mxx = MAXC;
int mny = -MAXC, mxy = MAXC;
while (n--) {
int x, y, f1, f2, f3, f4;
cin >> x >> y >> f1 >> f2 >> f3 >> f4;
if (!f1) mnx = max(mnx, x);
if (!f2) mxy = min(mxy, y);
if (!f3) mxx = min(mxx, x);
if (!f4) mny = max(mny, y);
}
if (mnx <= mxx && mny <= mxy)
cout << "1 " << mnx << " " << mny << "\n";
else
cout << "0\n";
}
return 0;
}
1196D1 - RGB Substring (easy version)
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
const string t = "RGB";
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int n, k;
string s;
cin >> n >> k >> s;
int ans = 1e9;
for (int j = 0; j < n - k + 1; ++j) {
for (int offset = 0; offset < 3; ++offset) {
int cur = 0;
for (int pos = 0; pos < k; ++pos) {
if (s[j + pos] != t[(pos + offset) % 3]) {
++cur;
}
}
ans = min(ans, cur);
}
}
cout << ans << endl;
}
return 0;
}
1196D2 - RGB Substring (hard version)
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
const string t = "RGB";
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int n, k;
string s;
cin >> n >> k >> s;
int ans = 1e9;
for (int offset = 0; offset < 3; ++offset) {
vector<int> res(n);
int cur = 0;
for (int j = 0; j < n; ++j) {
res[j] = (s[j] != t[(j + offset) % 3]);
cur += res[j];
if (j >= k) cur -= res[j - k];
if (j >= k - 1) ans = min(ans, cur);
}
}
cout << ans << endl;
}
return 0;
}
1196E - Connected Component on a Chessboard
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int b, w;
cin >> b >> w;
vector<pair<int, int>> res;
bool need = b < w;
if (need) swap(w, b);
int x = 2, y = 2;
while (w > 0) {
if ((x + y) % 2 == 1) {
res.push_back({x, y});
--b;
} else {
res.push_back({x, y});
--w;
}
++y;
}
int cx = 1, cy = 2;
while (b > 0 && cy <= y) {
res.push_back({cx, cy});
--b;
cy += 2;
}
cx = 3, cy = 2;
while (b > 0 && cy <= y) {
res.push_back({cx, cy});
--b;
cy += 2;
}
if (b > 0) {
res.push_back({2, 1});
--b;
}
if (b > 0) {
res.push_back({2, y});
--b;
}
if (b > 0) {
cout << "NO" << endl;
} else {
assert(w == 0);
cout << "YES" << endl;
for (auto it : res) cout << it.first << " " << it.second + need << endl;
}
}
return 0;
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const long long INF64 = 1e18;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
vector<pair<int, pair<int, int>>> e;
for (int i = 0; i < m; ++i) {
int x, y, w;
scanf("%d %d %d", &x, &y, &w);
--x, --y;
e.push_back(make_pair(w, make_pair(x, y)));
}
sort(e.begin(), e.end());
vector<int> vert;
for (int i = 0; i < min(m, k); ++i) {
vert.push_back(e[i].second.first);
vert.push_back(e[i].second.second);
}
sort(vert.begin(), vert.end());
vert.resize(unique(vert.begin(), vert.end()) - vert.begin());
int cntv = vert.size();
vector<vector<long long>> dist(cntv, vector<long long>(cntv, INF64));
for (int i = 0; i < cntv; ++i) dist[i][i] = 0;
for (int i = 0; i < min(m, k); ++i) {
int x = lower_bound(vert.begin(), vert.end(), e[i].second.first) - vert.begin();
int y = lower_bound(vert.begin(), vert.end(), e[i].second.second) - vert.begin();
dist[x][y] = dist[y][x] = min(dist[x][y], (long long)e[i].first);
}
for (int z = 0; z < cntv; ++z) {
for (int x = 0; x < cntv; ++x) {
for (int y = 0; y < cntv; ++y) {
dist[x][y] = min(dist[x][y], dist[x][z] + dist[z][y]);
}
}
}
vector<long long> res;
for (int i = 0; i < cntv; ++i) {
for (int j = 0; j < i; ++j) {
res.push_back(dist[i][j]);
}
}
sort(res.begin(), res.end());
cout << res[k - 1] << endl;
return 0;
}
Since we have the proof that the structure described in the problem E editorial is optimal, but Vovuh didn't post it for some reason, I'll try to explain it.
Consider the case $$$w \le b$$$. The structure from the editorial can handle at least $$$w - 1$$$ and at most $$$3w + 1$$$ black cells. It is impossible that $$$b < w - 1$$$, since $$$w \le b$$$. So we have to prove that there's no structure of component capable of supporting more than $$$3w + 1$$$ cells.
We can surround each white cell with four black cells, so we can't support more than $$$4w$$$ cells — but even this is possible only if $$$w = 1$$$, because we need do somehow connect all white cells. For a fixed black cell $$$i$$$, let's denote the number of white cells adjacent to it as $$$k_i$$$. The sum of $$$k_i$$$ over all black cells cannot exceed $$$4w$$$. Some cells can have $$$k_i = 1$$$, but if we want to connect some white cells, we have to use a black cell that has $$$k_i > 1$$$.
Let's analyze the sum of $$$(k_i - 1)$$$ over all black cells. I state that it is not less than $$$w - 1$$$, because we need at least $$$w - 1$$$ ''connections'' to connect all white cells. So, each value of $$$k_i$$$ is at least $$$1$$$, $$$\sum k_i \le 4w$$$, and $$$\sum (k_i - 1) \ge w - 1$$$. It means that there can be at most $$$3w + 1$$$ summands in these sums, so we can have at most $$$3w + 1$$$ black cells.
cool!
Nice
There's a typo, problem A links to 1015A instead of 1196A.
Thank you, fixed now!
Wouldn't Floyd Warshall be too much for around 800 vertices?
Because of some vectorization and other compiler optimizations it works very fine (around 1-1.2s in the worst case). But yes, I know that for interpreted language this feature doesn't work and this is sad :(
I mean, if you run it for each component independently then worsecase is improved by a factor of 8... there's no excuse for being lazy :)
Yeah well I didn't even come up with the Floyd Warshall idea during contest so t.t
Just use dijkstra on all vertices. That gives O(n*m*log(n)) solution.
Will it be within Time limit? (Considering n and m are in the range of 10^5).
I meant the reduced n and m.
You would have to reduce the graph as described in the editorial to atmost 2k vertices and k edges. In terms of the original constraints that will be: O(k*k*log(k)).
Okay, got it. :)
Great editorial! All the solutions are very nicely explained.
Can anyone explain B to me please? And if we print k-1 positions of odd numbers, what if there are more than one numbers of odd numbers in a segment? Please help. Thanks.
you can see the problem as we printing the k-1 positions of odd numbers, so making k-1 segments with just one odd number, and for the last segment, we just need to see if with the remaining odd we can create a segment that the sum of its elements is odd, that is, if (cnt — k)%2 == 1.
as we are printing the k-1 positions in order, each one of the segment have just one number, because the previous one odd number is the previous segment, because we printed it position.
(cnt-k+1)%2 == 1**, and with some manipulation you can get the cnt%2 == k%2
Hey, I got something in my mind I know it is ridiculous but this does not make a difference right?(I know it doesn't but when I think I fell like I can't proove that,is it normal? :D): If we have more than one numbers of odd numbers in any segment in k-1 segments.
Or is it like : If we want to change a segments number of odd numbers (lets say it is 1 and the last segment is bigger) we need to add 2 numbers to make numbers odd again and that means we remove 2 odd numbers so last segment's number of odd numbers's mod 2 didn't change am I rigth? I know my ideas are ridiculous.
The mod 2 didn't change, so If you wanted add more number in one segmento, you can subtract for other segment that have 3 or more odd number. It's not like the k-1 need to just have one odd, we do it because after that we just need to care about just one segmento( the least one)
Does someone use DP to pass the problem D.
You can make dp[i][j] mean from the i-th character and start with j=0('R'),j=1('G'),j=2('B')
make tab={'R','G','B'},ADD=(k-1)%3
so:
dp[i][0]=dp[i-1][2]-(s[i-2]!='B')+(s[i+k-2]!=tab[ADD]);
dp[i][1]=dp[i-1][0]-(s[i-2]!='R')+(s[i+k-2]!=tab[(ADD+1)%3]);
dp[i][2]=dp[i-1][1]-(s[i-2]!='G')+(s[i+k-2]!=tab[(ADD+2)%3]);
i think so!
This snippet creepily matches with mine 57687430
:D,really amazing
I did the same :D
The best Div 3 ever ! Fast and quality
Why do we need only min(k,m) edges for problem F?
If k>m, then it's obvious that we have to take all m edges given. But if k<=m, we can choose the first k edges after sorting the edges according to weighs. Our ans in this case can not exceed the value of weight of kth edge. And if the required ans is less than it, then all the required edges for the kth shortest path is already included in these first kth edges.
why there are two Tutorials
Two authors
Official and unofficial
The solution to E is very beautiful
I don't understand why doesn't need more than min(k,m), somebody knows the reason for this it
Explained above.
How to solve F for greater K? I read about Yen's algorithm for single source K-th shortest path. But this one is different.
If you use Dijkstra, you'll solve it in O(k*k*log(k)), so it supports K in the order of thousands (6.000 ~ 10.000 aprox)
Could you please explain this solution more? And why does it have this complexity?
You make a new graph with the minimum K edges, you'll find the answer among this edges for sure, and if the answer is not an edge by itself, it will be a path that contains some of these edges. Maybe this is the tricky part. The Dijkstra part is easy, you need to run one Dijkstra per the new graph's nodes. So given Dijkstra's complexity is E*log(V) , the edges is K and the nodes is also K, so for each run the complexity is O(K*log(K)) and you run one Dijkstra for each node, so K*K*log(K)
Oh, OK. So it's the same as the editorial solution but you just use a Dijkstra from every node instead of Floyd-Warshall. Thanks!
I was lazy to read the A statement, decided to read examples and send code.
It was easier to solve the problem with examples instead of the statement :D
Want moar!
I wrote n dijkstra's algorithms in F. I suppose it works in $$$O(nklog(n))$$$. It still passed in 450ms.
Please tell me where I am making mistake in solution of D1: 1) I make three strings of length K each starting with R,G,B. eg k=3 s[0]="RGB",s[1]="GBR",s[2]="BRG" 2) I am checking the longest common substring with each of the three strings with the given string and storing in mx. 3)return answer as k-mx; Pls Help /. My Solution
Checking the longest common substring does not accurately count how many characters you need to change to get the desired RGB sequence. For example, calling
lcs("RGBRGB", "RRRRRR")returns $$$1$$$ (meaning that your answer will be $$$5$$$), while you only need to change $$$4$$$ characters to obtain "RGBRGB" (same as with "GBRGBR" and "BRGBRG").I know its an old thread but I hope you would help, I wrote the solution of D2 by making three offset string RGB... GBR... BRG... and comparing them with original s.
But I'm getting this unusual error of uninitialized value usage in my solution of 4th test case, cf online judge is highlighting the line but I'm unable to crack it. Can you please help?
Here's my Submission
I see this issue immediately:
memset(g,0,sizeof(b));, where I guess you intend to memset onbinstead?Try fixing that, if it still doesn't work, message back probably
I tried to upsolve problem F. Once solved I submitted it. It failed on TC 3 so I spent some time trying to debug it but couldn't. I then read the editorial and it seemed that their approach was the same as mine. It would help me greatly if someone could tell me what was wrong with my solution.
57753983
Thanks in advance :)
There are many things that are wrong starting with the order of Floyd Warshall. Your Infinity value is also low and your complexity is n^3 as you are not compressing the graph.
Oh, oof.
Thanks though :)
Question F was nice, but can someone provide an efficient method to solve the harder variant of this question, where k can take any value between 1 and m.
Geothermal's tutorial is considering another solution with complexity O((N+K)log(N+K)+MlogM).
(link: https://mirror.codeforces.com/blog/entry/68642)
Problem E:
Can someone help me understand why BFS does not work? Something like an island trying to increase to all sides, or a minesweeper.
Let $$$b = 2$$$ and $$$w = 7$$$ for these examples (swapping black and white gives the same result). In the bfs, start with an arbitrary black cell and spread to the white cells around it.
Say, in the bfs, you arbitrarily pick another black cell, next to one of the white cells that you've chosen.
By picking that cell, you restrict yourself to $$$w = 6$$$ and get the wrong answer (since the bfs solution would think it's impossible). This is because you are only able to add 2 additional white cells for the black cell. Always expanding rightward (or in any of the cardinal directions) allows you to always gain 3 white cells per black cell, which is the optimal structure (as proven above). Here's an example:
In this, it's clear to see that you can achieve the requirements of the test case. As another example, picking the 5 black cells in the center 3x3 square on that example board only allows you to get 12 white cells (much worse than the 5:16 ratio achievable with the optimal solution).
Thank you for your explanation :)
So, I got hacked due to a time limit exceeded on problem B. I followed a similar process as shown in the solution with an O(q*n) solution. But I think the if(k==1) break; statement would have optimized my solution.
57661799
The complexity of editorial solution is actually $$$\sum\limits_{i = 1}^qn_i$$$ .
There is mistake in the solution to B: "at least one of k segments will have even number of odd elements (so will have odd sum)". An even number of odd elements yields an even sum, not an odd sum.
For F I got "accepted" when I did not use the "main observation" from the editorial solution and just used lazy Dijkstra-s from every node run in parallel with one shared priority_queue so that I find shortest distances one by one until I find k of them. I needed to make Dijkstra-s lazy because otherwise I had "memory limit exceeded"--I think because my priority_queue became too big. Here is my commented code:
https://mirror.codeforces.com/contest/1196/submission/57786369
I still can't figure out its complexity. Could you please help me with this?
Your solution is almost identical with Geothermal's.
You can read his unofficial tutorial. (link: https://mirror.codeforces.com/blog/entry/68642)
Thanks, this is very helpful although I don't think he proved there the correctness of his complexity. I have left a comment regarding this under his tutorial. I hope I will find an answer.
vovuh can you please tell me why the solution for D2 is always working ?
I am asking for the case when we have already a substring of size k in string s that is also the substring for the infinite string . Now when we are going to modify the string s according to offset then their are pretty much chances that the substring will be changed and we don't get optimal ans which is zero for this case .
I think you got my question ? Please explain ?
You should read tutorial correctly.
Vovuh are considering 3 different cases:
Obviously, the answer on problem will be found.
Where can i find proof for problem F ?
Please, help. In F, Can someone explain answer on test: 4 4 4 1 2 1 2 3 1 1 3 1 3 4 3
Author's solution gives 3 but optimal way is 1 -> 2 -> 3 with length 2.
In the problem, you're not trying to find the $$$k$$$-th smallest path out of all paths, you're trying to find the $$$k$$$-th smallest shortest path. The path from 1 -> 2 -> 3 is longer than the path going directly from 1 -> 3, so it will not be counted because it's not a valid shortest path between two vertices. Rather, the path from 3 -> 4 of length 3 will be the next smallest shortest path after the ones with length 1.
Thank you very much!
The tutorial for problem E is quite misleading.
should be $$$ w$$$ black cells <...> $$$(1, 2 w - 2 i) $$$
$$$ w$$$<...> $$$(3, 2 w - 2 i) $$$
Do I misunderstand something?
vovuh the editorial has not been linked to the contest page. Please look into it.
Hi! I don't understand why my code in python 3 do not works in the problem A — Three Piles of Candies
for a in range(int(input())): print(int((sum([int(i) for i in input().split()]))/2))
It says wrong answer on the third test....
Can somebody please explain the solution to problem d2
I coded the same idea for Problem F, but thought there might be a problem with it while coding. I got accepted anyways (and had a good moment of laughter bc i expected either TLE or WA) but now I'm here to ask, what if the weights of all the edges falls below the 400th minimum of all weights, so we're left with the very given graph... no reduction is made. How does this not face TLE?