Idea: fcspartakm
Tutorial
Tutorial is loading...
Solution (awoo)
for _ in range(int(input())):
a, b, c = map(int, input().split())
if (a + b + c) % 3 != 0:
print("NO")
continue
x = (a + b + c) // 3
print("YES" if b <= x else "NO")
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
int n;
cin >> n;
vector<int> a(n);
for(int j = 0; j < n; j++) cin >> a[j];
vector<int> pmax(n + 1);
vector<long long> psum(n + 1);
for(int j = 0; j < n; j++)
{
pmax[j + 1] = max(pmax[j], a[j]);
psum[j + 1] = psum[j] + a[j];
}
for(int k = 1; k <= n; k++)
cout << pmax[n - k + 1] + psum[n] - psum[n - k + 1] << " ";
cout << endl;
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
def beats(n, x, y):
if x == 0:
return y == n - 1
if x == n - 1:
return y != 0
return x > y
for _ in range(int(input())):
n = int(input())
owner = input()
good = False
for i in range(n):
if owner[i] != 'A':
continue
good_move = True
for j in range(n):
if owner[j] == 'B' and beats(n, j, i):
good_move = False
if good_move:
good = True
if good:
print('Alice')
else:
print('Bob')
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
const int N = 6e6;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
vector<int> p, ip(N, 1);
for (int i = 2; i < N; ++i) {
if (!ip[i]) continue;
p.push_back(i);
for (int j = i; j < N; j += i) {
ip[j] = 0;
}
}
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (auto& x : a) cin >> x;
sort(a.begin(), a.end(), greater<int>());
int ans = 0;
long long suma = 0, sump = 0;
for (int i = 0; i < n; ++i) {
suma += a[i];
sump += p[i];
if (suma >= sump) ans = i + 1;
}
cout << n - ans << endl;
}
}
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
fore(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;
int n, k;
string s;
inline bool read() {
if(!(cin >> n >> k))
return false;
cin >> s;
return true;
}
inline void solve() {
vector<int> d(n + 1, 0);
vector<vector<int>> nxt(n + 2, vector<int>(k, n));
for (int i = n - 1; i >= 0; i--) {
nxt[i] = nxt[i + 1];
int mx = *max_element(nxt[i].begin(), nxt[i].end());
d[i] = 1 + d[mx];
nxt[i][s[i] - 'a'] = i;
}
int q; cin >> q;
while (q--) {
string t; cin >> t;
int pos = -1;
for (char c : t)
pos = nxt[pos + 1][c - 'a'];
cout << d[pos] << "\n";
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const long long A = (long long)(1e18);
string S(long long x)
{
string s = to_string(x) + to_string(x + 1);
sort(s.begin(), s.end());
return s;
}
vector<long long> aux2;
vector<pair<string, long long>> aux;
long long get_num(string cur)
{
int first_non_zero = 0;
while(cur[first_non_zero] == '0') first_non_zero++;
swap(cur[first_non_zero], cur[0]);
return stoll(cur);
}
void rec(string cur, bool flag)
{
if(*max_element(cur.begin(), cur.end()) > '0')
{
long long x = get_num(cur);
aux.push_back(make_pair(S(x), x));
}
if(cur.size() < 9)
{
if(flag)
rec(cur + "9", true);
else
for(char c = '0'; c <= '9'; c++)
rec(cur + string(1, c), c < cur.back());
}
}
void precalc()
{
for(char c = '0'; c <= '9'; c++)
rec(string(1, c), false);
sort(aux.begin(), aux.end());
for(int i = 0; i < aux.size(); i++)
if(i == 0 || aux[i].first != aux[i - 1].first)
aux2.push_back(aux[i].second);
sort(aux2.begin(), aux2.end());
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
precalc();
for(int i = 0; i < t; i++)
{
long long n;
cin >> n;
cout << upper_bound(aux2.begin(), aux2.end(), n) - aux2.begin() << endl;
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
using pt = pair<int, int>;
const int N = 200007;
int n, q;
int k[N];
vector<pt> t[4 * N];
int p[N], e[N], rk[N];
int *pos[3 * N];
int val[3 * N];
int csz;
int ans[N];
void upd(int v, int l, int r, int L, int R, pt val) {
if (L >= R) return;
if (l == L && r == R) {
t[v].push_back(val);
return;
}
int m = (l + r) / 2;
upd(v * 2 + 1, l, m, L, min(R, m), val);
upd(v * 2 + 2, m, r, max(m, L), R, val);
}
void rollback(int tsz) {
while (csz > tsz) {
--csz;
(*pos[csz]) = val[csz];
}
}
pt get(int v) {
if (p[v] == v) return {v, 0};
auto [u, d] = get(p[v]);
return {u, d ^ e[v]};
}
void assign(int& x, int y) {
pos[csz] = &x;
val[csz] = x;
++csz;
x = y;
}
pt unite(int x, int y) {
auto [v, d1] = get(x);
auto [u, d2] = get(y);
if (v == u) return {0, d1 ^ d2};
if (rk[v] > rk[u]) swap(v, u);
assign(p[v], u);
assign(e[v], d1 ^ d2 ^ 1);
assign(rk[u], rk[v] + rk[u]);
return {1, 0};
}
void solve(int v, int l, int r, int cnt) {
int tsz = csz;
for (auto [x, y] : t[v]) {
auto [f, d] = unite(x, y);
//cerr << l << " " << r << " " << x + 1 << " " << y + 1 << " " << f << " " << d << endl;
if (!f) cnt ^= d;
}
if (l != r - 1) {
int m = (l + r) / 2;
solve(v * 2 + 1, l, m, cnt);
solve(v * 2 + 2, m, r, cnt);
} else {
ans[l] = k[l] % 3;
if (ans[l] == 2) ans[l] = cnt + 1;
}
rollback(tsz);
}
int main() {
cin >> n >> q;
vector<int> g(n), lst(n);
for (int i = 0; i < n; ++i) {
cin >> g[i];
--g[i];
}
for (int i = 0; i < q; ++i) {
int x, y;
cin >> x >> y >> k[i];
--x; --y;
upd(0, 0, q, lst[x], i, {x, g[x]});
g[x] = y;
lst[x] = i;
}
for (int i = 0; i < n; ++i) {
upd(0, 0, q, lst[i], q, {i, g[i]});
p[i] = i;
rk[i] = 1;
}
solve(0, 0, q, n & 1);
for (int i = 0; i < q; ++i) {
cout << ans[i] << '\n';
}
}








My Submission
can some one tell me why my solution give tle on E? i have used binary search instead of next array for next element
Your time complexity is O(n*k*log(n)), and when n=1,000,000 and k=26, the estimated time is 1,000,000*26*20=520,000,000. This is very slow.
but it should work
The line: vector v = mp[s1[j]]; creates a new vector v. You should instead use & to reference the vector in the map.
vector &v = mp[s1[j]];
thank you, got accepted after doing this small change.
Why my submissions give TLE on D problem? Submission 1 Submission 2
The line: void solve(vi P) creates a new vector P.You should instead use & to reference the vector in the solve function. like:void solve(vi& P)
In the solve function, you should use a reference pass instead of a value pass, which will create a new vector P in the local part of the function. Similar to the comments mentioned earlier, the user TeletubiGaim33 mentioned。
Is there a dp solution for F?
Consider which $$$x$$$ there does not exist any $$$y \lt x$$$ such that $$$S(x) = S(y)$$$. Excluding the obvious cases (for example, $$$y = 12349$$$ comes before $$$x = 32149$$$ because you can shuffle its prefix), $$$x$$$ is also not allowed to end with two or more $$$9$$$ (for example, for $$$x = 12399$$$, construct $$$y = 10293$$$ because you can remove two $$$9$$$ and insert a $$$0$$$ and a $$$9$$$ in the front), except for special cases such as $$$x = 1999\ldots9$$$, $$$x = 2999\ldots9$$$, ..., $$$x = 9999\ldots9$$$, and therefore, you also need to specifically consider numbers like $$$x = 900009991$$$, because even though they meet the conditions above, $$$y = 199999999$$$ paradoxically comes before it. Then you can write a digit DP to solve even $$$n \le 10^{10^6}$$$ (my submission).
another dp solution that's similar to the one described by the furry above me, but MUCH uglier: 336744397
F is very good
Can someone explain this part in the G tutorial?
Let's try to understand how to conveniently count the parity of the number of SCCs for a functional graph. Vertices that are not on cycles represent separate components, and each cycle is a separate component. If a cycle has even length, it changes the parity of the number of SCCs, while if it has odd length, it leaves it unchanged. Therefore, we are actually interested in the number of cycles of even length in the functional graph.
How do even-length SSCs contribute to the answer while the odd ones don't?
This is a problem reduction,let c=o+e c is the number of cycle,and o is the number of cycle with odd length and e is the number of cycle with even length,then obviously c mod 2=(o+e) mod 2
Nows we know o is either odd or even,if o is even then (o+e)mod2=e mod 2,if o is odd then (o+e)mod 2 = (e+1)mod 2,and it's obviously to see that no matter o is odd/even there is only a parameter which is e,so c is dependant on e,similarly you also can say eliminate e and say that c is dependant on o,just depent on which ways you are convenient to implement,its does not affect the result
Thank you
reason for tle on problem e? my time complexity is O(n*k), it should work.
Link
Time complexity is O(q * n * k) i think that is the problem. In test 9 q = 7058, n = 1e6 and k = 25 that is something equivalent to O(1e10) that n * k is happening for every query that is too much so precomputation needed instead of checking inside the query loop you should precompute it before going to the query.
Wow,the idea of F is great.This is a beautiful brute force.I've summarized the idea
First I need to think of a condition,count of numbers which follow this condition are not too more.And just search. Second I need to filter again after search.Search once for all answers is too hard.So I can set a wide condition and search,then filter.This idea is great
Educational Rounds are curse for me, while Div 1 + 2 are blessing.
Actually, you can directly use LCT to maintain the unicyclic graph and solve Problem G in $$$ O(q \log n) $$$ time.
Got FST in E. I don't know why I thought $$$\sum n \le 10^6$$$ over all queries, but there was only one $$$n$$$.
Since my solution was $$$O(nq)$$$, it got TLE. Why did this problem have so weak pretests?
317833875 My submission .
Can anyone tell why it's giving TLE , have used greedy + binary search , it should be n*k which should be fine , isn't it ?
processSubStr is O(n). O(q * n) is too slow
optimized the processSubStr . still getting TLE ?
317856556
the loop with ct is also slow, imagine abababab...
Can anyone pls explain why it is happening in problem D that if the sum of first K max element sum is atleast first K primes sum then we can make the array of size K beautiful?
Based on the description, we can decrease the element anytime we want. So for any array with element sum $$$S_0$$$, we can build another different array with $$$S \lt S_0 $$$. So we can change the first K max element to first K prime if the sum of first K max element sum is at least first K primes sum.
For example: [4,5,5] can change to [2,3,5].
Obviously, for any prime pair (x,y), gcd(x,y)=1
yeah! i have solved it before u have written it!
317853132
Question E It's a bit lengthy code, but it shouldn't get TLE, can someone help me to decrease its Time complexity.
this is the issue, worst case complexity is O(n)
But as sum of length of all queries is 1e6 at max, shouldn't this get accepted, and if not what can I do to make it faster??
you are running this loop for every query, so it causes O(q*n). You can precompute this for every index outside the query loop.
Actually I did that too and still it got TLE!!
317872056
The thing is I calculated it for every index and then got the cnt value but checking the its query, It still wasn't fast enough.
317876555 check what i changed and try to figure out how it improved the time complexity
Thank you, it was really helpful, actually inside the while loop I was using the same variable as the outer loop, so it did multiple calculations of the same index.
Really Appreciated your help.
no, even with that change, you'll still get a TLE.
The point is to use the precomputed values of the higher indices to reduce the reduntant calculations i.e DP.
I think my solution for E is a bit easier :)
I am calculating how many times all letters appear from i to n
and then for each query I am getting the first index where the subsequence will be found then use the precomputation I made above to find from this index to the end (how many times all letters appear) and then add one to it
You need 4⋅10^5 primes, so you have to use the sieve up to something like 6⋅10^6.
In Problem D, how to analyse that to get 4⋅10^5 primes, you have to go till 6⋅10^6 ?
According to the Prime Number Theorem, the number of primes $$$p \le n$$$ for some $$$n$$$ is $$$\approx n/\mathrm{ln} \; n=4\cdot 10^5$$$. Solving this, we get $$$n \approx 6 \cdot 10^6$$$.
Alternatively, you could just run a sieve locally till about $$$10^7$$$, and check how big an $$$n$$$ it takes to reach $$$4 \cdot 10^5$$$ primes.
Yes, I did the second one and I was like binary searching around it (joking not actually bs) coz I was too afraid as I am using Python and this idea was a bit new for me. Also, thanks for sharing the first way I always forget about it
Is it possible to do G without offline dynamic connectivity?
Seems like what would be required is to maintain the cycles + ordering, but I'm not sure if that's at all possible. If you ignore the rewiring of the graph, the code pretty straightforward
My attempt: https://codeforces.me/contest/2104/submission/319962878
Yes, it can be solved with online queries in O((n+q)log(n)): https://codeforces.me/contest/2104/submission/324625656 But the constant factor is very high, so it still takes over half the time limit...
Here is a brief hand-wavy explanation of my approach:
Think of each component in the graph as a tree + 1 extra edge to form a cycle. The root of this tree should be a node in the cycle. For all other nodes, g_i is the parent of node i. The extra edge that forms the cycle is stored in the root as a "lazy link" (this will become important later).
These trees are stored in a treap, where we make sure that the nodes of each tree are contiguous and in pre-order with respect to some dfs-traversal. This ensures that each subtree is stored in a contiguous range of the treap. We use this treap to store, for each node, the root of the tree it belongs to, and the distance to that root.
To re-assign some g_i, we first detach the subtree of node i from its tree. This is done by moving a contiguous range of the treap, and doing range updates to update the root and distance information. We then check if the "lazy link" in the old tree bridges the two new trees. If it does, we merge them back together by linking the root of the old tree to the node it should be connected to. This can be done in the same way, by moving a contiguous range and doing some range updates. Finally, we add the new edge, which either involves adding a "lazy link" if it is within the same tree, or linking the tree to some node in another tree in the same way as before.
The number of even cycles can be maintained by checking the parity of distances to the root every time a "lazy link" is added or removed.
This will be the first Div. 2 — D I've ever solved
C can be done in an even better way than brute force, for Alice to win you only need to check if she has (N and N-1) or (N and 1) or she needs to have N-1 cards. In any other case, Bob wins because he can see what card Alice chose and will have a better card.
My submission: 322895289
Further Explanation: (You are Alice) - If you have N and N-1, you can beat any of the Bob's card by choosing N-1 - If you have N and 1, you can beat any of the Bob's card by choosing N - If you have N-1 number of cards, whatever card Bob has, you win: — if Bob has 1, you have N-1 — if Bob has N, you have 1 — if Bob has any other card, you have N - In any other case, Bob will have a card to beat you.
In G editorial "If a cycle has even length, it changes the parity of the number of SCCs"
I don't get it...
my first div 2 d ever in practise i love whoever made this contest .. many many thanks
In problem F you can just directly store all $$$568725$$$ numbers in your code (while code limit size is $$$65536$$$ characters) by computing their difference array, applying LZW transform to it and then encoding the result into base $$$92$$$ instead of base $$$10$$$.
Resulting string is only ~$$$26000$$$ characters long, all what remained to do is to decode it by doing all the described steps in reverse to recover the initial array of $$$568725$$$ numbers.
Here is my implementation with ~$$$35000$$$ characters: 366723031
Can we solve problem E by binary search on answer??