[Tutorial] Knapsack, Subset Sum and the (max,+) Convolution, polygons, taking their Minkowski sum gets us the epigraph for $C$ and finding
Minkowski sum on convex, , taking their Minkowski sum gets us the epigraph for $C$ and finding Minkowski
sum on convex polygons is
→ Pay attention
Before contest
Codeforces Round 1097 (Div. 1, Based on Zhili Cup 2026)
3 days
Register now »
Codeforces Round 1097 (Div. 1, Based on Zhili Cup 2026)
3 days
Register now »
*has extra registration
Before contest
Codeforces Round 1097 (Div. 2, Based on Zhili Cup 2026)
3 days
Register now »
Codeforces Round 1097 (Div. 2, Based on Zhili Cup 2026)
3 days
Register now »
*has extra registration
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | adamant | 152 |
| 3 | Proof_by_QED | 146 |
| 3 | Um_nik | 146 |
| 5 | Dominater069 | 144 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
→ Find user
→ Recent actions
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 305andrew stankevich contests— search for words "andrew", "stankevich" and "contests" at the same timeuser:mikemirzayanov title:testlib— search containing "testlib" in title by MikeMirzayanov"vk cup"— use quotes to find phrase as istitle:educational— search in title
Results
1.
[Tutorial] Knapsack, Subset Sum and the (max,+) Convolution **Edit**: I have realized that this blog has been sent quite a lot on discord servers, so I am adding a content page at the start to help organize this blog better.
## Prerequisites
Let us first define the classical knapsack, unbounded knapsack and subset sum problems.
#### Subset Sum
There are $N$ items. The $i$-th item has weight $w_i$. Find a set $S$ such that $\sum\limits_{i \in S} w_i = C$.
#### Knapsack
There are $N$ items. The $i$-th item has weight $w_i$ and value $v_i$. Find a set $S$ such that $\sum\limits_{i \in S} w_i \leq C$ and $\sum\limits_{i \in S} v_i$ is maximized.
#### Unbounded Knapsack
There are $N$ items. The $i$-th item has weight $w_i$ and value $v_i$. Find a **multiset** $S$ such that $\sum\limits_{i \in S} w_i \leq C$ and $\sum\limits_{i \in S} v_i$ is maximized.
You should know how to do both versions of knapsack in $O(NC)$ and subset sum in $O(\frac{NC}{32})$ before reading this blog.
In this blog post, I will just show some res...
2.
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...
$; now observe that the set of all possible values of $z - x$ forms the
Minkowski sum of $A$ and, Minkowski sum of $A$ and reflection of $B$ (up to some shift), and the set of
all possible values of $y
Tutorial of Codeforces Round 283 (Div. 2)
Tutorial of Codeforces Round 283 (Div. 1)
3.
On linear recurrences and the math behind them Hi everyone!
There are already dozens of blogs on linear recurrences, why not make another one? In this article, my main goal is to highlight the possible approaches to solving linear recurrence relations, their applications and implications. I will try to derive the results with different approaches independently from each other, but will also highlight similarities between them after they're derived.
### Definitions
**Def. 1**. An order $d$ **homogeneous linear recurrence with constant coefficients** (or _linear recurrence_) is an equation of the form
$$
F_n = \sum\limits_{k=1}^d a_k F_{n-k}.
$$
**Def. 2**. In the equation above, the coefficients $a_1, \dots, a_d \in R$ are called the **recurrence parameters**,
**Def. 3**. and a sequence $F_0, F_1, \dots \in R$ is called an order $d$ **linear recurrence sequence**.
<hr>
The most common task with linear recurrences is, given initial coefficients $F_0, F_1, \dots, F_{d-1}$, to find the value of $F_n$.
<hr>
**Example...
operator $A$ and $\Sigma$ denotes the Minkowski sum of corresponding subspaces., \\}$ is the kernel of the linear operator $A$ and $\Sigma$ denotes the Minkowski
sum of corresponding
4.
Analysis of polynomial hashing Unfortunately, most derivations of the chance of polynomial hashing collision are invalid, wrong, or misleading, and finding reliable public sources with proofs is incredibly difficult. This article is a formal analysis of the method. The goal of this article is to complement well-known empirical facts with theory, provide boundaries on the probability of collision, justify common choices, and advise against certain popular parameters.
There is no code in this article, and it's mostly theoretical. It's more of a summa of everything we know about polynomial hashing in integers rather than a guide for beginners. You'll probably find something of interest still. I do, however, describe some methods of cracking hashes, which I can provide code and additional explanation for if someone asks in the comments and some general guidelines in the last section of the present article.
## Table of contents
- The concept of polynomial hashing
- Classical justification of the coprimality r...
twofold (i.e. $\Sigma \oplus (-\Sigma)$), where $\oplus$ denotes pairwise
summation/Minkowski sum
5.
CodeForces Beta Round #73 div. 1 analysis (particulary with div. 2) <span style="font-size: 10.0pt;font-family: Arial;color: rgb(0,0,0);background-color: transparent;font-weight: normal;font-style: normal;text-decoration: underline;vertical-align: baseline;">Problem DIV1-A, Div2-C. Trains.</span><br /><span style="font-size: 10.0pt;font-family: Arial;color: rgb(0,0,0);background-color: transparent;font-weight: normal;font-style: normal;text-decoration: none;vertical-align: baseline;">This
problem can be approached from two sides - from a programmer's
perspective and a mathematician's one. We consider both approaches.</span><br /><span style="font-size: 10.0pt;font-family: Arial;color: rgb(0,0,0);background-color: transparent;font-weight: normal;font-style: normal;text-decoration: none;vertical-align: baseline;"> </span><br /><span style="font-size: 10.0pt;font-family: Arial;color: rgb(0,0,0);background-color: transparent;font-weight: normal;font-style: normal;text-decoration: none;vertical-align: baseline;">First,
let's write some general propositio...
called Minkowski sum. We will need only one of its properties: the sum of two
convex polygons is a, or not. This set is called Minkowski sum. We will need only one of its
properties: thesum of two, Minkowski sum. This means that the Minkowski sum is a convex set.
Tutorial of Codeforces Beta Round 73 (Div. 1 Only)
Tutorial of Codeforces Beta Round 73 (Div. 2 Only)
6.
[Tutorial] Distance of two convex polygon Prequisite: Minkowski sum.
When I was solving the problem yesterday, I came up with a simple solution. I hadn't seen it published by anyone else, so I decided to write a blog myself.
Given two **convex** polygon $A$ and $B$, their minimum distance is equal to the minimum distance from the origin point $(0, 0)$ to their **Minkowski sum** $C = A + (-B)$. $-B$ means to negate all the vectors in $B$.
Heuristic proof: We want to know the minimum of distances of every pair vector $(a, b) s.t. a \in A, b \in B$. That equals to $\min(|a - b|) \forall a, b$. And that's the distance from the origin point to the Minkowski sum of $A$ and $-B$.
Note: This should also work for non-convex polygons, but I don't know how to do Minkowski sum (with good time complexity) for them.
The basic idea is similar to GJK algorithm (which is often used to detect object collision), but it is way easier to implement and can return the distance rather than a `bool`.
There will be no implementation h...
from the origin point $(0, 0)$ to their **Minkowski sum** $C = A + (-B)$. $-B$
means to negate all, point to the Minkowski sum of $A$ and $-B$., $ should be $C$ such that $C + B = A$ (the $+$ denotes Minkowski sum), in other
words, the inverse, 1. Left as an exercise for reader. 2. It's very easy, and template for Minkowski
sum can be easily, Note: This should also work for non-convex polygons, but I don't know how to do
Minkowski sum (with, Prequisite: Minkowski sum.
7.
AlgoWiki: A wiki dedicated to competitive programming <img align="right" src="https://wiki.algo.is/img/logo.png" alt="AlgoWiki logo" />
Hi everyone. Over the past couple of years I've been collecting problems,
articles, and competitive programming resources that I find interesting. It's
already grown to dozens of sheets in multiple Google Sheet documents, and is a
pretty bad mess. As an effort to organize this list and make it public, I
decided to turn it into an online wiki dedicated to competitive programming:
[AlgoWiki](https://wiki.algo.is/).
The url is **wiki.algo.is**, so it should be
easy to remember.
I'm far from done migrating stuff into the wiki, but I think there's already
quite a bit of useful information in there. I tried to prioritize
algorithms/data structures/techniques that are less known, and then listed
problems and articles that I thought were especially useful for
learning/practicing the given topic. In some cases I've additionally
extracted/written content about the given topic, with notes that po...
in point: the link to the third problem on the Minkowski sum page linked to
above is already dead, , consider the [Minkowski sum](https://wiki.algo.is/Minkowski%20sum) page, a
topic that I think is, To give you an example, consider the [Minkowski sum](https://wiki.algo.is/
Minkowski%20sum) page, a
8.
[Tutorial] Rotating calipers technique and its applications, Part 2 Hello Codeforces,
This is the second blog on the series about the applications of the rotating calipers technique. If you haven't read the [first part](https://mirror.codeforces.com/blog/entry/133763) yet, make sure to check it out, as much of the terminology that was introduced throughout the first part is going to be used here without further explanation. In this blog, a few more advanced applications will be presented.
### Short recap of the main terminology
- Line of support: a line $l$ that intersects the boundary of the polygon such that the entire polygon lays on one side of $l$
- Anti-podal pair: a pair of vertices which have two parallel lines of support intersecting them
- Rotating calipers: an algorithm where parallel lines of support get rotated around the polygon while being kept on the boundary of the polygon at all times
### Minimum-area enclosing rectangle of a convex polygon
The first application that is going to be discussed is the minimum area enclosing r...
between $pt_1$ and $pt_2$ must lay inside the minkowski sum, therefore, the
minkowski sum must be a, mentioning this application. So, what is the minkowski sum? The minkowski sum
of two polygons $P$ and $Q, this application. So, what is the minkowski sum? The minkowski sum of two
polygons $P$ and $Q$ is, ### Minkowski sums of two convex polygons, $ lays inside the minkowski sum as well. This segment can be described as:, Now, what would you do if you wanted to construct the leftmost vertex of the
minkowski sum? Since, Since every vertex of the minkowski sum is also an extreme point for a specific
direction, all, minkowski sum has up to $n+m$ vertices.
9.
[Solved] A problem related to: minkowski sum of two simple polygon I was trying to solve this problem : [cf-497D](https://mirror.codeforces.com/contest/497/problem/D)
My solution idea :
let $R_d(p) = p'$ where $p'$ is the new location of point $p$ if we rotate it $d$ degree counter-clockwise with respect to $(0,0)$.
That mean $R_d(p) = pe^{id}$
Hence, for some point $a \in A$ and $b \in B$ we can write $R_d(a-p)+p = R_d(b-q)+q$.
$R_d(a-p)+p = R_d(b-q)+q$
$\Longrightarrow R_d(a)-R_d(p)+p = R_d(b)-R_d(q)+q$
$\Longrightarrow p-q - R_d(p) + R_d(q)= R_d(b)-R_d(a)$
$\Longrightarrow (p-q) \frac{R_d - 1}{R_d}= a-b$
Here , $(p-q) \frac{R_d - 1}{R_d}$ actually represent a circle($C$) centered $p-q$ and radius = $|p-q|$.
And $a-b$ = Minkowski sum of A and (-B) [if we consider all $a$ and all $b$ ].
Hence, the problem turns into, checking if circle $C$ intersects polygon A-B or not.
My first idea was to triangulate $A$ and $-B$ then calculate the Minkowski sum of each pair, then check if the polygon(sum) intersects with circle $C$ or not...
[Solved] A problem related to: minkowski sum of two simple polygon, another one from $B$) and Minkowski sum them and got AC. My
[code](https://paste.ubuntu.com/p, And $a-b$ = Minkowski sum of A and (-B) [if we consider all $a$ and all $b$ ]., My first idea was to triangulate $A$ and $-B$ then calculate the Minkowski sum
of each pair, then, }$ actually represent a circle($C$) centered $p-q$ and radius = $|p-q|$. And
$a-b$ =Minkowski sum
10.
Разбор Codeforces Round 990 (Div. 2 + Div. 1) ### Div2A
Alyona is happy when there are no unfinished layers — that is, in front of her is a perfect square with odd side length. Since the order of pieces is fixed, it is enough to keep track of the total current size $s$ of the puzzle, and after each day check, if the $s$ is a perfect square of an odd number. The easiest way to do that is to create an additional array containing $1^2, 3^2, 5^3, ..., 99^2$, and check after each day, whether $s$ is in this array.
<spoiler summary="Code">
~~~~~
NT = int(input())
sqs = set()
k = 1
while k * k <= 100 * 1000:
sqs.add(k * k)
k += 2
for T in range(NT):
n = int(input())
a = list(map(int, input().split()))
answer = 0
cursum = 0
for t in a:
cursum += t
if cursum in sqs:
answer += 1
print(answer)
~~~~~
</spoiler>
### Div2B
Find the character which appears the lowest number of times — if tied, take the earlier character in the alphabet. Find the character which appears the highe...
each segment of '?' we write a polygon and sum them using Minkowski sum, we
will obtain constraints, Since in the Minkowski sum (after merging collinear consecutive segments) there
will be at most 6, Thus, if for each segment of '?' we write a polygon and sum them using Minkowski
sum, we will
Tutorial of Codeforces Round 990 (Div. 1)
Tutorial of Codeforces Round 990 (Div. 2)
11.
English Editorial for The 3rd Chromate Cup Algorithm Division Thank you everyone for participating in The 3rd Chromate Cup Algorithm Division! The full problemset can be accessed on [(link)](https://www.acmicpc.net/category/detail/4114) for upsolving. Also the profile badge/backgrounds are being a bit delayed, I am too busy ;-;
[A. Strange Shuffle](https://www.acmicpc.net/problem/31215)
<spoiler summary="Hint">
Simulate until you feel confident, e.g. until $n=10$. What do you see? I think the result should give you confidence.
</spoiler>
<spoiler summary="Solution">
Let us think step by step starting from $n=1$.
- If $n=1$, $n=l$ is true, therefore no swap will happen.
- If $n=2$, $n=l$ is true, therefore no swap will happen.
- If $n=3$, $l=1$, so $B_1$ and $B_3$ are swapped. Now $1$ is on index $3$.
- If $n>3$, $l$ is a power of $2$, and is therefore not $3$. The index of $1$ never changes afterwards.
Therefore, if $n\le 2$, the answer is $1$. Otherwise, the answer is $3$.
</spoiler>
[B. Super Primes](https://www.acmicpc...
because it is the intersection of two convex sets. Can this convex set be
represented as theMinkowski, their epigraph (or hypograph) is a convex set. Also, for all convex sets $A$
and $B$, theMinkowski sum, sum is also well defined, and the Minkowski sum is also a convex set.
Conversely, we can decompose
12.
2022-2023 ICPC Latin American Regional Programming Contest — Unofficial editorial Hi everyone!
The [2022-2023 ICPC Latin America Regional Programming Contest](https://mirror.codeforces.com/gym/104252) was held last weekend. Given that (as far as I know) there is no official editorial for the problems, I decided to create one.
Please notice that, given that these are not the official solutions, there can be typos/mistakes in the explanations. Feedback is always appreciated :)
I would like to thank [user:lsantire,2023-03-22] for reviewing the editorial and providing valuable feedback.
Don't hesitate to reach out to me if you have any questions/suggestions. Thank you!
[problem:104252A]
<spoiler summary="Hint">
Think in which case a person loses money. Remember we can choose the order in which events happen.
</spoiler>
<spoiler summary="Solution">
Let's fix a person $p$ and call $a$ and $b$ to the people $p$ will ask for money. It's easy to see that $p$ loses money if $a$, $b$ and $p$ are asked for money before $p$ requests $a$ or $b$ to pay.
This ...
linear time. This is called the [Minkowski sum
](https://cp-algorithms.com/geometry/minkowski.html) of $P, Minkowski sum of $P$ and $Q$, we have reduced the problem to be able to check
if $c$ lies inside a, So, after computing the Minkowski sum of $P$ and $Q$, we have reduced the
problem to be able to
13.
All the algorithms/techniques I have used "I'm just in a mood to shitpost. Don't take it too seriously." -Um_nik
#### Graphs
- DFS
- BFS
- 0-1 BFS
- Kruskal's
- Dijkstra's
- Bellman-Ford
- 2-Coloring
- Prim's
- Floyd-Warshall
- Johnsons
- Ford-Fulkerson
- Dinics
- Edmonds-Karp
- Level Graphs
- SCC
- 2VCC/2ECC
- 2-Sat
- Dominator-Trees
- Hopcroft-Karp
- Hungarian
- MCMF
- Top Sort
- Blossom's
- Eulerian Cycle
- Hamiltonian Cycle
- TSP
- Functional Graphs
- Augmenting Paths
#### DP
- Range DP
- Divide and Conquer DP
- Convex Hull Trick
- Space Save
- Alien Trick
- Bitmask DP
- State Switch
- Digit Descent
#### Strings
- Hashing
- KMP
- Z-function
- Trie
- Aho Corasick
- Suffix Automaton
- Suffix Tree
- Suffix Array
- Eertree
- Manachers
#### Data Structures
- Segment Tree
- Prefix Sum
- DSU
- DSU Rollback
- Treap
- Binary Indexed Tree
- Queue
- Stack
- Priority Queue
- Linked List
- Sets
- Maps
- Bitsets
- Ordered Statisic Tree
- Lazy Propagation
- Li Chao...
- Minkowski Sum - Convex Shell - Delaunay Triangluation - Voronoi Diagram -
Power Triangulation, - Planar Sweep - Radial Sweep - Halfplane intersection - Minkowski Sum -
Convex Shell - Delaunay
14.
Russian Code Cup 2017 Finals — Results and Editorial First of all, congratulations to [user:moejy0viiiiiv,2017-09-10] for winning, [user:LHiC,2017-09-10] and [user:jcccccccccccccccccccccsb,2017-09-10] for coming second and third. The Final Round proved to be quite challenging, and we are happy that the results are tight.
The round was prepared by [user:Aksenov239,2017-09-10], [user:GShark,2017-09-10], [user:izban,2017-09-10], [user:manoprenko,2017-09-10], [user:niyaznigmatul,2017-09-10], [user:qwerty787788,2017-09-10] and [user:SpyCheese,2017-09-10], supervisor [user:andrewzta,2017-09-10]. Special thanks for this round goes to [user:izban,2017-09-10] who is the author of problems D, E and F, and also gave a lot of important comments for all problems of the round.
Now let us move on to the editorial.
<div class="problem-statement"><div class="header"><div class="title">A. Set Theory</div></div><div class="tutorial"><p>First let us prove that the answer is always <span class="tex-font-style-tt">YES</span>.</p><p>Let us iterate ove...
> seconds. The new polygon is the Minkowski sum of the previous polygon and the
degenerate polygon: segment, Minkowski sum of the previous polygon and the degenerate polygon: segment with
two vertices
15.
Theoretical grounds of lambda optimization Hi everyone!
This time I'd like to write about what's widely known as "Aliens trick" (as it got popularized after 2016 IOI problem called [Aliens](https://ioinformatics.org/files/ioi2016problem6.pdf)). There are already some articles about it here and there, and I'd like to summarize them, while also adding insights into the connection between this trick and generic Lagrange multipliers and Lagrangian duality which often occurs in e.g. linear programming problems.
Familiarity with a [previous blog](https://mirror.codeforces.com/blog/entry/98524) about ternary search or, at the very least, definitions and propositions from it is expected.
Great thanks to [user:mango_lassi,2022-01-01] and [user:300iq,2022-01-01] for useful discussions and some key insights on this.
Note that although explanation here might be quite verbose and hard to comprehend at first, the algorithm itself is stunningly simple.
Another point that I'd like to highlight for those already familiar with "Aliens tr...
ones. Since elements are increasing, sum of first $k+y$ elements is convex as
a function of $y
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: May/03/2026 02:12:20 (g2).
Desktop version, switch to mobile version.
Supported by
