1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Find the Different Ones!
Contest: Codeforces Round 923 (Div. 3)
Difficulty rating: 1300
Tags: binary search, brute force, data structures, dp, dsu, greedy, two pointers

You are given an array $$$a$$$ of $$$n$$$ integers, and $$$q$$$ queries.

Each query is represented by two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$). Your task is to find, for each query, two indices $$$i$$$ and $$$j$$$ (or determine that they do not exist) such that:

- $$$l \le i \le r$$$;
- $$$l \le j \le r$$$;
- $$$a_i \ne a_j$$$.

In other words, for each query, you need to find a pair of different elements among $$$a_l, a_{l+1}, \dots, a_r$$$, or report that such a pair does not exist.

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — the elements of the array $$$a$$$.

The third line of each test case contains a single integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries.

The next $$$q$$$ lines contain two integers each, $$$l$$$ and $$$r$$$ ($$$1 \le l < r \le n$$$) — the boundaries of the query.

It is guaranteed that the sum of the values of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$. Similarly, it is guaranteed that the sum of the values of $$$q$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each query, output two integers separated by space: $$$i$$$ and $$$j$$$ ($$$l \le i, j \le r$$$), for which $$$a_i \ne a_j$$$. If such a pair does not exist, output $$$i=-1$$$ and $$$j=-1$$$.

You may separate the outputs for the test cases with empty lines. This is not a mandatory requirement.

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

Example input:
5
5
1 1 2 1 1
3
1 5
1 2
1 3
6
30 20 20 10 10 20
5
1 2
2 3
2 4
2 6
3 5
4
5 2 3 4
4
1 2
1 4
2 3
2 4
5
1 4 3 2 4
5
1 5
2 4
3 4
3 5
4 5
5
2 3 1 4 2
7
1 2
1 4
1 5
2 4
2 5
3 5
4 5

Example output:
2 3
-1 -1
1 3

2 1
-1 -1
4 2
4 6
5 3

1 2
1 2
2 3
3 2

1 3
2 4
3 4
5 3
5 4

1 2
4 2
1 3
2 3
3 2
5 4
5 4

Editorial:
Before processing the requests, let's calculate the position $$$p_i$$$ of the nearest element to the left that is not equal to it (we will consider $$$p_1 = -1$$$). To do this in linear time, we will traverse the array from left to right. For the $$$i$$$-th element ($$$1 < i \le n$$$), if $$$a_i \ne a_{i - 1}$$$, then $$$p_i=i-1$$$, otherwise $$$p_i=p_{i-1}$$$ (all elements between $$$p_{i - 1}$$$ and $$$i$$$ will be equal to $$$a_i$$$ by construction).
To answer a query, we will fix the right boundary as one of the positions for the answer. Then the best of all suitable positions for it is $$$p_r$$$, as it is the maximum, and we just need to check that $$$l \le p_r$$$. (Note that by fixing any other position, you may not find the answer for a segment of the form $$$[1, 1, 1, \dots, 1, 2]$$$)
Klever Permutation
Contest: Codeforces Round 923 (Div. 3)
Difficulty rating: 1400
Tags: constructive algorithms, math, two pointers

You are given two integers $$$n$$$ and $$$k$$$ ($$$k \le n$$$), where $$$k$$$ is even.

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

Your task is to construct a $$$k$$$-level permutation of length $$$n$$$.

A permutation is called $$$k$$$-level if, among all the sums of continuous segments of length $$$k$$$ (of which there are exactly $$$n - k + 1$$$), any two sums differ by no more than $$$1$$$.

More formally, to determine if the permutation $$$p$$$ is $$$k$$$-level, first construct an array $$$s$$$ of length $$$n - k + 1$$$, where $$$s_i=\sum_{j=i}^{i+k-1} p_j$$$, i.e., the $$$i$$$-th element is equal to the sum of $$$p_i, p_{i+1}, \dots, p_{i+k-1}$$$.

A permutation is called $$$k$$$-level if $$$\max(s) - \min(s) \le 1$$$.

Find any $$$k$$$-level permutation of length $$$n$$$.

Input format:
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. This is followed by the description of the test cases.

The first and only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le k \le n \le 2 \cdot 10^5$$$, $$$k$$$ is even), where $$$n$$$ is the length of the desired permutation.

It is guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output any $$$k$$$-level permutation of length $$$n$$$.

It is guaranteed that such a permutation always exists given the constraints.

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

Note:
In the second test case of the example:

- $$$p_1 + p_2 = 3 + 1 = 4$$$;
- $$$p_2 + p_3 = 1 + 2 = 3$$$.

Example input:
5
2 2
3 2
10 4
13 4
7 4

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

Editorial:
To construct a permutation, let's make an important observation: $$$s_i$$$ cannot be equal to $$$s_{i + 1}$$$ (i.e., they differ by at least $$$1$$$). Since the array $$$s$$$ can only contain two different values, it always has the form $$$[x, x+1, x, x+1, \dots]$$$ or $$$[x, x-1, x, x-1, \dots]$$$.
Let's construct a permutation of the first form.
• Since $$$s_1 + 1 = s_2$$$, then $$$a_1 + 1=a_{k+1}$$$;
• since $$$s_2 = s_3 + 1$$$, then $$$a_2 = a_{k+2} + 1$$$;
• since $$$s_3 + 1 = s_4$$$, then $$$a_3 + 1 = a_{k+3}$$$;
• $$$\dotsi$$$
• since $$$s_k = s_{k + 1} + 1$$$, then $$$a_k = a_{k+k} + 1$$$;
• $$$\dotsi$$$
Thus, for all odd positions $$$i$$$, it must hold that $$$a_i + 1 = a_{i + k}$$$, and for even positions, $$$a_i = a_{i + k} + 1$$$. To construct such a permutation, we will iterate through all positions $$$i$$$ from $$$1$$$ to $$$k$$$ and fill the permutation in positions $$$i, i+k, i+2\cdot k, \dots$$$.
Microcycle
Contest: Codeforces Round 923 (Div. 3)
Difficulty rating: 1900
Tags: data structures, dfs and similar, dsu, graphs, greedy, implementation, sortings, trees

Given an undirected weighted graph with $$$n$$$ vertices and $$$m$$$ edges. There is at most one edge between each pair of vertices in the graph, and the graph does not contain loops (edges from a vertex to itself). The graph is not necessarily connected.

A cycle in the graph is called simple if it doesn't pass through the same vertex twice and doesn't contain the same edge twice.

Find any simple cycle in this graph in which the weight of the lightest edge is minimal.

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$3 \le n \le m \le \min(\frac{n\cdot(n - 1)}{2}, 2 \cdot 10^5)$$$) — the size of the graph and the number of edges.

The next $$$m$$$ lines of the test case contain three integers $$$u$$$, $$$v$$$, and $$$w$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$, $$$1 \le w \le 10^6$$$) — vertices $$$u$$$ and $$$v$$$ are connected by an edge of weight $$$w$$$.

It is guaranteed that there is at most one edge between each pair of vertices. Note that under the given constraints, there is always at least one simple cycle in the graph.

It is guaranteed that the sum of the values of $$$m$$$ for all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a pair of numbers $$$b$$$ and $$$k$$$, where:

- $$$b$$$ — the minimum weight of the edge in the found cycle,
- $$$k$$$ — the number of vertices in the found cycle.

On the next line, output $$$k$$$ numbers from $$$1$$$ to $$$n$$$  — the vertices of the cycle in traversal order.

Note that the answer always exists, as under the given constraints, there is always at least one simple cycle in the graph.

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

Example input:
5
6 6
1 2 1
2 3 1
3 1 1
4 5 1
5 6 1
6 4 1
6 6
1 2 10
2 3 8
3 1 5
4 5 100
5 6 40
6 4 3
6 15
1 2 4
5 2 8
6 1 7
6 3 10
6 5 1
3 2 8
4 3 4
5 3 6
2 6 6
5 4 5
4 1 3
6 4 5
4 2 1
3 1 7
1 5 5
4 6
2 3 2
1 3 10
1 4 1
3 4 7
2 4 5
1 2 2
4 5
2 1 10
3 1 3
4 2 6
1 4 7
2 3 3

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

Editorial:
Let's use the disjoint sets union (DSU). We will add edges to the DSU in descending order of weight. At the same time, we will build a graph containing only the edges that, when added to the DSU, unite different sets. We will also remember the last edge that we did not add to the graph, as it will be the lightest edge of the desired cycle. To find the cycle itself, we will find a path in the constructed graph leading from one end of this edge to the other (due to the construction of the graph, it does not contain cycles, so we need to find a path in the tree).
A Good Contest
Contest: Codeforces Round 357 (Div. 2)
Difficulty rating: 800
Tags: implementation

Codeforces user' handle color depends on his rating — it is red if his rating is greater or equal to 2400; it is orange if his rating is less than 2400 but greater or equal to 2200, etc. Each time participant takes part in a rated contest, his rating is changed depending on his performance.

Anton wants the color of his handle to become red. He considers his performance in the rated contest to be good if he outscored some participant, whose handle was colored red before the contest and his rating has increased after it.

Anton has written a program that analyses contest results and determines whether he performed good or not. Are you able to do the same?

Input format:
The first line of the input contains a single integer n (1 ≤ n ≤ 100) — the number of participants Anton has outscored in this contest .

The next n lines describe participants results: the i-th of them consists of a participant handle namei and two integers beforei and afteri ( - 4000 ≤ beforei, afteri ≤ 4000) — participant's rating before and after the contest, respectively. Each handle is a non-empty string, consisting of no more than 10 characters, which might be lowercase and uppercase English letters, digits, characters «_» and «-» characters.

It is guaranteed that all handles are distinct.

Output format:
Print «YES» (quotes for clarity), if Anton has performed good in the contest and «NO» (quotes for clarity) otherwise.

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

Note:
In the first sample, Anton has outscored user with handle Burunduk1, whose handle was colored red before the contest and his rating has increased after the contest.

In the second sample, Applejack's rating has not increased after the contest, while both Fluttershy's and Pinkie_Pie's handles were not colored red before the contest.

Example input:
3
Burunduk1 2526 2537
BudAlNik 2084 2214
subscriber 2833 2749

Example output:
YES

Example input:
3
Applejack 2400 2400
Fluttershy 2390 2431
Pinkie_Pie -2500 -2450

Example output:
NO

Editorial:
Economy Game
Contest: Codeforces Round 357 (Div. 2)
Difficulty rating: 1300
Tags: brute force

Kolya is developing an economy simulator game. His most favourite part of the development process is in-game testing. Once he was entertained by the testing so much, that he found out his game-coin score become equal to 0.

Kolya remembers that at the beginning of the game his game-coin score was equal to n and that he have bought only some houses (for 1 234 567 game-coins each), cars (for 123 456 game-coins each) and computers (for 1 234 game-coins each).

Kolya is now interested, whether he could have spent all of his initial n game-coins buying only houses, cars and computers or there is a bug in the game. Formally, is there a triple of non-negative integers a, b and c such that a × 1 234 567 + b × 123 456 + c × 1 234 = n?

Please help Kolya answer this question.

Input format:
The first line of the input contains a single integer n (1 ≤ n ≤ 109) — Kolya's initial game-coin score.

Output format:
Print "YES" (without quotes) if it's possible that Kolya spent all of his initial n coins buying only houses, cars and computers. Otherwise print "NO" (without quotes).

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

Note:
In the first sample, one of the possible solutions is to buy one house, one car and one computer, spending 1 234 567 + 123 456 + 1234 = 1 359 257 game-coins in total.

Example input:
1359257

Example output:
YES

Example input:
17851817

Example output:
NO

Editorial:
Runaway to a Shadow
Contest: Codeforces Round 357 (Div. 2)
Difficulty rating: 2500
Tags: geometry, sortings

Dima is living in a dormitory, as well as some cockroaches.

At the moment 0 Dima saw a cockroach running on a table and decided to kill it. Dima needs exactly T seconds for aiming, and after that he will precisely strike the cockroach and finish it.

To survive the cockroach has to run into a shadow, cast by round plates standing on the table, in T seconds. Shadow casted by any of the plates has the shape of a circle. Shadow circles may intersect, nest or overlap arbitrarily.

The cockroach uses the following strategy: first he equiprobably picks a direction to run towards and then runs towards it with the constant speed v. If at some moment t ≤ T it reaches any shadow circle, it immediately stops in the shadow and thus will stay alive. Otherwise the cockroach is killed by the Dima's precise strike. Consider that the Dima's precise strike is instant.

Determine the probability of that the cockroach will stay alive.

Input format:
In the first line of the input the four integers x0, y0, v, T (|x0|, |y0| ≤ 109, 0 ≤ v, T ≤ 109) are given — the cockroach initial position on the table in the Cartesian system at the moment 0, the cockroach's constant speed and the time in seconds Dima needs for aiming respectively.

In the next line the only number n (1 ≤ n ≤ 100 000) is given — the number of shadow circles casted by plates.

In the next n lines shadow circle description is given: the ith of them consists of three integers xi, yi, ri (|xi|, |yi| ≤ 109, 0 ≤ r ≤ 109) — the ith shadow circle on-table position in the Cartesian system and its radius respectively.

Consider that the table is big enough for the cockroach not to run to the table edges and avoid Dima's precise strike.

Output format:
Print the only real number p — the probability of that the cockroach will stay alive.

Your answer will be considered correct if its absolute or relative error does not exceed 10 - 4.

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

Note:
The picture for the first sample is given below.

Red color stands for points which being chosen as the cockroach's running direction will cause him being killed, green color for those standing for survival directions. Please note that despite containing a circle centered in ( - 2, 2) a part of zone is colored red because the cockroach is not able to reach it in one second.

Example input:
0 0 1 1
3
1 1 1
-1 -1 1
-2 2 1

Example output:
0.50000000000

Example input:
0 0 1 0
1
1 0 1

Example output:
1.00000000000

Editorial:
Key races
Contest: Codeforces Round 427 (Div. 2)
Difficulty rating: 800
Tags: math

Two boys decided to compete in text typing on the site "Key races". During the competition, they have to type a text consisting of s characters. The first participant types one character in v1 milliseconds and has ping t1 milliseconds. The second participant types one character in v2 milliseconds and has ping t2 milliseconds.

If connection ping (delay) is t milliseconds, the competition passes for a participant as follows:

1. Exactly after t milliseconds after the start of the competition the participant receives the text to be entered.
2. Right after that he starts to type it.
3. Exactly t milliseconds after he ends typing all the text, the site receives information about it.

The winner is the participant whose information on the success comes earlier. If the information comes from both participants at the same time, it is considered that there is a draw.

Given the length of the text and the information about participants, determine the result of the game.

Input format:
The first line contains five integers s, v1, v2, t1, t2 (1 ≤ s, v1, v2, t1, t2 ≤ 1000) — the number of characters in the text, the time of typing one character for the first participant, the time of typing one character for the the second participant, the ping of the first participant and the ping of the second participant.

Output format:
If the first participant wins, print "First". If the second participant wins, print "Second". In case of a draw print "Friendship".

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

Note:
In the first example, information on the success of the first participant comes in 7 milliseconds, of the second participant — in 14 milliseconds. So, the first wins.

In the second example, information on the success of the first participant comes in 11 milliseconds, of the second participant — in 5 milliseconds. So, the second wins.

In the third example, information on the success of the first participant comes in 22 milliseconds, of the second participant — in 22 milliseconds. So, it is be a draw.

Example input:
5 1 2 1 2

Example output:
First

Example input:
3 3 1 1 1

Example output:
Second

Editorial:
Information on the success of the first participant will come in 2·t1 + v1·s milliseconds, of the second participant — in 2·t2 + v2·s milliseconds. We need to compare these numbers and print the answer depending on the comparison result.
The number on the board
Contest: Codeforces Round 427 (Div. 2)
Difficulty rating: 1100
Tags: greedy

Some natural number was written on the board. Its sum of digits was not less than k. But you were distracted a bit, and someone changed this number to n, replacing some digits with others. It's known that the length of the number didn't change.

You have to find the minimum number of digits in which these two numbers can differ.

Input format:
The first line contains integer k (1 ≤ k ≤ 109).

The second line contains integer n (1 ≤ n < 10100000).

There are no leading zeros in n. It's guaranteed that this situation is possible.

Output format:
Print the minimum number of digits in which the initial number and n can differ.

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

Note:
In the first example, the initial number could be 12.

In the second example the sum of the digits of n is not less than k. The initial number could be equal to n.

Example input:
3
11

Example output:
1

Example input:
3
99

Example output:
0

Editorial:
Let's rephrase the problem a little. Suppose that we initially have a number n and we need to make a number from it with the sum of digits at least k, changing as fewer digits as possible.
Obviously, it is optimal to replace the digit with 9. When we replace digit d with 9, we increase the sum by 9 - d. It means it's optimal to replace the minimal digit.
Let cnti be the number of occurrences of the digit i in n. While the sum is less than k we will repeat this
• Find minimal i that cnti > 0.
• Decrease cnti by 1.
• Increase the answer by 1.
• Increase the sum by 9 - i
It's not hard to prove, that algorithm makes as less replaces as possible.
Alogithm works in $$O(\log_{10} n)$$ time and O(1) additional memory.
Palindromic characteristics
Contest: Codeforces Round 427 (Div. 2)
Difficulty rating: 1900
Tags: brute force, dp, hashing, strings

Palindromic characteristics of string s with length |s| is a sequence of |s| integers, where k-th number is the total number of non-empty substrings of s which are k-palindromes.

A string is 1-palindrome if and only if it reads the same backward as forward.

A string is k-palindrome (k > 1) if and only if:

1. Its left half equals to its right half.
2. Its left and right halfs are non-empty (k - 1)-palindromes.

The left half of string t is its prefix of length ⌊|t| / 2⌋, and right half — the suffix of the same length. ⌊|t| / 2⌋ denotes the length of string t divided by 2, rounded down.

Note that each substring is counted as many times as it appears in the string. For example, in the string "aaa" the substring "a" appears 3 times.

Input format:
The first line contains the string s (1 ≤ |s| ≤ 5000) consisting of lowercase English letters.

Output format:
Print |s| integers — palindromic characteristics of string s.

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

Note:
In the first example 1-palindromes are substring «a», «b», «b», «a», «bb», «abba», the substring «bb» is 2-palindrome. There are no 3- and 4-palindromes here.

Example input:
abba

Example output:
6 1 0 0

Example input:
abacaba

Example output:
12 4 1 0 0 0 0

Editorial:
Observation I.
If the string is k-palindrome, then it is (k - 1)-palindrome.
Observation II.
The string is k-palindrome if and only if the both following conditions are true:
1. It is a palindrome.
2. It's left half is non-empty (k - 1)-palindrome.
Solution.
Let's calculate the following dp.
• dp[l][r] is the maximum k such that the substring built from characters from l to r is k-palindrome.
• The dynamics is calculated in the order of non-decreasing of substring lengths.
• The values for l = r and l = r - 1 are computed trivially.
• Let r - l > 1. Then, if s[l] ≠ s[r] or dp[l + 1][r - 1] = 0, dp[l][r] = 0. Otherwise dp[l][r] = dp[l][m] + 1, where $$m = \left\lceil \frac{l + r}{2} \right\rceil - 1$$.
When we have dp values, we can calculate cnt[k] — the number of substrings, which dp value is k. Then the number of substrings that are k-palindromes is $$$$.
The solution works in O(|s|2) time and uses O(|s|2) memory.
Also, you could notice that the string can be no more than $$\left\lfloor \log _ { 2 } | s | \right\rfloor$$-palindrome, and solve the problem in $$O(|s|^2 \log |s|)$$ time, reducing the memory usage to O(|s|).
Jzzhu and Chocolate
Contest: Codeforces Round 257 (Div. 1)
Difficulty rating: 1700
Tags: greedy, math

Jzzhu has a big rectangular chocolate bar that consists of n × m unit squares. He wants to cut this bar exactly k times. Each cut must meet the following requirements:

- each cut should be straight (horizontal or vertical);
- each cut should go along edges of unit squares (it is prohibited to divide any unit chocolate square with cut);
- each cut should go inside the whole chocolate bar, and all cuts must be distinct.

The picture below shows a possible way to cut a 5 × 6 chocolate for 5 times.

Imagine Jzzhu have made k cuts and the big chocolate is splitted into several pieces. Consider the smallest (by area) piece of the chocolate, Jzzhu wants this piece to be as large as possible. What is the maximum possible area of smallest piece he can get with exactly k cuts? The area of a chocolate piece is the number of unit squares in it.

Input format:
A single line contains three integers n, m, k (1 ≤ n, m ≤ 109; 1 ≤ k ≤ 2·109).

Output format:
Output a single integer representing the answer. If it is impossible to cut the big chocolate k times, print -1.

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

Note:
In the first sample, Jzzhu can cut the chocolate following the picture below:

In the second sample the optimal division looks like this:

In the third sample, it's impossible to cut a 2 × 3 chocolate 4 times.

Example input:
3 4 1

Example output:
6

Example input:
6 4 2

Example output:
8

Editorial: