You can use several words in query to find by all of them at the same time. In addition, if you are lucky search understands word forms and some synonyms. It supports search by title and author. Examples:

• 305 — search for 305, most probably it will find blogs about the Round 305
• andrew stankevich contests — search for words "andrew", "stankevich" and "contests" at the same time
• user:mikemirzayanov title:testlib — search containing "testlib" in title by MikeMirzayanov
• "vk cup" — use quotes to find phrase as is
• title:educational — search in title

#### Results Sort by: relevance popularity time

1.
By parveen1981, history, 2 months ago,
I compiled a list of almost all useful blogs ever published on Codeforces [update: till 09.06.2021] <h3 style="color:red">If there are any blogs that I have missed, please tell in the comment section. Thank you.</h3> # Mathematics Stuff - [Number Theory in Competitive Programming [Tutorial]](https://codeforces.com/blog/entry/46620) - [Number of points on Convex hull with lattice points](https://codeforces.com/blog/entry/62183) - [FFT, big modulos, precision errors.](https://codeforces.com/blog/entry/48465) - [Number of ways between two vertices](https://codeforces.com/blog/entry/19078) - [Mathematics For Competitive Programming](https://codeforces.com/blog/entry/76938) - [FFT and NTT](https://codeforces.com/blog/entry/19862) - [Burnside Lemma](https://codeforces.com/blog/entry/51272) - [Number of positive integral solutions of equation 1/x+1/y=1/n!](https://codeforces.com/blog/entry/76836) - [On burnside (again)](https://codeforces.com/blog/entry/64860) - [Simple but often unknown theorems/lemmas/formula? Do you know?](https://codeforces.com/blog/entry/55912) - [Probabili...
Visualizer: Visualize graph inputs](https://codeforces.com/blog/entry/88865) - [[Tutorial]1-K BFS](https, /88865) - [[Tutorial] 1-K BFS](https://codeforces.com/blog/entry/88408) - [Heuristic algorithm

• +1500

2.
By Yukuk, 5 months ago, translation,
[Tutorial] 1-K BFS Introduction ================== I recently noticed, that there is no Codeforces blog with explanation of 1-K BFS algorithm. So, I decided to create this blog for those, who likes reading tutorials here (like me). Algorithm ================== ![ ](/predownloaded/2a/e9/2ae9fb4bf76fa50558e5f6743eaaf2fa1e8bd65c.jpg) If you are familiar with BFS (if not, I recommend to do it before reading), look at the picture. 1-K BFS also finds the shortest path in the graph, like BFS, and the only difference is that we have several queues. Let's look at this problem: _Given graph with N vertexes and M edges, there's one non-zero digit on every edge. Every path corresponds to number formed by digits on edges. For each vertex, except the first, find the minimum sum of digits by the numbers corresponding to the paths from the first to it. N <= 10^7, M <= 5 * 10^7._ Let's rephrase the statement: "For each vertex, except the first, find the shortest path from the first to it". But restrictions...
[Tutorial] 1-K BFS, low restriction for edge weights — they belong to the segment [1;9]. "1-K" in the name, with explanation of 1-K BFS algorithm. So, I decided to create this blog for those, who likes reading tutorials, If you are familiar with BFS (if not, I recommend to do it before reading), look at the picture.1, It is easy to understand, that time complexity of this algorithm is O(N*K + M), because after, It may seem, that X is pretty big, because answer can be equal to (N — 1) * K for some, [pos % (k + 1)].empty()) { ++pos; } int u = bfs[pos % (k + 1)].front(); bfs[pos % (k

• +229

3.
By Golovanov399, 17 months ago,
C++ tips and tricks Hello, codeforces. I would like to tell you about some tricks and constructions I use in C++. They are not hidden or anything, moreover, most of them are from stl or maybe well known among software engineers, but I often see codes where something is done by hand in, say, 5 lines, while in stl there is a function which does the same. The things below are filtered by my personal sense of non-popularity (so no __builtin functions) and usage frequency (so there almost surely are similar things I don't know about) and are not really sorted in any reasonable order. Let's begin. [cut] <hr> - ### all(x) This may be an exception to the rule of non-popularity -- this is quite widely used, but some next items will depend on all(x), so I define it here. So, I talk about [c++] #define all(x) (x).begin(), (x).end()  Now sorting a vector looks like sort(all(vec)) instead of sort(vec.begin(), vec.end()). However, it's not all about this define. Imagine you nee...
to cyclically shift a vector by $k$. If $k = 1$ then one can write a loop of swaps:, . Or something else, where you need sometimes to cyclically shift a vector by $k$. If $k = 1$ then one can

• +756

4.
By ilyakrasnovv, 2 months ago, translation,
A-2A-BFS (1-2-BFS) Special case &mdash; 1-2-BFS ------------------ **The task:** we are given a weighted directed graph, where weight of every edge is in range $[1;2)$. We have to find shortest path from vertex $st$ to all the others. **Solution:** for every integer in range from $0$ to $2n - 1$ we will store a queue of vertices (let the $i$-th queue be $q_i$). In $i$-th queue there will be all the vertexes, distance to which is $\lfloor i \rfloor$ (and some vertexes with smaller distance). To calculate this, we will do it layer-by-layer. c++ realisation: ~~~~~ for (int i = 0; i < 2 * n; ++i) { for (int v : q[i]) { for (pair<int, double> e : g[v]) { if (dist[e.first] > dist[v] + e.second) { // dist -- distance from st to all the others dist[e.first] = dist[v] + e.second; q[floor(dist[e.first])].push_back(e.first); } } } } ~~~~~ **Proof:** Base: $q_0$ ans $q_1$ are calculated correctly. Assumpt...
A-2A-BFS (1-2-BFS), the same optimisation as in 1-k bfs and store only 3 layers, but the code provided is easier, **Comment:** it is obvious, that you can do the same optimisation as in 1-k bfs and store only 3

• +82

5.
By v_raman, history, 10 months ago,
CSES Labyrinth - Grid BFS The problem can be found here: https://cses.fi/problemset/result/1045629/ I've been working on this problem for a week now &mdash; I have over 20 submissions. With different methods: I tried passing the path along a node, which has a TLE on test case 13: ~~~~~ #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pi; typedef vector<int> vi; typedef vector<pi> vpi; #define FOR(i, a, b) for (ll i = a; i < b; i++) #define F0R(i, a) for(ll i = 0; i < a; i++) #define f first #define s second const int MOD = 1e9+7; // 998244353; const int MX = 2e5+5; // const ll INF = 1e18; // int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; string ds = "RLDU"; const int mxN = 1e3; int n, m, si, sj, gi, gj; string s[mxN]; bool e(int x, int y){ return (x < n && x >= 0 && y < m && y >= 0); } void bfs(){ queue<pair<pi, string> > fringe; fringe.push(make_pair(make_pair(si, sj), "")); s[si][sj] = '#'; // v...
; const int MX = 2e5+5; // const ll INF = 1e18; // int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1

• 0

6.
By adamant, history, 5 years ago, translation,
Quaternion algebra and geometry Hi everyone! As you may already know (if you don't then I advice you to [learn](http://codeforces.com/blog/entry/22175) it), in 2D geometry it is convenient to use complex numbers to handling points operations and rotations. Now I would like to tell you about similar construction, which allows you to work efficiently with 3D geometry, in particular to use vectors and linear operations on them, calculate many popular operations (like dot or cross products) and maintain rotations in 3D space. [cut] <br> Let $\vec r_1 = (x_1, y_1, z_1), \vec r_2 = (x_2, y_2, z_2)$ &mdash; are vectors in 3D space. Following notation from analytical geometry will be used: 1. Dot product: $(\vec r_1, \vec r_2) = x_1 x_2 + y_1 y_2 + z_1 z_2 = |\vec r_1| \cdot |\vec r_2| \cos \varphi$, where $\relax \varphi$ &mdash; is the angle between $\vec r_1$ and $\vec r_2$ in their common plane, $|\vec r_1|$ &mdash; length of vector $\vec r_1$. 2. Cross product: $[\vec r_1, \vec r_2] = \begin{vmatrix} \vec ... be derived from this identity: $$\begin{bmatrix} \times & {\bf 1} & {\bf i} & {\bf j} & {\bf k,$$\begin{bmatrix} \times & {\bf 1} & {\bf i} & {\bf j} & {\bf k} \\ {\bf 1} & 1 & i & j &k, : $$\begin{bmatrix} \times & {\bf 1} & {\bf i} & {\bf j} & {\bf k} \\ {\bf 1} & 1 & i & j & k \\ {\bf i Read more » • +128 7. By ParagonX97, history, 3 years ago, Amusement Park — A BFS Problem *Description John is having his vacations out of town and he decided to visit an amusement park to ride all the exciting attractions that the park has, he is very brave and loves to have adventures from time to time so he can distress from all the work he has at home. Vacations are finishing and he will have to return home, while he was spending some time in the amusement park he realized he has to bring some souvenirs home, however, as he already have made his baggage he can take only two small items. Being the adventurer man he is, John knows exactly what he will be getting home, the first item he is interested is a fridge magnet so he can remember his trip each time he will get some food from the fridge, the other item is a keychain so that he can remember the trip each time he is going to open a door. There are several souvenir stores in the park on some of them they sell the keychain, on others they sell the fridge magnet but none of them sell both items so John needs to go... N lines contain a string with exactly M characters these being one of '.', 'K ', 'F', 'J', 'E, of '.', 'K', 'F', 'J', 'E', or '#'. 1 <= T <= 10 and 5 <= N,M <= 1000 The map has only a starting, q.push(make_pair(cont + 1 , make_pair(make_pair(xx , yy) , make_pair(f , k)))); } } } Read more » • -16 8. By slow_coder4, history, 5 years ago, BFS/DFS Help.. problem :http://www.lightoj.com/volume_showproblem.php?problem=1111.. why its WA. Give me some critical case.. problem: K people are having a picnic. They are initially in N cities, conveniently numbered from 1 to N. The roads between cities are connected by M one-way roads (no road connects a city to itself). Now they want to gather in the same city for their picnic, but (because of the one-way roads) some people may only be able to get to some cities. Help them by figuring out how many cities are reachable by all of them, and hence are possible picnic locations. Input Input starts with an integer T (≤ 10), denoting the number of test cases. Each case starts with three integers K (1 ≤ K ≤ 100), N (1 ≤ N ≤ 1000), M (1 ≤ M ≤ 10000). Each of the next K lines will contain an integer (1 to N) denoting the city where the ith person lives. Each of the next M lines will contain two integers u v (1 ≤ u, v ≤ N, u ≠ v) denoting there is a road from u to v. Output For each c... integers K (1 ≤ K ≤ 100), N (1 ≤ N ≤ 1000), M (1 ≤ M ≤ 10000). Each of the next K lines will contain, Each case starts with three integers K (1 ≤ K ≤ 100), N (1 ≤ N ≤ 1000), M (1 ≤ M ≤ 10000). Each, problem: K people are having a picnic. They are initially in N cities, conveniently numbered from Read more » • +8 9. By Errichto, 13 months ago, Matrix Exponentiation tutorial + training contest tl;dr &mdash; video tutorial https://www.youtube.com/watch?v=eMXNWcbw75E and codeforces GYM training https://codeforces.com/gym/102644 (register by finding this contest in GYM instead of using the link directly) video editorial: [part 1 (ABCDEF)](https://www.youtube.com/watch?v=kQuCOFzWoa0) and [part 2 (GHI)](https://www.youtube.com/watch?v=RA_SpxP2t54) codes to all 9 problems: https://github.com/Errichto/youtube/tree/master/matrix-exponentiation Prerequisites: binary exponentiation and iterative dp (you don't need to know matrices) The youtube tutorial ([link](https://www.youtube.com/watch?v=eMXNWcbw75E)) focuses on intuition and graph-like visualization . Or, if you prefer, below is a shorter (less detailed) text tutorial instead. You can practice by solving a set of 9 educational problems in GYM https://codeforces.com/gym/102644. ABCD are easy, EF medium, GHI are hard. If you are stuck, see hints below or watch the full solution analysis &mdash; [part 1 (ABCDEF)](https:... k), too slow. Precompute M^1, M^2, M^4, M^8, \ldots — matrices with counts of paths Read more » • +606 10. By 1-gon, history, 5 weeks ago, [Tutorial] Blossom Algorithm for General Matching in O(n^3) I have decided to write a tutorial on a topic not even [user:Um_nik,2021-06-29] knows! ([source](https://codeforces.com/blog/entry/92248)) In this tutorial, I will talk about the blossom algorithm, which solves the problem of **general matching**. In this problem, you are given an undirected graph and you need to select a subset of edges (called matched edges) so that no two edges share a vertex, and the number of matched edges is maximized. More common in competitive programming is bipartite matching, which is the same problem but when the graph is guaranteed to be bipartite. In competitive programming, general matching seems to get a lot of hate for being very challenging to implement. However, the blossom algorithm is quite beautiful, and important in the history of algorithm research. It will help if you are already familiar with bipartite matching. I will discuss the high level ideas of the algorithm, but my main focus will be on the tricky implementation details. So you may... 1-gon, is simply a cycle of 2k+1 edges, where k of them are matched edges. This means there is exactly Read more » • +384 11. By ATSTNG, history, 23 months ago, [Tutorial] Matroid intersection in simple words **[This article is also available in [Russian](https://codeforces.com/blog/entry/69287?locale=ru)]** Hello, CodeForces. I think that matroids are beautiful and powerful concept, however, not really well known in competitive programming. I’ve discovered matroids at 2019 Petrozavodsk Winter Training Camp. There was a problem that clearly cannot be solved using usual techniques I knew, editorial for this problem was just these three words “just matroid intersection”. Back then it took me more than 2 days of upsolving to find all the information and details I need and implement solution that gets Accepted on this. And it took way longer to actually understand why does it work and exactly how does it work. (I still hesitate in some details.) Of course, it is not hard to google up all the definitions and some related articles, but in my opinion they all are focused more on mathematical part of theory, strict proofs in some not really obvious but short ways, and observing only ke... of size k are bases for this matroid, all subsets of size (k+1) are circuits for this matroid. We Read more » • +904 12. By FieryPhoenix, 18 months ago, Codeforces Round #621 (Div. 1 + Div. 2) Editorial [problem:1307A] Idea: [user:FieryPhoenix,2020-02-16] <spoiler summary="Tutorial"> [tutorial:1307A] </spoiler> <spoiler summary="Solution"> ~~~~~ #include <iostream> using namespace std; int N,D,a[105]; int main(){ int T; cin>>T; while (T--){ cin>>N>>D; for (int i=1;i<=N;i++) cin>>a[i]; while (D--){ //loop over D days for (int i=2;i<=N;i++) if (a[i]>0){ //move closest haybale over a[i]--; a[i-1]++; break; } } cout<<a[1]<<endl; } } ~~~~~ </spoiler> <spoiler summary="Alternative O(n) Solution:"> ~~~~~ #include <iostream> using namespace std; int N,D,a[105],ans; int main(){ int T; cin>>T; while (T--){ cin>>N>>D; for (int i=1;i<=N;i++) cin>>a[i]; for (int i=2;i<=N;i++){ int move=min(a[i],D/(i-1)); //number of haybales we can move from pile i to pile 1 a[1]+=move; //update pile 1 D-=move*(i-1); //update remaining days } cout<<... Codeforces Round #621 (Div. 1 + Div. 2) Editorial, > > data; for(int i=0;i<K;i++){ data.emplace_back(dist[0][as[i]]-dist[1 ][as[i]],as[i, [0],0); bfs(dist[1],N-1); std::vector > data; for(int i=0;i<K;i Read more » • +159 13. By send_nodes, history, 4 years ago, Codeforces Round #420 (Div. 2) Editorial First, I really need to apologize for the round. There was a serious problem in D that was even covered in the sample test, that the main solution did not handle correctly. I should have been much more careful with this problem and looked for these kind of cases. Unfortunately, it was a big enough issue that caused the round to be unrated. I know this upset a lot of people, but it's tricky to find a solution to this kind of problem after the problem has happened. I still hope the problems were good quality. If you learned something new from the round, or from this editorial, then the round was worth it. I would advise to solve the problems you couldn't solve during the contest, so you can take away something from the round. **If you want any further clarification on a problem, please ask in comments!** [821A &mdash; Okabe and Future Gadget Laboratory](http://codeforces.com/problemset/problem/821/A) We can simulate exactly what's described in the statement: loop over all c... ,-1}; int n,m,k; void filrow(int i, int val){ if (i >= 1 && i <= n && dr[i] == 0, So complexity is O(n+m+k), with a log factor somewhere for map or priority queue. Interestingly Read more » • +127 14. By mheideme1, history, 4 years ago, Why does this simple BFS give a runtime error on test case 21? I'm trying to solve the problem "Islands" of the following contest http://codeforces.com/gym/101291/attachments/download/5256/20162017-acmicpc-pacific-northwest-regional-contest-div-2-en.pdf This is my simple BFS solution, which produces a runtime error on testcase 21. Does anybody have an explanation? ~~~~~ #include <iostream> #include <queue> using namespace std; void check_position(int i, int k, char** grid, queue<pair<int,int> >& q){ if(grid[i][k]=='L' || grid[i][k]=='C'){ grid[i][k] = 'X'; q.push(pair<int,int>(i,k)); } } void bfs(int i, int k, char** grid, int n, int m){ queue<pair<int,int> > q; grid[i][k]='X'; q.push(pair<int,int>(i,k)); pair<int,int> temp; while(!q.empty()){ temp = q.front(); q.pop(); if (temp.first>0) check_position(temp.first-1,temp.second, grid, q); if (temp.second>0) check_position(temp.first,temp.second-1, grid, q); if (temp.second<m-1) check_position(temp.first,temp.second+... check_position(int i, int k, char** grid, queue >& q){ if(grid[i][k]=='L' || grid[i, void bfs(int i, int k, char** grid, int n, int m){ queue > q; grid[i][k]='X Read more » • -5 15. By Wild_Hamster, history, 5 years ago, Codeforces Round #355 (Div. 2) Editorial [problem:677A] For each friend we can check, if his height is more than h. If it is, then his width is 2, else 1. Complexity O(n). <spoiler summary="Code"> ~~~~~ #include <iostream> using namespace std; typedef long long ll; ll i,n,h,ans,x; int main() { cin >> n >> h; ans = n; for (i = 0; i < n; i++) { cin >> x; ans += (x>h); } cout << ans << endl; return 0; } ~~~~~ </spoiler> [problem:677B] The solution, that does same thing, as in the problem statement will fail with TL, because if the height of each piece of potato will be 10^9 and smashing speed will be 1, then for each piece we will do 10^9 operations. With each new piece of potato a_i we will smash the potato till a[i] MOD k, so we will waste a[i]/k seconds on it. If we can not put this piece of potato after that, we will waste 1 more second to smash everything, that inside, else just put this piece. We will get an answe... < last_size; k++) { ll last_x = g[i-1][k].X; ll last_y = g[i-1][k].Y; dp[cur_x, first #define Y second using namespace std; typedef int ll; ll i,j,n,h,x,y,glob,k,m,p,fx,fy; ll, ++) { ll last_x = g[i-1][k].X; ll last_y = g[i-1][k].Y; dp[cur_x][cur_y] = min(dp Read more » • +99 16. By Xellos, history, 6 years ago, Codeforces Round #333 — editorial ### Hints: [div2A](#div2A): Try conversions between bases. [div2B](#div2B): Solve a simpler version of the problem where A_{i+1} \neq A_i for all i. [div1A](#div1A): What are the shortest paths of the vehicles? what's the shorter of those paths? [div1B](#div1B): Forget about the ceiling function. Draw points (i,A[i]) and lines between them &mdash; what's the Lipschitz constant geometrically? [div1C](#div1C): Some dynamic programming. Definitely not for the exp. score of one person &mdash; look at fixed scores instead. [div1D](#div1D): Compute dif(v) in O(N) (without hashing) and then solve the problem in O(N^2). You need some smart merges. [div1E](#div1E): Can you solve the problem without events of type 1 or 2? Also, how about solving it offline &mdash; as queries on subsets. ![ ](https://i.imgur.com/bnWmD60.png) ### <a name="div2A"></a>Div. 2 A: Two Bases ------------------------------------ It's easy to compare two numbers if the same bas... is a contradiction We've just proved that to any L_1 computed for two elements A[i],A[k] with k > i+1, we Read more » • +490 17. By S.G.G, history, 5 years ago, Codeforces Round #345 (Div. 2)-E. Table Compression [Problem Link](http://www.codeforces.com/contest/651/problem/E) **Solution** ================== There is no harm in assumptioning that all the values in the table are unique.Then it gets easier to think out the solution of the problem.We can sort all the values from small to large and insert them into the final matrix one by one and change the value into the maximum value in the same row or column at present.It will be the final value after it added one.Then how to solve this problem when the values are not unique?How can we deal with the elements with the same value?We can use Union-Find Sets to merge the elements that have the same value and limit each other.Obviously the elements in the same union will have same final values and there is no limit from a union to another.Then the solution is similar to before. **Code** ================== ~~~~~ #include<algorithm> #include<cstdio> #include<cstdlib> #include<iostream> #include<cm... ); } bool cmp2(hh a,hh b) { return a.yk,mx=max(h[(x-1)/m+1, void bfs(int x) { int k,mx=max(h[(x-1)/m+1],l[(x-1)%m+1]); for (k=fi[x];k;k=lb[k ]) mx=max Read more » • -12 18. By vovuh, history, 15 months ago, Codeforces Round #636 (Div. 3) Editorial [problem:1343A] Idea: [user:vovuh,2020-04-22] <spoiler summary="Tutorial"> [tutorial:1343A] </spoiler> <spoiler summary="Solution"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { #ifdef _DEBUG freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); #endif int t; cin >> t; while (t--) { int n; cin >> n; for (int pw = 2; pw < 30; ++pw) { int val = (1 << pw) - 1; if (n % val == 0) { cerr << val << endl; cout << n / val << endl; break; } } } return 0; } ~~~~~ </spoiler> [problem:1343B] Idea: [user:vovuh,2020-04-22] <spoiler summary="Tutorial"> [tutorial:1343B] </spoiler> <spoiler summary="Solution"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { #ifdef _DEBUG freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); #endif int t; cin >> t; while (t--) { int n; cin >> n; n /= 2; if (n &... * k + 1); for (int i = 0; i < n / 2; ++i) { ++cnt[a[i] + a[n - i - 1]]; } vector Read more » • +163 19. By rabaiBomkarBittalBang, 2 months ago, Codeforces Round #724 — Editorial We hope you liked the problems! If you’re curious about the two different problem formats, initially [user:Tlatoani,2021-06-06], [user:golions,2021-06-06], [user:qlf9,2021-06-06] and I were working on Omkar 3 with [user:antontrygubO_o,2021-06-06] while [user:hu_tao,2021-06-06] was working on a separate round with [user:isaf27,2021-06-06]. We eventually decided to join forces and combine the rounds, resulting in the current Omkar 3. <h1>[problem:1536A]</h1> Idea: [user:rabaiBomkarBittalBang,2021-06-06] Preparation: [user:rabaiBomkarBittalBang,2021-06-06], [user:Tlatoani,2021-06-06], [user:qlf9,2021-06-06] [Video editorial](https://www.youtube.com/watch?v=GZeihS2xTSc) <spoiler summary="Hint"> Consider what happens when a contains a negative number. </spoiler> <spoiler summary="Solution"> We first claim that if any negative number exists in a, then no solution exists. Denote p as the smallest number in a and q as another arbitrary number in the array (as n... ++) { ss.push_back(s[i + k]); se.insert(ss); } } rep(len, 1 Read more » • +257 20. By BlueSmoke, 15 months ago, Codeforces Round #641 Editorial You can view Chinese editorial here: https://www.luogu.com.cn/blog/Caro23333/codeforces-round-641-zhong-wen-ti-xie Div2.A Problem and editorial by [user:ProgSlacking,2020-05-12] <spoiler summary="Editorial"> [tutorial:1350A] </spoiler> <spoiler summary="Code"> ~~~~~ #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> using namespace std; int main() { int T; cin >> T; while(T--) { int n,k; cin >> n >> k; if(n%2==0) { cout << n+2*k << endl; continue; } int p = 0; for(int i = n; i>=2; i--) if(n%i==0) p = i; cout << n+p+2*(k-1) << endl; } return 0; } ~~~~~ </spoiler> Div2.B Problem and editorial by [user:ProgSlacking,2020-05-12] <spoiler summary="Editorial"> [tutorial:1350B] </spoiler> <spoiler summary="Code"> ~~~~~ #include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; con... --) if(n%i==0) p = i; cout << n+p+2*(k-1) << endl; } return 0 Read more » • +296 21. By srajang_123, 16 months ago, Koders Korner Practice Contest 2 Problem A ================== At first let's notice that if there exists such triple a<sub>i</sub>, a<sub>j</sub> and a<sub>k</sub> that a<sub>i</sub> < a<sub>j</sub> < a<sub>k</sub>, then |a<sub>k</sub> - a<sub>i</sub>| > |a<sub>j</sub> - a<sub>i</sub>| and |a<sub>k</sub> - a<sub>i</sub>| > |a<sub>k</sub> - a<sub>j</sub>|. Thus we can sort all numbers and check only adjacent ones. There are exactly n - 1 of such pairs. The only thing left is to find minimal distance of all pairs and count pairs with that distance. Overall complexity: O(nlogn) Problem B ================== The task was just about implementing algorithm described in statement. This is one of many possible ways of doing this. Firstly you should notice that doing ai iterations in i-th step is equal to doing a<sub>i</sub> mod (n - i) iterations (0-based numbering). That is less than n. Now fill array of length n with ones and create pointer to current leader. Then on i-th step move pointer to the right (fr... to prove that if k = 0, then x is a leaf; if k = 1, then both children of x are leaves, and so, 1. Iterate over the possible sizes of sets x (from 1 to ![ ](/predownloaded/21/ bf Read more » • -10 22. By PrinceOfPersia, 6 years ago, Algorithm Gym :: Graph Algorithms Welcome to the new episode of [user:PrinceOfPersia,2015-01-31] presents: Fun with algorithms ;) You can find all the definitions here in the book "Introduction to graph theory", Douglas.B West. [cut] Important graph algorithms : DFS --- The most useful graph algorithms are search algorithms. DFS (Depth First Search) is one of them. While running DFS, we assign colors to the vertices (initially white). Algorithm itself is really simple : ~~~~~ dfs (v): color[v] = gray for u in adj[v]: if color[u] == white then dfs(u) color[v] = black ~~~~~ Black color here is not used, but you can use it sometimes. Time complexity : O(n + m). #### DFS tree DFS tree is a rooted tree that is built like this : ~~~~~ let T be a new tree dfs (v): color[v] = gray for u in adj[v]: if color[u] == white then dfs(u) and par[u] = v (in T) ... ) d[v][v] = 0 for each vertex v for k = 1 to n for i = 1 to n for j = 1 to n d[i][j Read more » • +355 23. By Supermagzzz, 3 months ago, translation, Codeforces Round #719 (Div. 3) Editorial [problem:1520A] Authors: [user:MikeMirzayanov,2021-02-16] <spoiler summary="Tutorial"> [tutorial:1520A] </spoiler> <spoiler summary="Solution"> ~~~~~ #include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using pii = pair<int, int>; using cd = complex<ld>; void solve() { int n; cin >> n; string s; cin >> s; for (char c = 'A'; c <= 'Z'; c++) { int first = n; int last = -1; for (int i = 0; i < n; i++) { if (s[i] == c) { first = min(first, i); last = max(last, i); } } for (int i = first; i <= last; i++) { if (s[i] != c) { cout << "NO\n"; return; } } } cout << "YES\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { solve(); }... sum; cin >> sum; if ((m - l + 1) - sum >= k) { calc(l, m, k); } else Read more » • +125 24. By ss_96, history, 4 years ago, BFS code not working properly I was trying to solve the following problem: You are given a grid of size N×N that has the following specifications: Each cell in the grid contains either a policeman or a thief. A policeman can only catch a thief if both of them are in the same row. Each policeman can only catch one thief. A policeman cannot catch a thief who is more than K units away from the policeman. Write a program to find the maximum number of thieves that can be caught in the grid. My solution:[solution](https://gist.github.com/Sharma96/afcc404a05bf69b457095cb67a3a84e9) PS:This was a question of [question](https://www.hackerearth.com/challenge/hiring/national-instruments-hiring-challenge-1/?utm_source=website&utm_medium=widget&utm_campaign=live-widget) and I have completed the test,couldn't qualify ,that's why asking for guidance here.Please suggest what corner cases are missing with the solution code. Thanks. thief. A policeman cannot catch a thief who is more than K units away from the policeman. Write Read more » • 0 25. By awoo, history, 3 years ago, translation, Educational Codeforces Round 45 Editorial [problem:990A] <spoiler summary="Tutorial"> [tutorial:990A] </spoiler> <spoiler summary="Solution (PikMike)"> ~~~~~ #include <bits/stdc++.h> #define forn(i, n) for(int i = 0; i < int(n); i++) using namespace std; int main() { long long n, m; int a, b; cin >> n >> m >> a >> b; cout << min(n % m * b, (m - n % m) * a) << endl; return 0; } ~~~~~ </spoiler> [problem:990B] <spoiler summary="Tutorial"> [tutorial:990B] </spoiler> <spoiler summary="Solution (adedalic)"> ~~~~~ #include<bits/stdc++.h> using namespace std; const int N = 200 * 1000 + 555; int n, k, a[N]; inline bool read() { if(!(cin >> n >> k)) return false; for(int i = 0; i < n; i++) assert(scanf("%d", &a[i]) == 1); return true; } inline void solve() { sort(a, a + n); a[n++] = int(2e9); int ans = 0, u = 0; for(int i = 0; i < n - 1; i++) { while(u < n && a[i] == a[u]) u++; if(a[u] - a[i] > k) ans++; } cout << ans << endl... ; int z = bfs(x, i); ans1[i] += z * 1ll * (z + 1) / 2; } for(int j = i, k = 1, ] = lst[i - 1]; else lst[i] = -1; } long long ans = INF64; forn(i, k){ long long t Read more » • +59 26. By Edvard, history, 5 years ago, translation, Разбор задач Educational Codeforces Round 7 ### [problem:622A] Вычтем из числа n единицу. Определим сначала номер блока в который попало n-е число. Для это сначала вычтем из числа n число 1, затем 2, затем 3 и так далее пока n не станет отрицательным. Количество вычитаний и будем номером блока, а позицией в блоке будет последнее неотрицательное число, которое мы встретим. [С++ solution](http://pastebin.com/hAnJGhvB) Сложность: O(\sqrt n). ### [problem:622B] В этой задаче можно было a раз прибавлять к текущему времени по одной минуте, аккуратно обрабатывая переполнения часов и минут. А можно было просто посчитать ответ формулой: x=h \cdot 60+m + a,\ h'=\lfloor \frac x{60} \rfloor\ mod\ 24, m'=x\ mod\ 60. [C++ solution 1](http://pastebin.com/NEQkkc3F) [C++ solution 2](http://pastebin.com/VH6EkNEK) Сложность: O(a) or O(1). ### [problem:622C] Задача является значительно упрощённой версией задачи предложенной Mohammad Nematollahi [user:Deemo,2016-02-11]. Эту задачу можно б... от 0 до k+1 (это легко сделать одним циклом за O(klogk)). Если n < k +2, то мы уже нашли, ,2016-02-11]. Утверждение: функция суммы является многочленом k+1-й степени относительно Read more » • +90 27. By Akikaze, history, 3 years ago, Codeforces Round #229 (Div. 2) Editorial [Unofficial] _Since the original data has been lost during the dark days of Codeforces, no version of the editorial has been re-released, and I feel the round itself is quite educational, so I decided to give a try._ [problem:390A] ------------------ <spoiler summary="Approach"> The criterion shows that we can only use either vertical segments or horizontal segments. Since there is no limit on the segments' length, we can see that it's always optimal to use a segment with infinite length (or may be known as a line). We can see that the vertical line x = a will span through every alarm clocks standing at positions with x-coordinate being equal to a. In a similar manner, the horizontal line y = b will span through every alarm clocks standing at positions with y-coordinate being equal to b. So, if we use vertical lines, the number of segments used will be the number of distinct values of x-coordinates found in the data. Similarly, the number of horizontal segments used will be... being nearest to cell (1, 1) (yup, including (1, 1) itself). To find these k points, we, of group (l_i + k - 1) \mod k? To make sure the answer for a query being "Yes", Dima has to remove Read more » • +37 28. By -Morass-, history, 4 years ago, Problem Topics Good Day to you! I've been asked to make some topic-wise list of problems I've solved. Even though I couldn't involve all problems, I've tried to involve at least "few" problems at each topic I thought up (I'm sorry if I forgot about something "easy"). I've alredy made such list once anyway I've tried to include more problems now &mdash; so here it is: <spoiler summary="aho"> http://www.spoj.com/problems/ADAJOBS/ URI 2226 (5) //[NICE][NUMBERS][DP] http://www.spoj.com/problems/SUB_PROB/en/ http://codeforces.com/contest/696/problem/D 8 http://www.spoj.com/problems/AHOCUR/ 5 //Aho-Corassic + DP https://www.codechef.com/problems/LYRC (5) //Sample aho-brute-force http://codeforces.com/problemset/problem/346/B //Proposed by [user:bradyawn,2019-08-03] </spoiler> <spoiler summary="automat"> 6861 [LA] //CYK UVA 10679 //Suffix Automat http://www.spoj.com/problems/STRMATCH/ //Suffix Automat &mdash; trie might do too http://www.spoj.com/problems/NSUBST... / (5) // N^{K-2}*Prod(comp_size) http://codeforces.com/contest/785/problem/D (5) // F'(' C"(+)-1 Read more » • +428 29. By Zlobober, 9 years ago, translation, Anti-hash test. Hi everyone! I wan't to share some interesting fact about how we're going to challenge almost every solution, that uses polynomial hashes modulo 2^64. We'll hack any solution, regardless of it's base (!), the only thing we need, that it's using int64 with overflows --- like many coders write hashing. Keywords: Only today, only for you, ladies and gentlemen: we're gonna challenge [user:Petr,2012-07-19]'s solution in problem [problem:7D] from Codeforces Beta Round #7! Is it interesting? Welcome reading after the cut. [cut] Firstly, for the most impatient of you. Here's the source of the generator: ~~~~~ const int Q = 11; const int N = 1 << Q; char S[N]; for (int i = 0; i < N; i++) S[i] = 'A' + __builtin_popcount(i) % 2; // this function in g++ returns // number of ones in binary representation of number i ~~~~~ Let's try solutions of two CFBR #7 winners on this test: Petr Mitrichev's and Vlad Epifanov's. [user:vepifanov,2012-07-18] solution doe... простым — это ничем не обосновано). Я утверждаю, что hash(S[0 \dots (2^{k} - 1 )]) при, is some odd number. I claim that hash(S[0 \dots (2^{k} - 1)]) for some sufficiently smallk k Read more » • +272 30. By Imakf, history, 21 month(s) ago, Problems of CSP(China) Sharing & Discussion Hello codeforces! CSP-J/S(Certified Software Professional-Junior/Senior) of China ended. CSP-J/S (or you can say NOIp ,but it has been dead) was held by OI rules. In OI rules, every problem has the same score distribution 100 points. In one problem, there is several testdatas (like 10 ,20 or 25). Every testdata has the same score distributions. Once you pass a testdata, you can get the score. You can submit your code during the contest, but can't see the result. The organizer will judge all the programs together after contest. I'd like to share the problems of CSP-S here! Hope you guys enjoy. Don't mind my poor English, I spent a whole afternoon translating. <spoiler summary="D1T1 code"> \bf{D1T1\ Gray\ Code\ 1s\ 256MB} \bf{Statement} _Gray Code_ is a special permutation of n-bit binary strings ,which requires adjacent strings have **exactly one different** bit. Specially, the first string is adjacent to the last string. One example of 2-bit _Gray Cod... , the answer. \bf{Constraints} 1\le n \le 64, 0\le k < 2^n Read more » • +71 31. By awoo, history, 7 months ago, translation, Educational Codeforces Round 102 Editorial [problem:1473A] Idea: [user:BledDest,2021-01-15], [user:adedalic,2021-01-15] <spoiler summary="Tutorial"> [tutorial:1473A] </spoiler> <spoiler summary="Solution (Neon)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { int tc; cin >> tc; while (tc--) { int n, d; cin >> n >> d; vector<int> a(n); for (int& x : a) cin >> x; sort(a.begin(), a.end()); cout << (a.back() <= d || a[0] + a[1] <= d ? "YES" : "NO") << endl; } } ~~~~~ </spoiler> [problem:1473B] Idea: [user:BledDest,2021-01-15] <spoiler summary="Tutorial"> [tutorial:1473B] </spoiler> <spoiler summary="Solution (Neon)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { auto mul = [](string s, int k) -> string { string res = ""; while (k--) res += s; return res; }; int tc; cin >> tc; while (tc--) { string s, t; cin >> s >> t; int n = s.length(), m = t.length(); ... ()) { val (n, k) = readLine()!!.split(' ').map { it.toInt() } for (i in 1 until (k - (n - k Read more » • +133 32. By Nerevar, 9 years ago, Codeforces Round #155 (Div. 2) — tutorial [problem:254A] For each x from 1 to 5000 store a list L(x) of such indexes i that a_i=x. Then just check that all lists have even size and output the elements of each list in pairs. [problem:254B] One of the possible solutions is: for each Olympiad find the period of the preparation. This can be done by iterating the days back from the day of the Olympiad. For each day d of the preparation add p_i to the number of distinct jury members that have to work on problems on day d. Then the answer is maximum calculated sum over all days. Be careful with the year 2012. [problem:254C] Lets denote the number of character x in s by C_s(x). Similarly C_t(x) is defined. Then the minimum number of changes required to get anagram of t from s is equal to \frac{\sum |C_s(x) - C_t(x)|}{2}. Now we need to obtain lexicographically minimum solution. Lets iterate through the positions in s from the left to the right. For a fixed position, look through all charact... kilos of food remaining from the day n-1. It is obvious that if we decide to feed k friends Read more » • +15 33. By vovuh, history, 2 years ago, Codeforces Round #544 (Div. 3) Editorial [problem:1133A] Idea: [user:MikeMirzayanov,2019-03-08] <spoiler summary="Tutorial"> [tutorial:1133A] </spoiler> <spoiler summary="Solution"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { #ifdef _DEBUG freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); #endif int h1, m1; scanf("%d:%d", &h1, &m1); int h2, m2; scanf("%d:%d", &h2, &m2); int t1 = h1 * 60 + m1; int t2 = h2 * 60 + m2; int t3 = (t1 + t2) / 2; printf("%02d:%02d\n", t3 / 60, t3 % 60); return 0; } ~~~~~ </spoiler> [problem:1133B] Idea: [user:MikeMirzayanov,2019-03-08] <spoiler summary="Tutorial"> [tutorial:1133B] </spoiler> <spoiler summary="Solution"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { #ifdef _DEBUG freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); #endif int n, k; cin >> n >> k; vector<int> cnt(k); for (int i = 0; i < n; ++i) { int x; ... ; for (int i = 1; i < (k + 1) / 2; ++i) { int j = k - i; ans += min(cnt[i], cnt[j Read more » • +33 34. By PedroBigMan, history, 5 months ago, SWERC Documentation ~~~~~ /* Author of all code: Pedro BIGMAN Dias Last edit: 15/02/2021 */ #include <iostream> #include <vector> #include <cmath> #include <algorithm> #include <string> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <queue> #include <deque> #include <list> #include <iomanip> #include <stdlib.h> #include <time.h> #include <cstring> using namespace std; typedef long long int ll; typedef unsigned long long int ull; typedef long double ld; #define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++) #define pb push_back #define mp make_pair #define pl pair<ll,ll> #define ff first #define ss second #define whole(x) x.begin(),x.end() #define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl #define INF 500000000LL #define EPS 0.00000001 #define pi 3.14159 ll mod=99824LL; vector<ll> fat,ifat; ll Mo_bucket; //sqrt(arr.size()) template<class A=ll> void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;} temp... );} if(k>N) {return ans;} if(k==1) {REP(i,0,N) {ans[i]=1LL;} return ans;} vector last=IC(k, =starting node closer to i { Reset(); ll K=sn.size(); vector distance Read more » • -25 35. By Ripatti, 9 years ago, translation, Editorial for Codeforces Round #139 **A.** You should iterate over all dices from up to down and restore answer. You can easily find number of the bottom side of the 1st dice. Using known sides of the 2nd dice you can find pair of numbets on top and bottom side of the 2nd dice. If one of them equal to number on bottom of the 1st dice, you can restore all numbers on the 2n dice. Then using this idea you can try restore numbers on the 3rd dice and so on. If you restored all numbers, you should write YES. If for some dice you cannot uniquely determine order of numbers on the top and botton sides, there will be at least 2 placing of numbers. In this case you shoyld write NO. Author is ~Ripatti,2012-09-19 . **B.** Firstly you should generate all k-bonacci numbers less than n. For k \le 32 you can do it straightforward, for bigger k you can see that all k-bonacci numbers less 10^9 are powers of two only (and 0). So you will have no more then 100 numbers. Then you should use greedy algo. You should substract ... proves: F(k,n) = F(k,n-1) + F(k,n-2) + ... + F(k,n-k) F(k,n-1) = F(k,n-2) + F(k,n-3 Read more » • +64 36. By Jon.Snow, 13 months ago, CSES Tree section editorial Hello Codeforces, [CSES](https://cses.fi/problemset/list) is a nice collection of classical CP problems which encourages you to learn a lot of basic and advanced concepts. Having editorials would help people to not get stuck on a problem for long. Here are my solutions to the tree section of the problem-set. Looking forward to read corrections/feedback/better solutions in the comment section. Happy coding! Subordinates ------------------ This can be solved using basic DP approach in linear time. <br> subordinates[u] = \sum\limits_{v:children[u]}^{} subordinates[v] where v is a child of u <spoiler summary="Code"> ~~~~~ #include<bits/stdc++.h> using namespace std; const int SZ = 200005; int n, m, x; vector<int> adj[SZ]; int S[SZ]; void dfs(int u,int l, int p) { S[u] = 1; for (int v: adj[u]) { if (v != p) { dfs(v, l+1, u); S[u] += S[v]; } } } int main() { cin >> n; for(int i = 2; i <=n ; i++) { cin >> x; ... (); while(q--) { cin >> u >> k; int boss = u; for(int i=0; i<=20; i++) if(k & (1 < Read more » • +84 37. By web_developer, history, 9 months ago, Help with 485(Div 1) A problem Hello codeforces, I was solving [this](https://codeforces.com/problemset/problem/986/A) problem and I ended up with below solution, but this solution doesn't seem to work on **test case 5**, can you help me find where I've gone wrong and I don't want to see the editorial until I don't get my approach accepted. It's a simple bfs if you've got time to see it. Please help..I wasted so much time on this. **My approach:** Firstly, I am making a bfs call from every node from 1 to n and finding their neighbours or second-neighbours and so on..so that minimum s towns having a different type of goods and for finding cost I am using a level array. Suppose I am starting bfs from node-2 then level of this node I am taking 0 and its neighbours level 1 and so on, so it gives me nearest s towns who has to produce a different type of goods and for answer, I am summing their cost. Hope you understood my approach. Code ~~~~~ #include <bits/stdc++.h> using namespace std; #define N 100005 #de... Help with 485(Div 1) A problem, ]) { q.push(child); level[child]=level[tp]+1; } } } } void solve() { cin>>n>>m>> k>>s Read more » • -1 38. By AGrigorii, 5 years ago, translation, Editorial Codeforces #354 round div.2 ### [problem:676A] All what you need to solve this problem &mdash; find the positions of numbers 1 and n in the given array. Let's this positions equal to p_1 and p_n, then the answer is the maximum of 4 values:$$abs(n-p_1),\; abs(n-p_n),\; abs(1-p_1),\; abs(1-p_n).$$Asymptotic behavior O(n). ### [problem:676B] The restrictions in this problem allow to simulate the process. Let the volume of one wineglass equals to 2^n conventional units. So the volume of the champagne surpluses which will stream to bottom level will always integer number. So let's pour in the top wineglass q*2^n units of champagne, and then we have following case: if in the current wineglass is more champagne than its volume, let's make surplus = V_{tek} - 2^n, and add surplus/2 of champagne in each of the two bottom wineglasses. Asymptotic behavior O(n^2). ### [problem:676C] This problem can be solved with help of two pointers. Let the first pointer is l and the second poin... {l+1}\dots s_{r} it is possible to make no more than k swaps to make this substring beautiful Read more » • +63 39. By dkyu021, history, 3 months ago, Some nice questions for beginners learning new stuffs (will be adding more in time) _Although I'm too a beginner but I try to learn new things everyday, so here are the questions on DS which beginners like me find hard but are too easy if learned the DS nicely._ ## Arrays | Index | Problem | Prerequisite | | --- | --- | --- | | 1 | [Maximum circular subarray sum](https://practice.geeksforgeeks.org/problems/max-circular-subarray-sum/0) | Kadane's Algorithm | | 2 | [Find subarray with given sum](https://practice.geeksforgeeks.org/problems/subarray-with-given-sum/0) | Hashing | | 3 | [Equilibrium index of an array](https://practice.geeksforgeeks.org/problems/equilibrium-point/0) | None | | 4 | [Maximum Sum Increasing Subsequence](https://practice.geeksforgeeks.org/problems/maximum-sum-increasing-subsequence/0) | Simple DP | | 5 | [K-Concatenation](https://www.codechef.com/problems/KCON) | Kadane's Algorithm | | 6 | [Convert array into Zig-Zag fashion](https://practice.geeksforgeeks.org/problems/convert-array-into-zig-zag-fashion/0) | None | | 7 | [Find... | Index | Problem | Prerequisite | | --- | --- | --- | | 1 | [Maximum circular subarray sum](https Read more » • +17 40. By .o., 7 years ago, Good Bye 2014 Editorial First of all, sorry for the late editorial. I was too exhausted and immediately went to bed after the round finished, and didn't write the editorial. There are many pictures in this editorial, to cover up my poor English skills! If you have detected any errors or have questions, feel free to ask questions by comments. Unfortunately, the authors only know English, so we can't answer you if you write comments in Russian. ## [problem:500A] Let's assume that I am in the cell i (1 \le i \le n). If i \le n-1, I have two choices: to stay at cell i, or to go to cell (i + a_{i}). If i = t, we are at the target cell, so I should print "YES" and terminate. If i > t, I cannot go to cell t because I can't use the portal backwards, so one should print "NO" and terminate. Otherwise, I must go to cell (i + a_{i}). Using this method, I visit each cell at most once, and there are n cells, so the problem can be solved in linear time. #### What is test 13? There are 9... +1}[k] = U[U^{n}[k]] and S^{n+1}[k] = S^{n}[k] + (P[U^{n+1}[k]] - R[U^{n}[k ]]). So, S^{n}[k Read more » Tutorial of Good Bye 2014 • +278 41. By Akikaze, history, 2 years ago, Codeforces Round #554 (Div. 2) Editorial [problem:1152A] ------------------ Author: [user:xuanquang1999,2019-04-24] Development: [user:xuanquang1999,2019-04-24], [user:Akikaze,2019-04-24], [user:GreenGrape,2019-04-24] Theme development: [user:Akikaze,2019-04-24], [user:GreenGrape,2019-04-24] Editorialist: [user:xuanquang1999,2019-04-24] <spoiler summary="Tutorial"> [tutorial:1152A] </spoiler> <spoiler summary="Solution (xuanquang1999)"> Submission link: [submission:53259456] <spoiler summary="Source code in plain text"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main(int argc, char* argv[]) { int n, m; scanf("%d%d", &n, &m); vector<int> a(n), b(m); for(int i = 0; i < n; ++i) scanf("%d", &a[i]); for(int i = 0; i < m; ++i) scanf("%d", &b[i]); int c0 = 0, c1 = 0; for(int i = 0; i < n; ++i) if (a[i]%2 == 0) ++c0; else ++c1; int k0 = 0, k1 = 0; for(int i = 0; i < m; ++i... ]); } int k = ind.size(); Graph g(k); for(int i = 0; i < n-1; ++i) g.addEdge(bprime Read more » • +115 42. By AnandOza, 2 years ago, Atcoder Beginner Contest 132 — Unofficial English Editorial Hi all, [Atcoder Beginner Contest 132](https://atcoder.jp/contests/abc132) was today. Atcoder only publishes Japanese editorials for beginner contests, so I wrote an unofficial English editorial. Hope it helps! ### [A: Fifty-Fifty](https://atcoder.jp/contests/abc132/tasks/abc132_a) After sorting the input, a "good" string will look like "AABB". Therefore, we simply sort and check for this format. <spoiler summary="Sample code"> ~~~~~ char[] s = in.next().toCharArray(); Arrays.sort(s); out.println(s[0] == s[1] && s[2] == s[3] && s[1] != s[2] ? "Yes" : "No"); ~~~~~ </spoiler> ### [B: Ordinary Number](https://atcoder.jp/contests/abc132/tasks/abc132_b) It suffices to simply check every range of 3 and see if its middle element should be counted. A simple way is to sort each range of 3 and check that the middle element remains in the middle. Runtime: \mathcal{O}(n). <spoiler summary="Sample code"> ~~~~~ int n = in.nextInt(); int[] p = new int[n]; for (int i =... to the easiest ARC problem (problem (N/2+1), after sorting), we need to select K such that B < K \le R Read more » • +124 43. By Ripatti, 9 years ago, translation, Solutions for Codeforces Round #125 **Div2 A.** You can just output "0 0 n". Author is ~Alex_KPR,2012-06-23 [cut]. **Div2 B.** You should check for every circle of one ring: it have intersections with another ring or not. So, there are 4 checks. There are 2 cases: 1. circle is inside of ring; 2. circle is outside of ring and ring is outside of circle; 3. circle is outside of ring and ring is inside of circle. If at least one of these cases is performed, circle is good. You can easily do checks following way. Let us d be a distance between centers of ring and circle, r_1 and R_1 are inside and outside radii of ring, r be radius of circle. Then conditions for all cases will be 1. d+r \le r_1. 2. r+R_1 \le d. 3. d+R_1 \le r. You can check all conditions in integers using squares of distances. Author is ~Alex_KPR,2012-06-23 **Div2 C.** **Div1 A.** The first solution. Consider sequence a_0=1, a_i=a_{i-1} k + b: a_0, a_1, a_2, ..., a_n=z. ... A.** The first solution. Consider sequence a_0=1, a_i=a_{i-1} k + b: a_0, a_1, a_2, ..., a_n=z Read more » • +47 44. By skywalkert, history, 3 years ago, 2018-2019 ACM-ICPC, Asia Jiaozuo Regional Contest, Editorial SPOILER ALERT: Please do not read these hints if you want to solve some problems in this contest but haven't attempted yet. <spoiler summary="DO NOT open if you want to solve them by yourself"> Hints are categorized by the number of accepted teams. <spoiler summary="hints for ADEFI"> [problem:102028A] <spoiler summary="hint for A"> Read and implement. </spoiler> [problem:102028D] <spoiler summary="hint for D"> There are only two cases, so just draw them on draft paper. </spoiler> [problem:102028E] <spoiler summary="hint for E"> The resistance of the n-th section is a multiplicative function of n, which only depends on distinct prime factors. </spoiler> [problem:102028F] <spoiler summary="hint for F"> BFS is enough. Be careful with leading whitespaces and too many test cases. </spoiler> [problem:102028I] <spoiler summary="hint for I"> Picking half of points from every boundary is enough. </spoiler> </spoiler> <spoiler summary="hints for ... pair of vertices (k = 1, 2). Imagine these k edges split a component (tree) into (k + 1 Read more » • +62 45. By Agnimandur, history, 5 weeks ago, Codeforces Round 736 Editorial Problems A, B, C, D, E, F1, and F2 were all created by [user:Agnimandur,2021-07-06]. Problem G was created by [user:Benq,2021-07-06]. I hope that this hint-based editorial helps you, no matter what your rating is! Solution code is provided in both Java and C++. [problem:1549A] --------------------------- <spoiler summary="Hint 1"> Fix a into a convenient constant. </spoiler> <spoiler summary="Solution"> Since P \ge 5 and is also a prime number, we know that P-1 is an even composite number. A even composite number is guaranteed to have at least 2 unique divisors greater than 1. Let two of these divisors be a and b. It is guaranteed that P\mod{a} = P\mod{b} = 1, and thus this selection is valid. For example, we can simply pick a=2 and b=P-1, and we will get a correct solution. The time complexity is \mathcal{O}(Q). </spoiler> <spoiler summary="C++ Code"> Written by [user:penguinhacker,2021-07-06] (Runtime: 15ms) ~~~~~ #include <bits/stdc++.h>... until n) { if (here[k] == '1') { if (k > 0 && enemies[k - 1] == '1 Read more » • +231 46. By JaySharma1048576, 4 weeks ago, Codeforces Round #730 (Div. 2) Editorial #### [A: Exciting Bets](https://codeforces.com/contest/1543/problem/A) <spoiler summary="Hint 1"> GCD(a,b)=GCD(a-b,b) if a>b </spoiler> <spoiler summary="Hint 2"> a-b does not change by applying any operation. However, b can be changed arbitrarily. </spoiler> <spoiler summary="Tutorial"> If a=b, the fans can get an infinite amount of excitement, and we can achieve this by applying the first operation infinite times. Otherwise, the maximum excitement the fans can get is g=\lvert a-b\rvert and the minimum number of moves required to achieve it is min(a\bmod g,g-a\bmod g). <spoiler summary="Proof"> Without loss of generality, assume a>b otherwise we can swap a and b. We know that GCD(a,b) = GCD(a-b,b). Notice that no matter how many times we apply any operation, the value of a-b does not change. We can arbitrarily change the value of b to a multiple of a-b by applying the operations. In this way, we can achieve a GCD equal to a-b. Now, ... /contest/1543/problem/D2) The generalised k-itwise XOR does Read more » • +181 47. By suncongbo, history, 3 years ago, About Solving Simple Recursions **Summary: This blog talks about solving two kinds of simple recursions: F(n+1)=aF(n)+b and F(n+1)=aF(n)+bF(n-1)** ###### 1. Preliminary Knowledge (1) The solution of recursion F(n+1)=aF(n) is F(n)=a^{n-1}F(1). (2) The solution of recursion F(n+1)=F(n)+a is F(n)=(n-1)a+F(1). (3) The recursion F(n+1)=kF(n) is the same as F(n)=kF(n-1), also F(n+1)=aF(n)+bF(n-1) is the same as F(n)=aF(n-1)+bF(n-2) in this blog. ###### 2. Solving F(n+1)=aF(n)+b, a, b are constants, a>1 **The main idea is to create another function G(n) that satisfy G(n)=kG(n-1) with constant k, solve G(n), and then solve F(n).** F(n+1)=aF(n)+b F(n+1)=aF(n)+\frac{ab-b}{a-1} F(n+1)=a(F(n)+\frac{b}{a-1})-\frac{b}{a-1} F(n+1)+\frac{b}{a-1}=a(F(n)+\frac{b}{a-1}) Let G(n)=F(n)+\frac{b}{a-1} we have G(n)=aG(n-1) G(n)=a^{n-1}G(1) F(n)+\frac{b}{a-1}=a^{n-1}(F(1)+\frac{b}{a-1}) F(n)=a^{n-1}(F(1)+\frac{b}{a-1})-\frac{b}{a-1} ###### 3. Solving F... +1)=aF(n)+bF(n-1)** ###### 1. Preliminary Knowledge (1) The solution of recursion F(n+1)=aF(n Read more » • +19 48. By usaxena95, history, 6 years ago, Divide by Zero 4.0 Summary ##Statistics Total Users/Teams who have made a submission: **754** Total Submissions: **4212** Number of distinct users/teams with correct submissions: **498** [Contest Link]( https://www.codechef.com/DIBZ2016) [Feedback form](http://goo.gl/forms/cMY4KZLEJV) --- ##Winners <li>Rank 1: [user:Sumeet.Varma,2016-01-31]</li> <li>Rank 2: [user:amankedia1994,2016-01-31]</li> <li>Rank 3: [user:PrashantM,2016-01-31]</li> --- The Editorials of the following problems are prepared by me, [user:aditya1495,2016-01-31] and [user:_shil,2016-01-31]. --- ##Shil and RasenShuriken (setter: [user:_shil,2016-01-31])<br> Total number of pairs such that their product is even. Count total number of odd numbers = x.<br> Product of two numbers is odd if the both numbers are odd.<br> Ans = **N*(N-1)/2 &mdash; x*(x-1)/2** --- ##Shil Loves Exclusive Or (setter: [user:_shil,2016-01-31])<br> Use the fact that Xor of 2x and 2x+1 is 1.<br> Therefore xo... such steps will be our lexicographical Kth shortest path string. Hence we will make d[1 Read more » • +52 49. By ChiNhan, history, 15 months ago, 1354C2 The smallest side of the square containing 2*n regular polygon, n odd Note: This is **NOT** an official proof of the derived solution, as it is incoherent. It's rather a personal note for my illogical brain. It contains a derivation to the solution and the solution of [Educational Codeforces Round 87](https://codeforces.com/contest/1354) [C2](https://codeforces.com/contest/1354/problem/C2) at the bottom. ![ ](/predownloaded/e8/fb/e8fb1504a3d34d4b24bf2facb52b0876a3d0bec5.png) Source: https://math.stackexchange.com/a/458593/496530 From the above observation, 4 points of the polygon must be on the 4 sides of the minimal square. Each of 2 pairs, whose 2 points are on the opposite sides of the square, has the center of the polygon as its midpoint. Below figures illustrate the minimal square when n=5. Half square on the left, full square on the right. ![ ](/predownloaded/d0/f3/d0f3cbaeeef6af09d930e48f6741d52f5b886ebe.png) ![ ](/predownloaded/20/71/2071ed6da1fec265488ac3125cb99b409526514d.png) Consider the point of interest to be P. Let's... \measuredangle{RMU} by using k+1,k+2,..,n. Why do these fail? Because, when k>\lfloor\frac{n Read more » • +48 50. By Visors, history, 5 months ago, 2021 SCUEC Rookie Cup Editorial 比赛传送门： [contest:319429] Idea:[user:aabbccSu,2021-03-13] [tutorial:319429A] ~~~~~ #include <bits/stdc++.h> #include <unordered_map> using namespace std; #define ENDL "\n" #define lowbit(x) (x & (-x)) typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<double, double> pdd; const double eps = 1e-8; const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; const double dinf = 1e300; const ll INF = 1e18; const int Mod = 1e9 + 7; const int maxn = 2e5 + 10; bool isLeap(int x) { if ((x % 4 == 0 && x % 100) || x % 400 == 0) return 1; return 0; } int p[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; int q[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; int v[] = {0, 1, 2, 4, 8, 16, 32}; //2021/1/1 Friday int getWeek(int Y, int M, int D) { int y = 2021, m = 1, d = 1, w = 5; while (y != Y || m != M || d != D) { if... = pow(2, i); k < min((int) pow(2, i + 1), n + 1); k++) { for (int t = pow(2, j); t Read more » • 0 51. By vovuh, history, 2 years ago, Codeforces Round #565 (Div. 3) Editorial [problem:1176A] Idea: [user:Vovuh,2019-06-10] <spoiler summary="Tutorial"> [tutorial:1176A] </spoiler> <spoiler summary="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 n; cin >> n; int cnt2 = 0, cnt3 = 0, cnt5 = 0; while (n % 2 == 0) { n /= 2; ++cnt2; } while (n % 3 == 0) { n /= 3; ++cnt3; } while (n % 5 == 0) { n /= 5; ++cnt5; } if (n != 1) { cout << -1 << endl; } else { cout << cnt2 + cnt3 * 2 + cnt5 * 3 << endl; } } return 0; } ~~~~~ </spoiler> [problem:1176B] Idea: [user:MikeMirzayanov,2019-06-10] <spoiler summary="Tutorial"> [tutorial:1176B] </spoiler> <spoiler summary="Solution"> ~~~~~ #include<bits/stdc++.h> using namespace std; int t, n; int cnt[3]; int mai... nxt = (j + k) % 10; int f = (j + k >= 10 ? 1 : 0); dp[i + 1][nxt] = max(dp[i + 1][nxt], dp Read more » • +46 52. By SPyofgame, history, 8 months ago, C2/A2-Binary Table minimize operations ### Original Problem - Easy Version: [Div 2](https://codeforces.com/contest/1440/problem/C1), [Div 1](https://codeforces.com/contest/1439/problem/A1) - Hard Version: [Div 2](https://codeforces.com/contest/1440/problem/C2), [Div 1](https://codeforces.com/contest/1439/problem/A2) ------- You are given a binary table of size n×m. This table consists of symbols 0 and 1 You can make such operation: select 3 different cells that belong to one 2×2 square and change the symbols in these cells (change 0 to 1 and 1 to 0) Your task is to make all symbols in the table equal to 0. You dont have to minimize the number of operations. **(It can be proved, that it is always possible)** -------- And the constraints are - 2 \leq N, M \leq 100 - Easy Version: Limited in 3 \cdot N \cdot M operations - Hard Version: Limited in 1 \cdot N \cdot M operations <spoiler summary="Code solution without minimizing (with comments)"> <spoiler summary="Problem ... ; flip(v, selected_x[k], selected_y[k]); if (F[v] == -1 Read more » • +56 53. By cgy4ever, 6 years ago, Codeforces Round #290 Editorial **Update 1** : here are the reference solutions for this contest: 1. Div2-A: [http://ideone.com/JP1Ksj](http://ideone.com/JP1Ksj) 1. DIv2-B: [http://ideone.com/udz3bN](http://ideone.com/udz3bN) 1. Div2-C / Div1-A: [http://ideone.com/KVobNb](http://ideone.com/KVobNb) 1. Div2-D / Div1-B: [http://ideone.com/7MQqOm](http://ideone.com/7MQqOm) 1. Div2-E / Div1-C: [http://ideone.com/z3FsU2](http://ideone.com/z3FsU2) 1. Div1-D: [http://ideone.com/Y7j21a](http://ideone.com/Y7j21a) 1. Div1-E: [http://ideone.com/Orbacp](http://ideone.com/Orbacp) Note that for Div2-E / Div1-C, it is for the harder version: we need to handle '1' in the cycle. [problem:510A] There are 2 different ways to solve this kind of task: First one is to simulate the movement of the snake head, and you draw '#'s on the board. The code will look like: ~~~~~ head = (1, 1) repeat: repeat m-1 times: head move to right repeat 2 times: head move down repeat 2 times: head move down repeat m-1 ti... is the minimal sum of costs that we can select k cards, so their GCD is 1. First observation is that: GCD Read more » • +156 54. By vovuh, history, 3 years ago, translation, Codeforces Round #527 (Div. 3) Editorial [problem:1092A] <spoiler summary="Tutorial"> [tutorial:1092A] </spoiler> <spoiler summary="Solution"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { #ifdef _DEBUG freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); #endif int t; cin >> t; for (int i = 0; i < t; ++i) { int n, k; cin >> n >> k; for (int j = 0; j < n; ++j) { cout << char('a' + j % k); } cout << endl; } return 0; } ~~~~~ </spoiler> [problem:1092B] <spoiler summary="Tutorial"> [tutorial:1092B] </spoiler> <spoiler summary="Solution"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { #ifdef _DEBUG freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); #endif int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } sort(a.begin(), a.end()); int res = 0; for (int i = 0; i < n; i += 2) { res += a[i + 1] - a[i]; } ... ; cin >> t; for (int i = 0; i < t; ++i) { int n, k; cin >> n >> k; for (int j = 0; j < n Read more » • +32 55. By vovuh, history, 20 months ago, Codeforces Round #605 (Div. 3) Editorial All ideas except the problem C belong to [user:MikeMirzayanov,2019-12-13]. The author of C is [user:Rox,2019-12-13]. Special thanks to [user:opukittpceno_hhr,2019-12-13] for the invaluable help with the round preparation! [problem:1272A] <spoiler summary="Tutorial"> [tutorial:1272A] </spoiler> <spoiler summary="Solution"> ~~~~~ #include <bits/stdc++.h> using namespace std; int calc(int a, int b, int c) { return abs(a - b) + abs(a - c) + abs(b - c); } 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 a, b, c; cin >> a >> b >> c; int ans = calc(a, b, c); for (int da = -1; da <= 1; ++da) { for (int db = -1; db <= 1; ++db) { for (int dc = -1; dc <= 1; ++dc) { int na = a + da; int nb = b + db; int nc = c + dc; ans = min(ans, calc(na, nb, nc)); } } } cout << ans << endl; } ret... ans = calc(a, b, c); for (int da = -1; da <= 1; ++da) { for (int db = -1; db <= 1; ++db Read more » • +61 56. By Alex_2oo8, 5 years ago, translation, Editorial for CROC 2016 Finals and Codeforces Round #347 [problem:664A] -------------- Author of the idea &mdash; [user:GlebsHP,2016-04-17] We examine two cases: 1. a = b &mdash; the segment consists of a single number, hence the answer is a. 2. a < b &mdash; we have gcd(a, a + 1, a + 2, \dots, b) = gcd(gcd(a, a + 1), a + 2, \dots, b) = gcd(1, a + 2, \dots, b) = 1. <spoiler summary="Code"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { string a, b; cin >> a >> b; if (a == b) cout << a; else cout << 1; return 0; } ~~~~~ </spoiler> [problem:663A] -------------- Author of the idea &mdash; [user:gen,2016-04-17] First we check whether any solution exists at all. For that purpose, we calculate the number of positive (the first one and any other with the + sign) and negative elements (with the - sign) in the sum. Let them be pos and neg, respectively. Then the minimum value of the sum that can be possibly obtained is equal to min = (1\,\cdot\,pos -... possible values from 1 to n. **BONUS** Let k be the number of unknowns in the rebus. Prove Read more » • +50 57. By Sabamak, history, 2 years ago, I explain the problem "Rumor" number 893 First you must notice that in tags are written dfs and similar. Lets read the text There is one man who sell rumors.Rumors spread quickly by some people and your ambition is to find the minimal loss so that everybody here about them. In input The first line contains two integer numbers n and m (1 ≤ n ≤ 105, 0 ≤ m ≤ 105) — the number of characters in Overcity and the number of pairs of friends. The second line contains n integer numbers c[i] (0 ≤ c[i] ≤ 109) — the amount of gold i-th character asks to start spreading the rumor. Then m lines follow, each containing a pair of numbers (x[i], y[i]) which represent that characters x[i] and y[i] are friends (1 ≤ x[i], y[i] ≤ n, x[i] ≠ y[i]). It is guaranteed that each pair is listed at most once. Lets explain first input 5 2 2 5 3 4 8 1 4 4 5 The first person tell 4-th and 4-th tell 5-th. The prices of first,4-th and 5-th persons are 2,4 and 8; So the minimal price is 2.If man tell first person he get 2. Because second an... ++){ // cin>>d[i]; // } // for(int i = 1; i <= b; i++){ // cin>>z>>k; // v[z].push_back Read more » • +24 58. By pashka, history, 15 months ago, Разбор задач Апрельского кубка Санкт-Петербургской олимпиады по программированию 2020 [Апрельский кубок Санкт-Петербургской олимпиады по программированию 2020](https://codeforces.com/group/a6606NKaXI/contests) прошел вместо очной олимпиады Санкт-Петербурга для 3-7 классов (но мы планируем все-таки провести ее, когда карантин закончится!) Социальная дистанция (первая лига A) ------------------------------------ Если d\ge x, то условие уже соблюдается, поэтому ответ 0, иначе ответ равен x-d. Пример кода на языке Python: ~~~~~ d = int(input()) x = int(input()) if d >= x: print(0) else: print(x - d) ~~~~~ Три оценки (первая лига B) -------------------------- Для того, чтобы сделать сумму второй и третьей оценки как можно больше, нужно стараться сделать первую оценку как можно меньше. Если n\le 11, то можно сделать первую оценку равной 1, а остаток распределить между второй и третьей оценкой, только надо делать это аккуратно, чтобы обе оценки были от 1 до 5. Один из способов это сделать &mdash; разделить на две примерно равные части... == 1: print(-1) exit() print((n - k) * k // 2) for i in range(k // 2): for j in range(n Read more » • +13 59. By arham_doshi, history, 13 months ago, cses graph session editorial(incomplete) I got bored with solving and wanted to do something which is related to cp and also very fun so i decided to write this tutorial.bare me for my bad English . ### how to solve grid problems <spoiler summary="trick"> here is my template to solve grid problems ~~~~~ int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0}; string ds="RLDU"; int n,m; bool possible(int x,int y){ //cout<<n<<" "<<m<<" "<<x<<" "<<y<<" possible"<<endl; return (x<n&&x>=0&&y<m&&y>=0); } ~~~~~ here we cand do just x+dx[i],y+dx[i] to move the four <br> directions and ds helps if we want to record path.<br> we can easily extend it to include four diagonals </spoiler> 1) counting rooms ------------------ <spoiler summary="explanation"> For each unvisited '.' cell we have to make dfs(or bfs)<br> and keep on coloring the visited nodes.We keep track number<br> of dfs by count variable .our answer would be count. </spoiler> <spoiler summary="code"> ~~~~~ void dfs(... components connect their head node via k-1 edges between heads. Read more » • +77 60. By Endagorion, 6 years ago, Codeforces Round #295 Editorial (now with bonuses!) We would like to thank the testers of this round's and Winter Computer Camp olympiad's problems: [user:alger95,2015-03-02], [user:thefacetakt,2015-03-02], [user:adamant,2015-03-02], [user:dragonic,2015-03-02], [user:Who179,2015-03-02], [user:ASverdlov,2015-03-02]. Make sure to comment if you find any mistakes. **UPD**: I've just remembered to put up the usual challenges for the problems. So, here they go. [problem:520A] Idea: [user:Endagorion,2015-03-02] Preparation: [user:Endagorion,2015-03-02] To check that every letter is present in the string we can just make a boolean array of size 26 and for every letter set the corresponding variable to TRUE. In the end check that there are 26 TRUEs. That is an O(n) solution. Also don't forget to change all letters to lowercase (or all to uppercase). To make all the letters lowercase, one could use standard functions, like tolower in Python. Also, it is known that the letters from a to z have consecutive ASCII numbe... that the other (n - 1) - (l + 1) = n - l - 2 gaps may contain k-1 pluses in any possible way Read more » • +151 61. By boleyn.su, 8 years ago, Codeforces Round #221 Tutorial [problem:376A] writer: [user:boleyn.su,2013-12-25] O(n): Let mid = position of ^ Let value(x) = x if x is a digit , 0 otherwise. Let sum = value(i-th char)*(i-mid) If sum = 0 then answer = balance Else if sum<0 then answer = left Else answer = right [problem:376B] writer: [user:oGhost,2013-12-25] O(n^4): Let f[i][j] = how many money i owes j \#It can be proved we only need to loop n times. Loop n times do: For i,j,k in [1..n] If f[i][j]>0 and f[j][k]>0 then Let delta = min (f[i][j], f[j][k]) Decrease f[i][j] and f[j][k] by delta Increase f[i][k] by delta Answer will be sum{f[i][j]} O(m+n): Let owe[i] = 0 for all i \#Suppose there is an agnecy to help people with debts. \#If you owe someone, you give money to the agency. \#If someone owes you, you get money from the agency. For each ai, bi, ci Increase owe[ai] by ci Decrease owe[bi] by ci Ansewr will be sum{owe[i]|owe[i]>0} [problem:... be proved we only need to loop n times. Loop n times do: For i,j,k in [1..n] If f[i][j]>0 and f Read more » • +30 62. By Nerevar, 9 years ago, translation, Codeforces Round #154 (Div. 2) — tutorial Sorry for the short tutorial: we are too busy preparing and conducting school competition. [problem:253A] Lets assume that we have more boys than girls (the other case is solved similarly). Then we can construct one of the optimal solutions in the following way: we add pairs consisting of a boy and a girl (BG, in that order) to the end of the line until we don't have girls any more. Then add remaining boys to the end of the line. For instance, with 7 boys and 4 girls we will come to the solution BGBGBGBGBBB. [problem:253B] For each x from 1 to 5000 calculate count(x) &mdash; the number of measurements equal to x. The iterate over all possible minimal values m (from 1 to 5000). For a fixed m we can easily figure out which numbers we have to erase: we should erase every number k that k < m or k > 2 \cdot m. To find out the number of such values in the given sequence, we should sum up values count(k) for all such k. [problem:253C] One of the solutions... to the solution BGBGBGBGBBB. [problem:253B] For each x from 1 to 5000 calculate count(x) &mdash Read more » • +40 63. By Ripatti, 10 years ago, translation, Solutions for Codeforces Beta Round #68 <b>A.</b> You can do exactly what is written in a statement. Only one pitfall in this problem is that room leader may have number of points less than zero.<br>[cut]<br><b>B.</b> In this problem you may find optimal strategy for a stowaway. Next you may just simulate a game.<br><br>Optimal strategy for the stowaway is placing from a conrtoller as far as possible. In the moving minute the stowaway should go into wagon that farther to the controller. In the idle minute stowaway should go into wagon in which the controller enter as later as possible. It is always the first or the last wagon of train.<br><br>You may also wrote some dynamic programming solution or a solution fot classic game.<br><br><b>C.</b> Define a trajectory as a line that center of a billiard ball is drawing while it is moving. At begin of moving, the ball chose one from no more than two trajectoties and is moving <span id="result_box" class="short_text" lang="en"><span title="Нажмите, чтобы увидеть альтернативный перев... ">k. Define z as maximal number of billiard balls Read more » • +43 64. By IlyaLos, history, 5 years ago, translation, Editorial for Codeforces Round #346 (Div. 2) [659A &mdash; Round House](http://codeforces.com/contest/659/problem/A) The answer for the problem is calculated with a formula ((a - 1 + b) \mod n + n) \mod n + 1. Such solution has complexity O(1). There is also a solution with iterations, modelling every of |b|'s Vasya's moves by one entrance one by one in desired direction, allowed to pass all the tests. This solution's complexity is O(|b|). [659B &mdash; Qualifying Contest](http://codeforces.com/contest/659/problem/B) Let's consider the participants from every region separately. So for every region we just need to sort all of its participants by their score in non-increasing order. The answer for a region is inconsistent if and only if the score of the second and the third participant in this order are equal, otherwise the answer is the first and the second participant in this order. The solution complexity is O(n \log{n}). [659C &mdash; Tanya and Toys](http://codeforces.com/contest/65... for the problem is calculated with a formula ((a - 1 + b) \mod n + n) \mod n + 1. Such solution Read more » • +85 65. By abusomani, history, 3 years ago, Difference between taking cumulative maximum VS individual maximum for SPOJ problem: ABCPATH I successfully solved a very simple and yet conceptual problem on SPOJ called ( [ABCPATH ](https://www.spoj.com/problems/ABCPATH/)) using three concepts(multi source BFS, Dijkstra and DP) and in the process I hit a surprising result in between, while implementing DP solution. Let me first describe the problem in a nutshell : We are given a 2D array of characters from 'A' to 'Z'. We need to start from 'A' and find the longest path with consecutive alphabets ( cannot trace back like 'N' to 'M' and then again a 'N'). Direction of travel is horizontal, vertical and diagonal. I submitted two times for the problem. One wrong answer and second accepted. The only thing I did differently in the accepted logic was taking maximum after travelling into all eight directions. To give more insight let me add the logic of code. Link to the Accepted solution : [Accepted Solution](https://ideone.com/FnY4vt) Link to the Wrong solution : [Wrong Solution with one line shifted](https://ideon... input and headers) : for (int i = 1; i <= N; i Read more » • 0 66. By gridnevvvit, 8 years ago, translation, Editorial Codeforces Round #216 (Div. 2) ###[problem:369A] We will use greedy algorithm. Let's now i-th day, and current dish is a dish of first type. Then if we have the bowl, let's use it. Otherwise we will increase the answer. If the current dish is a dish of the second type, we first try to get the plate, and then the bowl. If there are no plates/bowls at all, then we will increase the answer. Author's solution: [submission:5306397] ###[problem:369B] In this task you are to determine such array a_1, a_2, \ldots, a_n, that following conditions are met: 1. r \ge a_1 \ge a_2 \ge \ldots \ge a_n \ge l; 2. s_k = \sum_{i = 1}^{k} a_i; 3. s_{all}= \sum_{i = 1}^{n} a_i; It's clear to understand, that value s_k should be distributed evenly between the first k elements. For example, you can use following algorithm: ~~~ remainder = (s_k mod k); for(int i = 0; i < k; i++) { a_i = s_k / k + (remainder > 0); remainder = remainder - 1; } ~~~ If k \ne n, you should use same algorithm... . s_k = \sum_{i = 1}^{k} a_i; 3. s_{all}= \sum_{i = 1}^{n} a_i; It's clear to understand Read more » • +49 67. By fcspartakm, 6 years ago, translation, Codeforces Round #297 (Div.2) Editorial [525A &mdash; Vitaliy and Patty](http://codeforces.ru/problemset/problem/525/A) ------------------ To solve this problem we need to use array cnt[]. In this array we will store number of keys of every type, which we already found in rooms, but didn't use. Answer will store in variable ans. Now, we iterate on string. If current element of string s_i is lowercase letter (key), we make cnt[s_i]++. Else if current element of string s_i uppercase letter (door) and cnt[tolower(s_i)] > 0, we make cnt[tolower(s_i)]--, else we make ans++. It remains only to print ans. Asymptotic behavior of this solution — O(|s|), where |s| — length of string s. [525B &mdash; Pasha and String](http://codeforces.ru/problemset/problem/525/B) ------------------ At first we need to understand next fact &mdash; it doesn't matter in wich order make reverses, answer will be the same for all orders. Let's numerate elements of string from one. To solve given problem we need to coun... + 1], where k — count of exclamation marks which we have in the beginning. After Read more » • +110 68. By kazama460, 2 months ago, (almost) Every Algorithms & Data Structures you needed to learn , with practice problems Hello guys this is <a href="https://www.youtube.com/channel/UC0zvY3yIBQTrSutsV-4yscQ?view_as=subscriber"> CodeNCode </a> and as you guys know I have been working for more than 3 years on Data Structures and algorithms courses. So I thought let's compile it to one place and share so it can be helpful to everyone. <h3>List of Courses</h3> <div class="spoiler"> <b class="spoiler-title"><h5> Basic Algorithms </h5></b> <div class="spoiler-content" style="display: none;"> <ul> <li><a href="https://www.youtube.com/watch?v=NoDYJ7Ks_M0">L01 : Why you should learn binary search</a></li> <li><a href="https://www.youtube.com/watch?v=3vMpagKkqrc">L02 : Understanding Core of Binary Search</a></li> <li><a href="https://www.youtube.com/watch?v=-IMyOkNLRoY">L03 : Monk's encounter with polynomial (HackerEarth)</a></li> <li><a href="https://www.youtube.com/watch?v=FJXZ4Zt8SOk">Ternary String (Codeforces)</a></li> ... =1-VgYXmrF-k">L06 : Chef Got Recipes (Codechef) * Read more » • +308 69. By M.Mahdi, 5 years ago, Codeforces Round #360 Editorial [+ Challenges!] Hi again! If you notice typos or errors, please send a private message. ### [688A: Opponents](http://codeforces.com/contest/688/problem/A) #### Solution Let's find out for each row of the given matrix if it is completely consisting of _ones_ or not. Make another array canWin, and set canWin_i equal to one if the i-th row consists at least one _zero_. Then the problem is to find the maximum subsegment of canWin array, consisting only ones. It can be solved by finding for each element of canWin, the closest zero to it from left. The complexity of this solution is O(nd), but the limits allow you to solve the problem in O(nd^2) by iterating over all possible subsegments and check if each one of them is full of _ones_ or not. <spoiler summary="C++ code"> ~~~~~ // . .. ... .... ..... be name khoda ..... .... ... .. . \\ #include <bits/stdc++.h> using namespace std; inline int in() { int x; scanf("%d", &x); return x; } const int N = 202; int ... ], cnt); } } bool ok = 1; while(k > 1) { ok &= (cntP[isP[k]] > 0); cntP[isP[k Read more » • +94 70. By adamant, 7 years ago, translation, Aho-Corasick algorithm. Construction Hi everyone! This time I would like to write about the Aho-Corasick algorithm. This structure is very well documented and many of you may already know it. However, I still would try to describe some of the applications that are not so well known. [cut]<br> This algorithm was proposed by Alfred Aho and Margaret Corasick. Its is optimal string pattern matching algorithm. e.g. given the string set {"a", "abba", "acb"} and given text, say, "abacabba". With Aho-Corasick algorithm we can for each string from the set say whether it occurs in the text and, for example, indicate the first occurrence of a string in the text in \mathit O(|T| + |S|), where |T| is the total length of the text, and |S| is the total length of the pattern. But in fact it is a drop in the ocean compared to what this algorithm allows. To understand how all this should be done let's turn to the prefix-function and KMP. Let me remind you, the prefix function is called array \pi[i] = max(k): s[0..k) ... to the prefix-function and KMP. Let me remind you, the prefix function is called array \pi[i] = max(k): s[0..k Read more » • +100 71. By Tampere, 4 years ago, Notes on Codeforces Beta Round #79, Div2-A, B, C, D, E, Div1-D [problem:102A] We can adopt a triple loop to enumerate all the reasonable combination, and find out the one with the minimum cost. [problem:102B] A simple implementation problem. Keep adding all the digits to obtain a new integer, and repeat again until it is reduced to an integer with only one digit. [problem:102C] At first, we count the number that each letter has appeared in the string. To eliminate the number of different letters as many as possible, it is straightforward to first delete the letter with the minimum number, and then the one with the second minimum number, and then the one with the third minimum number, and so on. [problem:102D] Although n can be as large as 10^9, the value of m in fact has determined that at most 2m of the nodes (stops) really affect the result, since the person can only get off the bus at these specified stops. Thus, we should first compress the number of nodes (or stops) to the order of O(m), which can be achieve... }^{k}dp1[i]. For a route from node i to node j, we can calculate dp1[j]=\sum_{k=i}^{j-1}dp1[k Read more » • +3 72. By Malinovsky239, 9 years ago, translation, Разбор задач Codeforces Round #140 ### [A div2. Куда свернуть?](http://codeforces.ru/contest/227/problem/A) Посмотрим на векторное произведение \overrightarrow{AB} на \overrightarrow{BC}, численно равное \overrightarrow{AB_x} \cdot \overrightarrow{BC_y} - \overrightarrow{AB_y} \cdot \overrightarrow{BC_x}. Знак векторного произведения определяется знаком синуса ориентированного угла между векторами (т.к. векторное произведение также равно |\overrightarrow{AB}| \cdot |\overrightarrow{BC}| \cdot sin(\overrightarrow{AB}, \overrightarrow{BC})), а именно этот-то знак нам и нужно узнать. Если произведение равно нулю, то это в данной задаче означает, что A, B и C лежат на одной прямой, а значит ответ &mdash; <<TOWARDS>>. Если произведение больше нуля, то ответ &mdash; <<LEFT>>. И, наконец, если оно меньше нуля, то ответ &mdash; <<RIGHT>>. Также стоит обратить внимание, что вычисление векторного произведения требуется производить в 64-битном типе, чтобы избежать переполнения. [Решение](http://past... кучек с 1-й по k-ю (в 0-индексированном, отсортированном в порядке невозрастания массиве Read more » • +57 73. By fchirica, 8 years ago, Codeforces Round #191 — Tutorial [problem:327A] I’ll present here the O(N ^ 3) algorithm, which is enough to solve this task. Then, for those interested, I’ll show a method to achieve O(N) complexity. **O(N ^ 3) method:** The first thing to observe is that constrains are slow enough to allow a brute force algorithm. Using brute force, I can calculate for each possible single move the number of 1s resulting after applying it and take maximum. For consider each move, I can just generate with 2 FOR loops all indices i, j such as i <= j. So far we have O(N ^ 2) complexity. Suppose I have now 2 fixed vaIues i and j. I need to calculate variable cnt (initially 0) representing the number of ones if I do the move. For do this, I choose another indice k to go in a[] array (taking O(N) time, making the total of O(N ^ 3) complexity). We have two cases: either k is in range [i, j] (this means i <= k AND k <= j) or not (if that condition is not met). If it’s in range, then it gets flipped, so we add to count variable 1 – ... – a[k] (observe that it makes 0 to 1 and 1 to 0). If it’s not in range, we simply add to cnt variable Read more » • +86 74. By Tampere, 4 years ago, Notes on Codeforces Beta Round #95, A, B, C, D, E, F (two pointers) [problem:131A] Modify the letters as the problem requires. [problem:131B] We use a[i] to denote the number of a non-negative integer i while using b[i] to denote the number of a negative integer -i (i>0). For any positive integer i, we have min(a[i], b[i]) choice, while for i=0, we have \frac{a[0] \times (a[0]-1)}{2} choice. Thus, the final answer should be \sum_{i=1}^{10}(min(a[i], b[i]))+\frac{a[0] \times (a[0]-1)}{2}. [problem:131C] We enumerate all the feasible combination of boys and girls, and only consider those that satisfy the requirements. Then, the main issue is to calculate C_n^k=\frac{n!}{k! \times (n-k)!}. Although n is not larger than 30, it is still difficult (or infeasible) to compute n!. Thus, we modify the formula as C_n^k=\frac{n\times (n-1)\times (n-2)...\times (n-k+1)}{1 \times 2 \times 3... \times k}=n/1 * (n-1)/2 * (n-2)/3 ... * (n-k+1)/k, which could handle all n\le 30. [problem:131D] The solution is first DF... =\frac{n\times (n-1)\times (n-2)...\times (n-k+1)}{1 \times 2 \times 3... \times k}=n/1 * (n-1)/2 * (n-2 Read more » • 0 75. By vok8, history, 14 months ago, Editorial: Programming Contest #1 (Chapter 'Ramayan') - Contest Link: [Programming Contest #1 (Chapter 'Ramayan')](https://www.codechef.com/PCR12020?itm_campaign=contest_listing) [Laxman and Maths](https://www.codechef.com/PCR12020/problems/LAXMAN) - Problem Setter: [user:Pallove,2020-05-19] <spoiler summary="Logic (Explanation)"> We know that: ![ ](/predownloaded/b8/3a/b83afd2ddee685b45f909470706df7f89fab3252.png) So, one of the best ways to create the array A of length n, is: A[i]=i, where 1<=i<=n **Time Complexity**: O(n), per test case. **Space Complexity**: O(1), per test case. </spoiler> <spoiler summary="Problem Setter's Code">~~~~~ #include<bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while(t--) { int n; cin >> n; for(int i=1;i<=n;++i) cout << i << " "; cout << '\n'; } return 0; } ~~~~~ </spoiler> -/-/- [Raavan and Subar... Editorial: Programming Contest #1 (Chapter 'Ramayan'), K-1 elements as 0, then we will have the XOR of first sub-array of length  K, equal to X Read more » • +25 76. By vovuh, history, 3 years ago, translation, Educational Codeforces Round 43 Editorial [problem:976A] <spoiler summary="Editorial"> [tutorial:976A] </spoiler> <spoiler summary="Solution (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; string s; cin >> n >> s; if (n == 1) { cout << s << endl; } else { int cnt0 = 0; for (int i = 0; i < n; ++i) cnt0 += s[i] == '0'; cout << 1; for (int i = 0; i < cnt0; ++i) cout << 0; cout << endl; } return 0; } ~~~~~ </spoiler> [problem:976B] <spoiler summary="Editorial"> [tutorial:976B] </spoiler> <spoiler summary="Solution (PikMike)"> ~~~~~ #include <bits/stdc++.h> #define forn(i, n) for (int i = 0; i < int(n); i++) using namespace std; int n, m; long long k; int main() { scanf("%d%d%lld", &n, &m, &k); if (k < n){ printf("%lld 1\n", k + 1); return 0; } k -= n; long long row = k / (m - 1); prin... < n){ printf("%lld 1\n", k + 1); return 0; } k -= n; long long row = k / (m - 1 Read more » • +27 77. By Retired_MiFaFaOvO, 7 years ago, Codeforces Round #268 Editorial I'll upload my example solutions and will post links to them as soon as it becomes possible. All the problems in Div 1 don't have the unique solution. I list several solutions to each problems. There are also some interesting bonus problems. I can't solve some of them yet :( If you have interesting ideas, feel free to share and discuss your ideas in the comments. :) My English is poor, so if there are some mistakes or something you can't understand, you can also discuss it in the comments. [problem:469A] [I Wanna Be the Guy](http://kayin.moe/iwbtg/downloads.php) is an interesting game. I strongly recommend it to you. The problem itself is easy. Just check if all the levels could be passed by Little X or Little Y. [submission:7894174] [problem:469B] This problem is not hard. Just iterator over all possible t, and check if the schedule of Little X and Little Z will overlap. [submission:7894252] **Bonus:** 1. p,q\leq 50, l,r\leq 10^9 2. p,q,l,r\leq 1... the problems in Div 1 don't have the unique solution. I list several solutions to each problems Read more » • +124 78. By AnandOza, history, 20 months ago, Atcoder Beginner Contest 146 -- Unofficial English Editorial Hi all, [Atcoder Beginner Contest 146](https://atcoder.jp/contests/abc146) was today. I wrote an unofficial English editorial. Hope it helps! ### [A: Can't Wait for Holiday](https://atcoder.jp/contests/abc146/tasks/abc146_a) We simply find the index in the week, and print 7-i (taking care to order the days correctly so Sunday gives us 7 as the output). Runtime: \mathcal{O}(1). <spoiler summary="Sample code"> ~~~~~ String w = "SUNMONTUEWEDTHUFRISAT"; // this is sort of a bad way to do this String s = in.next(); int i = w.indexOf(s) / 3; out.println(7 - i); ~~~~~ </spoiler> ### [B: ROT N](https://atcoder.jp/contests/abc146/tasks/abc146_b) We can simply loop through the string and increment each character by N, taking care to subtract 26 if we go past the end of the alphabet. Runtime: \mathcal{O}(|S|). <spoiler summary="Sample code"> ~~~~~ int n = in.nextInt(); char[] s = in.next().toCharArray(); for (int i = 0; i < s.length; i++) { s[i]... to be equal to the actual number of elements, so we require j-(i-1) < K. We can count the pairs Read more » • +36 79. By misof, 6 years ago, Yandex Algo 2015 (cancelled) round 2 editorial Hello :) I was the writer for the Round 2. I'm very sad that the contest platform failed and you couldn't do your best solving them -- for me it's also sad as my work on the problems is now wasted. Hopefully you liked the problems themselves. Here are the problem statements: - A http://pastebin.com/raw.php?i=U8SfbSL8 - B http://pastebin.com/raw.php?i=bAi07eMm - C http://pastebin.com/raw.php?i=R72vqKkk - D http://pastebin.com/raw.php?i=Ar5CmJ8j - E http://pastebin.com/raw.php?i=wiCtb0ab - F http://pastebin.com/raw.php?i=iaMnb9cs And below are brief solution ideas. Ask if anything is unclear. **A (ascending the stairs)** Dynamic programming in O(n). Let W[x] be the number of ways to climb the first x steps of the stairs. (We will call that "state x".) W[n] is the answer we want. For each x, let y be the lowest state that we can go directly from state y to state x -- i.e., the sum H[y]+...+H[x-1] is still <= m. Then W[x] is simply the sum of W[y] through W[... to state x -- i.e., the sum H[y]+...+H[x-1] is still <= m. Then W[x] is simply the sum of W[y] through W Read more » • +156 80. By ifsmirnov, history, 5 years ago, translation, Codeforces Round #349 Editorial [problem:667A] To know how much water you consume per second you should divide consumed volume, v, by the area of the cup, \dfrac{\pi d^2} 4. Then you should compare thisit with e. If your speed of drinking is greater, then you'll drink all the water in \dfrac{h}{\tfrac{4v}{\pi d^2}-e} seconds. Otherwise you would never do it. [problem:667B] It is possible to make a convex polygon with given side lengths if and only if a generalized triangle inequality holds: the length of the longest side is less than the sum of lengths of other sides. It is impossible to make a convex polygon from a given set, so there is a side which is longest than (or equals to) than sum of others. Assume it is greater by k; then it is sufficient to add a rod of length k+1. More, it is clear that adding any shorter length wouldn't satisfy the inequality. Thus the answer for the problem is \texttt{max}(l_1, \dots, l_n) - (l_1 + \dots + l_n - \texttt{max}(l_1, \dots, l_n)) + 1. [probl... . Assume it is greater by k; then it is sufficient to add a rod of length k+1 . More, it is clear Read more » • +68 81. By I_Love_Tina, history, 5 years ago, Codeforces Round #361 (Div. 2) Editorial [A.Mike and Cellphone](http://codeforces.com/contest/689/problem/A) Author:[user:dans,2016-07-06]. Developed:[user:reality,2016-07-06],[user:ThatMathGuy,2016-07-06] We can try out all of the possible starting digits, seeing if we will go out of bounds by repeating the same movements. If it is valid and different from the correct one, we output "NO", otherwise we just output "YES". <spoiler summary="C++ code"> ~~~~~ pair < int , int > s[55][55]; int v[55][55]; pair < int , int > where[55]; int main(void) { for (int i = 1;i <= 10;++i) for (int j = 1;j <= 10;++j) v[i][j] = -1; v[1][1] = 1; v[1][2] = 2; v[1][3] = 3; v[2][1] = 4; v[2][2] = 5; v[2][3] = 6; v[3][1] = 7; v[3][2] = 8; v[3][3] = 9; v[4][2] = 0; for (int k = 0;k <= 9;++k) for (int i = 1;i <= 4;++i) for (int j = 1;j <= 4;++j) if (v[i][j] == k) where[k] = {i,j}; for (int i = 0;i <= 9;++i... ][2] = 0; for (int k = 0;k <= 9;++k) for (int i = 1;i <= 4;++i) for (int Read more » • +113 82. By Geothermal, history, 8 months ago, AtCoder Beginner Contest 184 Unofficial Editorial #A &mdash; Determinant Just perform the requested computation. There really isn't much to do here. Time Complexity: O(1). [Click here for my submission.](https://atcoder.jp/contests/abc184/submissions/18318540) --- #B &mdash; Quizzes A simple brute-force simulation works here. Iterate over the characters of S from left to right, adding one to the answer if the current character is an o and subtracting one if it's an x (while ensuring that the score never drops below zero). Time Complexity: O(N). [Click here for my submission.](https://atcoder.jp/contests/abc184/submissions/18318362) --- #C &mdash; Super Ryuma The key observation is that the answer will always be at most three. We will provide a constructive proof. Suppose that we want to go from (x_1, y_1) to (x_2, y_2). In our first move, we move to any point (x_3, y_3) such that x_3 + y_3 has the same parity as x_2 - y_2. Then, we will finish with two diagonal moves. We want to ... } = 0. Otherwise, we have$$dp_{ijk} = 1 + \frac{i}{i+j+k} dp_{(i+1)jk} + \frac{j}{i+j+k} dp_{i(j+1 Read more » • +45 83. By cgy4ever, 7 years ago, Codeforces Round #270 Editorial [problem:472A] One way to solve this is by bruteforce: there are O(n) different ways to decomose n as sum of two number. If we can check if a number is a prime in O(1) then the whole algorithm can run in O(n). You can use Sieve of Eratosthenes to do the pre-calculation. And another way is try to prove this theorem. The prove is simple: if n is odd number, then 9 and (n-9) is an answer (n-9 is an even number at least 4, so a composite number), and if n is even number, then 8 and (n-8) is an answer (n-8 is an even number at least 4, also must be a composite number). [problem:472B] This task can be solve by greedy: the k people with highest floor goes together, and next k people with highest floor goes together and so on. So the answer is 2 * ((f[n]-1) + (f[n-k]-1) + (f[n-2k]-1) + ...) . It is a bit tricky to prove the correctness of greedy, since people can get off the elevator and take it again. We can give a lower bound of the answer by flow analysis: between floor i ... with highest floor goes together and so on. So the answer is 2 * ((f[n]-1) + (f[n-k]-1) + (f[n-2k Read more » Tutorial of Codeforces Round #270 • +137 84. By piloop, 9 years ago, Codeforces Round #119 — Editorial ### Problem [189A --- Cut Ribbon](http://www.codeforces.com/problemset/problem/189/A) The problem is to maximize _x+y+z_ subject to _ax+by+cz=n_. Constraints are low, so simply iterate over two variables (say _x_ and _y_) and find the third variable (if any) from the second equation. Find the maximum over all feasible solutions. Other approaches: Use dynamic programming with each state being the remainder of ribbon. Select the next piece to be _a_, _b_ or _c_. ### Problem [189B --- Counting Rhombi](http://www.codeforces.com/problemset/problem/189/B) Observe that lots of rhombi have the same shape, but are in different locations. What uniquely determines the shape of a rhombus? Its width and its height. Is it possible to build a rhombus with every width and every height such that the vertices of the rhombus are in integer points? [cut] No, it is possible only if the width and the height are both even. How many places we can put a rhombus of width _w0_ and height ... the following equation: _ans(k,i,j) = min (ans(k-1,i,l)+ans(0,l,j))_ for (_1≤l≤k_) which can Read more » • +29 85. By Geothermal, history, 2 years ago, AtCoder Beginner Contest 137 English Solutions Although AtCoder seems to be getting back to posting English editorials, I'm continuing to release some myself in case having the extra explanations helps some people. (Sidenote: Some of the provided submissions come from after the contest itself, because I had to leave midway through, before I got the chance to debug my E or write my F.) --- #A &mdash; +-X Just use your language's max function. As$A$and$B$are small, we don't need to worry about integer overflow. Runtime:$O(1).$[Click here for my submission.](https://atcoder.jp/contests/abc137/submissions/6802607) --- #B &mdash; One Clue Let's try to find the minimum and maximum values in the answer. It's fairly easy to see that all integers between them will also be in the set. To find the minimum possible position of a black stone, we place$K$black stones such that$X$is at the maximum position. Then, the minimum position will thus be$X-K+1$, as we have$K-1$black stones to the left of$X$.... . Then, the minimum position will thus be$X-K+1$, as we have$K-1$black stones to the left of$X

• +34

86.
By Endagorion, history, 4 years ago,
Яндекс.Алгоритм 2017, третий отборочный раунд: разбор (с челленджами и свистелками) На этот раз я решил попробовать писать разбор в спойлерах, как уже делал кое-кто из авторов. Буду рад вашим комментариям о том, стало ли лучше. #### Задача A. Сдвиги Темы: динамическое программирование. Общий комментарий: это первая среди "сложных" задач контеста. В ней можно помочь хорошее знакомство со стандартными задачами на ДП, но довести решение до финального правильного вида все равно непросто. Решение: пускай мы можем сдвигать не только вправо, но и влево. <spoiler summary="Как решать такую задачу?"> Прежде всего заметим, что сделать сдвиг -- это то же самое, что переместить какой-то символ в другое место. Ясно, что никакой символ не надо двигать больше одного раза, поскольку вместо этого можно сразу поставить его на финальное место и не тратить действия. Кроме того, очевидно, что сдвиги не меняют количество вхождений каждого символа в строку, поэтому в обеих строках посимвольные вхождения должны совпадать. Посмотрим теперь на символы исходной строки, котор...
$, противоречие! , , then the sequence is not$k$-recursive**. Otherwise, the function defined by$f(a_{i -1}, \ldots, a_

• +255

87.
By Zlobober, 6 years ago, translation,
VK Cup Round 3 editorial [problem:542A] -------------- Let's fix the TV channel window and look for a commerical having the largest intersection with it. There are four types of commercials: lying inside the window, overlapping the window and partially intersecting the window from the left and from the right. It's easy to determine if there is overlapping commercial: it's enough to sort commercials in increasing order of the left end and then while iterating over them from left to right, keep the minimum value of a right end of a commercial. If when we pass the window $j$ and see that current value of the maximum right end is no less than $b_j$ then there exists a commercial overlapping our window and the value is equal to the $(r_i - l_i) \cdot c_i$. Among all commercials that lie inside our window we need the longest one. It can be done by similar but a bit harder manner. Let's use sweepline method. While passing through the end of the commercial $r_i$, let's assign in some data structure (like seg...
$and also remember for each prime number$p$in it in which powers$k$the value$(p^k + 1)$divides Read more » • +97 88. By Edvard, history, 6 years ago, translation, Разбор задач Educational Codeforces Round 3 Этот раунд был немного необычным: некоторые из задач были ранее подготовлены студентами и сотрудниками Саратовского ГУ для прошедших олимпиад, одна из задач была подготовлена участником [user:dalex,2015-12-19] для одного из регулярных (неучебных) раундов Codeforces, но не использована там. [problem:609A] Отсортируем массив по невозрастанию. Тогда ответом на задачу будет несколько первых флешек. Будем идти по массиву слева направо пока не наберем сумму$m$. Количество взятых элементов и будет ответом на задачу. Асимптотическая сложность решения:$O(n logn)$. [problem:609B] Пусть$cnt_i$&mdash; количество книг$i$-го жанра. Тогда ответом на задачу будет величина равная$\sum\limits_{i=1}^m \sum\limits_{j=i+1}^m cnt_i \cdot cnt_j=\frac{n \cdot (n - 1)}2 - \sum\limits_{i=1}^m \frac{cnt_i \cdot (cnt_i - 1)}2$. В первой сумме мы считаем непосредственно количество хороших пар книг, а во втором из общего количества пар книг вычитаем количество плохих пар. Асимптотическая... Нура может купить$k$гаджетов за$x$дней то за$x+1$день она тоже сможет их купить. Таким образом Read more » • +55 89. By Alexander, 10 years ago, translation, Разбор задач. Codeforces beta round #89. <p class="MsoNormal"><span style="">Editorial. </span></p> <p class="MsoNormal"><b style=""><span style="">Task A.</span></b></p> <p class="MsoNormal"><span style="">First problem only is realization. In need read input string, delete all uppercase and lowercase vowels letter and print answer. </span></p> <p class="MsoNormal"><span style=""><span style="">&nbsp;</span></span></p> <p class="MsoNormal"><b style=""><span style="">Task B. </span></b></p> <p class="MsoNormal"><span style="">Second problem is realization too. Good solution to calc count space in beginning of string. In handkerchief pattern there is 2 * n + 1 rows. In rows form 0 to N number of space is 2 * n &ndash; i. In rown number from N + 1 to 2 * N number of space is (I - N) * 2. </span></p> <p class="MsoNormal"><span style="">&nbsp;</span></p> <p class="MsoNormal"><b style=""><span style="">Task C. </span></b></p> <p class="MsoNormal"><span style="">In this task it need to find a minimal sum that to find a beau... . In handkerchief pattern there is 2 * n + 1 rows. In rows form 0 to N number of space is 2 * n – i Read more » • +8 90. By Lance_HAOH, history, 4 years ago, How to solve this Coin Change problem? Hi. I am trying to solve [this](https://dunjudge.me/analysis/problems/348/) problem. For convenience, I have replicated the problem statement below: A person is on floor$ N $of a building. He has to take the lift down to floor$ 0 $. To use the lift exactly **once**, one token is needed. This lift is special as it can only travel downwards for **one** of the following levels each time it is used:$ 1, 5, 10, 17, 50, 100, 500, 1000, 5000, 10000 $For example, if the person is standing on floor$ 6 $, one way to reach floor$ 0 $is to take the lift down$ 5 $floors, then take the lift again to go down$ 1 $more floor$(6 - 5 - 1 = 0)$.$ 2 $tokens are used in this case. The objective is to find the **minimum** number of tokens that the person needs to use to reach floor$ 0 $from a given floor$ N $. For the above example, the answer is$ 2 $. **My analysis:** This problem looks exactly like the classical coin change problem where we want to find the minimum ... it is used:$ 1, 5, 10, 17, 50, 100, 500, 1000, 5000, 10000 $For example, if the person Read more » • -3 91. By GlebsHP, history, 6 years ago, translation, Codeforces Round #327 problems analysis I like the idea of [user:Endagorion,2015-10-25] to supplement the problems analysis with small challenges, somehow related to the problem preparation, it's generalization, or more effective solution. Following this, some problems in this analysis are also complemented with this sort of tasks. Div. 2A (Wizards' Duel) ------------------ Idea of the problem: Roman Gusarev, development: [user:timgaripov,2015-10-25]. Let's start with determining the position of the first collision. Two impulses converge with a speed$p + q$, so the first collision will occur after$\frac{L}{p + q}$seconds. The coordinate of this collision is given by the formula$x_1 = p \cdot \frac{L}{p + q}$. Note, that the distance one impulse passes while returning to it's caster is equal to the distance it has passed from the caster to the first collision. That means impulses will reach their casters simultaneously, and the situation will be identic to the beginning of the duel. Hence, the second collision ... =(i_1 - 1) + ... +(i_k - k)=\sum\limits_{p = 1}^ki_p$ — $\dfrac{k\cdot(k+1 )}{2}$. $T$$\le Read more » • +106 92. By salt_n_ice, history, 8 months ago, CSES Longest Flight Route TLE in one test case Problem : [Link](https://cses.fi/problemset/task/1680). I simply did bfs from node 1 and found the maximum distance from this node to all other nodes <spoiler summary="Code"> ~~~~~ const int INF = 1e9; const int sz = 1e5+1; int n,m; vector<int> last(sz); vector<vector<int> > adj(sz); vector<int> d(sz,0); void solve() { cin>>n>>m; for(int i=0; i<m; ++i) { int a,b; cin>>a>>b; adj[a].push_back(b); } queue<int> q; q.push(1); while(!q.empty()) { int s = q.front(); q.pop(); for(auto u : adj[s]) { if(d[s]+1>d[u]) { d[u]=1+d[s]; last[u]=s; q.push(u); } } } if(d[n]==0) { cout<<"IMPOSSIBLE"<<endl; return; } vector<int> ans; int k=n; while(k!=1) { ans.push_back(k); k=last[k]; } ans.push_back(1);... k=n; while(k!=1) { ans.push_back(k); k=last[k Read more » • -2 93. By AK18, 17 months ago, Invitation to CodeRed — 2020 by IIIT Allahabad Hello everyone !! After 3 successful editions, [Aparoksha](https://aparoksha.org/) is back with flagship coding event &mdash; **CodeRed**. **CodeRed 2020** consists of 2 rounds, **Online preliminary round** and **Onsite final round**. The online preliminary round will be a **3-hour** long team event with a maximum size of the team being 3 members. The participants need not be from the same college/institution/organization. Problem set has 6/7 problems of varying difficulty. [CodeRed 2020](https://www.codechef.com/CORE2020?itm_campaign=contest_listing) is scheduled at [March 11, 2020 at 22:00 IST](https://www.timeanddate.com/worldclock/fixedtime.html?msg=CodeRed+2020&iso=20200311T1630&ah=3) Last year [CodeRed 2019](https://www.codechef.com/CORD2019?itm_campaign=contest_listing) had 1271 teams registered, we are expecting higher participation this year. You can register your team here &mdash; [CodeRed 2020 online preliminary round](https://www.codechef.com/CORE2020?itm_campaig... such that → k > 0 → z_i <= 0 If B+1 - A = q \times GCD(k,a_1 , a_2 , .. a_n Read more » • +77 94. By netman, 7 years ago, translation, Codeforces Round #260 — Editorial Warning: my English is very bad. [problem:456A] Solution: [submission:7407613]; In this task you need to check the existense of such pair i and j, such that i \neq j, a[i] < a[j], b[i] > b[j]. If such i and j exist, Alex is happy. There is very simple solution. Let's check that for all i a[i] = b[i]. If this condition is true we should print "Poor Alex". We can easy prove it. Let's sort arrays a and b like pair of numbers in increasing order. We can see that Alex is happy if we have at least one inversion in array b, i.e there is such pair i and j that b[i] > b[j] и i < j (i < j \Leftrightarrow a[i] < a[j]). i.e it means that array b is not sorted and it's means that a \neq b. [problem:456B] Solutions: [submission:7407625], [submission:7407631]; In this task you need to calculate formula that given in the statement, but it's hard to calculate it with the naive way. But we can transform our formula to this: (1^{n} + ... ] = true and lose[v] = false, then if k \mod 2 = 1, then first player win, else second player win Read more » • +45 95. By Shadek, 7 years ago, Round 249 DIV 2 Problem B I tried to solve it by bfs by considering every possible states. That's why I got TLE. Greedy was the intended solution for this problem. My code that got TLE in contest: ~~~~~ string s; map<string, int> mp; struct state { string in; int swap; }; int main(void) { //freopen("1.txt", "r", stdin); //freopen("2.txt", "w", stdout); char in[20]; int k; int i,j; int ind; while(cin >> in >> k) { queue<state> pq; //cout << in << " " << k << endl; struct state st, temp; st.in= in; ind = 1; st.swap = 0; pii pii1 = make_pair(st.in, st.swap); pq.push(st); mp[st.in] = ind++; s = "0000000000000000000"; while(!pq.empty()) { temp = pq.front(); pq.pop(); //if(temp.swap == k) //{ if(temp.in > s) ... ) { //freopen("1.txt", "r", stdin); //freopen("2.txt", "w", stdout); char in[20]; intk Read more » • -6 96. By Ripatti, 9 years ago, translation, Editorial for Codeforces Round #150 **Adiv2.** Consider an array A of integers in range from 1 to nk. Let's remove from A all numbers a_i and all other numbers store into an array B. The array B will have (n-1)k elements. Now for i-th kid you should output numbers a_i, B[(n-1)*(i-1) + 1], B[(n-1)*(i-1) + 2], ... B[(n-1)*(i-1) + n - 1] (B is 1-based). Author is [user:Gerald] [cut] . **Bvid2.** Solution 1. You should write some bruteforce solution over all numbers with no more than 9 digits (number 10^9 should be considered separately). Bruteforce algo seems like this: ~~~~~ dfs( int num ) // run it as dfs(0) if (num > 0 && num <= n) ans++ if (num >= 10^8) return for a = 0..9 do if num*10+a>0 then if number num*10+a has no more than 2 different digits then dfs( num*10+a ) ~~~~~ ans will store the answer. After that you wrote bruteforce, you can run it and see that it works fast (that is same time for any testcase). Solution 2. Let's build al... numbers a_i and all other numbers store into an array B. The array B will have (n-1)k elements Read more » • +44 97. By dalex, 8 years ago, translation, Codeforces Round #222 — Problem Analysis [Link to announcement and discussion](/blog/entry/10138). And here is the problem analysis. #### A div 2: [problem:378A] Make three counters: for wins of both players and for a draw. Iterate over all six ways how they can throw a dice. For each way determine who wins or there is a draw and increment the corresponding counter. #### B div 2: [problem:378B] You can think a bit and understand that you should consider only corner cases: k = 0 and k = \frac{n}{2}. All other cases will be something between them. If k = 0, we should choose n biggest elements from two sorted lists, one of the ways is to use two pointers method. And if k = \frac{n}{2}, we just mark first \frac{n}{2} people in each list. #### A div 1 / C div 2: [problem:377A] Start BFS or DFS from any free cell. As the maze is connected, this search will visit all s free cells. But we can stop the search when it visits s - k free cells. It's obvious that these s - k cells are connected to... and understand that you should consider only corner cases: k = 0 and k = \frac{n}{2}. All other cases Read more » • +60 98. By practice080, 10 months ago, Need help for a multi-source searching problem :) The problem statement is simple: - **Given a undirected unweighted graph with V vertex and E edges, M (1\leq M\leq V) of the vertex are special vertex. For every vertex, find the K-th nearest special vertex to it.** For K=1, I realize that this is just a BFS, starting from special vertex can get \mathcal{O}(V+E) complexity. But when K>1, I have no idea how to optimize the BFS that can get better complexity that brute force \mathcal{O}(V(V+E)) I am wondering is there any algorithm to find out the answer more efficiency, such as \mathcal{O}(K(V+E)) or \mathcal{O}(V+E). Thanks! edges, M (1\leq M\leq V) of the vertex are special vertex. For every vertex, find the K-th, But when K>1, I have no idea how to optimize the BFS that can get better complexity that brute, For K=1, I realize that this is just a BFS, starting from special vertex can get \mathcal{O}(V+E Read more » • +7 99. By Kostroma, 9 years ago, translation, Codeforces Round #120 (Div.2) — editorial #### A --- [Vasya and the Bus](http://codeforces.com/contest/190/problem/A) Firstly, if n=0, then children can't be in the bus, so if m=0 then the answer is (0, 0), otherwise the answer is "Impossible". Now n>0. If m==0, than it is only one possible variant of passage --- the answer is (n, n). Otherwise, more grown-up take some children, less the sum that people pay. So, if only one adult takes all children, than we get maximal sum --- n+m-1. Maximum min(n, m) adults can take the children with them, so the minimal answer is n+m-min(n, m)=max(n, m). #### B --- [Surrounded](http://codeforces.com/contest/190/problem/B) Let's find the minimum distance between two circles L. Then the answer to our problem is L/2. Now d is the distance between the centers of the circles, R, r --- their radiuses. There are 3 possible cases: - Circles don't intersect. Then L = d - R - r. Firstly, it's reachable: let's consider the segment, connecting the ce... +1. Let's find for every index i a minimal index j such that segment [i,j] contsins k Read more » • +19 100. By BekzhanKassenov, 6 years ago, translation, Center of a graph Hello, CodeForces! From time to time some people ask questions related to center, radius and diameter of graph (I could google only [about tree](http://codeforces.com/blog/entry/3814)). In this topic you can find their definitions and algorithms for finding them. **Problem:** you are given graph G = (V, E), where V is set of nodes and E is set of edges. You have to find its center, radius and diameter. Let's denote d_{i, j} as shortest distance between nodes {i, j \in V}. Then diameter of graph is denoted as the greatest possible among all possible shortest distances between two nodes: diam(G) = \displaystyle \max_{u, v \in V} d_{v, u} Also we can define eccentricity of node as maximal distance from that node to other: \varepsilon (v) = \displaystyle \max_{u \in V} d_{v, u} Having values of eccentricity of all nodes, we can define radius of graph as minimal one among them: rad(G) = \displaystyle \min_{v \in V} \varepsilon (v) Also we can obser... diam; // Diamater of graph // Floyd-Warshall's algorithm for (int k = 0; k < N; k Read more » • +20 101. By Sereja, 9 years ago, translation, Разбор задач Codeforces Round #131 ### [problem:214A] В данной задаче решение --- просто перебрать возможные пары чисел и проверить их на правильность. Делать это можно было любым способом. ### [problem:214B] Число делится на 2,3,5 только в том случае, если сумма цифр кратна 3, а последняя цифра 0, то есть если в наборе нету нулей, то ответ -1. Дальнейшее решение --- разбор случаев. Возьмем все цифры в невозрастающем порядке, если сумма цифр кратна 3, то это и есть ответ. Если остаток от деления вышел 1, то нужно убрать 1 цифру у которой остаток от деления на 3 равен 1. Если такой не нашли то нужно убрать 2 цифры с остатком 2. Аналогично рассматривается случай когда изначальный остаток равен 2. Так-же нужно рассмотреть случай когда остались только нули, в этом случае нужно вывести только 1 ноль. ### [problem:213A] Решение --- жадность. Пусть у нас компьютеры стоят по кругу, и ходами "вперед" назовем перемещения (1->2, 2->3, 3->1), а перемещением "назад" (1->3,3->2,2->1). Заметим что ходить "наз... (len,9) = 1, если len>=a[9], 0 если lenk) --- количество способов выбрать k элементов Read more » • +40 102. By Dambola, history, 3 years ago, SESCOMP Marathon 2018 — Federal University of Ceará — TUTORIAL Problem A – Academia ------------------ #### ENGLISH This is a Dynamic programming (and/or simulation) question. It's a derivative from the classic Knapsack Problem. First we do vector, with size from 0 to T_{max} (T_{max}+1), where we can simulate "how heavy is our bag", that is, how much time we spend. Initially the vector is filled with zeros, because we have no Power of Muscle. For every exercise we will do the following: 1) We are going to see the vector between [0, T_{max} - T_{exercise}], this is our storage vector for every exercise. 2) For t_i in [0,T_{max} - T_{exercise}] we will propagate the sum of Power of Muscle from vector[t_i] and P_{exercise} to the next time. 3) Doing: vector[t_{i} + T_{exercise}] = max(vector[t_i] + P_{exercise}, vector[t_{i} + T_{exercise}]) OBS: Do ti in [0,T_{max} - T_{exercise}] goes from right to left to not have a overlapping of Power of Muscle. At the end, search for the higher value of ... . The binary number formed by 1's is a decimal number in the form 2^k - 1. For that we need Read more » • 0 103. By gridnevvvit, 8 years ago, translation, Editorial Codeforces Round #209 (Div. 2) **I'm not good in English. So, if you find an mistake in editorial, please, send me a private message.** ##[problem:359A] If there are some good cell, which is located in the first row or in the first column, the answer is two. Similarly, if If there are some good cell, which is located in the last row or in the last column, the answer is two. Otherwise, the answer is four. Авторское решение: [submission:4968279] ##[problem:359B] The answer is a slightly modified permutation 1, 2, \ldots, 2n. Let's reverse numbers 2i - 1 and 2i for each 1 \le i \le k. It's not hard to understand, that this permutation is good. Авторское решение: [submission:4968385] ##[problem:359C] Obviously, the answer is x^v. Let sum = a_1 + a_2 + \ldots + a_n. Also let s_i = sum - a_i (the array of degrees). After that let's find value v by the following algorithm: Let's consider a sequence of degrees as decreasing sequence. Now we will perform the following operation until ... , 2, \ldots, 2n. Let's reverse numbers 2i - 1 and 2i for each 1 \le i \le k. It's not hard Read more » • +25 104. By Corvus, history, 3 years ago, [Training] [Arabic] ACM JCPC Summer Training 2018 Hello Codeforces, From 27/8/2018 to 6/9/2018 the JCPC Summer Training 2018 was held, two weeks covers varied topics consists of 4 different levels 1 &mdash; 4 and Level 1 and 2 consists of 5 lectures and Level 3 and 4 consists of 4 Lectures. The training is recorded and published on youtube on [user:SolverToBe,2018-09-02] channel *note: language of training is Arabic. **Level 1** ----------- **Lecture 1** &mdash; Presented By Mohammad Zuhair [user:Zuhair,2018-09-02] <spoiler summary="STL Data Structures"> Part 1 | [Vector](https://www.youtube.com/watch?v=svZA0aRRYvg) Part 2 | [Pair](https://www.youtube.com/watch?v=8W_lryPTj-s) Part 3 | [Complexity](https://www.youtube.com/watch?v=ZBrzms-78iQ) Part 4 | [Queue](https://www.youtube.com/watch?v=dcr8SzMAdT4) Part 5 | [Stack](https://www.youtube.com/watch?v=ZTQiPSCDIqo) Part 6 | [Priority Queue](https://www.youtube.com/watch?v=ZDR4STKNkxQ) </spoiler> **Lecture 2** &mdash; Presented By Nada Al-Shamayleh [us... covers varied topics consists of 4 different levels 1 — 4 and Level 1 and 2 consists of 5 Read more » • +135 105. By Xellos, 8 years ago, Codeforces Trainings Season 1 Episode 10: Editorial #### **Welcome to The Editorial!** <img src="http://th04.deviantart.net/fs70/PRE/f/2013/078/b/f/mi_super_saiyan_god_remasterizado_by_salvamakoto-d5ymxyi.png" height="50%" width="50%" /> **Keep the upvotes piling up! muhehe** IZ.COMPLETE. ### A. Rasheda And The Zeriba [cut] \ (difficulty: medium) The first question is: When is it possible to construct a (convex) polygon from sticks of given lengths L_i? This question is answered by what's sometimes known as Polygon inequality theorem, which states that the sufficient and necessary condition is for every L_i to be strictly less than the sum of all other L_i. You can imagine that it works because for the endpoints of every side, the shortest path between them (equal to the length of that side) must be smaller than any other path, including the other one along the perimeter of the polygon; constructing such a polygon, even a convex one, is pretty easy, just imagine it as having sticks linked to each other that... Codeforces Trainings Season 1 Episode 10: Editorial, the topmost full floor with exactly 1 side block removed, and k blocks on the topmost incomplete floor Read more » • +108 106. By codeonwort, 5 years ago, Haskell Implementations for Round 379 (Div. 2) This post doesn't include a special or creative solution. It's about how to implement the solutions in the [editorial](http://codeforces.com/blog/entry/48397). This kind of post is unnecessary for C++ or Java, but it's Haskell and there's no one who completed the round with Haskell ;) I can't assure if my codes are in pure functional way or very efficient, but at least they were accepted. I hope it will be helpful. #### [problem:734A] Take the outcome as a String and count the number of 'A' and 'D' in it. It's very simple problem so I just traversed the string twice (two calls of length . filter.) If you want to do it 2x faster, you can use partition in Data.List. code: [submission:22282938] #### [problem:734B] Another simple problem. Here is the line that reads the input: ~~~~~ [k2, k3, k5, k6] <- (map read . words) fmap getLine :: IO [Integer] ~~~~~ If input is small like this, it has no problem. When you have to read a large number of integers, there... = upperBound ds k s let freePotion = cs ! (ub - 1) let noFirst = if ub > 0 then (max (n Read more » • +85 107. By Nickolas, 10 years ago, translation, Codeforces Beta Round #96: editorial <h3><a href="http://codeforces.ru/contest/133/problem/A">A. HQ9+</a></h3> <p>The problem described <a href="http://progopedia.com/language/hq9-plus/">HQ9+</a> programming language and asked whether the given program will print anything. Given the extraordinary simplicity of the language, it was enough to check whether the program contains at least one of the characters H, Q and 9.</p> [cut] <h3><a href="http://codeforces.ru/contest/133/problem/B">B. Unary</a></h3> <p>A lovely language <a href="http://progopedia.com/language/brainfuck/">Brainfuck</a> has dialects for literally every occasion; I guess one could write a whole round about it (not Unknown Language Round, of course, it's too well-known for it), but this time I used it in one problem only.</p> <p>The solution is quite simple: all you have to do is to follow the described procedure of transforming code from Brainfuck to Unary. If your language has built-in long arithmetics, the solution is straightforward: replace characte... of the output can be calculated as (rev[i-1]-rev[i]+256)%256 (for i=0 rev[i-1]=0). Read more » • +58 108. By map, 10 years ago, translation, Analysis Codeforces Beta Round #63 (Div. 2) <div><div><div><p class="MsoNormal"></p><p class="MsoNormal"></p><p class="MsoNormal"><span lang="EN-US" style="mso-ansi-language:EN-US">Problem A.<o:p></o:p></span></p> <p class="MsoNormal"><span lang="EN-US" style="mso-ansi-language:EN-US">In this task all you had to do was to make sure that the sum of all </span>Σ<span lang="EN-US" style="mso-ansi-language:EN-US">x<sub>i</sub> is 0, the sum of all </span>Σ<span lang="EN-US" style="mso-ansi-language:EN-US">y<span class="Apple-style-span" style="font-size: 13px; "><sub>i</sub></span>&nbsp;is 0 and that the sum of all </span>Σ<span lang="EN-US" style="mso-ansi-language:EN-US">z<sub>i</sub> - 0 . </span><br> <span lang="X-NONE" style="mso-ansi-language:X-NONE">We have not written that condition evidently in order that participants will have a chance to break a solution.</span><span lang="EN-US" style="mso-ansi-language:EN-US"><o:p></o:p></span></p><p></p> <p class="MsoNormal"><span lang="EN-US" style="mso-ansi-language:EN-US">... a segment from (a[i] .. a[i + k - 1]) for 1 item left (a[I + 1] .. a[I + k]) you have to: Read more » • +31 109. By Hasan0540, 3 years ago, [Tutorial] 2018 PSUT Coding Marathon [**A. Two Fashillows**](http://codeforces.com/gym/101798/problem/A) If w+m \leq d or w>d, we print "good luck". Otherwise, we print "see you next semester". Complexity: O(1). <spoiler summary="Solution"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { int d, w, m; cin >> d >> w >> m; if (w + m <= d || w > d) printf("good luck\n"); else printf("see you next semester\n"); return 0; } ~~~~~ </spoiler> [**B. Two Palindromes**](http://codeforces.com/gym/101798/problem/B) We can always build a palindrome if we have at most one letter with odd frequency. Since both strings are palindromes, all letters have even frequencies, except he middle letter when the length of the string is odd. So the answer is NO only when both strings are of odd length and the middle letters are different. Complexity: O(|s_1|+|s_2|) for reading, and O(1) to check. <spoiler summary="Solution"> ~~~~~ #include <bits/stdc++.h> using namespace std... will also face k teams, winning k-1 times and losing the last one. This will contribute Read more » • +45 110. By skavurskaa, history, 5 years ago, Need help with string matching problem Short problem statement: Given T<200 binary strings S (|S| \leq 10^5), find the size of the shortest pattern that doesn't match S for all input strings. Examples : S = 011101001, answer = 3 (doesnt match '000') S = 11111, answer = 1 (doesnt match '0') My current solution is building a suffix automaton for S and searching all patterns of size i (i=1, i=2, ...) while the number of matches of this size equals 2^i. When i find some k such that matches(k) < 2^k, this is the answer. This is O(|S|) for building suffix automata plus O(\sum_{i=1}^k 2^{i}) == O(2^{k+1}) for matchings, which i think is always small but still relevant. This solution gets TLE. Can anyone help me with a faster solution for this problem? Thanks in advance. EDIT 2: Solved the problem using the strategy below. I will leave the blog here any way because this problem looks interesting so i want to share the solution in case any one is interested :) Run BFS in suffix automata startin... , this is the answer. This is O(|S|) for building suffix automata plus O(\sum_{i=1}^k 2^{i}) == O(2^{k+1 Read more » • -1 111. By gen, 8 years ago, translation, Codeforces Round #165 Tutorial ### [problem:270A,Div II A — Fancy Fence] #### Problem The problem is to tell whether there exists a regular polygon with angle equal to a. #### Solution Consider all supplementary angles of the regular n-polygon with angle a, which are equal to 180^\circ-a. Their sum is equal to 360^\circ, because the polygon is convex. Then the following equality holds: n\cdot(180-a) = 360, which means that there is an answer if and only if 360\mod(180-a) \equiv 0. ![ ](http://oi47.tinypic.com/qx1538.jpg) Time: O(t). Memory: O(1). Implementation: [C++](http://ideone.com/xnq9Iu), [Java](http://ideone.com/D2hHEL) #### Comments The problem can be also solved by rotating vector (1,0) by angle 180^\circ-a until it returns in this position (but at most 360 times), and checking that only one full turn has been made (implementation example: C++). It is also a rare problem on Codeforces that contains just 1 sample test, 1 pretest and 1 full test. ### [proble... the last such element be a_k. Then all of the elements a_{k+1}, a_{k+2}, \ldots, a_n can Read more » • +88 112. By Corvus, history, 3 years ago, [Training] [Arabic] ACM JCPC Summer Training 2017 Hello Codeforces, On Septemper 2017 the JCPC Summer Training 2017 was held in the University of Jordan, covers varied topics consists of 2 main levels 1 & 2 each consists of 8 Lectures and one additional lecture in level 3. The training is recorded and published on youtube on [user:SolverToBe,2018-09-14] channel *note: language of training is Arabic. **Level 1** ----------- **Lecture 1** &mdash; Presented By Ibraheem Tuffaha [user:Vendetta.,2017-09-02] <spoiler summary="ACM and Problem Solving"> Part 1 | [ACM and Problem Solving](https://www.youtube.com/watch?v=7pdNV-8BwIk) Part 2 | [Complexity](https://www.youtube.com/watch?v=adTPPwU0w-w) Part 3 | [Implementation 1](https://www.youtube.com/watch?v=ftZGTQxaNzQ) Part 4 | [Implementation 2](https://www.youtube.com/watch?v=e4-m2uHOsds) </spoiler> **Lecture 2** &mdash; Presented By Mohammad Zuhair [user:zuhair,2018-09-14] <spoiler summary="STL"> Part 1 | [STL Pair](https://www.youtube.com/watch?v=fR7GcvxCA... ,2018-09-14] Part 1 | [K-th Ancesstor](https://www.youtube.com Read more » • +6 113. By KADR, 9 years ago, translation, Editorial of Codeforces Round #153 This is a complete English version of the editorial of Codeforces Round #153. If you have any questions or suggestions, feel free to post them in the comments. ### [problem:252A] (A div 2) Let's iterate over all segments in our array. For each of them we'll find the xor of all its elements. Then we need to output the maximal xor we've seen. ### [problem:252B] (B div 2) If all elements in the array are equal then there's no pair of numbers we are looking for. Now we can assume that there exist at least 2 different numbers in the array. Let's iterate over all pairs of different numbers in the array and for each such pair we'll check if it can be the answer. If some pair indeed can be the answer, we'll output it and terminate the program. Otherwise, there is no pair of numbers we are looking for, so we need to output -1. It may seem that the complexity of described algorithm is O(N^3). Actually it's not true and the real complexity is O(N). One may notice that in ... k * (k - 1) / 2 triplets of points with the fixed rightmost point. The only thing left is to sum Read more » • +34 114. By darkshadows, 7 years ago, CodeCraft'15 IIIT Hyderabad Editorial [problem:100589A] ------------------ Given a rooted tree(at node 1) of **N** nodes,you have to handle a total of **Q** operations of type: **1 U L X**: Increase coins by **X** of all nodes at a distance of **L** from root. **2 X**: Report sum of all coins in subtree rooted at **X**. **N** <= 10<sup>5</sup> **Q** <= 10<sup>4</sup> #### Difficulty: Medium-Hard ####Explanation: This approach uses a very specific technique of maintaining a buffer of update queries and updating the whole tree once buffer size exceeds a constant limit(we maintain this limit as sqrt(M)). ~~~~~ buffer=[] q=input while q--: query = input() if query==update: buffer.add(query) else: //say query is “2 X” //the answer that has been already calculated for node X prevans= ans(X) for i=0 to buffer.size(): //add to prevans the effect of buffer[i] //let’s say buffer[i]=”1 U L... nodes in cycle. First let’s say we map all cycle nodes(say total of **K**) values1 to **K**. Now we pre Read more » • +81 115. By flamestorm, 6 weeks ago, EZ Programming Contest #1 Editorial Thank you for competing! I hope you had fun in the contest. **UPD:** Implementations have been added. [problem:103150A] <spoiler summary="Short Solution"> The value of k is irrelevant, just output the answer when zero operations are performed. </spoiler> <spoiler summary="Editorial"> If we perform 0 operations on the array, then the answer is just \max{(a_i)} - \min{(a_i)} (maximum element of a minus minimum element of a). Call this value r. Now we claim that, no matter how many operations are performed on the array, the answer will always be r. Let's prove it. Let s be the sum of the elements of the array. Then the operation is equivalent to turning a_i into s - a_i for all i. In particular, let a_p be the maximum element and a_q be the minimum element of a. Then after the operation, a_p becomes s - a_p and a_q becomes s - a_q. It's easy to see that s - a_p will be the smallest number of the resulting array, and s - a_q will be... EZ Programming Contest #1 Editorial, ; cin >> n >> k; int a[n + 7], mn = MOD, mx = -1; for (int i = 0; i < n; i Read more » • +100 116. By Nerevar, 8 years ago, translation, Codeforces Round #217 (Div. 2): tutorial ### [problem:370A] There are two approaches to this task. The first is use BFS to find the shortest path three times. The second is to notice that: * A rook can reach the destination in one or two moves. If the starting and the destination fields are in the same row or column, one move is enough. * A bishop can reach only fields that are colored the same as the starting cell, and can do this in at most two moves: if the starting and the destination fields are on the same diagonal, one move is enough. To find this out, check that r_1-c_1=r_2-c_2 OR r_1+c_1=r_2+c_2. * A king should make max(|r_1-r_2|, |c_1-c_2|) moves. ~~~ int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2; if (r1 == r2 || c1 == c2) cout << 1; else cout << 2; cout << " "; if ((r1 + c1) % 2 != (r2 + c2) % 2) cout << 0; else { if (r1 + c1 == r2 + c2 || r1 - c1 == r2 - c2) cout << 1; else cout << 2; } cout << " "; cout << max(abs(r1 - r2), abs(c1 - c2)) << endl; ... the i-th block). Then, try to fix where the previous block can actually end (fix the state D(i-1,k Read more » • +20 117. By Zlobober, 6 years ago, An editorial of Topcoder SRM 672 Hi everybody! It was my first experience of writing problems for TopCoder SRM, hope you liked it. I was a writer of Easy and Medium task in both divisions, [user:subscriber,2015-10-21] was an author of both Hard tasks. In div1 they were harder than usual, but I hope you still liked them. #### Div2 easy This task was just about implementing exactly what is described in the statement. Looks like Python has a built-in support of set comparison. Usually coders using Python have a disadvantage, but in this task it looks more like an advantage :) There are built-in functions for sets in C++ and Java too, I recommend to learn about them even if you successfully submitted this problem. #### Div2 medium Knowing strings a and b, we can build a reverse mapping q[d] = c, that maps the encoded letter d to it's original corresponding letter c. For letters that do not appear in b, we remember that we don't know their pre-image. After that, we just apply our mapping q to a string... that the connected component that contains vertex number 1 consists of k vertices (obviously, 1 \leq k Read more » • +103 118. By Konjac, 7 years ago, [Spoiler Alert!!!] Hints for Crypto Cup 1.0 Really a funny contest. Hope for more. Here are some hints. #### Problem A RSA #### Problem B Case #1 ~~~~~ c..r..h .h..z.. ..a..e. ~~~~~ #### Problem C msg[i] = (26 + cipher[i]-cipher[i-1] ) mod 26 + 'a' #### Problem D The first character is Z/O we guess it means zero or one. Z,1,2,3,2,1,2,1,1,4,2,4,1,1,3,2,1,2,4,1,1,2,2,2,1,1,1,1,2,1,1,3 Means start with zero, we have 1 zero then 2 ones, 3 zeros, 2 ones, 1 zero … The last step is the same to Problem I. #### Problem E Morse code. #### Problem F 2715 seems like base 27 and base 15. 26 letters in base 27 and 15 letters in base 15. Maybe the 26 letters are 1-26 instead of 0-25. #### Problem G brute force + search + good luck. Some online anagram websites will be helpful. ps: The answer may not be unique? For example, "yvuoedloreoic" could both be "I love your code" or "I love you coder". But the system test only accept "I love you coder". #### Problem H 26 integers in first line... to build a map. #### Problem K For most samples, cipher[i] ≈ cipher[i-1]*31. After checking Read more » • +29 119. By Xellos, 7 years ago, Codeforces Trainings Season 2 Episode 8: Editorial [Complete problemset + tests + original presentation of solutions.](http://www.bapc.eu/problemset.zip) [Official scoreboard](http://bapc.eu/scoreboards/bapc/), [public contest scoreboard](http://www.bapc.eu/scoreboards/public/), [used for training elsewhere](http://www.cs.ubc.ca/~acm-web/practice/2014-10-25/scores.php). Short hints first, more detailed solutions afterwards. ### A. Avoiding the Apocalypse (difficulty: medium-hard, [code](http://ideone.com/JQOMyq)) Maxflow in a suitably selected graph. Ford-Fulkerson is sufficient. <hr> The vertices of our graph need to correspond to states that one person can be in when traversing the original road network; the number of people moving in a group is then represented by flow along edges. Therefore, the most natural choice is to use vertices corresponding to states (location, time). The rules from the problem statement say that at most c people can move along an edge e=(u->v) in the original at any time. That me... coprime (easy proof by induction), so F_{n-2} has a modular inverse and$$a=k F_{n-1}+NF_{n-2 Read more » • +116 120. By Tampere, 4 years ago, Notes on Codeforces Beta Round #72, A, B, C, D, E [problem:84A] The strict proof seems to be a little complicated as far as I consider, however an intuitive understanding suggests that the answer is$n+n/2$, and it is accpeted... [problem:84B] We must find out all the intervals that consist of the same integers. For an interval with$P$integers, the number of reasonable subsequences is$\frac{P(P+1)}{2}$. Thus, we can adopt two pointers to find out all the target intervals, and calculate the answer. [problem:84C] As it has been guaranteed that no two circles intersect with each other, the given point can only fall into at most one particular circle (one special case is that two circles touch each other at the given point). Thus, we first sort the circles in an increasing order of their X-coordinates, and find out two circles between which the give point falls (check the X-coordinate of the given point as well, and a special case is that the given point falls at one of two ends of all the circles), which can be achieved... }^{n-1}min(a[i], T)\le K$. Moreover, we compute $K-S$ as the remainder. Then, any $a[i Read more » • +2 121. By kpw29, 4 years ago, Solutions for MeetIT training contest **Disclaimer** The post will be mostly in Polish, as it will just contain solutions for training contests. I found Codeforces the most convenient place for writing them and allowing the participants comment. **Pierwszy krok (23 grudnia)** Obydwa zadania pochodzą z 11 oia. Szczegółowe rozwiązania można przeczytać w niebieskiej książeczce olimpiady. <spoiler summary="Most"> To było dzisiaj łatwiejsze zadanie. Wiele osób skończyło z 10 punktami, nieuważnie testując swoje rozwiązanie. Zadanie wydaje się proste, chociaż ma pewien haczyk. Rozwiązanie zachłanne niestety nie do końca działa. <spoiler summary="Hint 1"> Posortujmy elementy tablicy. Spróbujmy policzyć wynik programowaniem dynamicznym. Często opłaca nam się przeprawiać osobę najszybszą z ostatnią osobą. To jednak nie zawsze jest optymalne. </spoiler> <spoiler summary="Hint 2"> Jest jeszcze drugi rodzaj ruchu -- możemy wziąć dwie najwolniejsze osoby, a latarkę wrócą wcześniej przewiezieni najszybsi. Z tego ... przedziale jest >= k, czyli suma większa niż (b-a+1)*k. Łatwo wykazać, że to warunek konieczny i pokazać Read more » • +14 122. By coderbond007, 4 years ago, Number of path pairs from node u to any vertex having distance <= K How can we calculate number of node &mdash; disjoint paths pair between _u_ and other vertex say _v_ (such that distance of _v_ from source vertex is _K_).Vertex v is not known to us. I thought of implementing BFS for every node until maximum distance from source node is <= **K**. But I am not getting idea for implementation. Anybody please help me? Given the number of vertices in graph can be up to than **10^5** and edges can be **6 * 10^5**. In every test case, value of K will be at max 10 % of number of edges. ~~~~~ A path is sequence of vertices: s, v_1, .., v_m, t. Two paths s, v_1, .., v_m, t and s, u_1, ..., u_k, t are called node-disjoint if v_i != u_j for any valid i and j. ~~~~~ We are given a example graph shown as following. Adjacency List representation of given **Directed Graph** ~~~~~ 1 - 2, 5 2 - 3, 4, 6 3 - 4 4 - 8 5 - 7 6 - 11 7 - 11 8 - 9, 10 9 - 10 10 - 11 ~~~~~ Value of **K** is 6(including source node and end node). ![Graph](/predown... Number of path pairs from node u to any vertex having distance <= K, of implementing BFS for every node until maximum distance from source node is <= **K**. But I am Read more » • +4 123. By Geothermal, history, 19 months ago, AtCoder Beginner Contest 151 English Solutions #A &mdash; Next Alphabet The easiest way to deal with this problem is probably to convert the given character to an integer, add one, and convert it back. If you absolutely can't do that, a somewhat more annoying implementation would involve iterating through the alphabet, waiting until you find the given letter, using a boolean variable to store that the letter has been found, and printing the letter on the next iteration of the loop. (However, iterating over the alphabet is itself nasty unless you have conversion from letters to integers, so this approach is rather pointless unless your language just doesn't support the first method, though in that case you should probably switch languages anyway.) Runtime:$O(1)$. [Click here for my submission.](https://atcoder.jp/contests/abc151/submissions/9440245) --- #B &mdash; Achieve the Goal In total, we need to earn$NM$points. We subtract the points earned so far and determine whether this is a valid score for the final ... of sets in which$A_i$is the largest value is the number of ways to choose$K- 1$smaller integers Read more » • +40 124. By Aksenov239, 10 years ago, translation, Solutions for Codeforces Beta Round #56 <div><div><div><b>Problem A.</b> Solution -$O(n^2)$.&nbsp;</div><div>We take phrase and parse it. Mark all cells, that obviously didn't match -$O(n)$. In the end we go through the array and count all unmarked cells.</div><div>If 0 - we print "-1", else - amount of unmarked cells.</div><div><br></div><div><b>Problem B.</b> Solution -$O(k \times n \times m)$.&nbsp;</div><div>We start BFS from given point. Go from cell to all 6 directions. The answer - number of visited cells.</div><div><br></div><div><b>Problem C</b>. Solution -$O(2^7 \times n^2)$.&nbsp;</div><div>We can see, that in connected component - if we know 1 number - then we know all others in component, because in each pare we know minimal and maximal</div><div>power of each primes. Because number of different primes in one number "$&lt;= 1000000$" is less, than 7, we can look over all possibilities of 1 number in connected compoment - and for each number, that we get, we check, that it suits.</div><div><br></div><div>How ... all unmarked cells.If 0 - we print "-1", else - amount of unmarked cells. Read more » • +66 125. By karamkontar, 3 years ago, ACPC Arab Collegiate Programming Contest 2018 Editorial Hello, Since the editorial posted for the ACPC 2018 is rather complicated (no offense), I decided to write my own tutorial with much simpler solutions. There are two problems missing, and, hopefully, they will be available soon. Hope you like it! [problem:101991A] <spoiler summary="Hint"> A tree has all its edges as bridges (initially$ \relax N-1 $bridges). </spoiler> <spoiler summary="Hint"> Joining the end-points of a simple path with length$ \relax P $edges, removes$ \relax P $bridges from the tree (resulting in$ \relax N-1-P $bridges). </spoiler> <spoiler summary="Tutorial"> Initially, all edges of the given tree are bridges since removing any of them disconnects the graph. So, we start with$ \relax N-1 $bridges. Joining the end-points of a simple path with length$ \relax P $edges, removes$ \relax P $bridges from the tree (resulting in$ \relax N-1-P $bridges). Since we want the resulting graph to have the number of bridges in$ \relax [L, R] $,... starting at$ \relax (1, 1) $. Complexity$ \relax O (K^2 \; log \; K) $[problem Read more » • +11 126. By burunduk3, history, 4 years ago, Алгоритм Монтгомери: (A × B) % N Вступление ================== Недавно мне рассказали про некое «преобразование Монтгомери», которое якобы сводит вычисления по произвольному модулю к вычислениям по модулю$2^k$. Звучит интересно: во всяких вычислениях по простому модулю самое долгое место — как раз взятие по модулю после каждой операции. Но как именно преобразование работает, не рассказали. Повезло, что я живу в эпоху интернета и любую интересующую меня тему могу с тем или иным успехом загуглить.[cut] Гугл рассказал, что штука называется «алгоритм Монтгомери», описана на [википедии](https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9C%D0%BE%D0%BD%D1%82%D0%B3%D0%BE%D0%BC%D0%B5%D1%80%D0%B8) и итмошных [вики-конспектах](https://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BE_%D0%9C%D0%BE%D0%BD%D1%82%D0%B3%D0%BE%D0%BC%D0%B5%D1%80%D0%B8). Оба описания мне не очень понравились, потому что (хоть и объясняют, что делать) пок...$2^k > N$) мы научились без деления вычислять$(A \times B \times R^{-1 })~\%~N$. Для этого нам надо Read more » • +145 127. By Kostroma, history, 6 years ago, Codeforces Round #317 [AimFund Thanks-Round] Editorial [problem:572A] In this problem one need to check whether it's possible to choose$k$elements from array$A$and$m$elements from array$B$so that each of chosen element in$A$is less than each of chosen elements in$B$. If it's possible then it's possible to choose$k$smallest elements in$A$and$m$largest elements in$B$. That means that in particular,$k$-th smallest element of$A$is less than$m$-th largest element in$B$. So, if$A[k] < B[n - m + 1]$then the answer is "YES" and if not, then the answer is "NO". Problem author: [user:zeliboba,2015-08-22]. Problem developers: [user:AlexDmitriev,2015-08-22], [user:Kostroma,2015-08-22]. Solution code: [submission:12873382]. [problem:572B] First of all the problem may be solved for buy orders and sell orders separately. The easiest soultion is to use structure like std::map or java.lang.TreeMap. To aggregate orders we just add volume to the corresponding map element: aggregated[price] += volume`. After ... of$A$is less than$m$-th largest element in$B$. So, if$A[k] < B[n - m + 1 ]$then the answer is "YES Read more » • +70 128. By Betlista, 7 years ago, Betlista's TopCoder SRM 646 editorial In SRM there were 849 registered participants [cut] - DIV1 383, DIV2 410 + 56 newcomers ### DIV2 — easy (250) [(link)](http://community.topcoder.com/stat?c=problem_statement&pm=13626&rd=16278) if k == 1, the answer is 0 (we have consecutive sequence of length 1 already) For k == 2, one can use sort, find the smallest difference d and return d-1. Unfortunately elements in input were distinct, so one corner case less :-( ### DIV2 — medium (500) [(link)](http://community.topcoder.com/stat?c=problem_statement&pm=13628&rd=16278) It's a graph problem, one have to find how far we can move in 1000 steps. On empty board our max coordinates are like -1000..1000, so I modified those to be in 0..2000 and used 2D array to prevent visiting (processing) same point twice during BFS from (0, 0) coordinate... To prevent moving on invalid coordinate I simple marked those as visited before queue processing. So I used queue, added (0, 0) to it with 0 as number of steps. Th... =16278) if k == 1, the answer is 0 (we have consecutive sequence of length 1 already) Fork Read more » • +15 129. By Tampere, 4 years ago, Solutions to Codeforces Beta Round #29, A, B, C, D A. Spit Problem For a camel with given parameters x[i] and d[i], he (or it) can hit at position x[i]+d[i] according to the problem. As the number of camels is at most up to 100, it is feasible to check for any two camels whether they can hit each other or not. B. Traffic Lights When the car arrives at the traffic light, if it is green, then the car can move on as if there were no traffic lights; while if it is red, the car has to wait until the light turns to be green, and then it can reach the destination. Therefore, the key point is in fact to determine whether the car has to wait or not, and if yes, how much time should it wait for. We can take the total time that green light and red light lasts as an entirety (or a cycle), i.e., t=g+r, and then we should find out at which cycle does the car reach the traffic light. At first, we compute k=d/((g+r)*v), where "integer division" is adopted. The value of k means that when the car reaches the traffic light, it takes at least... at least k cycles. Then, the problem can be solved based on the following two cases:1) (g+r)*v*k<=d Read more » • -9 130. By BYN, 7 years ago, Elimination Round Editorial — Bayan programming Contest 2014-2015 ### A. New Rock Paper Scissors The$O(n^2)$solution is straight forward, although it can be solved in$O(n)$but it was not required. Even the$O(n)$seems easier to implement, but some cases might be missed. That's why the easiest problem of the contest turned out to be a little tricky. You see both kind of solutions in the scoreboard. ### B. Bayan Health Bracelet In this problems you had to find the first condition that is met. If carefully implemented one can get accepted with no hassle. ### C. Grid History The following two statements should hold for a valid grid: + If the board is checkered, two cells have the same parity, if and only if they are colored the same. + Let$x$be the value of a cell, and$y$be the value of the first cell with greater value than$x$. The length of the shortest path from$x$to$y$among the cells with value greater than or equal to$x$, is not greater than$y - x$. + two greatest values of the board must differ by one. Checkin... that water reaches$k+1$-th barrel. The whole algorithm runs in$O(n^2+m)$. + As a exercise, try Read more » • +78 131. By Nerevar, 8 years ago, translation, Codeforces Round #207: tutorial #### [problem:357A] In this problem you need to iterate over all possible values of passing rate from 1 to 100 and for each value calculate the sizes of two groups. #### [problem:357B] Let's process the dances in the given order and determine the colors of dancers' clothes. If there are no dancer from some previous dance, we can give the dances different colors arbitrarily. And if there is such dancer, we already know the color of his clothes. So, we arbitrarily distribute the other two colors between the remaning two dancers. #### [problem:356A] Let's the current fight$(l, r, x)$consists of$K$knights fighting. Then all we have to do is to find all these knights in time$O(K)$or$O(KlogN)$. There are several ways to do that, let's consider some of them. The first way is to store the numbers of all alive knights in std::set (C++) or TreeSet (Java). Then in C++ we can use lower_bound method to find the first knight in the fight that is alive, and to iterate over ... from 1 to 100 and for each value calculate the sizes of two groups. #### [problem:357B Read more » • +60 132. By loser21, history, 5 years ago, Google APAC 2017 Round A Editorial Since Google APAC is one of the few contests where there is no official editorial/analysis available, I decided to write a short editorial for Round A of Google APAC 2017. You can read the problem statements from this [link](https://code.google.com/codejam/contest/11274486/dashboard). #### **Problem A** You need to find the number of distinct uppercase English alphabets in each of the given strings. Out of all those strings who have the maximum number of distinct alphabets, simply output the smallest one in the lexicographic order. Be careful while taking input for the large test data as the strings might contain spaces too. [Code](http://pastebin.com/7iV1uEEg) #### **Problem B** To solve this problem, iterate from the smallest height to the largest height. For a given height h, find all connected component of cells where all cells have height h using BFS/DFS. Now for a particular connected component of height h, look at all neighbours of cell in this connected component (not... ://pastebin.com/ARsdy14Y) #### **Problem C** Divide the entire expression by$(1 +r)^M$. The expression Read more » • +30 133. By Tampere, 4 years ago, Notes on Codeforces Beta Round #94 Div-2, A, B, C, E (Pascal Triangle) [problem:129A] We can compute the sum of all the integers. Then, we enumerate each element and test whether their difference is even or not. [problem:129B] A straightforward implementation problem. We can use BFS to find out all the nodes whose degree is exactly one. The answer is just the total number of BFS. [problem:129C] Note that at the eighth second, all the positions are definitely safe. Therefore, it is sufficient to check whether we can survive within the first eight seconds. One feasible solution is to record and update all the safe positions at each second. If we can survive after eight seconds, it means that we can always reach the right upper corner; otherwise not. [problem:129E] In fact we might obtain some more clear observation if we consider the length and width of each rectangular in an independent perspective. For instance, for the length, the rectangulars can only have positions at (1, 2, 3,... n-1). As there are exactly$k$rectangulars, we ... , the rectangulars can only have positions at (1, 2, 3,... n-1). As there are exactly$k$rectangulars, we Read more » • -3 134. By Tampere, 4 years ago, Solutions to Codeforces Beta Round #27, A, B, C, D, E A. Next Test As the range of input size is only up to 3000, we can maintain an array to indicate which number has appeared in the given test. Then, we enumerate this array from index 1 to n, and the first number that cannot be found is the answer. B. Tournament It seems that there exist some other simpler methods than mine... The key idea of my solution is to build a directed graph. The players can be viewed as nodes in a directed graph, and node A has en edge directed to node B if we can find a match in which A wins against B. Then, we can maintain an array to count the number of matches that a player has participated in. It is straightforward that we will find out two players who have only participated in n-2 matches while the other ones all have participated in n-1 matches. After finding out the two players, without of loss generality, we denote them as A and B, and then we implement "graph traversal" for two times witht the starting point as A and B, respectively. If we ca... which number has appeared in the given test. Then, we enumerate this array from index1 to n Read more » • +9 135. By Rifat_Hasan, history, 15 months ago, My problem in Hackerrank Coding Fever #Round 01 I have recently set a problem for the contest named **"Coding Fever #Round 01"**. I am inviting you to take a look over the problem statement — [Armies are coming Home](https://www.hackerrank.com/contests/coding-fever/challenges/armies-are-coming-home). Here is the _**editorial**_ of my problem: It is a normal dfs/bfs problem to find the shortest path of the node which contains armies. For finding the cost for returning to home we should add all the sum of shortest path distance. The distance of each node from the root can be calculated as **dis[child] = dis[parent]+1**. Just one simple observation is here that when we pass a node which contains armies we do not add the distance for the next node so **dis[child]** will be same as **dis[parents]**, **dis[child] = dis[parent]**. Here **dis** is an array for storing the distance from root. My solution: ~~~~~ #include<bits/stdc++.h> #define ll long long #define MAXN 1000006 using namespace std; int dis[MAXN]; b... ); cin.tie(0), cout.tie(0); int n,k; cin>>n>>k; for(int i=1;i Read more » • +3 136. By Xellos, 8 years ago, Samara SAU ACM ICPC 2013-2014 Quarterfinal Qualification Contest: Editorial ### A. The Power of the Dark Side (difficulty: easy) Let's sort the parameters of every Jedi:$a \ge b \ge c$. The "coverted" Jedi obviously wants to use his strongest 2 parameters ($a_k,b_k$) against the opponent's weakest 2 ($b_i,c_i$) to get 2 victories as assuredly as possible; besides, the optimal order is$a_k$against$b_i$and$b_k$against$c_i$, because if he can win when using them in the opposite order, then he'll win after swapping them, too. So we want to find all Jedis that have$a_k > b_i$and$b_k > c_i$for all$i$. That's simple, because those are the same conditions as$a_k > B=\max(b_i)$and$b_k > C=\max(c_i)$. When processing the input, we can count$B$,$C$and then we just check for every Jedi if he satisfies these 2 conditions, in linear time. I decided during the contest to code a solution which is a bit slower, but more powerful &mdash; it allows us to answer stronger versions of this problem like "which Jedis can we choose, if we're satisfied with... that contains$k$such groups, it contains at least$k-1$groups of consecutive zeroes (between those Read more » • +37 137. By Ripatti, 9 years ago, translation, Croc Champ 2012 — Round 1 — Editorial **A.** Naive solution in$O(n)$(some simulation all of n rounds) gets TL. Let's speed up this solution. Let's consider rounds on segments [1..mk], [mk+1..2mk], [2mk+1..3mk] and so on. You can see that results of games on these segments will repeat. So you can simulate over exactly one segment and then take into consideration them [n/(mk)] times ([x] is rounding down). Remainder of n%(mk) last rounds you can simulate separately. So you have$O(mk)\$ solution that easily fits into time limits. Authors are ~Ripatti,2012-04-06 and ~Gerald,2012-04-06 [cut] . **B.** In this problem you should build bipartite graph with n+m vertices. All vertices of the firts part correspond to the rows of the table, vertices of the second part correspond to the columns of the one. Edge connects vertices iff some regular column is placed in the cross of corresponding row and column. Firstly death ray covers only last row of the table that corresponds to one of vertices of our graph. When you are ch...
Croc Champ 2012 — Round 1 — Editorial, this solution. Let's consider rounds on segments [1..mk], [mk+1..2mk], [2mk+1 ..3mk] and so on. You can see

• +103

138.
By RussianCodeCup, history, 4 years ago, translation,
Russian Code Cup Qual 2 — Editorial <h2>A. Very Important Persons</h2> <p>There are two main ways to solve the problem.</p><p>The first way is to assign guests to seats by diagonals, starting from the seat (1,&thinsp;1). You should be careful with considering cases <i>n</i>&thinsp;&lt;&thinsp;<i>m</i> and <i>m</i>&thinsp;&lt;&thinsp;<i>n</i> when implementing traversal. </p><p>The second way is a more common solution which however requires more advanced algorithm. Let us run BFS from (1,&thinsp;1) and assign seats to guests in order they are popped from the queue, starting from the most important one.<h2>B. Least Common Multiple</h2> <p>Let <i>p</i>&thinsp;/&thinsp;<i>q</i> be divisible by both <i>a</i>&thinsp;/&thinsp;<i>b</i> and <i>c</i>&thinsp;/&thinsp;<i>d</i>, all fractions are irreducible. So the numbers (<i>p</i>&thinsp;/&thinsp;<i>q</i>):&thinsp;(<i>a</i>&thinsp;/&thinsp;<i>b</i>)&thinsp;=&thinsp;(<i>p</i>&middot;<i>b</i>)&thinsp;/&thinsp;(<i>q</i>&middot;<i>a</i>) and (<i>p</i>&thinsp;/&thinsp;<i>q</i>):&thin...
;1)·K (here K is approximately sqrt(n)). In each group sort