1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Flawed Flow
Contest: Codeforces Round 165 (Div. 1)
Difficulty rating: 2100
Tags: constructive algorithms, flows, graphs, greedy

Emuskald considers himself a master of flow algorithms. Now he has completed his most ingenious program yet — it calculates the maximum flow in an undirected graph. The graph consists of n vertices and m edges. Vertices are numbered from 1 to n. Vertices 1 and n being the source and the sink respectively.

However, his max-flow algorithm seems to have a little flaw — it only finds the flow volume for each edge, but not its direction. Help him find for each edge the direction of the flow through this edges. Note, that the resulting flow should be correct maximum flow.

More formally. You are given an undirected graph. For each it's undirected edge (ai, bi) you are given the flow volume ci. You should direct all edges in such way that the following conditions hold:

1. for each vertex v (1 < v < n), sum of ci of incoming edges is equal to the sum of ci of outcoming edges;
2. vertex with number 1 has no incoming edges;
3. the obtained directed graph does not have cycles.

Input format:
The first line of input contains two space-separated integers n and m (2 ≤ n ≤ 2·105, n - 1 ≤ m ≤ 2·105), the number of vertices and edges in the graph. The following m lines contain three space-separated integers ai, bi and ci (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ ci ≤ 104), which means that there is an undirected edge from ai to bi with flow volume ci.

It is guaranteed that there are no two edges connecting the same vertices; the given graph is connected; a solution always exists.

Output format:
Output m lines, each containing one integer di, which should be 0 if the direction of the i-th edge is ai → bi (the flow goes from vertex ai to vertex bi) and should be 1 otherwise. The edges are numbered from 1 to m in the order they are given in the input.

If there are several solutions you can print any of them.

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

Note:
In the first test case, 10 flow units pass through path $$1 \rightarrow 2 \rightarrow 3$$, and 5 flow units pass directly from source to sink: $$\rightarrow$$.

Example input:
3 3
3 2 10
1 2 10
3 1 5

Example output:
1
0
1

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

Example output:
0
0
1
1
0

Editorial:
Make it Beautiful
Contest: Educational Codeforces Round 141 (Rated for Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, math, sortings

An array $$$a$$$ is called ugly if it contains at least one element which is equal to the sum of all elements before it. If the array is not ugly, it is beautiful.

For example:

- the array $$$[6, 3, 9, 6]$$$ is ugly: the element $$$9$$$ is equal to $$$6 + 3$$$;
- the array $$$[5, 5, 7]$$$ is ugly: the element $$$5$$$ (the second one) is equal to $$$5$$$;
- the array $$$[8, 4, 10, 14]$$$ is beautiful: $$$8 \ne 0$$$, $$$4 \ne 8$$$, $$$10 \ne 8 + 4$$$, $$$14 \ne 8 + 4 + 10$$$, so there is no element which is equal to the sum of all elements before it.

You are given an array $$$a$$$ such that $$$1 \le a_1 \le a_2 \le \dots \le a_n \le 100$$$. You have to reorder the elements of $$$a$$$ in such a way that the resulting array is beautiful. Note that you are not allowed to insert new elements or erase existing ones, you can only change the order of elements of $$$a$$$. You are allowed to keep the array $$$a$$$ unchanged, if it is beautiful.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 2000$$$) — the number of test cases.

Each test case consists of two lines. The first line contains one integer $$$n$$$ ($$$2 \le n \le 50$$$). The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_1 \le a_2 \le \dots \le a_n \le 100$$$).

Output format:
For each test case, print the answer as follows:

- if it is impossible to reorder the elements of $$$a$$$ in such a way that it becomes beautiful, print NO;
- otherwise, in the first line, print YES. In the second line, print $$$n$$$ integers — any beautiful array which can be obtained from $$$a$$$ by reordering its elements. If there are multiple such arrays, print any of them.

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

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

Example output:
YES
3 6 3 6
NO
YES
2 4 1 5 3
YES
1 4 4

Editorial:
If we put the maximum in the array on the first position, then for every element, starting from the third one, the sum of elements before it will be greater than it (since that sum is greater than the maximum value in the array). So, the only element that can make our array ugly is the second element. We need to make sure that it is not equal to the first element.
Let's put the maximum element on the first position, the minimum element on the second position, and then fill the rest of the array arbitrarily. The only case when it fails is when the maximum element is equal to the minimum element — and it's easy to see that if the maximum is equal to the minimum, then the first element of the array will be equal to the second element no matter what, and the array cannot become beautiful.
So, the solution is to check if the maximum is different from the minimum, and if it is so, put them on the first two positions, and the order of remaining elements does not matter. Note that the given array is sorted, so the minimum is the first element, the maximum is the last element.
Matrix of Differences
Contest: Educational Codeforces Round 141 (Rated for Div. 2)
Difficulty rating: 1100
Tags: constructive algorithms, math

For a square matrix of integers of size $$$n \times n$$$, let's define its beauty as follows: for each pair of side-adjacent elements $$$x$$$ and $$$y$$$, write out the number $$$|x-y|$$$, and then find the number of different numbers among them.

For example, for the matrix $$$\begin{pmatrix} 1 & 3\\ 4 & 2 \end{pmatrix}$$$ the numbers we consider are $$$|1-3|=2$$$, $$$|1-4|=3$$$, $$$|3-2|=1$$$ and $$$|4-2|=2$$$; there are $$$3$$$ different numbers among them ($$$2$$$, $$$3$$$ and $$$1$$$), which means that its beauty is equal to $$$3$$$.

You are given an integer $$$n$$$. You have to find a matrix of size $$$n \times n$$$, where each integer from $$$1$$$ to $$$n^2$$$ occurs exactly once, such that its beauty is the maximum possible among all such matrices.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 49$$$) – the number of test cases.

The first (and only) line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 50$$$).

Output format:
For each test case, print $$$n$$$ rows of $$$n$$$ integers — a matrix of integers of size $$$n \times n$$$, where each number from $$$1$$$ to $$$n^2$$$ occurs exactly once, such that its beauty is the maximum possible among all such matrices. If there are multiple answers, print any of them.

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

Example input:
2
2
3

Example output:
1 3
4 2
1 3 4
9 2 7
5 8 6

Editorial:
The first step is to notice that beauty doesn't exceed $$$n^2-1$$$, because the minimum difference between two elements is at least $$$1$$$, and the maximum difference does not exceed $$$n^2-1$$$ (the difference between the maximum element $$$n^2$$$ and the minimum element $$$1$$$).
At first, finding a matrix with maximum beauty seems to be a quite difficult task. So let's try to find an array of $$$n^2$$$ elements of maximum beauty. In this case, it is not difficult to come up with an array of the form $$$[n^2, 1, n^2-1, 2, n^2-2, 3, \dots]$$$. In such an array, there are all possible differences from $$$1$$$ to $$$n^2-1$$$. So we found an array with the maximum possible beauty.
It remains to find a way to "convert" the array to the matrix, i.e. to find such a sequence of matrix cells that each two adjacent cells in it are side-adjacent. One of the ways is the following: traverse the first row of the matrix from left to right, go down to the second row, traverse it from right to left, go down to the third row, traverse it from left to right, and so on.
Thus, we constructed a matrix with the maximum possible beauty $$$n^2-1$$$.
Indivisible
Contest: Codeforces Round 869 (Div. 2)
Difficulty rating: 900
Tags: constructive algorithms

You're given a positive integer $$$n$$$.

Find a permutation $$$a_1, a_2, \dots, a_n$$$ such that for any $$$1 \leq l < r \leq n$$$, the sum $$$a_l + a_{l+1} + \dots + a_r$$$ is not divisible by $$$r-l+1$$$.

A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). Description of the test cases follows.

The first line of each test case contain a single integer $$$n$$$ ($$$1 \leq n \leq 100$$$) — the size of the desired permutation.

Output format:
For each test case, if there is no such permutation print $$$-1$$$.

Otherwise, print $$$n$$$ distinct integers $$$p_1, p_{2}, \dots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — a permutation satisfying the condition described in the statement.

If there are multiple solutions, print any.

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

Note:
In the first example, there are no valid pairs of $$$l < r$$$, meaning that the condition is true for all such pairs.

In the second example, the only valid pair is $$$l=1$$$ and $$$r=2$$$, for which $$$a_1 + a_2 = 1+2=3$$$ is not divisible by $$$r-l+1=2$$$.

in the third example, for $$$l=1$$$ and $$$r=3$$$ the sum $$$a_1+a_2+a_3$$$ is always $$$6$$$, which is divisible by $$$3$$$.

Example input:
3
1
2
3

Example output:
1
1 2
-1

Editorial:
If $$$n > 1$$$ is odd, there is no solution, as the sum of the whole array $$$\frac{n(n+1)}{2}$$$ is always divisible by $$$n$$$. Otherwise, the solution is as follows:
1. Start with the identity permutation $$$1, 2, \dots, n$$$.
2. Swap the adjacent pairs to get $$$2, 1, 4, 3, 6, 5, ..., n, n-1$$$.
Indeed, consider the sum of a sub-array $$$a_l, \dots, a_r$$$. There are $$$2$$$ cases:
• $$$l$$$ and $$$r$$$ have different parity: the sum is $$$\frac{(r-l+1)(l+r)}{2}$$$ and its greatest common divisor with $$$r-l+1$$$ is $$$\frac{r-l+1}{2}$$$, as $$$l+r$$$ is not divisible by $$$2$$$;
• $$$l$$$ and $$$r$$$ have the same parity: the sum is $$$\frac{(r-l+1)(l+r)}{2}+1$$$ or $$$\frac{(r-l+1)(l+r)}{2}-1$$$, depending on the parity. The first summand is divisible by $$$r-l+1$$$, as $$$l+r$$$ is even. So, the whole sum has the remainder $$$1$$$ or $$$-1$$$ modulo $$$r-l+1$$$, thus it can't be divisible by it.
Alice and Bob
Contest: Codeforces Round 201 (Div. 1)
Difficulty rating: 1600
Tags: games, math, number theory

It is so boring in the summer holiday, isn't it? So Alice and Bob have invented a new game to play. The rules are as follows. First, they get a set of n distinct integers. And then they take turns to make the following moves. During each move, either Alice or Bob (the player whose turn is the current) can choose two distinct integers x and y from the set, such that the set doesn't contain their absolute difference |x - y|. Then this player adds integer |x - y| to the set (so, the size of the set increases by one).

If the current player has no valid move, he (or she) loses the game. The question is who will finally win the game if both players play optimally. Remember that Alice always moves first.

Input format:
The first line contains an integer n (2 ≤ n ≤ 100) — the initial number of elements in the set. The second line contains n distinct space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the elements of the set.

Output format:
Print a single line with the winner's name. If Alice wins print "Alice", otherwise print "Bob" (without quotes).

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

Note:
Consider the first test sample. Alice moves first, and the only move she can do is to choose 2 and 3, then to add 1 to the set. Next Bob moves, there is no valid move anymore, so the winner is Alice.

Example input:
2
2 3

Example output:
Alice

Example input:
2
5 3

Example output:
Alice

Editorial:
Lucky Common Subsequence
Contest: Codeforces Round 201 (Div. 1)
Difficulty rating: 2000
Tags: dp, strings

In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, the sequence BDF is a subsequence of ABCDEF. A substring of a string is a continuous subsequence of the string. For example, BCD is a substring of ABCDEF.

You are given two strings s1, s2 and another string called virus. Your task is to find the longest common subsequence of s1 and s2, such that it doesn't contain virus as a substring.

Input format:
The input contains three strings in three separate lines: s1, s2 and virus (1 ≤ |s1|, |s2|, |virus| ≤ 100). Each string consists only of uppercase English letters.

Output format:
Output the longest common subsequence of s1 and s2 without virus as a substring. If there are multiple answers, any of them will be accepted.

If there is no valid common subsequence, output 0.

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

Example input:
AJKEQSLOBSROFGZ
OVGURWZLWVLUXTH
OZ

Example output:
ORZ

Example input:
AA
A
A

Example output:
0

Editorial:
Number Transformation II
Contest: Codeforces Round 201 (Div. 1)
Difficulty rating: 2200
Tags: greedy, math

You are given a sequence of positive integers x1, x2, ..., xn and two non-negative integers a and b. Your task is to transform a into b. To do that, you can perform the following moves:

- subtract 1 from the current a;
- subtract a mod xi (1 ≤ i ≤ n) from the current a.

Operation a mod xi means taking the remainder after division of number a by number xi.

Now you want to know the minimum number of moves needed to transform a into b.

Input format:
The first line contains a single integer n (1 ≤  n ≤ 105). The second line contains n space-separated integers x1, x2, ..., xn (2 ≤  xi ≤ 109). The third line contains two integers a and b (0  ≤ b ≤  a ≤ 109, a - b ≤ 106).

Output format:
Print a single integer — the required minimum number of moves needed to transform number a into number b.

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

Example input:
3
3 4 5
30 17

Example output:
6

Example input:
3
5 6 7
1000 200

Example output:
206

Editorial:
Robot Control
Contest: Codeforces Round 201 (Div. 1)
Difficulty rating: 2600
Tags: dp, graphs, shortest paths

The boss of the Company of Robot is a cruel man. His motto is "Move forward Or Die!". And that is exactly what his company's product do. Look at the behavior of the company's robot when it is walking in the directed graph. This behavior has been called "Three Laws of Robotics":

- Law 1. The Robot will destroy itself when it visits a vertex of the graph which it has already visited.
- Law 2. The Robot will destroy itself when it has no way to go (that is when it reaches a vertex whose out-degree is zero).
- Law 3. The Robot will move randomly when it has multiple ways to move (that is when it reach a vertex whose out-degree is more than one). Of course, the robot can move only along the directed edges of the graph.

Can you imagine a robot behaving like that? That's why they are sold at a very low price, just for those who are short of money, including mzry1992, of course. mzry1992 has such a robot, and she wants to move it from vertex s to vertex t in a directed graph safely without self-destruction. Luckily, she can send her robot special orders at each vertex. A special order shows the robot which way to move, if it has multiple ways to move (to prevent random moving of the robot according to Law 3). When the robot reaches vertex t, mzry1992 takes it off the graph immediately. So you can see that, as long as there exists a path from s to t, she can always find a way to reach the goal (whatever the vertex t has the outdegree of zero or not).

Sample 2

However, sending orders is expensive, so your task is to find the minimum number of orders mzry1992 needs to send in the worst case. Please note that mzry1992 can give orders to the robot while it is walking on the graph. Look at the first sample to clarify that part of the problem.

Input format:
The first line contains two integers n (1 ≤ n ≤ 106) — the number of vertices of the graph, and m (1 ≤ m ≤ 106) — the number of edges. Then m lines follow, each with two integers ui and vi (1 ≤ ui, vi ≤ n; vi ≠ ui), these integers denote that there is a directed edge from vertex ui to vertex vi. The last line contains two integers s and t (1 ≤ s, t ≤ n).

It is guaranteed that there are no multiple edges and self-loops.

Output format:
If there is a way to reach a goal, print the required minimum number of orders in the worst case. Otherwise, print -1.

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

Note:
Consider the first test sample. Initially the robot is on vertex 1. So, on the first step the robot can go to vertex 2 or 3. No matter what vertex the robot chooses, mzry1992 must give an order to the robot. This order is to go to vertex 4. If mzry1992 doesn't give an order to the robot at vertex 2 or 3, the robot can choose the "bad" outgoing edge (return to vertex 1) according Law 3. So, the answer is one.

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

Example output:
1

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

Example output:
1

Editorial:
Doodle Jump
Contest: Codeforces Round 201 (Div. 1)
Difficulty rating: 3000
Tags: math, number theory

In Doodle Jump the aim is to guide a four-legged creature called "The Doodler" up a never-ending series of platforms without falling. — Wikipedia.

It is a very popular game and xiaodao likes it very much. One day when playing the game she wondered whether there exists a platform that the doodler couldn't reach due to the limits of its jumping ability. Consider the following problem.

There are n platforms. The height of the x-th (1 ≤ x ≤ n) platform is a·x mod p, where a and p are positive co-prime integers. The maximum possible height of a Doodler's jump is h. That is, it can jump from height h1 to height h2 (h1 < h2) if h2 - h1 ≤ h. Initially, the Doodler is on the ground, the height of which is 0. The question is whether it can reach the highest platform or not.

For example, when a = 7, n = 4, p = 12, h = 2, the heights of the platforms are 7, 2, 9, 4 as in the picture below. With the first jump the Doodler can jump to the platform at height 2, with the second one the Doodler can jump to the platform at height 4, but then it can't jump to any of the higher platforms. So, it can't reach the highest platform.

User xiaodao thought about the problem for a long time but didn't solve it, so she asks you for help. Also, she has a lot of instances of the problem. Your task is solve all of these instances.

Input format:
The first line contains an integer t (1 ≤ t ≤ 104) — the number of problem instances. Each of the next t lines contains four integers a, n, p and h (1 ≤ a ≤ 109, 1 ≤ n < p ≤ 109, 0 ≤ h ≤ 109). It's guaranteed that a and p are co-prime.

Output format:
For each problem instance, if the Doodler can reach the highest platform, output "YES", otherwise output "NO".

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

Example input:
3
7 4 12 2
7 1 9 4
7 4 12 3

Example output:
NO
NO
YES

Editorial:
Shooshuns and Sequence
Contest: Codeforces Round 137 (Div. 2)
Difficulty rating: 1200
Tags: brute force, implementation

One day shooshuns found a sequence of n integers, written on a blackboard. The shooshuns can perform one operation with it, the operation consists of two steps:

1. Find the number that goes k-th in the current sequence and add the same number to the end of the sequence;
2. Delete the first number of the current sequence.

The shooshuns wonder after how many operations all numbers on the board will be the same and whether all numbers will ever be the same.

Input format:
The first line contains two space-separated integers n and k (1 ≤ k ≤ n ≤ 105).

The second line contains n space-separated integers: a1, a2, ..., an (1 ≤ ai ≤ 105) — the sequence that the shooshuns found.

Output format:
Print the minimum number of operations, required for all numbers on the blackboard to become the same. If it is impossible to achieve, print -1.

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

Note:
In the first test case after the first operation the blackboard will have sequence [1, 1, 1]. So, one operation is enough to make all numbers the same. Thus, the answer equals one.

In the second test case the sequence will never consist of the same numbers. It will always contain at least two distinct numbers 3 and 1. Thus, the answer equals -1.

Example input:
3 2
3 1 1

Example output:
1

Example input:
3 1
3 1 1

Example output:
-1

Editorial:
Cosmic Tables
Contest: Codeforces Round 137 (Div. 2)
Difficulty rating: 1300
Tags: data structures, implementation

The Free Meteor Association (FMA) has got a problem: as meteors are moving, the Universal Cosmic Descriptive Humorous Program (UCDHP) needs to add a special module that would analyze this movement.

UCDHP stores some secret information about meteors as an n × m table with integers in its cells. The order of meteors in the Universe is changing. That's why the main UCDHP module receives the following queries:

- The query to swap two table rows;
- The query to swap two table columns;
- The query to obtain a secret number in a particular table cell.

As the main UCDHP module is critical, writing the functional of working with the table has been commissioned to you.

Input format:
The first line contains three space-separated integers n, m and k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 500000) — the number of table columns and rows and the number of queries, correspondingly.

Next n lines contain m space-separated numbers each — the initial state of the table. Each number p in the table is an integer and satisfies the inequality 0 ≤ p ≤ 106.

Next k lines contain queries in the format "si xi yi", where si is one of the characters "с", "r" or "g", and xi, yi are two integers.

- If si = "c", then the current query is the query to swap columns with indexes xi and yi (1 ≤ x, y ≤ m, x ≠ y);
- If si = "r", then the current query is the query to swap rows with indexes xi and yi (1 ≤ x, y ≤ n, x ≠ y);
- If si = "g", then the current query is the query to obtain the number that located in the xi-th row and in the yi-th column (1 ≤ x ≤ n, 1 ≤ y ≤ m).

The table rows are considered to be indexed from top to bottom from 1 to n, and the table columns — from left to right from 1 to m.

Output format:
For each query to obtain a number (si = "g") print the required number. Print the answers to the queries in the order of the queries in the input.

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

Note:
Let's see how the table changes in the second test case.

After the first operation is fulfilled, the table looks like that:

2 1 4

1 3 5

After the second operation is fulfilled, the table looks like that:

1 3 5

2 1 4

So the answer to the third query (the number located in the first row and in the third column) will be 5.

Example input:
3 3 5
1 2 3
4 5 6
7 8 9
g 3 2
r 3 2
c 2 3
g 2 2
g 3 2

Example output:
8
9
6

Example input:
2 3 3
1 2 4
3 1 5
c 2 1
r 1 2
g 1 3

Example output:
5

Editorial: