1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Anti-Sudoku
Contest: Codeforces Round 634 (Div. 3)
Difficulty rating: 1300
Tags: constructive algorithms, implementation

You are given a correct solution of the sudoku puzzle. If you don't know what is the sudoku, you can read about it here.

The picture showing the correct sudoku solution:

Blocks are bordered with bold black color.

Your task is to change at most $$$9$$$ elements of this field (i.e. choose some $$$1 \le i, j \le 9$$$ and change the number at the position $$$(i, j)$$$ to any other number in range $$$[1; 9]$$$) to make it anti-sudoku. The anti-sudoku is the $$$9 \times 9$$$ field, in which:

- Any number in this field is in range $$$[1; 9]$$$;
- each row contains at least two equal elements;
- each column contains at least two equal elements;
- each $$$3 \times 3$$$ block (you can read what is the block in the link above) contains at least two equal elements.

It is guaranteed that the answer exists.

You have to answer $$$t$$$ independent test cases.

Input format:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case consists of $$$9$$$ lines, each line consists of $$$9$$$ characters from $$$1$$$ to $$$9$$$ without any whitespaces — the correct solution of the sudoku puzzle.

Output format:
For each test case, print the answer — the initial field with at most $$$9$$$ changed elements so that the obtained field is anti-sudoku. If there are several solutions, you can print any. It is guaranteed that the answer exists.

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

Example input:
1
154873296
386592714
729641835
863725149
975314628
412968357
631457982
598236471
247189563

Example output:
154873396
336592714
729645835
863725145
979314628
412958357
631457992
998236471
247789563

Editorial:
Well, if we replace all occurrences of the number $$$2$$$ with the number $$$1$$$, then the initial solution will be anti-sudoku. It is easy to see that this replacement will make exactly two copies of $$$1$$$ in every row, column, and block. There are also other correct approaches but I found this one the most pretty.
Elimination
Contest: RCC 2014 Warmup (Div. 2)
Difficulty rating: 1500
Tags: dp, implementation, math

The finalists of the "Russian Code Cup" competition in 2214 will be the participants who win in one of the elimination rounds.

The elimination rounds are divided into main and additional. Each of the main elimination rounds consists of c problems, the winners of the round are the first n people in the rating list. Each of the additional elimination rounds consists of d problems. The winner of the additional round is one person. Besides, k winners of the past finals are invited to the finals without elimination.

As a result of all elimination rounds at least n·m people should go to the finals. You need to organize elimination rounds in such a way, that at least n·m people go to the finals, and the total amount of used problems in all rounds is as small as possible.

Input format:
The first line contains two integers c and d (1 ≤ c, d ≤ 100) — the number of problems in the main and additional rounds, correspondingly. The second line contains two integers n and m (1 ≤ n, m ≤ 100). Finally, the third line contains an integer k (1 ≤ k ≤ 100) — the number of the pre-chosen winners.

Output format:
In the first line, print a single integer — the minimum number of problems the jury needs to prepare.

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

Example input:
1 10
7 2
1

Example output:
2

Example input:
2 2
2 1
2

Example output:
0

Editorial:
Crash
Contest: RCC 2014 Warmup (Div. 2)
Difficulty rating: 1400
Tags: implementation

During the "Russian Code Cup" programming competition, the testing system stores all sent solutions for each participant. We know that many participants use random numbers in their programs and are often sent several solutions with the same source code to check.

Each participant is identified by some unique positive integer k, and each sent solution A is characterized by two numbers: x — the number of different solutions that are sent before the first solution identical to A, and k — the number of the participant, who is the author of the solution. Consequently, all identical solutions have the same x.

It is known that the data in the testing system are stored in the chronological order, that is, if the testing system has a solution with number x (x > 0) of the participant with number k, then the testing system has a solution with number x - 1 of the same participant stored somewhere before.

During the competition the checking system crashed, but then the data of the submissions of all participants have been restored. Now the jury wants to verify that the recovered data is in chronological order. Help the jury to do so.

Input format:
The first line of the input contains an integer n (1 ≤ n ≤ 105) — the number of solutions. Each of the following n lines contains two integers separated by space x and k (0 ≤ x ≤ 105; 1 ≤ k ≤ 105) — the number of previous unique solutions and the identifier of the participant.

Output format:
A single line of the output should contain «YES» if the data is in chronological order, and «NO» otherwise.

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

Example input:
2
0 1
1 1

Example output:
YES

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

Example output:
NO

Editorial:
Football
Contest: RCC 2014 Warmup (Div. 2)
Difficulty rating: 1400
Tags: constructive algorithms, graphs, implementation

One day, at the "Russian Code Cup" event it was decided to play football as an out of competition event. All participants was divided into n teams and played several matches, two teams could not play against each other more than once.

The appointed Judge was the most experienced member — Pavel. But since he was the wisest of all, he soon got bored of the game and fell asleep. Waking up, he discovered that the tournament is over and the teams want to know the results of all the matches.

Pavel didn't want anyone to discover about him sleeping and not keeping an eye on the results, so he decided to recover the results of all games. To do this, he asked all the teams and learned that the real winner was friendship, that is, each team beat the other teams exactly k times. Help Pavel come up with chronology of the tournir that meets all the conditions, or otherwise report that there is no such table.

Input format:
The first line contains two integers — n and k (1 ≤ n, k ≤ 1000).

Output format:
In the first line print an integer m — number of the played games. The following m lines should contain the information about all the matches, one match per line. The i-th line should contain two integers ai and bi (1 ≤ ai, bi ≤ n; ai ≠ bi). The numbers ai and bi mean, that in the i-th match the team with number ai won against the team with number bi. You can assume, that the teams are numbered from 1 to n.

If a tournir that meets the conditions of the problem does not exist, then print -1.

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

Example input:
3 1

Example output:
3
1 2
2 3
3 1

Editorial:
Cunning Gena
Contest: RCC 2014 Warmup (Div. 2)
Difficulty rating: 1900
Tags: bitmasks, dp, greedy, sortings

A boy named Gena really wants to get to the "Russian Code Cup" finals, or at least get a t-shirt. But the offered problems are too complex, so he made an arrangement with his n friends that they will solve the problems for him.

The participants are offered m problems on the contest. For each friend, Gena knows what problems he can solve. But Gena's friends won't agree to help Gena for nothing: the i-th friend asks Gena xi rubles for his help in solving all the problems he can. Also, the friend agreed to write a code for Gena only if Gena's computer is connected to at least ki monitors, each monitor costs b rubles.

Gena is careful with money, so he wants to spend as little money as possible to solve all the problems. Help Gena, tell him how to spend the smallest possible amount of money. Initially, there's no monitors connected to Gena's computer.

Input format:
The first line contains three integers n, m and b (1 ≤ n ≤ 100; 1 ≤ m ≤ 20; 1 ≤ b ≤ 109) — the number of Gena's friends, the number of problems and the cost of a single monitor.

The following 2n lines describe the friends. Lines number 2i and (2i + 1) contain the information about the i-th friend. The 2i-th line contains three integers xi, ki and mi (1 ≤ xi ≤ 109; 1 ≤ ki ≤ 109; 1 ≤ mi ≤ m) — the desired amount of money, monitors and the number of problems the friend can solve. The (2i + 1)-th line contains mi distinct positive integers — the numbers of problems that the i-th friend can solve. The problems are numbered from 1 to m.

Output format:
Print the minimum amount of money Gena needs to spend to solve all the problems. Or print -1, if this cannot be achieved.

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

Example input:
2 2 1
100 1 1
2
100 2 1
1

Example output:
202

Example input:
3 2 5
100 1 1
1
100 1 1
2
200 1 2
1 2

Example output:
205

Editorial:
Square Table
Contest: RCC 2014 Warmup (Div. 2)
Difficulty rating: 2400
Tags: constructive algorithms, math, probabilities

While resting on the ship after the "Russian Code Cup" a boy named Misha invented an interesting game. He promised to give his quadrocopter to whoever will be the first one to make a rectangular table of size n × m, consisting of positive integers such that the sum of the squares of numbers for each row and each column was also a square.

Since checking the correctness of the table manually is difficult, Misha asks you to make each number in the table to not exceed 108.

Input format:
The first line contains two integers n and m (1 ≤ n, m ≤ 100)  — the size of the table.

Output format:
Print the table that meets the condition: n lines containing m integers, separated by spaces. If there are multiple possible answers, you are allowed to print anyone. It is guaranteed that there exists at least one correct answer.

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

Example input:
1 1

Example output:
1

Example input:
1 2

Example output:
3 4

Editorial:
Bear and Poker
Contest: Codeforces Round 318 [RussianCodeCup Thanks-Round] (Div. 1)
Difficulty rating: 1300
Tags: implementation, math, number theory

Limak is an old brown bear. He often plays poker with his friends. Today they went to a casino. There are n players (including Limak himself) and right now all of them have bids on the table. i-th of them has bid with size ai dollars.

Each player can double his bid any number of times and triple his bid any number of times. The casino has a great jackpot for making all bids equal. Is it possible that Limak and his friends will win a jackpot?

Input format:
First line of input contains an integer n (2 ≤ n ≤ 105), the number of players.

The second line contains n integer numbers a1, a2, ..., an (1 ≤ ai ≤ 109) — the bids of players.

Output format:
Print "Yes" (without the quotes) if players can make their bids become equal, or "No" otherwise.

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

Note:
In the first sample test first and third players should double their bids twice, second player should double his bid once and fourth player should both double and triple his bid.

It can be shown that in the second sample test there is no way to make all bids equal.

Example input:
4
75 150 75 50

Example output:
Yes

Example input:
3
100 150 250

Example output:
No

Editorial:
Any positive integer number can be factorized and written as 2a·3b·5c·7e·....
We can multiply given numbers by 2 and 3 so we can increase a and b for them. So we can make all a and b equal by increasing them to the same big value (e.g. 100). But we can't change powers of other prime numbers so they must be equal from the beginning. We can check it by diving all numbers from input by two and by three as many times as possible. Then all of them must be equal.
Alternative solution is to calculate GCD of given numbers. Answer is "YES" iff we can get each number by multiplying GCD by 2 and 3. Otherwise, some number had different power of prime number other than 2 and 3.
Bear and Blocks
Contest: Codeforces Round 318 [RussianCodeCup Thanks-Round] (Div. 1)
Difficulty rating: 1600
Tags: binary search, data structures, dp, math

Limak is a little bear who loves to play. Today he is playing by destroying block towers. He built n towers in a row. The i-th tower is made of hi identical blocks. For clarification see picture for the first sample.

Limak will repeat the following operation till everything is destroyed.

Block is called internal if it has all four neighbors, i.e. it has each side (top, left, down and right) adjacent to other block or to the floor. Otherwise, block is boundary. In one operation Limak destroys all boundary blocks. His paws are very fast and he destroys all those blocks at the same time.

Limak is ready to start. You task is to count how many operations will it take him to destroy all towers.

Input format:
The first line contains single integer n (1 ≤ n ≤ 105).

The second line contains n space-separated integers h1, h2, ..., hn (1 ≤ hi ≤ 109) — sizes of towers.

Output format:
Print the number of operations needed to destroy all towers.

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

Note:
The picture below shows all three operations for the first sample test. Each time boundary blocks are marked with red color.

Example input:
6
2 1 4 6 2 2

Example output:
3

Example input:
7
3 3 3 1 3 3 3

Example output:
2

Editorial:
In one operation the highest block in each tower disappears. So do all blocks above heights of neighbour towers. And all other blocks remain. It means that in one operation all heights change according to formula hi = min(hi - 1, hi - 1, hi + 1) where h0 = hn + 1 = 0. By using this formula two times we get height after two operations: hi = max(0, min(hi - 2, hi - 1 - 1, hi - 2, hi + 1 - 1, hi + 2)) and so on. From now I will omit max(0, ...) part to make it easier to read.
After k operations we get hi = min(Left, Right) where Left = min(hi - j - (k - j)) = min(hi - j + j - k) for $$j \in \{0, 1, \ldots, k\}$$ and Right is defined similarly. hi becomes zero when Left or Right becomes zero. And Left becomes zero when k = min(hi - j + j) - we will find this value for all i. If you are now lost in this editorial, try to draw some test and analyze my formulas with it.
For each i we are looking for min(hi - j + j). We can iterate over i from left to right keeping some variable best:
1) best = max(best, hi) to consider hi - 0
2) best is our answer for i
3) best +  +
We should to the same for Right and take min(Left, Right) for each i. Then final answer is maximum over answers for i.
Bear and Drawing
Contest: Codeforces Round 318 [RussianCodeCup Thanks-Round] (Div. 1)
Difficulty rating: 2300
Tags: constructive algorithms, dfs and similar, trees

Limak is a little bear who learns to draw. People usually start with houses, fences and flowers but why would bears do it? Limak lives in the forest and he decides to draw a tree.

Recall that tree is a connected graph consisting of n vertices and n - 1 edges.

Limak chose a tree with n vertices. He has infinite strip of paper with two parallel rows of dots. Little bear wants to assign vertices of a tree to some n distinct dots on a paper so that edges would intersect only at their endpoints — drawn tree must be planar. Below you can see one of correct drawings for the first sample test.

Is it possible for Limak to draw chosen tree?

Input format:
The first line contains single integer n (1 ≤ n ≤ 105).

Next n - 1 lines contain description of a tree. i-th of them contains two space-separated integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi) denoting an edge between vertices ai and bi. It's guaranteed that given description forms a tree.

Output format:
Print "Yes" (without the quotes) if Limak can draw chosen tree. Otherwise, print "No" (without the quotes).

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

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

Example output:
Yes

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

Example output:
No

Editorial:
Let's consider a tree already drawn on a strip of paper. Let's take first vertex on the left and last vertex on the right (in case of two vertices with the same x, we choose any of them). There is a path between them. Let's forget about vertices not on this path. A path divides a strip into 1D regions.
What can be added to a path? Only simple paths with one edge to a main path. So it can be one of the following structures (Line or Y-letter):
Note that Y-letter can have long legs but its main part can have only one edge.
How check it? TODO
Bear and Cavalry
Contest: Codeforces Round 318 [RussianCodeCup Thanks-Round] (Div. 1)
Difficulty rating: 3000
Tags: data structures, divide and conquer, dp

Would you want to fight against bears riding horses? Me neither.

Limak is a grizzly bear. He is general of the dreadful army of Bearland. The most important part of an army is cavalry of course.

Cavalry of Bearland consists of n warriors and n horses. i-th warrior has strength wi and i-th horse has strength hi. Warrior together with his horse is called a unit. Strength of a unit is equal to multiplied strengths of warrior and horse. Total strength of cavalry is equal to sum of strengths of all n units. Good assignment of warriors and horses makes cavalry truly powerful.

Initially, i-th warrior has i-th horse. You are given q queries. In each query two warriors swap their horses with each other.

General Limak must be ready for every possible situation. What if warriors weren't allowed to ride their own horses? After each query find the maximum possible strength of cavalry if we consider assignments of all warriors to all horses that no warrior is assigned to his own horse (it can be proven that for n ≥ 2 there is always at least one correct assignment).

Note that we can't leave a warrior without a horse.

Input format:
The first line contains two space-separated integers, n and q (2 ≤ n ≤ 30 000, 1 ≤ q ≤ 10 000).

The second line contains n space-separated integers, w1, w2, ..., wn (1 ≤ wi ≤ 106) — strengths of warriors.

The third line contains n space-separated integers, h1, h2, ..., hn (1 ≤ hi ≤ 106) — strengths of horses.

Next q lines describe queries. i-th of them contains two space-separated integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi), indices of warriors who swap their horses with each other.

Output format:
Print q lines with answers to queries. In i-th line print the maximum possible strength of cavalry after first i queries.

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

Note:
Clarification for the first sample:

Warriors: 1 10 100 1000Horses:   3  7  2    5

After first query situation looks like the following:

Warriors: 1 10 100 1000Horses:   3  5  2    7

We can get 1·2 + 10·3 + 100·7 + 1000·5 = 5732 (note that no hussar takes his own horse in this assignment).

After second query we get back to initial situation and optimal assignment is 1·2 + 10·3 + 100·5 + 1000·7 = 7532.

Clarification for the second sample. After first query:

Warriors:  7 11 5Horses:    2  3 1

Optimal assignment is 7·1 + 11·2 + 5·3 = 44.

Then after second query 7·3 + 11·2 + 5·1 = 48.

Finally 7·2 + 11·3 + 5·1 = 52.

Example input:
4 2
1 10 100 1000
3 7 2 5
2 4
2 4

Example output:
5732
7532

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

Example output:
44
48
52

Editorial:
Let's sort warriors and horses. It can be proved that there is an optimal assignment that assign very near (+-2) things. Solution is $${\mathcal{O}}(q\log n)$$ with big constant factor.
Broken Keyboard
Contest: Educational Codeforces Round 75 (Rated for Div. 2)
Difficulty rating: 1000
Tags: brute force, strings, two pointers

Recently Polycarp noticed that some of the buttons of his keyboard are malfunctioning. For simplicity, we assume that Polycarp's keyboard contains $$$26$$$ buttons (one for each letter of the Latin alphabet). Each button is either working fine or malfunctioning.

To check which buttons need replacement, Polycarp pressed some buttons in sequence, and a string $$$s$$$ appeared on the screen. When Polycarp presses a button with character $$$c$$$, one of the following events happened:

- if the button was working correctly, a character $$$c$$$ appeared at the end of the string Polycarp was typing;
- if the button was malfunctioning, two characters $$$c$$$ appeared at the end of the string.

For example, suppose the buttons corresponding to characters a and c are working correctly, and the button corresponding to b is malfunctioning. If Polycarp presses the buttons in the order a, b, a, c, a, b, a, then the string he is typing changes as follows: a $$$\rightarrow$$$ abb $$$\rightarrow$$$ abba $$$\rightarrow$$$ abbac $$$\rightarrow$$$ abbaca $$$\rightarrow$$$ abbacabb $$$\rightarrow$$$ abbacabba.

You are given a string $$$s$$$ which appeared on the screen after Polycarp pressed some buttons. Help Polycarp to determine which buttons are working correctly for sure (that is, this string could not appear on the screen if any of these buttons was malfunctioning).

You may assume that the buttons don't start malfunctioning when Polycarp types the string: each button either works correctly throughout the whole process, or malfunctions throughout the whole process.

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

Then the test cases follow. Each test case is represented by one line containing a string $$$s$$$ consisting of no less than $$$1$$$ and no more than $$$500$$$ lowercase Latin letters.

Output format:
For each test case, print one line containing a string $$$res$$$. The string $$$res$$$ should contain all characters which correspond to buttons that work correctly in alphabetical order, without any separators or repetitions. If all buttons may malfunction, $$$res$$$ should be empty.

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

Example input:
4
a
zzaaz
ccff
cbddbb

Example output:
a
z

bc

Editorial:
If a key malfunctions, each sequence of presses of this key gives a string with even number of characters. So, if there is a substring consisting of odd number of equal characters $$$c$$$, such that it cannot be extended to the left or to the right without adding other characters, then it could not be produced by presses of button $$$c$$$ if $$$c$$$ was malfunctioning.
The only thing that's left is to find all maximal by inclusion substrings consisting of the same character.