Tutorial
Tutorial is loading...
Solution
t = int(input())
for i in range(t):
n = int(input())
a = list(map(int, input().split()))
cnt0 = a.count(0)
if cnt0 >= 2:
print(a[0] + a[-1])
else:
print(-1)
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
void solve()
{
long long x, y, k;
cin >> x >> y >> k;
long long ans = 0;
for(long long i = 0; i < min(y, k); i++)
ans += (y + i) % (x + i);
long long full = max(0ll, k - y);
ans += full * (y - x);
cout << ans << endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
for(int i = 0; i < t; i++)
solve();
}
2260C - Maximize XOR, Minimize Operations
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int x, y;
cin >> x >> y;
int s = x + y;
for(int d = (1 << 30); d >= 1; d >>= 1)
if((s & d) != 0 && x >= d)
x -= d;
cout << s << " " << x << endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
for(int i = 0; i < t; i++)
solve();
}
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
const int K = 3;
const int INF = int(1e9);
pair<int, int> get_segment(char c)
{
if(c == '0') return {K, K};
if(c == '-') return {0, K - 1};
return {K + 1, K * 2};
}
void solve()
{
int n;
string s;
cin >> n >> s;
vector<vector<int>> dp(n + 1, vector<int>(2 * K + 1, INF));
dp[0][K] = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < 2 * K + 1; j++)
{
if(dp[i][j] == INF) continue;
auto [l, r] = get_segment(s[i]);
for(int k = l; k <= r; k++)
{
if(k == j) continue;
int& d = dp[i + 1][k];
d = min(d, max(dp[i][j], abs(k - j)));
}
}
int ans = *min_element(dp[n].begin(), dp[n].end());
if(ans == INF) ans = -1;
cout << ans << endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
for(int i = 0; i < t; i++)
solve();
}
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
int get(int c00, int c11, int cd)
{
int len = c00 + c11 + cd;
int lf = len / 4;
int rg = 1e8;
int ans = 1e8;
while(rg >= lf)
{
int mid = (lf + rg) / 2;
int need_break = max(0, c00 - mid) + max(0, c11 - mid);
if(need_break + cd / 2 <= mid)
{
ans = mid;
rg = mid - 1;
}
else
lf = mid + 1;
}
return ans;
}
void solve()
{
int n, q;
cin >> n >> q;
string s;
cin >> s;
vector<int> pref1(n + 1), prefdiff(n);
for(int i = 0; i < n; i++)
pref1[i + 1] = pref1[i] + (s[i] - '0');
for(int i = 0; i + 1 < n; i++)
prefdiff[i + 1] = prefdiff[i] + (s[i] != s[i + 1]);
for(int i = 0; i < q; i++)
{
int l, r;
cin >> l >> r;
if(l == r)
cout << 3 << "\n";
else
{
int c1 = pref1[r] - pref1[l - 1];
int cd = prefdiff[r - 1] - prefdiff[l - 1];
if(s[l - 1] != s[r - 1])
cd++;
int c0 = (r - l + 1) - c1;
int c00 = c0 - (cd / 2);
int c11 = c1 - (cd / 2);
cout << get(c00, c11, cd) * 4 - (r - l + 1) << "\n";
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
//cin >> t;
for(int i = 0; i < t; i++)
solve();
}
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
const int N = 3010;
vector<pair<int, int>> g[N];
int p[N];
int pe[N];
int used[N];
int n, m;
vector<int> bad_edges;
int cycle[N];
int xs[N], ys[N];
void dfs1(int x)
{
for(auto [y, i] : g[x])
if(p[y] == -1)
{
p[y] = x;
pe[y] = i;
dfs1(y);
}
else if(p[x] != y)
bad_edges.push_back(i);
}
void go_to_root(int x)
{
while(x != 0)
{
cycle[pe[x]] ^= 1;
x = p[x];
}
}
void dfs2(int x)
{
used[x] = true;
for(auto [y, i] : g[x])
if(cycle[i] == 0 && !used[y])
dfs2(y);
}
void solve()
{
cin >> n >> m;
bad_edges.clear();
for(int i = 0; i < n; i++)
{
g[i].clear();
p[i] = -1;
pe[i] = -1;
}
for(int i = 0; i < m; i++)
{
int x, y;
cin >> x >> y;
--x;
--y;
xs[i] = x;
ys[i] = y;
g[x].push_back(make_pair(y, i));
g[y].push_back(make_pair(x, i));
}
p[0] = 0;
dfs1(0);
sort(bad_edges.begin(), bad_edges.end());
bad_edges.erase(unique(bad_edges.begin(), bad_edges.end()), bad_edges.end());
int k = bad_edges.size();
for(int mask = 1; mask < (1 << k); mask++)
{
for(int edge = 0; edge < m; edge++) cycle[edge] = 0;
for(int bit = 0; bit < k; bit++)
if((mask >> bit) & 1)
{
go_to_root(xs[bad_edges[bit]]);
go_to_root(ys[bad_edges[bit]]);
cycle[bad_edges[bit]] ^= 1;
}
for(int vertex = 0; vertex < n; vertex++)
used[vertex] = 0;
dfs2(0);
bool good = true;
for(int vertex = 0; vertex < n; vertex++)
if(!used[vertex])
good = false;
if(good)
{
cout << "YES\n";
return;
}
}
cout << "NO\n";
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
for(int i = 0; i < t; i++)
solve();
}
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int add(int x, int y)
{
x += y;
while(x >= MOD) x -= MOD;
while(x < 0) x += MOD;
return x;
}
int mul(int x, int y)
{
return (x * 1ll * y) % MOD;
}
int binpow(int x, int y)
{
int z = 1;
while(y > 0)
{
if(y % 2 == 1) z = mul(z, x);
x = mul(x, x);
y /= 2;
}
return z;
}
int inv(int x)
{
return binpow(x, MOD - 2);
}
const int N = 200043;
int mind[N];
int fact[N];
int ifact[N];
void precalc()
{
for(int i = 2; i < N; i++)
for(int j = i; j < N; j += i)
if(mind[j] == 0)
mind[j] = i;
fact[0] = 1;
for(int i = 1; i < N; i++)
fact[i] = mul(fact[i - 1], i);
ifact[N - 1] = inv(fact[N - 1]);
for(int i = N - 1; i >= 1; i--)
ifact[i - 1] = mul(ifact[i], i);
}
int choose(int n, int k)
{
if(n < 0 || n < k || k < 0) return 0;
return mul(fact[n], mul(ifact[k], ifact[n - k]));
}
int n;
vector<int> factorize(int x)
{
vector<int> res;
while(x != 1)
{
res.push_back(mind[x]);
x /= mind[x];
}
return res;
}
void gen(const vector<int>& d, int i, long long cur, int m, vector<pair<long long, int>>& res)
{
if(i == d.size()) res.push_back(make_pair(cur, m));
else
{
gen(d, i + 1, cur, m, res);
gen(d, i + 1, cur * 1ll * d[i], -m, res);
}
}
void solve()
{
cin >> n;
vector<pair<pair<long long, int>, int>> edges;
for(int i = 1; i < n; i++)
{
auto f1 = factorize(i);
auto f2 = factorize(i + 1);
for(auto x : f2) f1.push_back(x);
sort(f1.begin(), f1.end());
f1.erase(unique(f1.begin(), f1.end()), f1.end());
vector<pair<long long, int>> pos;
gen(f1, 0, 1, 1, pos);
for(auto [x, s] : pos)
{
if(x == 1) continue;
edges.push_back(make_pair(make_pair(x, s), i));
}
}
int ans = 1;
int l = 0;
sort(edges.begin(), edges.end());
while(l < edges.size())
{
int r = l;
while(r < edges.size() && edges[r].first.first == edges[l].first.first)
r++;
vector<int> e;
for(int i = l; i < r; i++)
e.push_back(edges[i].second);
long long i = edges[l].first.first;
int m = edges[l].first.second;
if(m != 0)
{
int absent = n / i;
int cur = mul(fact[n], ifact[n - absent]);
int lf = 0;
while(lf < e.size())
{
int rg = lf;
int nxt = e[lf];
while(rg < e.size() && e[rg] == nxt)
{
rg++;
nxt++;
}
vector<int> cnt(2);
for(int k = e[lf]; k <= e[rg - 1] + 1; k++)
{
if(k % i != 0)
cnt[k % 2]++;
}
//cout << cnt[0] << " " << cnt[1] << endl;
cur = mul(cur, choose(cnt[0] + cnt[1], cnt[0]));
lf = rg;
}
//cout << i << " " << cur << endl;
ans = add(ans, -1 * m * add(cur, -1));
}
l = r;
}
cout << ans << endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
precalc();
int t = 1;
//cin >> t;
for(int i = 0; i < t; i++)
solve();
}








The tutorials for problems will be available in a few minutes.
In problem C, what's preventing us from having a greedy pick where, if in the sum S=X+Y there is a 0 bit, it is a result of 1 in X and 1 in Y?
In other words, Why can't I have 1 ^ 1 resulting in 0 in S?
Why should I be mapping the set bits of S to X and Y? Why not have a configuration where unset bits are a result of 1 bit in X and 1 bit in Y?
cause that would lead to X&Y being non zero.
My bad, thanks!!
B felt like a bullet stuck in the ribs, nor does in come out nor was it blocked, felt suffocated!
Tomorrow is my exam—worst decision ever to register!
same here bro...it sucks...
A — easy, B, C literally 1500
l agree
I guess I shall improve my implementation skills now, as I got WA on #2 5 times during contest while getting AC only require changing a few chars (my specific implementation was inferior to the official solution that made debugging harder, though). Submission: 389954784.
I wrongly enumerated bitmasks starting from 0, yet another trivial bug in determining connectivity prevented me from detecting it from the samples :(
In my opinion you needed to spend more time with pencil and paper. The solution only requires 50 or so lines of code.(Assuming this was for problem C)
Um, but this is F.
Oh nvm. You did great by the way. The tutorial for F looks like a trip to hell.
Solution to E without using binary search 389952685
if x1 is number of 00 , x2 is number of 11 and x3 is number of 01 then following function gives the answer
I was close to solving D , just kept trying to find a arrangement of the prefix that is optimal by considering block interval sizes (if its odd , then it can have 1 , 1 on the ends optimal).
figured prefix would only take value between [-2 , 2] .
The prefix values need not be in [-2, 2], Example : -++++-, Answer : 2, Construction : (-1, 2, 2, -1, -1, -2), Prefix : (-1, 1, 3, 2, 1, -1), I too got one WA due to missing this case where increasing by 2 while positive makes sign transition using -2 possible.
Good contest, tho I couldn't solve C. I found the obervation where we need $$$x$$$ $$$AND$$$ $$$y$$$ $$$=$$$ $$$0$$$ but I couldn't do anything further
This is not a competition, but I got to the coding part(though contest ended before I can fix sillies).
It seems that I was able to somehow find all the possible cases and ended up just if-else my solution for D, submission — https://codeforces.me/contest/2260/submission/389959167
can you just have a look at my submission too i also tried to make cases but couldn't understand where it fails https://codeforces.me/contest/2260/submission/390562811
If I have something like +----+ your code will output 3, when in reality it should be 2. The actual case when you should get 3 is when you have something like +--+, just two '-'s between the '+'s, also at some places you should write ans = max(2, ans) but you just write ans = 2.
ohkk i wrote ans = 2 because if the ans has been 3 before it will break out of the loop that time only
Thanks it got AC i miscalculated the ans to be 3 in that case
6 successful hacking attempts(tl) on C, E and F :>
Why isn't this blog more openly visible. I had to go to dude's profile to get this.
Sorry, I forgot to link this blog to the round. Will do it right now
I have another approach for D. We can just consider few cases and decide if its -1,1,2 or 3.
1) If 1st char is 0 or there are consecutive 0s then -1
2) Now we set ans=1
3) If + and — are adjacent anywhere or there are even number of — or even number of + between 2 0s then we update ans to 2
4) If we encounter +--+ or -++- then we update it to 3
There's code in previous Rev
I had the exact same approach. Took me like 6 WA's tho.
can you just have a look at my submission too i also tried to do the same but couldn't understand where it is failing https://codeforces.me/contest/2260/submission/390562811
Hey can I ask why for answer 3 you only check for +--+ or -++-? Won't the answer be always at least 3 if we have + (even number of -) + or vice versa?
Edit: nvm I got it.
Another necessary and sufficient condition for problem E is $$$cnt_0 = cnt_1 = numFlips$$$ where $$$numFlips$$$ represents $$$cnt_{01} + cnt_{10}$$$
Anyone else found their questions skipped? What could be the potential reasons?
My unusual solution for C was doing binary-search on every possible combination of bits to find the maximum <= x. But I have now realized that I could have done it greedily.
nice contest, learn a lot tysm
Alternative solution for F:
After seeing that the edges colored 1 and 2 must form a cycle, we also observe that this cycle must have length $$$\leq m-n+1$$$. This is because the graph still needs to be connected after removing the cycle. The minimum number of edges needed for a graph of size $$$n$$$ to be connected is $$$n-1$$$ edges, so if the cycle was more than $$$m-n+1$$$ edges long, it is impossible for the graph to be connected after removing them.
So, we just run a dfs starting from each node, with a max depth of 10, finding every cycle candidate containing that node. The complexity should be the same as in the official solution.
Submission: 390181201
There can be many paths of length at most $$$10$$$. Enumerating all of them may be too slow. Consider for example this graph:
You are right about that. I think repeatedly removing leaves of the graph until only nodes of degree $$$\geq 2$$$ are left will reduce the amount of paths by an order of $$$n$$$, since the sum of degrees of all nodes will be $$$\leq 2n+20$$$, and the maximum degree of any node will also be 20. It should pass within the time limit now.
390263643
Problem D can also be solved by greedy 390216387
tourist where to learn each topics for competetive programming
What I did for F: We take only 1 edge of colour 1. Now we need to find a path connecting the 2 nodes of that edge which can be coloured 2. Since colour 3 must form atleast a tree, the nodes of all the 1 or 2 coloured edges must have degree atleast 3. So we find edges which will have both vertices of degree atleast 3. It feels that such edges should be low when m<=n+9. (It turns out that such edges are atmost 27). Then for each such edge say e={u,v} we try to find a path of length atmost m-n edges (with vertices that must belong to those precalculated 3 degree egdes) from u to v via DFS and if we find a path we then check if the remaining 3 colour edges form a connected tree. We are doing like DFS inside DFS so I didn't think it would work but idk it worked somehow.
Submission: 390066836
I passed F with DFS and union-find disjoint sets. Actually it just like brute force. But it runs faster than the tutorials' solution. (lol)
390234644
(I'm sorry for the terrible variable name.)
Problem E can be solve in $$$O(n+q)$$$ 390259364
The logic is
1.Simulate adding 0/1,we observe that we can increase #00 when #00>0/#01/#10 > 0,increase #01/10 when #00>0/#11>0 ,increase #11 when #11>0 /#01/10 > 0
2.From step 2,we observe #01/10 is always increase same unit and the problem didn't say there is impossible condition,this lead me think that #01 and #10 is always same otherwise it can't exist solution,and the truth is it can be show that #01 and #10 is always same
3.now we got a element u=(x,y1,y2,z) x=#00,y1=#01,y2=#10,z=#11,the problem reduce to the minimum operation to make all number in u equal,and since from step 2 ,y1 always equal y2,then we may cut one of them into u=(x,y,z)
4.Problem now is minimum operation to make all element in (x,y,z) equal,and constraints is x/z can reduce 1 unit to increase y 1 unit,if x/z == 0 then can't perform this operation,if y>0 then x/z can increase 1 unit
5.Let m be the number of (x,y,z) final be,then it can be show that answer is $$$4\cdot m-(r-l+1)$$$ and $$$m = \max(1,y,\lceil \frac{x+y}{2} \rceil,\lceil \frac{y+z}{2} \rceil,\lceil \frac{x+y+z}{3} \rceil) $$$
let
$$$a$$$=times of $$$x$$$ increase $$$1$$$
$$$c$$$=times of $$$x$$$ decrease $$$1$$$ to $$$y$$$
$$$b$$$=times of $$$z$$$ increase $$$1$$$
$$$d$$$=times of $$$z$$$ decrease $$$1$$$ to $$$y$$$
$$$m$$$=the final number of $$$x,y,z$$$
then obviously
from $$$(1)$$$
similar ways you can get $$$d \ge z-m$$$,since $$$c$$$ and $$$d$$$ is #times of operation so it can't be negative,so $$$c=\max (0,x-m) $$$ and $$$d=\max (0,z-m)$$$
from $$$(2)$$$
There will be four possible outcome,which is $$$(0,0),(0,z-m),(x-m,0),(x-m,z-m)$$$,i will just show you one of them,and the residue you can just expand it yourself.
if outcome is $$$(x-m,z-m)$$$ then
At the end it prove the formula in step 5,but i left something let you to prove,if the $$$m$$$ is fulfill the criterion of step 5,does that exist some case may not reach the $$$m$$$ due to the operation constraints?($$$x$$$ can increase if $$$x \gt 0$$$ or $$$y \gt 0$$$,$$$x$$$/$$$z$$$ to decrease $$$1$$$ to let $$$y$$$ increase,$$$z$$$ can increase if $$$z \gt 0$$$ or $$$y \gt 0$$$)
i hate tutorial of nowadays why there are no hints why direct solution hints give us the thought process required to solve a problem a novel problem
In problem C, the editorial said lastly
iterate over the bits of s from the most significant to the least significant
Why is that ? why is that gives me the nearest true value smaller than x? why is that greedily work?
Why from the least significant to the most significant does not work?
Explaination
Assume x = 01101010 s = x + y = 11100010
Our target to get the maximum number less than or equal to x and all its on bits are on in the s as well at the same positions.
What i mean by that is if s = 1101 all of those answers are valid 0000 0001 0100 0101 1000 1001 1100 1101
lets go bit by bit from left to right
x = 01101010 s = 11100010
x[0] = 0
so ans[0] = 0 no matter what, because ans must be less than x. if ans[0] = 1 and x[0] = 0, so ans will be greater no matter what and this is not what we want.
Remember we want to find the biggest number less than or equal to x and its on bits is also on bits in s "s = x + y".
x[1] = 1
lets see s[1].
s[1] = 1
so ans[1] = 1, right now ans will might be less than or equal to zero
x[2] = 1
s[2] = 1
ans[2] should be equal to 1
x[3] = 0
ans[3] = 0
x[4] = 1
s[4] = 0
ans[4] = 0 and it should be, because we can't have a bit in ans that is on and at the same position off at s.
from now on, ans must be less than x, we should from now on MAXIMIZE ANS AS WE COULD, we make this by "whenever we see an on bit in s, make the bit in ans on as well and we do not afraid to be larger that x because x[4] = 1 and ans[4] = 0, so no matter what are the next bits in ans, ans will be smaller than x"
this result to ans being equal to 01100010, and this is the maximum number less than or equal to x and at the same time all its bits are on at s at the same positions.
This is my solution on F, simple and easy
EDIT this is obviously wrong LMAO but if all bits could be used it would be true Would like to note that the "greedy algorithm" in the C editorial is just binary search in disguise, if you wrote out a full binary search with a search range from $$$0$$$ to $$$2^{30} - 1$$$ it would do the exact same thing. This is a common way to write binary search on bits