Codeforces Round #283: editorial (with bonuses!) Each problem comes with a challenge — a bonus task somehow related to the problem; you may tackle at the challenges for fun and practice, also feel free to discuss them at the comments. =) [problem:496A] For every option of removing an element we run through the remaining elements and find the maximal difference between adjacent ones; print the smallest found answer. The solution has complexity $O(n^2)$. It can be noticed that after removing an element the difficulty either stays the same or becomes equal to the difference between the neighbours of the removed element (whatever is larger); thus, the difficulty for every option of removing an element can be found in $O(1)$, for the total complexity of $O(n)$. Any of these solutions (or even less efficient ones) could pass the tests. **Challenge**: suppose we now have to remove exactly $k$ arbitrary elements (but the first and the last elements have to stay in their places). How small the maximal difference between adjacen...

Full text and comments »

Codeforces Round 1048 (Div. 1, Div. 2) Editorial [2139A &mdash; Maple and Multiplication](https://codeforces.me/contest/2139/problem/A) Idea: [user:installb,2025-09-08] Preparation: [user:installb,2025-09-08],[user:2014CAIS01,2025-09-08] <spoiler summary="Solution"> If $a=b$ we need $0$ steps. If $a$ can be divided by $b$, we only need $1$ step, which is to multiply $b$ by $\frac{a}{b}$. Same for the case when $b$ can be divided by $a$. Otherwise, we need at most $2$ steps. As both $a$ and $b$ are positive integers, we can first multiply $a$ by $b$ and then multiply $b$ by the original value of $a$. Both number will be equal to $a\times b$. </spoiler> <spoiler summary="Code (C++)"> ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; int solve(){ int a,b; cin >> a >> b; if(a == b) return 0; if(a % b == 0 || b % a == 0) return 1; return 2; } int main(){ ios::sync_with_stdio(false); int TC; cin >> TC; while(TC --){ cout <<...

Full text and comments »

Educational Geometry Problems These problems are taken from CSES Problem set and Codeforces Problem set archives [Problem 1 &mdash; Point Location Test](https://cses.fi/problemset/task/2189/) <spoiler summary="Hint 1: "> Use the concept of slopes to determine the position of point p3 relative to the line formed by points P1 and P2. </spoiler> <spoiler summary="Hint 2: "> Calculate the slopes m1 and m2 for line segments P1P2 and P2P3 respectively. </spoiler> <spoiler summary="Hint 3: "> ~~~~~ cout << (m2 > m1 ? "LEFT" : (m2 < m1 ? "RIGHT" : "TOUCH")) << "\n"; ~~~~~ Try to interprete this geometrically </spoiler> <spoiler summary="Code"> ~~~~~ void solve() { ll x1,y1,x2,y2,x3,y3; cin>>x1>>y1>>x2>>y2>>x3>>y3; ll m1 = (y2-y1)*(x3-x2); //Slope for P1P2 ll m2 = (y3-y2)*(x2-x1); //Slope for P2P3 if (m2 > m1) //Slope of P2P3 is greater than P1P2 means P3 is lies on the left of the given line segment { cout<<"LEFT"<<"\n"; } else if (m2 < m1) /...

Full text and comments »

Codeforces Round #219 editorial Sorry for late. This is the editorial of Codeforces Round #219. Div2 A, Div2 B, Div1 C are made by [user:m.kagamiz,2013-12-15], and other problems are made by me. [problem:373A] /\\_/\ First, you need to count the occurence of each number (1 through 9). If none of them are greater than 2 * k, Cucumber boy is able to press the panels in perfect timing. Complexity is O(1). My solution : http://ideone.com/CwQtBv [problem:373B] /\\_/\ Naive simulation (subtracting S(i) * k from w while w >= 0) won't finish in 2 seconds. At first, these two facts will make it easier to solve the problem : 1. k doesn't matter for solving this problem, so you can simply divide w with k at the first point. 2. S(10^x) + S(10^x + 1) + ... + S(10^(x+1) &mdash; 1) = 9 * x * 10^x . There are many ways to solve this problem, and I'll show you 2 ways. 1. Binary Search Let's define f(n) as \sum_{k=1}^{n} S(n). This problem can be solved by finding largest x that satisfies f(x) &md...

Full text and comments »

Editorial of Educational Codeforces Round 11 ### [problem:660A] The problem was suggested by Ali Ibrahim [user:New_Horizons,2016-04-09]. Note that we should insert some number between any adjacent not co-prime elements. On other hand we always can insert the number $1$. <spoiler summary="С++ solution"> ~~~~~ const int N = 1010; int n, a[N]; bool read() { if (!(cin >> n)) return false; forn(i, n) assert(scanf("%d", &a[i]) == 1); return true; } void solve() { function<int(int, int)> gcd = [&](int a, int b) { return !a ? b : gcd(b % a, a); }; vector<int> ans; forn(i, n) { ans.pb(a[i]); if (i + 1 < n && gcd(a[i], a[i + 1]) > 1) ans.pb(1); } cout << sz(ans) - n << endl; forn(i, sz(ans)) { if (i) putchar(' '); printf("%d", ans[i]); } puts(""); } ~~~~~ </spoiler> Complexity: $O(nlogn)$. ### [problem:660B] The problem was suggested by Srikanth Bhat [user:srikkbhat,2016-04-09]. In this problem you should simply do what was written in the problem sta...

Full text and comments »

Geometry: 2D points and lines [Tutorial] I get an impression that a lot of coders struggle with geometric problems and prefer to avoid them. That's not much of a surprise, considering that I couldn't find a good writing explaining the basics and giving useful advice how to proceed. Moreover, some resources obfuscate this beautiful area to the point it's despised by the readers. I'll try to change that, but first I'll mention some of the better resources: [geomalgorithms.com](http://geomalgorithms.com/points_and_vectors.html) This is where you can start if you don't have a basic notion of a vector. Also there are more detailed explanations for some examples I'll list, but I dislike the implementations. [This post in Russian](http://codeforces.me/blog/entry/6642) has a link to the code that's most similar to mine, with some comments (unfortunately, also is Russian)[cut]. ### Point structure and operations Without further ado, I'll start with my code for the `Point` structure. Explanations are below, so don't rush t...

Full text and comments »

[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...

Full text and comments »

TeamsCode Spring 2025 Contest Editorial Sorry for the long wait. All problems were written, prepared, and editorialized by [user:Yam,2025-03-23], [user:hyforces,2025-04-14], [user:culver0412,2025-04-15], [user:HaccerKat,2025-03-23], [user:alexlikemath007,2025-03-23], [user:jay_jayjay,2025-03-23], [user:n685,2025-03-23], [user:Mustela_Erminea,2025-03-23], [user:Jasonwei08,2025-03-23], [user:eysbutno,2025-03-23], [user:training4usaco,2025-03-23], [user:Nyctivoe,2025-03-23], and [user:gggg0,2025-03-23]. The problems (with problem credits) can be found in the [Novice Gym](https://codeforces.me/gym/105819) and [Advanced Gym](https://codeforces.me/gym/105818). Also thanks to our testers for providing valuable feedback and to our logistics and web team for making TeamsCode possible! [Novice A/](https://codeforces.me/gym/105819/problem/A)[Advanced A: Lily Pads](https://codeforces.me/gym/105818/problem/A) ================================================================================================================= <spoi...

Full text and comments »

How to solve Light OJ 1058 — Parallelogram Counting ? I am new in geometry.I am trying to solve some basic problem about geometry.Hence i found a nice problem http://lightoj.com/volume_showproblem.php?problem=1058 . But I have no idea about this types of problem. If anyone can help with some idea by how i solve this problem, i will be so much benefited. Please help me. Thanks in advance. :)

Full text and comments »

List of Problems Having Short Statements (800 to 1500) ## List of Problems Having Short Statements (800 to 1500) Long, wordy statements can be exhausting, especially for beginners. So here is a list of problems with **short and easy-to-read statements** in the **800–1500** range, a companion to [Abdullah500's list for 1600–3000](https://codeforces.me/blog/entry/146051). **Notes:** - Every problem here has a statement of **under 1000 characters** (input/output and samples not counted). - Within each rating, problems are listed in order of problem ID, **not** sorted by statement length. - Ratings are as of April 2026 and may shift a little over time. - Short statement does not always mean an easy idea. Some of these are tricky! - The data comes from [alwa97/codeforces-1000](https://github.com/alwa97/codeforces-1000). Many thanks to the author. I picked about 50 problems per rating from there, so check that repo if you want even more. **800** 1. [41A &mdash; Translation](https://codeforces.me/problemset/problem/41/A) 2. [5...

Full text and comments »