1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Little Victor and Set
Contest: Codeforces Round 262 (Div. 2)
Difficulty rating: 2300
Tags: brute force, constructive algorithms, math

Little Victor adores the sets theory. Let us remind you that a set is a group of numbers where all numbers are pairwise distinct. Today Victor wants to find a set of integers S that has the following properties:

- for all x $$( x \in S )$$ the following inequality holds l ≤ x ≤ r;
- 1 ≤ |S| ≤ k;
- lets denote the i-th element of the set S as si; value $$f(S) = s_1 \oplus s_2 \oplus \cdots \oplus s_{|S|}$$ must be as small as possible.

Help Victor find the described set.

Input format:
The first line contains three space-separated integers l, r, k (1 ≤ l ≤ r ≤ 1012; 1 ≤ k ≤ min(106, r - l + 1)).

Output format:
Print the minimum possible value of f(S). Then print the cardinality of set |S|. Then print the elements of the set in any order.

If there are multiple optimal sets, you can print any of them.

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

Note:
Operation $$x \oplus y$$ represents the operation of bitwise exclusive OR. In other words, it is the XOR operation.

Example input:
8 15 3

Example output:
1
2
10 11

Example input:
8 30 7

Example output:
0
5
14 9 28 11 16

Editorial:
Roland and Rose
Contest: Codeforces Round 262 (Div. 2)
Difficulty rating: 2700
Tags: brute force, geometry, math, sortings

Roland loves growing flowers. He has recently grown a beautiful rose at point (0, 0) of the Cartesian coordinate system. The rose is so beautiful that Roland is afraid that the evil forces can try and steal it.

To protect the rose, Roland wants to build n watch towers. Let's assume that a tower is a point on the plane at the distance of at most r from the rose. Besides, Roland assumes that the towers should be built at points with integer coordinates and the sum of squares of distances between all pairs of towers must be as large as possible. Note, that Roland may build several towers at the same point, also he may build some of them at point (0, 0).

Help Roland build the towers at the integer points so that the sum of squares of distances between all towers is maximum possible. Note that the distance in this problem is defined as the Euclidian distance between points.

Input format:
The first line contains two integers, n and r (2 ≤ n ≤ 8; 1 ≤ r ≤ 30).

Output format:
In the first line print an integer — the maximum possible sum of squared distances. In the i-th of the following n lines print two integers, xi, yi — the coordinates of the i-th tower. Each tower must be inside or on the border of the circle with radius r. Note that there may be several towers located at the same point of the plane, also some towers can be located at point (0, 0).

If there are multiple valid optimal arrangements, choose any of them.

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

Example input:
4 1

Example output:
16
0 1
0 1
0 -1
0 -1

Example input:
3 6

Example output:
312
0 6
5 -3
-5 -3

Editorial:
Misha and XOR
Contest: Codeforces Round 285 (Div. 1)
Difficulty rating: 2700
Tags: bitmasks

After Misha's birthday he had many large numbers left, scattered across the room. Now it's time to clean up and Misha needs to put them in a basket. He ordered this task to his pet robot that agreed to complete the task at certain conditions. Before the robot puts a number x to the basket, Misha should answer the question: is it possible to choose one or multiple numbers that already are in the basket, such that their XOR sum equals x?

If the answer is positive, you also need to give the indexes of these numbers. If there are multiple options of choosing numbers, you are allowed to choose any correct option. After Misha's answer the robot puts the number to the basket.

Initially the basket is empty. Each integer you put in the basket takes some number. The first integer you put into the basket take number 0, the second integer takes number 1 and so on.

Misha needs to clean up the place as soon as possible but unfortunately, he isn't that good at mathematics. He asks you to help him.

Input format:
The first line contains number m (1 ≤ m ≤ 2000), showing how many numbers are scattered around the room.

The next m lines contain the numbers in the order in which the robot puts them in the basket. Each number is a positive integer strictly less than 10600 that doesn't contain leading zeroes.

Output format:
For each number either print a 0 on the corresponding line, if the number cannot be represented as a XOR sum of numbers that are in the basket, or print integer k showing how many numbers are in the representation and the indexes of these numbers. Separate the numbers by spaces. Each number can occur in the representation at most once.

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

Note:
The XOR sum of numbers is the result of bitwise sum of numbers modulo 2.

Example input:
7
7
6
5
4
3
2
1

Example output:
0
0
0
3 0 1 2
2 1 2
2 0 2
2 0 1

Example input:
2
5
5

Example output:
0
1 0

Editorial:
Misha and LCP on Tree
Contest: Codeforces Round 285 (Div. 1)
Difficulty rating: 3000
Tags: binary search, dfs and similar, hashing, string suffix structures, trees

Misha has a tree with characters written on the vertices. He can choose two vertices s and t of this tree and write down characters of vertices lying on a path from s to t. We'll say that such string corresponds to pair (s, t).

Misha has m queries of type: you are given 4 vertices a, b, c, d; you need to find the largest common prefix of the strings that correspond to pairs (a, b) and (c, d). Your task is to help him.

Input format:
The first line contains integer n (1 ≤ n ≤ 300 000) — the number of vertices in the tree.

Next follows a line consisting of n small English letters. The i-th character of the string corresponds to the character written on the i-th vertex.

Next n - 1 lines contain information about edges. An edge is defined by a pair of integers u, v (1 ≤ u, v ≤ n, u ≠ v), separated by spaces.

The next line contains integer m (1 ≤ m ≤ 1 000 000) — the number of queries.

Next m lines contain information about queries. A query is defined by four integers a, b, c, d (1 ≤ a, b, c, d ≤ n), separated by spaces.

Output format:
For each query print the length of the largest common prefix on a separate line.

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

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

Example output:
2
2
2
0
1
0

Editorial:
Reorder the Array
Contest: Codeforces Round 497 (Div. 1)
Difficulty rating: 1300
Tags: combinatorics, data structures, math, sortings, two pointers

You are given an array of integers. Vasya can permute (change order) its integers. He wants to do it so that as many as possible integers will become on a place where a smaller integer used to stand. Help Vasya find the maximal number of such integers.

For instance, if we are given an array $$$[10, 20, 30, 40]$$$, we can permute it so that it becomes $$$[20, 40, 10, 30]$$$. Then on the first and the second positions the integers became larger ($$$20>10$$$, $$$40>20$$$) and did not on the third and the fourth, so for this permutation, the number that Vasya wants to maximize equals $$$2$$$. Read the note for the first example, there is one more demonstrative test case.

Help Vasya to permute integers in such way that the number of positions in a new array, where integers are greater than in the original one, is maximal.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the length of the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the elements of the array.

Output format:
Print a single integer — the maximal number of the array's elements which after a permutation will stand on the position where a smaller element stood in the initial array.

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

Note:
In the first sample, one of the best permutations is $$$[1, 5, 5, 3, 10, 1, 1]$$$. On the positions from second to fifth the elements became larger, so the answer for this permutation is 4.

In the second sample, there is no way to increase any element with a permutation, so the answer is 0.

Example input:
7
10 1 1 1 5 5 3

Example output:
4

Example input:
5
1 1 1 1 1

Example output:
0

Editorial:
The answer is $$$n$$$ minus maximal number of equal elements.
Let the maximal number of equals be $$$x$$$. Let's proove that $$$n-x$$$ is reachable. It's clear that for every permutation of the array the answer will be the same, so let's sort the array in non-decreasing order. Now we should just make a left shift on $$$x$$$. After it the $$$n-x$$$ right elements will move to a position of a smaller element.
Now let's proove that the answer is no more than $$$n-x$$$. Let's consider some permutation. It's known that every permutation breaks into cycles. Let's look at two occurences of the same number in the same cycle. Then there is at least one number between them which will move on a postion of a non-smaller element. Even if it the same occurence and even if the length of the cycle is $$$1$$$, we can say that for every occurence of this number there is at least one number which moves on a postion of a non-smaller one. So if some number occurs $$$x$$$ times, there are at least $$$x$$$ bad positions and therefore no more than $$$n-x$$$ good positions.
To count the number of equals you can, for instance, use std::map.