1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
DAG
Contest: AIM Tech Poorly Prepared Contest (unrated, funny, Div. 1 preferred)
Tags: constructive algorithms

This is an unusual problem in an unusual contest, here is the announcement: http://codeforces.com/blog/entry/73543

You are given a directed acyclic graph $$$G$$$ with $$$n$$$ vertices and $$$m$$$ edges. Denote by $$$R(v)$$$ the set of all vertices $$$u$$$ reachable from $$$v$$$ by moving along the edges of $$$G$$$. Find $$$\sum\limits_{v=1}^n |R(v)|^2$$$.

Input format:
The first line contains two integers $$$n, m$$$ ($$$1 \leq n, m \leq 5 \cdot 10^4$$$) denoting the number of vertices and the number of edges of $$$G$$$.

Each of the next $$$m$$$ lines contains two integers $$$u, v$$$ ($$$1 \leq u \neq v \leq n$$$), denoting the edge from $$$u$$$ to $$$v$$$.

It's guaranteed that the given graph does not contain any cycles.

Output format:
Print one integer — the answer to the problem.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Example input:
5 4
1 2
2 3
3 4
4 5

Example output:
55

Example input:
12 6
1 2
3 4
5 6
8 7
10 9
12 11

Example output:
30

Editorial:
To solve this problem one can update a bitset of all reachable vertices from every vertex $$$v$$$ in the topological sorted order and then calculate the sum of sqr(reachable[v].count()). The bug was, maybe, less obvious than in the previous problem, but still quite common (at least we thought so): instead of creating an edge $$$u\to v$$$ we created edges $$$v\to u$$$. Again, the first two samples contained a path and a set of isolated edges, while the third one has an incorrect answer.
However, bitset sometimes doesn't fit into memory, so one can, for example, calculate $$$n/64$$$ times for each vertex the number of reachable vertices with indices from $$$64k$$$ to $$$64(k+1) - 1$$$ and then sum up all the reachable counts.
Segment tree or Fenwick?
Contest: AIM Tech Poorly Prepared Contest (unrated, funny, Div. 1 preferred)
Tags: data structures

This is an unusual problem in an unusual contest, here is the announcement: http://codeforces.com/blog/entry/73543

You are given an array $$$A$$$ of length $$$n$$$, initially filled with zeros. You need to process $$$q$$$ queries to the array, each of one of the following types:

1. 1 x y: you need to assign $$$A_x=y$$$;
2. 2 l r: you need to print $$$\sum\limits_{i=l}^r A_i$$$.

Input format:
The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 10^5$$$) — the number of test cases.

Each test case description starts with two integers $$$n, q$$$ ($$$1 \leq n, q \leq 10^5$$$) — the length of the array and the number of queries. The following $$$q$$$ lines contain the description of queries: $$$1~x~y$$$ ($$$1 \leq x \leq n$$$, $$$0 \leq y \leq 10^9$$$) for queries of the first type and $$$2~l~r$$$ ($$$1 \leq l \leq r \leq n$$$) for queries of the second type.

It is guaranteed that the sum of $$$n$$$ as well as the sum of $$$q$$$ does not exceed $$$10^6$$$.

Output format:
For each query of the second type print its result on a separate line.

Constraints:
Time limit: 2.5 s
Memory limit: 256.0 MB

Example input:
2
6 5
2 1 6
1 3 2
2 2 4
1 6 3
2 1 6
5 3
1 3 7
1 1 4
2 1 5

Example output:
0
2
5
11

Editorial:
Well, the problem itself is a standard segment tree/fenwick tree exercise. So where could one mess up here?
We expected participants to notice that this is the only problem with several test cases here, so the common bug used here is not clearing the global data structure between tests. One can see that both Fenwick tree and Segment tree without clearing produce same answers.
Dijkstra
Contest: AIM Tech Poorly Prepared Contest (unrated, funny, Div. 1 preferred)

This is an unusual problem in an unusual contest, here is the announcement: http://codeforces.com/blog/entry/73543

Find the distance between vertices $$$1$$$ and $$$n$$$ in an undirected weighted graph.

Input format:
The first line contains two integers $$$n, m$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5$$$) — the number of vertices and the number of edges.

Each of the next $$$m$$$ lines contain description of an edge $$$a_i~b_i~cost_i$$$ ($$$1 \leq a_i, b_i \leq n$$$, $$$1 \leq cost_i \leq 10^9$$$).

Loops and multiple edges? Hmm, why not?

Output format:
Print one integer — the answer to the problem. If there is no path, print $$$-1$$$ instead.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3 3
1 2 5
2 3 1
1 3 7

Example output:
6

Editorial:
This was a tough problem, but (arguably) the most popular Dijkstra implementation uses priority_queue structure (it's faster than std::set), but its .top() method returns the greatest element, not the smallest, which may be easy to mess up with. So the bug was fixing the vertex with the greatest current distance, not with the smallest.
Amazing bitset
Contest: AIM Tech Poorly Prepared Contest (unrated, funny, Div. 1 preferred)

This is an unusual problem in an unusual contest, here is the announcement: http://codeforces.com/blog/entry/73543

Andrey has just started to study competitive programming and he is fascinated by bitsets and operations on them.

For example, assume he has a bitset with $$$n$$$ elements. He can change the values of the bitset in the following way:

1. He chooses different indices $$$i_0$$$, $$$i_1$$$, $$$i_2$$$, ... $$$i_k$$$ ($$$k \geq 1$$$, $$$1 \leq i_j \leq n$$$) so that bit $$$i_0$$$ is different from all bits $$$i_1$$$, $$$i_2$$$, ... $$$i_k$$$.
2. He flips all these $$$k + 1$$$ bits.

He calls a bitset amazing if he can flip all the bits using several such changes.

Another topic Andrey is interested in is probability theory. For given $$$n$$$ and $$$p$$$, where $$$p$$$ is a rational number represented as $$$\frac{a}{b}$$$ with integer $$$a, b$$$, he considers all bitsets of length $$$n$$$, where each element is equal to $$$1$$$ with probability $$$p$$$ independently of the other elements.

He wants to know the probability that a bitset generated by the described method is amazing.

It is guaranteed that the answer to this problem can be represented as a rational number $$$\frac{x}{y}$$$, where $$$y$$$ is coprime with $$$1\,234\,567\,891$$$. You need to output such integer $$$z$$$ that $$$x \equiv yz \pmod{1\,234\,567\,891}$$$ and $$$0 \leq z < 1\,234\,567\,891$$$.

Input format:
The only line contains three integers $$$n, a, b$$$ ($$$1 \leq n \leq 10^9$$$, $$$0 \leq a \leq 10^5$$$, $$$1 \leq b \leq 10^5$$$, $$$a \leq b$$$), denoting the length of the bitset and the probability of an element to be $$$1$$$ (probability is $$$\frac{a}{b}$$$).

Output format:
Output the answer to the problem in the only line.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
5 1 2

Example output:
848765426

Example input:
1 228 239

Example output:
0

Editorial:
First of all, we claim that a bitset is amazing iff it has distinct elements. Indeed, if all its elements are equal, then we cannot do a single operation. Otherwise, if there are $$$a$$$ zero bits and $$$b$$$ one bits (wlog $$$a\leq b$$$), then we can do $$$(a - 1)$$$ operations to flip one 0-bit and one 1-bit per operation, and then flip all the remaining bits using the last operation.
So it can be seen that the probability for a bitset not to be amazing is $$$p^n + (1 - p)^n$$$. This can be calculated using fast exponentiation, and then subtracted from $$$1$$$.
The problem is that if we calculate both summands in ints, then their sum can exceed INT_MAX, because $$$1\,234\,567\,891 > 2^{30}$$$, so int overflow is the bug here.
Who needs suffix structures?
Contest: AIM Tech Poorly Prepared Contest (unrated, funny, Div. 1 preferred)

This is an unusual problem in an unusual contest, here is the announcement: http://codeforces.com/blog/entry/73543

You run a string shop. During a day your customers want to buy strings of certain lengths and sometimes satisfying other properties.

You have a string of length $$$n$$$ and can cut a string of any length starting at any position out of it. Today your first customer asks you some questions of type "Is there any difference between substrings of length $$$k$$$ if one of them starts at position $$$i$$$ and another one starts from the $$$j$$$-th position?" You are to answer all these questions.

Please note that in your shop strings are over an alphabet of size $$$987\,898\,789$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1\leq q, n\leq 200\,000$$$). The second line contains $$$n$$$ space-separated integers $$$a_1$$$, ..., $$$a_n$$$ ($$$0\leq a_i < 987\,898\,789$$$) which denote the letters of string $$$s$$$, and each of the following $$$q$$$ lines contains three integers $$$len$$$, $$$pos_1$$$ and $$$pos_2$$$ ($$$1\leq len\leq n$$$, $$$1\leq pos_1, pos_2\leq n - len + 1$$$) denoting the corresponding query.

Output format:
Print $$$q$$$ lines, $$$i$$$-th of them containing Yes if the two substrings in the $$$i$$$-th query (of length $$$len$$$ starting from $$$pos_1$$$ and $$$pos_2$$$) are equal and No otherwise.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
5 2
1 2 3 1 2
2 1 4
3 1 3

Example output:
Yes
No

Example input:
9 3
0 0 0 0 0 0 0 0 0
9 1 1
8 1 2
1 1 9

Example output:
Yes
Yes
Yes

Editorial:
The problem name and the folder with open tests hint that the intended solution uses hashes. We already have the modulo from the statement. The rest is to obtain the base.
There is a bunch of tests where all queries compare the first segment of length $$$k$$$ with all other subsegments of length $$$k$$$ which end at a position divisible by $$$k$$$. One can manually (using an $$$O(nq)$$$ algorithm or a suffix structure) get all such pairs of substrings with a collision. Each of them gives us a constraint of form $$$P(base)\equiv 0\pmod{987\,898\,789}$$$ where $$$P$$$ is a polynomial. One can get a GCD of all such polynomials to obtain a polynomial having $$$base$$$ as its root.
GCD'ing such polynomials from the whole pack of open tests, one can obtain that $$$base$$$ is the root of the polynomial $$$x - 456\,545\,664$$$.
Deja vu
Contest: AIM Tech Poorly Prepared Contest (unrated, funny, Div. 1 preferred)

This is an unusual problem in an unusual contest, here is the announcement: http://codeforces.com/blog/entry/73543

You run a string shop. During a day your customers want to buy strings of certain lengths and sometimes satisfying other properties.

Today your first customer asked you if you have a string of length $$$k$$$. In fact, you have a string of length $$$n$$$ and can cut a string of length $$$k$$$ starting at any position out of it. You wonder how many distinct values this string can equal.

Please note that in your shop strings are over an alphabet of size $$$2$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1\leq k\leq n\leq 200\,000$$$). The second line contains a binary string $$$s$$$ of length $$$n$$$.

Output format:
In the only line print the number of distinct substrings of length $$$k$$$ of the string $$$s$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The second sample test represents the de Bruijn sequence of order 3.

Example input:
5 2
01101

Example output:
3

Example input:
10 3
1110001011

Example output:
8

Editorial:
The folder name in the open tests archive hints that this problem is about breaking hashing modulo $$$2^{64}$$$. One can also see this in the Thue-Morse open tests.
In the last but one test seeing $$$n = 128$$$ and $$$k = 64$$$ and an incorrect answer one can assume that the first and the last string give a collision. If you are not sure, you can decode the last input string considering it as a bit representation of some string:
>>> "".join(map(lambda x: chr(int(x, 2)), [s[i:i+8] for i in range(0, len(s), 8)]))
'if the answer is incorrect then maybe prefix =/= suffix, just a guess'
Subtracting the suffix polynomial from the prefix one we get a polynomial with coefficients from $$$\{-1, 0, 1\}$$$ and having base as the root modulo $$$2^{64}$$$. It is obvious that the base is odd. It turns out that its remainder modulo $$$4$$$ is uniquely determined. Using the remainder modulo $$$4$$$, its remainder modulo $$$8$$$ is also unique, and so on (the condition is that the free coefficient is nonzero, the total sum of coefficients is even and the total sum of coefficients of $$$x^1$$$, $$$x^3$$$, $$$x^5$$$, $$$\ldots$$$ is odd). Thus one can restore the base bit by bit.
Split a Number
Contest: Codeforces Round 567 (Div. 2)
Difficulty rating: 1500
Tags: greedy, implementation, strings

Dima worked all day and wrote down on a long paper strip his favorite number $$$n$$$ consisting of $$$l$$$ digits. Unfortunately, the strip turned out to be so long that it didn't fit in the Dima's bookshelf.

To solve the issue, Dima decided to split the strip into two non-empty parts so that each of them contains a positive integer without leading zeros. After that he will compute the sum of the two integers and write it down on a new strip.

Dima wants the resulting integer to be as small as possible, because it increases the chances that the sum will fit it in the bookshelf. Help Dima decide what is the minimum sum he can obtain.

Input format:
The first line contains a single integer $$$l$$$ ($$$2 \le l \le 100\,000$$$) — the length of the Dima's favorite number.

The second line contains the positive integer $$$n$$$ initially written on the strip: the Dima's favorite number.

The integer $$$n$$$ consists of exactly $$$l$$$ digits and it does not contain leading zeros. Dima guarantees, that there is at least one valid way to split the strip.

Output format:
Print a single integer — the smallest number Dima can obtain.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first example Dima can split the number $$$1234567$$$ into integers $$$1234$$$ and $$$567$$$. Their sum is $$$1801$$$.

In the second example Dima can split the number $$$101$$$ into integers $$$10$$$ and $$$1$$$. Their sum is $$$11$$$. Note that it is impossible to split the strip into "1" and "01" since the numbers can't start with zeros.

Example input:
7
1234567

Example output:
1801

Example input:
3
101

Example output:
11

Editorial:
Suppose that the number doesn't contain any zeros (that is, we can split it at any point).
Than it is easy to show that it is enough to check only the following cuts:
• $$$k$$$; $$$k$$$, if the length of the number is $$$2k$$$.
• $$$k + 1$$$; $$$k$$$ and $$$k$$$; $$$k + 1$$$, if the length of the number is $$$2k + 1$$$.
Some intuition behind this: it's not optimal to make "inbalanced" cuts. Because the sum $$$a + b$$$ is at least $$$max(a, b)$$$. And in case the maximum is large already, we could have built a more optimal answer if we would make a cut in a less "inbalanced" way.
One can also examine not only $$$1-2$$$ possible cuts, but rather $$$\mathcal{O}(1)$$$ different options around the center, this way solution is a bit easier to proof.
In case we have zeros, the solution is mostly the same: we just simply need to consider the closest valid cut to the left from center and closest valid cut to the right. And take a minimum of them.
One can note that in the solution above we need to add and compare "long integers". One could have used a programming language in which they are already implemented (Python/Java) or implemented the required functions themselves. The number can be simply stored as a sequence of digits from least-important digit to the most-important. It's simple to implement the summation and comparing of such integers.
A Story of One Country (Easy)
Contest: Codeforces Round 567 (Div. 2)
Difficulty rating: 2500
Tags: brute force, divide and conquer, sortings

This problem differs from the next problem only in constraints.

Petya decided to visit Byteland during the summer holidays. It turned out that the history of this country is quite unusual.

Initially, there were $$$n$$$ different countries on the land that is now Berland. Each country had its own territory that was represented as a rectangle on the map. The sides of the rectangle were parallel to the axes, and the corners were located at points with integer coordinates. Territories of no two countries intersected, but it was possible that some territories touched each other. As time passed, sometimes two countries merged into one. It only happened if the union of their territories was also a rectangle. In the end only one country remained — Byteland.

Initially, each country had a rectangular castle inside its territory. Its sides were parallel to the axes and its corners had integer coordinates. Some castles might touch the border of the corresponding country and sides or other castles. Miraculously, after all the unions the castles are still intact. Unfortunately, their locations are the only information we have to restore the initial territories of the countries.

The possible formation of Byteland. The castles are shown in blue.

Petya wonders why no information about the initial countries remained. He suspected that the whole story is a fake. You were recommended to him as a smart person. Please check whether or not there exists a possible set of initial territories that could make the story true.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) — the number of countries and castles.

Each of the next $$$n$$$ lines contains four integers $$$a_i, b_i, c_i, d_i$$$ ($$$0 \leq a_i < c_i \leq 10^9$$$, $$$0 \leq b_i < d_i \leq 10^9$$$) — the coordinates of the $$$i$$$-th castle, where $$$(a_i, b_i)$$$ are the coordinates of the lower left corner and $$$(c_i, d_i)$$$ are the coordinates of the upper right corner.

It is guaranteed, that no two castles intersect, however, they may touch.

Output format:
If there exists a possible set of territories that satisfies the story, print "YES", otherwise print "NO".

You can print each letter in any case (upper or lower).

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
The castles in the first and second examples are shown on the pictures below.

Example input:
4
0 0 1 2
0 2 1 3
1 0 2 1
1 1 2 3

Example output:
YES

Example input:
4
0 0 2 1
1 2 3 3
2 0 3 2
0 1 1 3

Example output:
NO

Editorial:
Treasure Hunt
Contest: Educational Codeforces Round 23
Difficulty rating: 1200
Tags: implementation, math, number theory

Captain Bill the Hummingbird and his crew recieved an interesting challenge offer. Some stranger gave them a map, potion of teleportation and said that only this potion might help them to reach the treasure.

Bottle with potion has two values x and y written on it. These values define four moves which can be performed using the potion:

- $$(a,b)\rightarrow(a+x,b+y)$$
- $$(a,b)\rightarrow(a+x,b-y)$$
- $$(a,b)\rightarrow(a-x,b+y)$$
- $$(a,b)\rightarrow(a-x,b-y)$$

Map shows that the position of Captain Bill the Hummingbird is (x1, y1) and the position of the treasure is (x2, y2).

You task is to tell Captain Bill the Hummingbird whether he should accept this challenge or decline. If it is possible for Captain to reach the treasure using the potion then output "YES", otherwise "NO" (without quotes).

The potion can be used infinite amount of times.

Input format:
The first line contains four integer numbers x1, y1, x2, y2 ( - 105 ≤ x1, y1, x2, y2 ≤ 105) — positions of Captain Bill the Hummingbird and treasure respectively.

The second line contains two integer numbers x, y (1 ≤ x, y ≤ 105) — values on the potion bottle.

Output format:
Print "YES" if it is possible for Captain to reach the treasure using the potion, otherwise print "NO" (without quotes).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example there exists such sequence of moves:

1. $$(0,0)\rightarrow(2,3)$$ — the first type of move
2. $$(2,3)\rightarrow(0,6)$$ — the third type of move

Example input:
0 0 0 6
2 3

Example output:
YES

Example input:
1 1 3 6
1 5

Example output:
NO

Editorial:
Firstly, let's approach this problem as if the steps were $$(a,b)\to(a\pm x,0)$$ and $$(a,b)\to(0,b\pm y)$$. Then the answer is "YES" if |x1 - x2| mod x = 0 and |y1 - y2| mod y = 0.
It's easy to see that if the answer to this problem is "NO" then the answer to the original one is also "NO".
Let's return to the original problem and take a look at some sequence of steps. It ends in some point (xe, ye). Define cntx as $$\frac{|x_{e}-x_{1}|}{x}$$ and cnty as $$\frac{|y_{e}-y_{1}|}{y}$$. The parity of cntx is the same as the parity of cnty. It is like this because every type of move changes parity of both cntx and cnty.
So the answer is "YES" if |x1 - x2| mod x = 0, |y1 - y2| mod y = 0 and $$\frac{|x_{1}-x_{2}|}{x}$$ mod $$2 = \frac{|y_1 - y_2|}{y}$$ mod 2.
Overall complexity: O(1).
Makes And The Product
Contest: Educational Codeforces Round 23
Difficulty rating: 1500
Tags: combinatorics, implementation, math, sortings

After returning from the army Makes received a gift — an array a consisting of n positive integer numbers. He hadn't been solving problems for a long time, so he became interested to answer a particular question: how many triples of indices (i,  j,  k) (i < j < k), such that ai·aj·ak is minimum possible, are there in the array? Help him with it!

Input format:
The first line of input contains a positive integer number n (3 ≤ n ≤ 105) — the number of elements in array a. The second line contains n positive integer numbers ai (1 ≤ ai ≤ 109) — the elements of a given array.

Output format:
Print one number — the quantity of triples (i,  j,  k) such that i,  j and k are pairwise distinct and ai·aj·ak is minimum possible.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example Makes always chooses three ones out of four, and the number of ways to choose them is 4.

In the second example a triple of numbers (1, 2, 3) is chosen (numbers, not indices). Since there are two ways to choose an element 3, then the answer is 2.

In the third example a triple of numbers (1, 1, 2) is chosen, and there's only one way to choose indices.

Example input:
4
1 1 1 1

Example output:
4

Example input:
5
1 3 2 3 4

Example output:
2

Editorial:
Minimal product is obtained by multiplying three smallest elements of the array.
Let's iterate over the middle element of these three and calc sum of all options.
Firstly let's precalc two arrays of pairs — mnl and mnr. mnl[x] is minimum and number of its occurrences on the prefix of array a up to index x inclusive. mnr[x] is minimum and number of its occurrences on the suffix of array a up to index x inclusive. It can be done with two traversals over the array.
Let's also store set of three elements which give minimal product of the array.
Consider every index j from 1 to n - 2 inclusive (0-indexed). If set (a[j],  mnl[j - 1].first,  mnr[j + 1].first) is equal to the stored set of three minimums then add to the answer number of ways to choose pair (i,  k), that is mnl[j - 1].second · mnr[j + 1].second.
Overall complexity: O(n).