Top Recent Blog Posts
TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!) Editorial
By rsj, history, 2 days ago,
1787A - Exponential Equation
For even $$$n$$$, a key observation is that $$$x=1,y=\dfrac{n}{2}$$$ is always legit.
And for odd $$$n$$$, notice that $$$x^yy+y^xx=xy(x^{y-1}+y^{x-1})$$$. So if $$$x$$$ or $$$y$$$ is an even number, obviously $$$x^y y+y^x x$$$ is an even number. Otherwise if both $$$x$$$ and $$$y$$$ are all odd numbers , $$$x^{y-1}$$$ and $$$y^{x-1}$$$ are all odd numbers, so $$$x^{y-1}+y^{x-1}$$$ is an even number, and $$$x^yy+y^xx$$$ is also an even number. That means $$$x^yy+y^xx$$$ is always even and there's no solution for odd $$$n$$$.
1787B - Number Factorization
First, $$$a_i^{p_i}$$$ is equivalent to the product of $$$a_i^{1}$$$ for $$$p$$$ times, so it is sufficient to set all $$$p_i$$$ to $$$1$$$.
Decomposite $$$n$$$ to some prime factors, greedily choose the most number of distinct prime numbers, the product is the maximum.
pair<int, int> s[110];
int d[110];
void get() {
int n, l = 0, i, c;
for (i = 2; i * i <= n; i++) {
if (n % i == 0) {
while (n % i == 0) c++, n /= i;
s[++l] = make_pair(c, i);
if (n != 1) s[++l] = make_pair(1, n);
sort(s + 1, s + l + 1), d[l + 1] = 1;
for (i = l; i >= 1; i--) d[i] = d[i + 1] * s[i].second;
for (i = 1; i <= l; i++) if (s[i].first != s[i - 1].first) ans += d[i] * (s[i].first - s[i - 1].first);
cout << ans << endl;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
while (T--) get();
1787C - Remove the Bracket
This is the reason why the problem was named as Remove the Bracket.
$$$ \begin{aligned} \text{Product} &= a_1 \cdot a_2 \cdot a_3 \cdot \ldots \cdot a_n = \\ &= a_1 \cdot (x_2+y_2) \cdot (x_3+y_3) \cdot \ldots \cdot (x_{n-1}+y_{n-1}) \cdot a_n = \\ &\overset{\text{?}}{=} a_1 \cdot x_2+y_2 \cdot x_3+y_3 \cdot \ldots \cdot x_{n-1}+y_{n-1} \cdot a_n. \end{aligned} $$$
However, We discussed to remove it on 28th Jan in the statement. Really sorry for inconvenience of the statement!
$$$(x_i-s)(y_i-s)\geq 0$$$ tells us either $$$\min(x_i,y_i)\geq s$$$ or $$$\max(x_i,y_i) \leq s$$$, so pickable $$$x_i$$$ is a consecutive range.
Just consider $$$(x_i+y_i)$$$, remove the bracket then it turns to $$$\ldots+ y_{i-1}\cdot x_i+y_i\cdot x_{i+1}+\ldots$$$. When $$$y_{i-1} = x_{i+1}$$$, the result is constant, so we assume that $$$y_{i-1} < x_{i+1}$$$.
If $$$x_i$$$ does not hit the maximum, increase $$$x_i$$$ by $$$1$$$ and decrease $$$y_i$$$ by $$$1$$$, the result will increase by $$$y_{i-1}$$$ and decrease by $$$x_{i+1}$$$, which means decrease by $$$x_{i+1}-y_{i-1}$$$, always better. So $$$x_i$$$ will either hit the maximum or the minimum. Thus, each number has only two ways of rewriting that might be optimal.
This can be done with DP.
const int N = 200005;
long long f[N][2],x[N],y[N];
int i,n,s,j;
cin>>n>>s;
for(i=1; i<=n; i++) {
cin>>j;
if(i==1||i==n) x[i]=y[i]=j;
else if(j<=s) x[i]=0,y[i]=j;
else x[i]=s,y[i]=j-s;
f[1][0]=f[1][1]=0;
f[i][0]=min(f[i-1][0]+y[i-1]*x[i],f[i-1][1]+x[i-1]*x[i]);
f[i][1]=min(f[i-1][0]+y[i-1]*y[i],f[i-1][1]+x[i-1]*y[i]);
cout<<f[n][0]<<endl;
int T; cin>>T;
while(T--) get();
1787D - Game on Axis
First, add directed edges from $$$i$$$ to $$$i+a_i$$$. If there's a path from $$$1$$$ to $$$x$$$ satisfying $$$x<1$$$ or $$$x>n$$$, the game end. We consider all nodes $$$x$$$ satisfying $$$x<1$$$ or $$$x>n$$$ to be the end node, and we call the path which starts at node $$$1$$$ until it loops or ends the key path.
If we can end the game at first:
Let's count the opposite — the number of invalid pairs. The graph with the end node forms a tree. Changing edges not on the key path is always legal. If changing the edges on the key path, for node $$$x$$$, we can only change its successor to nodes on the tree with the end node except its precursor or itself.
For the answer, use dfs to count the number of precursors for every nodes on this tree, which is the size of subtree.
If we cannot end the game at first:
We can only change the edge on the key path, redirect them to any nodes on the tree with the end node.
int a[N], v[N], s[N];
int to;
E *nex;
} *h[N];
void add(int u, int v) {
E *cur = new E;
cur->to = v, cur->nex = h[u], h[u] = cur;
void dfs(int u) {
s[u] = v[u] = 1;
for (E *cur = h[u]; cur; cur = cur->nex)
dfs(cur->to), s[u] += s[cur->to];
int i, j, n;
for (i = 1; i <= n + 1; i++)
s[i] = v[i] = 0, h[i] = 0;
for (i = 1; i <= n; i++) {
cin >> a[i], a[i] = min(i + a[i], n + 1);
if (a[i] <= 0) a[i] = n + 1;
add(a[i], i);
dfs(n + 1);
long long ans = 0;
if (v[1] == 1) {
j = 1; do { ans -= s[j] + (n - s[n + 1] + 1), j = a[j]; }
while (j != n + 1);
ans += 1ll * n * (2 * n + 1);
j = 1; do { ans += (n + s[n + 1]), v[j] = 2, j = a[j]; }
while (v[j] != 2);
1787E - The Harmonization of XOR
First, we observe that three subsequences can combine into one, so we only need to care about the maximum number of subsequences.
Make subsequences in the form of $$$[a,a \oplus x]$$$ as much as possible, leave $$$[x]$$$ alone if possible, and the rest becomes a subsequence. This would be optimal.
Proof:
Let $$$B$$$ be the highest bit of $$$x$$$, i.e. the $$$B$$$-th bit of $$$x$$$ is on.
Let $$$M$$$ be the number of numbers from $$$1$$$ to $$$n$$$ satisfying the $$$B$$$-th bit is on.
Then the number of subsequences must be smaller than or equal to $$$M$$$, since there's at least one $$$B$$$-th-bit-on number in each subsequence.
These $$$B$$$-th-bit-on numbers XOR $$$x$$$ must be smaller than themselves, so we can always obtain $$$M$$$ subsequences.
Bonus Problem: What if $$$x=0$$$?
1787F - Inverse Transformation
Consider another question: Given the initial permutation $$$a$$$ and find the permutation $$$a'$$$ on the $$$k$$$-th day?
After a day, element $$$x$$$ will become $$$\sigma(x) = a_x$$$, so we can consider the numbers as nodes, and we add directed edges from $$$x$$$ to $$$a_x$$$. Note that $$$a$$$ is a permutation, so the graph consists of several cycles. After one day, $$$a_x$$$ will become $$$a_{\sigma(x)} = a_{a_x}$$$ -- the second element after $$$x$$$ in the corresponding cycle. Similarly, we can conclude that $$$a_x$$$ will become the $$$2^k$$$-th element after $$$x$$$.
If a cycle $$$c$$$ has an odd length $$$l$$$. Because $$$2^k \bmod l \neq 0$$$, the cycle will never split, the element $$$c_x$$$ will become $$$c_{(x+2^k)\bmod l}$$$ on the $$$k$$$-th day. Otherwise, if a cycle $$$c$$$ has an even length $$$l$$$, after the first day, $$$c_1$$$ will become $$$c_3$$$, $$$c_3$$$ will become $$$c_5$$$, $$$\ldots$$$, $$$c_{2l-1}$$$ will become $$$c_1$$$. And so will the even indices -- that means the original cycle split into two small cycles of the same size $$$\dfrac{l}{2}$$$. So, if a cycle of length $$$l = p\cdots 2^q$$$ will split into $$$2^q$$$ small cycles of length $$$p$$$ after exactly $$$q$$$ days.
Because the length of a cycle $$$l\le n$$$, so we can perform the transformation for at least $$$\log n$$$ days to split all the cycles of even lengths into cycles of odd lengths. Then we can use our conclusion to calculate the final permutation on the $$$k$$$-th day.
Now let's back to our question. We observed that $$$\sum\limits^n_{i=1} \dfrac{1}{f(i)}$$$ means the number of cycles in the original graph. Then we need to construct the original permutation $$$a$$$ of the least possible cycle. As we've said before, the cycle of length $$$l = p\cdots 2^q$$$ will split into $$$2^q$$$ small cycles of length $$$p$$$ after exactly $$$q$$$ days. So we can count all the cycles in permutation $$$a'$$$.
For cycles of odd length $$$l$$$, we can combine some of them. Specifically, we can combine $$$2^q$$$ cycles into a cycle of length $$$l\cdots 2^q$$$ in the original permutation $$$a$$$. Note that $$$q$$$ must be less than or equal to $$$k$$$.
And for cycles of even length $$$l$$$, we can also combine them. But because they haven't been split on the $$$k$$$-th day, we must combine exactly $$$2^k$$$ cycles. So if the number of these cycles isn't a multiple of $$$2^k$$$, just print \t{NO}.
int dest[N], visit[N], ans[N], mp[N], ansinv[N], sp;
int pow2(int y, int M) {
long long x = 2, ans = 1;
while (y) {
if (y & 1) ans = ans * x % M;
x = x * x % M, y >>= 1;
return ans % M;
vector<int> cyc[N];
sp = 0;
int n, i, j, m, z, o;
cin >> n >> m;
for (i = 1; i <= n; i++) cyc[i].clear();
for (i = 1; i <= n; i++) visit[i] = 0, cin >> dest[i];
if (visit[i]) continue;
j = i, z = 0; do { ++z, visit[j] = 1, j = dest[j]; } while (j != i);
cyc[z].push_back(i);
int lim = pow2(min(m, 20), 1e9), s = 0, d, t, num, cp;
if (!cyc[i].size()) continue;
int siz = cyc[i].size();
if (i % 2 == 0 && siz % lim) {
cout << "NO" << endl; return;
cp = -1;
for (j = lim; j > 0; j /= 2) {
while (siz >= j) {
siz -= j, d = s + j * i, t = j;
while (t--) {
++s, ++cp, num = s, o = cyc[i][cp];
ans[num] = o, num += pow2(m, i * j);
if (num > d) num -= j * i;
o = dest[o];
} while (o != cyc[i][cp]);
for (int k = sp + 1; k < sp + j * i; k++) mp[k] = k + 1;
mp[sp + j * i] = sp + 1, sp += j * i, s = d;
cout << "YES" << endl;
for (i = 1; i <= n; i++) ansinv[ans[i]] = i;
for (i = 1; i <= n; i++) cout << ans[mp[ansinv[i]]] << " \n"[i == n];
ios::sync_with_stdio(0), cin.tie(0);
1787G - Colorful Tree Again
On the original tree, all good paths are constant and one edge can only be on at most one good path.
For each color $$$c$$$, find all edges of color $$$c$$$, and judge if they form a simple path by counting the degree of each node on the path. If so, mark these edges and calculate the length.
When a query changes a node $$$u$$$, several paths across $$$u$$$ are infected.
If we are destroying node $$$2$$$, path $$$8-1-2-3$$$, $$$2-4-9$$$, $$$2-5$$$, and $$$7-6-2-10$$$ will not be good paths.
A brute-force solution is to use a priority queue, delete length of bad paths, find the maximum length.
To gain better time complexity, treat two cases of influenced paths separately:
Only one path that goes from the ancestor of $$$u$$$ to its subtree, like $$$8-1-2-3$$$.
All paths whose LCA is $$$u$$$ will be infected, like $$$2-4-9$$$, $$$2-5$$$, and $$$7-6-2-10$$$.
This inspires us to maintain these paths according to their LCAs. That is, use priority queue on every node $$$u$$$ to maintain all paths whose LCA is $$$u$$$.
Then use a global priority queue to maintain the answer of all paths maintained on all nodes.
UPD: An alternative implementation using segment tree comment link.
1787H - Codeforces Scoreboard
Have to declare that we built up Problem H from zero. ;)
Since $$$\max (b_i-k_i\cdot t,a_i) = b_i - \min(k_i\cdot t, b_i - a_i)$$$, we can pre-calculate the sum of $$$b_i$$$. Let $$$c_i = b_i - a_i$$$. Now our mission is to minimize the sum of $$$\min(k_i\cdot t, b_i - a_i)$$$.
If we assume $$$\min(k_i\cdot t, b_i - a_i) = k_i\cdot t$$$ for some $$$i$$$, sort these problems in descending order of $$$k_i$$$, then assign $$$1,2,3,\ldots$$$ to their $$$t$$$ in order. For $$$\min(k_i\cdot t, b_i - a_i) = b_i - a_i$$$, they can be directly calculated.
There comes a DP solution: Let $$$f_{i,j}$$$ be the minimum sum, when considering first $$$i$$$ problems (after sorting), $$$j$$$ problems of them satisfying $$$\min(k_i\cdot t, b_i - a_i) = k_i\cdot t$$$.
$$$ f_{i,j}=\left\{ \begin{aligned} f_{i-1,j}+c_i & & j=0 \\ \min\{f_{i-1,j}+c_i,f_{i-1,j-1}+k_i\cdot j\} & & j>0 \end{aligned} \right. $$$
The time complexity is $$$O(n^2)$$$.
We can find that $$$f_{i,j}$$$ is convex. Proof below:
Let $$$g_{i,j}=f_{i,j}-f_{i,j-1}$$$.
Thus $$$f_{i,j}=f_{i,0}+\sum\limits_{k=1}^jg_{i,k}$$$, rewrite this formula with the original recursive formula.
$$$f_{i,0}+\sum_{k=1}^{j}g_{i,k}=\min\{f_{i-1,0},\sum_{k=1}^{j}g_{i-1,k}+c_i,f_{i-1,0}+\sum_{k=1}^{j-1}g_{i-1,k}+k_i\cdot j\}$$$ $$$c_i+\sum_{k=1}^{j}g_{i,k}=\sum_{k=1}^{j-1}g_{i-1,k}+\min\{g_{i-1,j}+c_i,k_i\cdot j\}$$$
Let $$$j-1$$$ be $$$j$$$
$$$c_i+\sum_{k=1}^{j-1}g_{i,k}=\sum_{k=1}^{j-2}g_{i-1,k}+\min\{g_{i-1,j-1}+c_i,k_i\cdot (j-1)\}$$$
Subtract the above two formulas from each other
$$$g_{i,j}=g_{i-1,j-1}+\min\{g_{i-1,j}+c_i,k_i\cdot j\}-\min\{g_{i-1,j-1}+c_i,k_i\cdot (j-1)\}$$$
Because $$$k$$$ is monotone non-increasing, so we can use mathematical induction to proof that for $$$j$$$, the increase speed of $$$g_{i-1,j}$$$ is faster than that of $$$k_i\cdot j$$$. We can find a critical value $$$M$$$ that $$$\forall j\le M, g_{i,j}<k_i\cdot j$$$ and $$$\forall j>M,g_{i,j}>k_i\cdot j$$$.
So compared $$$g_i$$$ with $$$g_{i+1}$$$, the first part of the sequence remains unchanged, and the last part is added with $$$k_i$$$, with an additional number $$$k_i\cdot j$$$ in the middle, where $$$j$$$ is the maximum number satisfied $$$g_{i-1,j-1}\le k_i \cdot j$$$.
Use the treap to maintain this sequence, which might be called the slope trick.
1787I - Treasure Hunt
First, we observe that: $$$\max\limits_{l>p\,\texttt{or}\,r\leq p}{(\sum\limits_{i=1}^{p}{a_i}+\sum\limits_{i=l}^{r}{a_i})}=\max\limits_{p=1}^{n}{\sum\limits_{i=1}^{p}{a_i}}+\max\limits_{l,r}{\sum\limits_{i=l}^{r}{a_i}}$$$.
Proof: We can proof it by contradiction. Define $$$g(l,r,p)$$$ as $$$\sum\limits_{i=1}^{p}{a_i}+\sum\limits_{i=l}^{r}{a_i}$$$. Suppose $$$l\leq p<r$$$ when $$$g(l,r,p)$$$ hits the maximum value. If $$$\sum\limits_{i=p+1}^{r}{a_i}\geq 0$$$, $$$g(l,r,r)\geq g(l,r,p)$$$, otherwise $$$g(l,p,p)> g(l,r,p)$$$. So the above observation is always correct.
So we can divide the problem into two parts: $$$\max\limits_{p=1}^{n}{\sum\limits_{i=1}^{p}{a_i}}$$$ and $$$\max\limits_{l,r}{\sum\limits_{i=l}^{r}{a_i}}$$$.
For $$$\max\limits_{p=1}^{n}{\sum\limits_{i=1}^{p}{a_i}}$$$, it's easy to solve it by using a stack to calculate the prefix maximum value, and then calculate the answer.
And for $$$\max\limits_{l,r}{\sum\limits_{i=l}^{r}{a_i}}$$$, consider divide and conquer. For a part $$$[l,r]$$$,let $$$m=\lfloor \frac{l+r}{2}\rfloor$$$. Define $$$h(L,R)$$$ as $$$\max\limits_{L\leq l,r\leq R}{\sum\limits_{i=l}^{r}{a_i}}$$$. We want to calculate the sum of $$$h(L,R)$$$ satisfied $$$l\leq L\leq m<R < r$$$. Obviously $$$h(L,R) = \max(\max(h(L,m),h(m+1,R)),\max\limits_{L\leq p\leq m}{\sum\limits_{j=p}^{m}{a_j}}+\max\limits_{m<p\leq R}{\sum\limits_{j=m+1}^{p}{a_j}})$$$, and it's easy to calculate above four value in the time complexity of $$$O(r - l)$$$. We can use binary search to calculate the maximum value. So the problem can be solved in the time complexity of $$$O(n\log ^2n)$$$.
But it's not good enough. We can solve it in the time complexity of $$$O(n\log n)$$$ based on the following theorem:
Define $$$f(p)$$$ as $$$\max\limits_{1\leq q\leq p}{\sum\limits_{i=1}^q{a_i}}$$$. $$$h(1,p)-f(p)$$$ is non-decreasing.
Proof: Actually, if we extend the first theorem, we will find $$$l>p$$$ or $$$r=p$$$ :
If $$$l>p$$$, so $$$\sum\limits_{i=p+1}^r{a_i}<0$$$. When we add an element at the back of the sequence: If $$$\sum\limits_{i=1}^{len}{a_i}>\sum\limits_{i=1}^p{a_i}$$$, $$$p$$$ and $$$r$$$ become $$$len$$$ at the same time. So $$$\Delta f(len)<\Delta h(1,len)$$$ since $$$\sum\limits_{i=p+1}^r{a_i}<0$$$. Otherwise if $$$\sum\limits_{i=1}^{len}{a_i}\leq \sum\limits_{i=1}^p{a_i}$$$, $$$\Delta f(len)=0$$$ while $$$\Delta h(1,len) \geq 0$$$. So the theorem always holds in this circumstance.
If $$$p=r$$$, $$$\Delta f(len)=\Delta h(1,len)$$$, so the theorem holds too.
Because of the theorem, we can replace binary search by two pointers. So the final time complexity is $$$O(n\log n)$$$.
I'm really sorry for the unsatisfactory problems and the tough 3 hours ;)
However, I still hope you can enjoy the problems after the contest. The editorial hasn't been fully checked, so feel free to comment if there're errors, typos or you have questions about them. We'll check them out tomorrow. Thanks!
Expand | Full text and comments »
Tutorial of TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!)
How Can I Persuade My Mother to Join Codeforces Contest?
By chenye3N, history, 2 days ago,
I'm in China.Because of the time difference,almost every contest starts at 22:35.My mother thought it was too late,and she disagreed.What should I do?
chenye3N
xor basis tutorial
By tallbee23, 9 hours ago,
level: **VERY HARD*
hello today am gonna tech xor basis/ but proofs are very hard so no proof. it inituavautve
okl we hvae arary basis[37] mane basis[i] mst's i so we habvee
flolpowing codem for is to isnert x in tonhe the set;/ buist it's bveyr har adsso i wont';t exp[alaomn
include<stdc++/bits.h>
using namespace = std; typedef int long long; void insert(x){ for(i in 30 to 0) if(x's i'th bit is not 1) : ccinonitue if(basis[i] == -1) basis[i] = x; break; else x = x $$$\oplus$$$ basis[i] } ~~~~~
isneritng is same aas qureying hwo to i mane queery if ew cna maefae the X swith gigven xorn basis ealneaments
fi yow odsndint udnestsnad yoib can askj in comenents
UPD: code for query
using namespace = std; typedef int long long; void insert(x){ for(i in 30 to 0) if(x's i'th bit is not 1) : ccinonitue if(basis[i] == -1) return false; else x = x $$$\oplus$$$ basis[i] return true;} ~~~~~
tallbee23
Every Technique and Algorithm I Used to Become Grandmaster
By Noble_Mushtak, history, 40 hours ago,
Hi everyone, I became grandmaster today so I decided to go down memory lane and review every problem I have ever done in a CodeForces contest to look back and see every technique and algorithm I had to use to become a grandmaster. I am not sure how useful this is, I mostly think it's fun to look at all the old solutions I wrote and how different it was from how I write code now. The main takeaway is that, as many people have said before, you don't need to know or memorize a bunch of advanced algorithms to become grandmaster. As you will see, there are many problems where I just used "ad hoc reasoning," meaning there's not a standard technique I used to solve the problem and you just need to make some clever mathematical observations to solve the problem. Also, there are many popular algorithms that I have never needed in a CodeForces contest despite being a grandmaster:
Sparse tables, Fenwick trees, and segment trees
String algos, like rolling hashes, Knuth-Morris-Pratt, suffix arrays, and Aho-Corasick
Shortest path algos, like Dijkstra's algorithm, Bellman-Ford, and Floyd-Warshall
Flow algos, like Edmonds-Karp, Dinic's, and push-relabel
Convex hull trick
Fast Fourier transform and number theoretic transform
This isn't to say that learning algorithms is bad—I love reading cp-algorithms.com and learning new algorithms—and I have used many of these algorithms in other contests, like CodeChef, ICPC, and Google Code Jam, but practicing consistently and getting better at ad hoc reasoning and your general problem-solving abilities matter much more.
CodeForces Round #362 (Div. 2): Rating went from 1500 to 1504 (back then, default rating was 1500 instead of 0)
Problem A: Ad hoc reasoning and math
Problem B: Basic string manipulation
Codeforces Round #363 (Div. 2): Rating went from 1504 to 1536 (+36)
Problem A: Brute force
Problem B: Brute force
Problem C: Ad hoc reasoning and basic bitmasks (there is a dynamic programming solution, but that's not how I solved it)
Problem B: Brute force and bitwise operations
Problem C: Ad hoc reasoning and math
Codeforces Round #570 (Div. 3): Rating went from 1566 to 1732 (+166)
Problem A: Basic number theory
Problem B: Ad hoc reasoning and math
Problem D: Greedy and priority queue
Problem E: Ad hoc reasoning with strings (there is a BFS solution, but that's not how I solved it)
Problem H: Dynamic programming (I used the count unique subsequences of a given length algorithm)
Educational CodeForces Round 68: Rating went from 1732 to 1766 (+44)
Problem B: Brute force and row/column sums
Problem C: Ad hoc reasoning with strings and subsequences
Problem D: Game theory
CodeForces Global Round 4: Rating went from 1776 to 1807 (+31)
Problem A: Greedy
Problem B: Dynamic programming
Problem C: Binary exponentiation
Problem D: Ad hoc reasoning with graphs
Problem E: Deques
Educational Codeforces Round 74: Rating went from 1807 to 1920 (+113)
Problem B: Greedy and sorting
Problem C: Greedy
Problem D: Ad hoc reasoning and combinatorics
Codeforces Round #600 (Div. 2): Rating went from 1920 to 1877 (-43)
Problem C: Sorting, prefix sums, and dynamic programming
Problem D: Depth-first search and connected components
Problem B: Ad hoc reasoning with graphs and sorting
Problem C: Ad hoc reasoning with graphs and permutations
Problem D: Ad hoc reasoning with grids
Problem E1: Greedy
Codeforces Global Round 14: Rating went from 2005 to 1877 (-128)
Problem A: Ad hoc reasoning with sorting
Problem B: Ad hoc reasoning with number theory
Problem C: Greedy and priority queue
Deltix Round, Spring 2021: Rating went from 1877 to 1975 (+98)
Problem A: Ad hoc reasoning with simulations
Problem C: Stacks
CodeForces LATOKEN Round 1: Rating went from 1975 to 1974 (-1)
Problem A: Ad hoc reasoning with grids
Problem C: Cycle decomposition and binary exponentiation
Problem D: Ad hoc reasoning with trees
Problem C: Ad hoc reasoning with number theory
Problem D: Binary exponentiation and dynamic programming
Problem E1: Dynamic programming and combinatorics (I used the count permutations with given number of inversions algorithm, the numbers of permutations with a given number of inversions are also known as Mahonian numbers)
Hello 2022: Rating went from 2132 to 2085 (-47)
Problem B: Greedy
Problem C: Cycle decomposition
Codeforces Round #765 (Div. 2): Rating went from 2085 to 2092 (+7)
Problem A: Greedy and bitwise operations
Problem B: Ad hoc reasoning and maps
Problem C: Dynamic programming
Educational Codeforces Round 122: Rating went from 2092 to 2168 (+76)
Problem A: Ad hoc reasoning with number theory
Problem C: Brute force
Problem D: Dynamic programming
Problem E: Kruskal's algorithm and binary search tree maps
Problem B: Ad hoc reasoning with simulations
Codeforces Global Round 23: Rating went from 2138 to 2239 (+101)
Problem B: Greedy with stacks
Problem C: Ad hoc reasoning with permutations
Problem D: Tree DP
Problem E: Ad hoc reasoning, with inspiration from binary search
Codeforces Global Round 24: Rating went from 2239 to 2291 (+52)
Problem C: Prefix sums and maps
Problem D: Modular arithmetic, extended Euclidean algorithm, and combinatorics
Problem E: Greedy, sorting, and binary search tree sets
Good Bye 2022: 2023 is NEAR: Rating went from 2291 to 2358 (+67)
Problem A: Greedy and binary search tree sets
Problem B: Ad hoc reasoning with permutations
Problem C: Ad hoc reasoning with number theory (I did use Miller-Rabin, but only to generate the primes <100, which could have been hardcoded instead)
Problem D: Disjoint set union, and I also used DFS trees for the intuition behind this solution
Problem E: Tree DP and extended Euclidean algorithm
Problem D: IntervalContainer and maps
Problem E: Sorting and ad hoc reasoning with graphs and strongly connected components
TypeDB Forces 2023: Rating went from 2331 to 2416 (+85)
Problem B: Miller-Rabin, Pollard's rho algorithm, and number theory
Problem D: Tarjan's SCC algorithm and DP over directed acylic graphs
Problem E: Greedy and bitwise operations
Problem F: Binary exponentiation, extended Euclidean algorithm, and cycle decomposition
Noble_Mushtak
Codeforces Round #847 (Div. 3) Editorial
By Vladosiya, history, 3 days ago, translation,
1790A - Polycarp and the Day of Pi
Idea: MikeMirzayanov
Tutorial is loading...
t = int(input())
pi = '31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679'
for _ in range(t):
n = input() + '#'
for i in range(len(n)):
if pi[i] != n[i]:
print(i)
1790B - Taisia and Dice
Idea: Gornak40
const int MAXN = 55;
int n, s1, s2;
vector<int> res;
void solve() {
res.clear();
int d = s1 - s2;
for (; s2 >= d; s2 -= d)
res.push_back(d);
if (s2) res.push_back(s2);
for (int i = 0; i < res.size() && res.size() + 1 < n;) {
if (res[i] == 1) {
++i;
--res[i];
res.push_back(1);
int t; cin >> t;
cin >> n >> s1 >> s2;
solve();
sort(res.begin(), res.end());
for (int x: res)
cout << x << ' ';
1790C - Premutation
#include "bits/stdc++.h"
void solve(){
vector<vector<int>>perm(n, vector<int>(n - 1));
vector<int>p(n, 0);
vector<int>cnt(n + 1, 0);
for(int i = 0; i < n; i++){
p[i] = i + 1;
for(int j = 0; j < n - 1; j++){
cin >> perm[i][j];
if(j == 0) cnt[perm[i][j]]++;
for(int i = 1; i <= n; i++){
if(cnt[i] == n - 1){
p[0] = i;
if(perm[i][0] != p[0]){
p[j + 1] = perm[i][j];
for(int i = 0; i < n; i++) cout << p[i] << ' ';
while(t--){
1790D - Matryoshkas
#include <set>
vector<int> a(n);
map<int, int> cnt;
set<int> b;
for (int i = 0; i < n; ++i) {
cin >> a[i];
cnt[a[i]]++;
b.insert(a[i]);
b.insert(a[i] + 1);
int last = 0;
int res = 0;
for (auto x: b) {
int c = cnt[x];
res += max(0, c - last);
last = c;
cout << res << '\n';
for (int i = 0; i < t; ++i) {
1790E - Vlad and a Pair of Numbers
Idea: Vladosiya
x = int(input())
a = x
for i in range(32, -1, -1):
if x & (1 << i) > 0:
if 2 * x - a - b >= (2 << i):
a += 1 << i
b += 1 << i
if a + b == 2 * x and a ^ b == x:
print(a, b)
1790F - Timofey and Black-White Tree
Idea: molney
const int MAXN = 200200;
const int INF = 1e9;
int n, ANS = INF;
int crr[MAXN], dist[MAXN], res[MAXN];
bool clr[MAXN];
vector<int> gr[MAXN];
void init() {
ANS = INF;
for (int v = 0; v < n; ++v)
gr[v].clear();
fill(dist, dist + n, INF);
memset(clr, 0, n);
void dfs(int v, int p) {
if (dist[v] >= ANS) return;
if (clr[v]) ANS = min(ANS, dist[v]);
for (int u: gr[v]) {
if (u == p) continue;
if (dist[v] + 1 < dist[u]) {
dist[u] = dist[v] + 1;
dfs(u, v);
} else ANS = min(ANS, dist[v] + 1 + dist[u]);
dist[*crr] = 0;
dfs(*crr, -1);
clr[*crr] = true;
dist[crr[i]] = 0;
dfs(crr[i], -1);
clr[crr[i]] = true;
res[i] = ANS;
int gorilla; cin >> gorilla;
while (gorilla--) {
cin >> n >> *crr, --(*crr);
cin >> crr[i], --crr[i];
int v, u; cin >> v >> u, --v, --u;
gr[v].push_back(u);
gr[u].push_back(v);
cout << res[i] << ' ';
cout << '\n';
1790G - Tokens on Graph
Idea: DmitriyOwlet
#include<bits/stdc++.h>
void solve()
vector<int> token(n), boni(n);
vector<vector<int>> g(n);
vector<int> good(n);
cin >> m;
int p, b;
cin >> p >> b;
for(int i = 0; i < p; i++)
cin >> x;
--x;
token[x] = 1;
for(int i = 0; i < b; i++)
boni[x] = 1;
for(int i = 0; i < m; i++)
cin >> x >> y;
--y;
g[x].push_back(y);
g[y].push_back(x);
for(int i = 0; i < n; i++)
for(auto x : g[i])
if(boni[i] && boni[x]) good[i] = 1;
set<int> good_tokens;
set<int> not_so_good_tokens;
if(token[i] && good[x]) good_tokens.insert(i);
else if(token[i] && boni[x]) not_so_good_tokens.insert(i);
vector<int> d(n, int(1e9));
queue<int> q;
d[0] = 0;
q.push(0);
while(!q.empty())
int k = q.front();
q.pop();
for(auto x : g[k])
if(d[x] > d[k] + 1)
d[x] = d[k] + 1;
if(boni[x]) q.push(x);
bool has_ans = false;
if(!token[i] || d[i] > n) continue;
has_ans |= (!good_tokens.empty() && (*good_tokens.begin() != i || *good_tokens.rbegin() != i));
int cnt = not_so_good_tokens.size();
if(not_so_good_tokens.count(i)) cnt--;
has_ans |= d[i] <= 1 + cnt;
cout << (has_ans ? "YES" : "NO") << endl;
ios_base::sync_with_stdio(0);
freopen("input.txt", "r", stdin);
int tc = 1;
cin >> tc;
for(int i = 0; i < tc; i++)
Tutorial of Codeforces Round #847 (Div. 3)
Vladosiya
I made a YouTube channel!
By Kita, 44 hours ago,
Hey guys, about a month ago I made a YouTube channel, where I post video animated editorials to some questions I have solved in-contest that were cool or interesting to me. The problems I have made editorial videos on are:
1787C - Remove the Bracket (today's contest problem C)
1775D - Friendly Spiders
1782D - Many Perfect Squares
1775A2 - Gardener and the Capybaras (hard version)
1783D - Different Arrays
1768D - Lucky Permutation
1779A - Hall of Fame
Please tell me what you think of them and let me know if you have any suggestions so I can improve my videos. Thank you so much!!
youtube, editorial, cool, manim
1787-C leaked on YT during contest
By bajelega, 13 hours ago,
When will the plagiarism check run? In TypeDB's round, 1787-C, Remove brackets was leaked on youtube and many cheaters did it disrupting the standings.
UPD: I don't cheat. Cheat is a dishonor! I just found the problem name on a youtube channel a day after the contest! And this is unfair harming fair contestants. I hope plag check is run soon so those cheaters are skipped. And I won't say the name of the channel so it is not an advertisement. Please, upvote so admins skip cheaters and standings become better!
bajelega
What a bad luck for Radewoosh
By speedy_boy, history, 2 days ago,
see standings
Radewoosh deserved first.
speedy_boy
AtCoder Regular Contest 155 Announcement
By maroonrk, history, 3 days ago,
We will hold AtCoder Regular Contest 155.
Contest URL: https://atcoder.jp/contests/arc155
Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230129T2100&p1=248
Number of Tasks: 6
Writer: chinerist
Tester: tatyam, satashun
Rated range: — 2799
The point values will be 400-500-700-800-900-1000.
We are looking forward to your participation!
maroonrk
Click here if you want to know your future CF rating
By jerefigo, history, 26 hours ago,
If you want a (very) rough estimate of your future CF rating and you're tired of waiting for a response in stefdasca's famous post, then wait no longer! I present to you this simple repo that performs logarithmic regression over your rating history.
This is by no means perfect, but you can help with that! Write your suggestions in the comments.
Edit: Apparently, as suggested by tgp07, you can run the code online.
jerefigo