1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Present
Contest: Codeforces Round 626 (Div. 1, based on Moscow Open Olympiad in Informatics)
Difficulty rating: 2100
Tags: binary search, bitmasks, constructive algorithms, data structures, math, sortings

Catherine received an array of integers as a gift for March 8. Eventually she grew bored with it, and she started calculated various useless characteristics for it. She succeeded to do it for each one she came up with. But when she came up with another one — xor of all pairwise sums of elements in the array, she realized that she couldn't compute it for a very large array, thus she asked for your help. Can you do it? Formally, you need to compute

$$$$$$ (a_1 + a_2) \oplus (a_1 + a_3) \oplus \ldots \oplus (a_1 + a_n) \\ \oplus (a_2 + a_3) \oplus \ldots \oplus (a_2 + a_n) \\ \ldots \\ \oplus (a_{n-1} + a_n) \\ $$$$$$

Here $$$x \oplus y$$$ is a bitwise XOR operation (i.e. $$$x$$$ ^ $$$y$$$ in many modern programming languages). You can read about it in Wikipedia: https://en.wikipedia.org/wiki/Exclusive_or#Bitwise_operation.

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 400\,000$$$) — the number of integers in the array.

The second line contains integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^7$$$).

Output format:
Print a single integer — xor of all pairwise sums of integers in the given array.

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

Note:
In the first sample case there is only one sum $$$1 + 2 = 3$$$.

In the second sample case there are three sums: $$$1 + 2 = 3$$$, $$$1 + 3 = 4$$$, $$$2 + 3 = 5$$$. In binary they are represented as $$$011_2 \oplus 100_2 \oplus 101_2 = 010_2$$$, thus the answer is 2.

$$$\oplus$$$ is the bitwise xor operation. To define $$$x \oplus y$$$, consider binary representations of integers $$$x$$$ and $$$y$$$. We put the $$$i$$$-th bit of the result to be 1 when exactly one of the $$$i$$$-th bits of $$$x$$$ and $$$y$$$ is 1. Otherwise, the $$$i$$$-th bit of the result is put to be 0. For example, $$$0101_2 \, \oplus \, 0011_2 = 0110_2$$$.

Example input:
2
1 2

Example output:
3

Example input:
3
1 2 3

Example output:
2

Editorial:
Let's calculate each bit in the answer separately. Suppose we want to know the value of $$$k$$$-th (in 0-indexation) bit in the answer. Then we can notice that we are only interested in bits from $$$0$$$-th to $$$k$$$-th, which means that we can take all numbers modulo $$$2^{k+1}$$$. After that, the sum of the two numbers can't exceed $$$2^{k+2} - 2$$$. $$$k$$$-th bit is 1 if and only if sum belongs to $$$[2^k; 2^{k+1})$$$ or $$$[2^{k+1} + 2^k; 2^{k+2} - 2]$$$.
So, we have to count the number of pairs of numbers that give a sum that belongs to these segments. Let's sort all numbers (taken by modulo) and make a pass with two pointers or do binary searches for each number.
Total complexity: $$$O(n \log n \log C)$$$
Bonus: can you do it in $$$O(n \log C)$$$?
Inna and Choose Options
Contest: Codeforces Round 234 (Div. 2)
Difficulty rating: 1000
Tags: implementation

There always is something to choose from! And now, instead of "Noughts and Crosses", Inna choose a very unusual upgrade of this game. The rules of the game are given below:

There is one person playing the game. Before the beginning of the game he puts 12 cards in a row on the table. Each card contains a character: "X" or "O". Then the player chooses two positive integers a and b (a·b = 12), after that he makes a table of size a × b from the cards he put on the table as follows: the first b cards form the first row of the table, the second b cards form the second row of the table and so on, the last b cards form the last (number a) row of the table. The player wins if some column of the table contain characters "X" on all cards. Otherwise, the player loses.

Inna has already put 12 cards on the table in a row. But unfortunately, she doesn't know what numbers a and b to choose. Help her win the game: print to her all the possible ways of numbers a, b that she can choose and win.

Input format:
The first line of the input contains integer t (1 ≤ t ≤ 100). This value shows the number of sets of test data in the input. Next follows the description of each of the t tests on a separate line.

The description of each test is a string consisting of 12 characters, each character is either "X", or "O". The i-th character of the string shows the character that is written on the i-th card from the start.

Output format:
For each test, print the answer to the test on a single line. The first number in the line must represent the number of distinct ways to choose the pair a, b. Next, print on this line the pairs in the format axb. Print the pairs in the order of increasing first parameter (a). Separate the pairs in the line by whitespaces.

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

Example input:
4
OXXXOXOOXOOX
OXOXOXOXOXOX
XXXXXXXXXXXX
OOOOOOOOOOOO

Example output:
3 1x12 2x6 4x3
4 1x12 2x6 3x4 6x2
6 1x12 2x6 3x4 4x3 6x2 12x1
0

Editorial:
Inna and New Matrix of Candies
Contest: Codeforces Round 234 (Div. 2)
Difficulty rating: 1200
Tags: brute force, implementation, schedules

Inna likes sweets and a game called the "Candy Matrix". Today, she came up with the new game "Candy Matrix 2: Reload".

The field for the new game is a rectangle table of size n × m. Each line of the table contains one cell with a dwarf figurine, one cell with a candy, the other cells of the line are empty. The game lasts for several moves. During each move the player should choose all lines of the matrix where dwarf is not on the cell with candy and shout "Let's go!". After that, all the dwarves from the chosen lines start to simultaneously move to the right. During each second, each dwarf goes to the adjacent cell that is located to the right of its current cell. The movement continues until one of the following events occurs:

- some dwarf in one of the chosen lines is located in the rightmost cell of his row;
- some dwarf in the chosen lines is located in the cell with the candy.

The point of the game is to transport all the dwarves to the candy cells.

Inna is fabulous, as she came up with such an interesting game. But what about you? Your task is to play this game optimally well. Specifically, you should say by the given game field what minimum number of moves the player needs to reach the goal of the game.

Input format:
The first line of the input contains two integers n and m (1 ≤ n ≤ 1000; 2 ≤ m ≤ 1000).

Next n lines each contain m characters — the game field for the "Candy Martix 2: Reload". Character "*" represents an empty cell of the field, character "G" represents a dwarf and character "S" represents a candy. The matrix doesn't contain other characters. It is guaranteed that each line contains exactly one character "G" and one character "S".

Output format:
In a single line print a single integer — either the minimum number of moves needed to achieve the aim of the game, or -1, if the aim cannot be achieved on the given game field.

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

Example input:
3 4
*G*S
G**S
*G*S

Example output:
2

Example input:
1 3
S*G

Example output:
-1

Editorial:
Inna and Huge Candy Matrix
Contest: Codeforces Round 234 (Div. 2)
Difficulty rating: 1500
Tags: implementation, math

Inna and Dima decided to surprise Sereja. They brought a really huge candy matrix, it's big even for Sereja! Let's number the rows of the giant matrix from 1 to n from top to bottom and the columns — from 1 to m, from left to right. We'll represent the cell on the intersection of the i-th row and j-th column as (i, j). Just as is expected, some cells of the giant candy matrix contain candies. Overall the matrix has p candies: the k-th candy is at cell (xk, yk).

The time moved closer to dinner and Inna was already going to eat p of her favourite sweets from the matrix, when suddenly Sereja (for the reason he didn't share with anyone) rotated the matrix x times clockwise by 90 degrees. Then he performed the horizontal rotate of the matrix y times. And then he rotated the matrix z times counterclockwise by 90 degrees. The figure below shows how the rotates of the matrix looks like.

Inna got really upset, but Duma suddenly understood two things: the candies didn't get damaged and he remembered which cells contained Inna's favourite sweets before Sereja's strange actions. Help guys to find the new coordinates in the candy matrix after the transformation Sereja made!

Input format:
The first line of the input contains fix integers n, m, x, y, z, p (1 ≤ n, m ≤ 109; 0 ≤ x, y, z ≤ 109; 1 ≤ p ≤ 105).

Each of the following p lines contains two integers xk, yk (1 ≤ xk ≤ n; 1 ≤ yk ≤ m) — the initial coordinates of the k-th candy. Two candies can lie on the same cell.

Output format:
For each of the p candies, print on a single line its space-separated new coordinates.

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

Note:
Just for clarity. Horizontal rotating is like a mirroring of the matrix. For matrix:

Example input:
3 3 3 1 1 9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

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

Editorial:
Dima and Bacteria
Contest: Codeforces Round 234 (Div. 2)
Difficulty rating: 2000
Tags: dsu, graphs, shortest paths

Dima took up the biology of bacteria, as a result of his experiments, he invented k types of bacteria. Overall, there are n bacteria at his laboratory right now, and the number of bacteria of type i equals ci. For convenience, we will assume that all the bacteria are numbered from 1 to n. The bacteria of type ci are numbered from $$(\sum_{k=1}^{i-1} c_k) + 1$$ to $$\sum_{k=1}^{i} c_k$$.

With the help of special equipment Dima can move energy from some bacteria into some other one. Of course, the use of such equipment is not free. Dima knows m ways to move energy from some bacteria to another one. The way with number i can be described with integers ui, vi and xi mean that this way allows moving energy from bacteria with number ui to bacteria with number vi or vice versa for xi dollars.

Dima's Chef (Inna) calls the type-distribution correct if there is a way (may be non-direct) to move energy from any bacteria of the particular type to any other bacteria of the same type (between any two bacteria of the same type) for zero cost.

As for correct type-distribution the cost of moving the energy depends only on the types of bacteria help Inna to determine is the type-distribution correct? If it is, print the matrix d with size k × k. Cell d[i][j] of this matrix must be equal to the minimal possible cost of energy-moving from bacteria with type i to bacteria with type j.

Input format:
The first line contains three integers n, m, k (1 ≤ n ≤ 105; 0 ≤ m ≤ 105; 1 ≤ k ≤ 500). The next line contains k integers c1, c2, ..., ck (1 ≤ ci ≤ n). Each of the next m lines contains three integers ui, vi, xi (1 ≤ ui, vi ≤ 105; 0 ≤ xi ≤ 104). It is guaranteed that $$\sum_{i=1}^{k} c_i = n$$.

Output format:
If Dima's type-distribution is correct, print string «Yes», and then k lines: in the i-th line print integers d[i][1], d[i][2], ..., d[i][k] (d[i][i] = 0). If there is no way to move energy from bacteria i to bacteria j appropriate d[i][j] must equal to -1. If the type-distribution isn't correct print «No».

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

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

Example output:
Yes
0 2
2 0

Example input:
3 1 2
2 1
1 2 0

Example output:
Yes
0 -1
-1 0

Editorial:
Inna and Binary Logic
Contest: Codeforces Round 234 (Div. 2)
Difficulty rating: 2100
Tags: binary search, bitmasks, data structures

Inna is fed up with jokes about female logic. So she started using binary logic instead.

Inna has an array of n elements a1[1], a1[2], ..., a1[n]. Girl likes to train in her binary logic, so she does an exercise consisting of n stages: on the first stage Inna writes out all numbers from array a1, on the i-th (i ≥ 2) stage girl writes all elements of array ai, which consists of n - i + 1 integers; the k-th integer of array ai is defined as follows: ai[k] = ai - 1[k] AND ai - 1[k + 1]. Here AND is bit-wise binary logical operation.

Dima decided to check Inna's skill. He asks Inna to change array, perform the exercise and say the sum of all $$\frac{n(n+1)}{2}$$ elements she wrote out during the current exercise.

Help Inna to answer the questions!

Input format:
The first line contains two integers n and m (1 ≤ n, m ≤ 105) — size of array a1 and number of Dima's questions. Next line contains n integers a1[1], a1[2], ..., a1[n] (0 ≤ ai ≤ 105) — initial array elements.

Each of next m lines contains two integers — Dima's question description. Each question consists of two integers pi, vi (1 ≤ pi ≤ n; 0 ≤ vi ≤ 105). For this question Inna should make a1[pi] equals vi, and then perform the exercise. Please, note that changes are saved from question to question.

Output format:
For each question print Inna's answer on a single line.

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

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

Example output:
6
4
7
12

Editorial:
Frames
Contest: Codeforces Beta Round 76 (Div. 1 Only)
Difficulty rating: 1700
Tags: implementation

Throughout Igor K.'s life he has had many situations worthy of attention. We remember the story with the virus, the story of his mathematical career and of course, his famous programming achievements. However, one does not always adopt new hobbies, one can quit something as well.

This time Igor K. got disappointed in one of his hobbies: editing and voicing videos. Moreover, he got disappointed in it so much, that he decided to destroy his secret archive for good.

Igor K. use Pindows XR operation system which represents files and folders by small icons. At that, m icons can fit in a horizontal row in any window.

Igor K.'s computer contains n folders in the D: disk's root catalog. The folders are numbered from 1 to n in the order from the left to the right and from top to bottom (see the images). At that the folders with secret videos have numbers from a to b inclusive. Igor K. wants to delete them forever, at that making as few frame selections as possible, and then pressing Shift+Delete exactly once. What is the minimum number of times Igor K. will have to select the folder in order to select folders from a to b and only them? Let us note that if some selected folder is selected repeatedly, then it is deselected. Each selection possesses the shape of some rectangle with sides parallel to the screen's borders.

Input format:
The only line contains four integers n, m, a, b (1 ≤ n, m ≤ 109, 1 ≤ a ≤ b ≤ n). They are the number of folders in Igor K.'s computer, the width of a window and the numbers of the first and the last folders that need to be deleted.

Output format:
Print a single number: the least possible number of times Igor K. will have to select the folders using frames to select only the folders with numbers from a to b.

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

Note:
The images below illustrate statement tests.

The first test:

In this test we can select folders 3 and 4 with out first selection, folders 5, 6, 7, 8 with our second selection and folder 9 with our third, last selection.

The second test:

In this test we can first select all folders in the first row (2, 3, 4, 5), then — all other ones.

Example input:
11 4 3 9

Example output:
3

Example input:
20 5 2 20

Example output:
2

Editorial:
End of Exams
Contest: Codeforces Beta Round 76 (Div. 1 Only)
Difficulty rating: 1900
Tags: greedy

Students love to celebrate their holidays. Especially if the holiday is the day of the end of exams!

Despite the fact that Igor K., unlike his groupmates, failed to pass a programming test, he decided to invite them to go to a cafe so that each of them could drink a bottle of... fresh cow milk. Having entered the cafe, the m friends found n different kinds of milk on the menu, that's why they ordered n bottles — one bottle of each kind. We know that the volume of milk in each bottle equals w.

When the bottles were brought in, they decided to pour all the milk evenly among the m cups, so that each got a cup. As a punishment for not passing the test Igor was appointed the person to pour the milk. He protested that he was afraid to mix something up and suggested to distribute the drink so that the milk from each bottle was in no more than two different cups. His friends agreed but they suddenly faced the following problem — and what is actually the way to do it?

Help them and write the program that will help to distribute the milk among the cups and drink it as quickly as possible!

Note that due to Igor K.'s perfectly accurate eye and unswerving hands, he can pour any fractional amount of milk from any bottle to any cup.

Input format:
The only input data file contains three integers n, w and m (1 ≤ n ≤ 50, 100 ≤ w ≤ 1000, 2 ≤ m ≤ 50), where n stands for the number of ordered bottles, w stands for the volume of each of them and m stands for the number of friends in the company.

Output format:
Print on the first line "YES" if it is possible to pour the milk so that the milk from each bottle was in no more than two different cups. If there's no solution, print "NO".

If there is a solution, then print m more lines, where the i-th of them describes the content of the i-th student's cup. The line should consist of one or more pairs that would look like "b v". Each such pair means that v (v > 0) units of milk were poured into the i-th cup from bottle b (1 ≤ b ≤ n). All numbers b on each line should be different.

If there are several variants to solve the problem, print any of them. Print the real numbers with no less than 6 digits after the decimal point.

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

Example input:
2 500 3

Example output:
YES
1 333.333333
2 333.333333
2 166.666667 1 166.666667

Example input:
4 100 5

Example output:
YES
3 20.000000 4 60.000000
1 80.000000
4 40.000000 2 40.000000
3 80.000000
2 60.000000 1 20.000000

Editorial:
Flags
Contest: Codeforces Beta Round 76 (Div. 1 Only)
Difficulty rating: 2500
Tags: dp, math, matrices

When Igor K. was a freshman, his professor strictly urged him, as well as all other freshmen, to solve programming Olympiads. One day a problem called "Flags" from a website called Timmy's Online Judge caught his attention. In the problem one had to find the number of three-colored flags that would satisfy the condition... actually, it doesn't matter. Igor K. quickly found the formula and got the so passionately desired Accepted.

However, the professor wasn't very much impressed. He decided that the problem represented on Timmy's Online Judge was very dull and simple: it only had three possible colors of flag stripes and only two limitations. He suggested a complicated task to Igor K. and the fellow failed to solve it. Of course, we won't tell anybody that the professor couldn't solve it as well.

And how about you? Can you solve the problem?

The flags consist of one or several parallel stripes of similar width. The stripes can be one of the following colors: white, black, red or yellow. You should find the number of different flags with the number of stripes from L to R, if:

- a flag cannot have adjacent stripes of one color;
- a flag cannot have adjacent white and yellow stripes;
- a flag cannot have adjacent red and black stripes;
- a flag cannot have the combination of black, white and red stripes following one after another in this or reverse order;
- symmetrical flags (as, for example, a WB and a BW flag, where W and B stand for the white and black colors) are considered the same.

Input format:
The only line contains two integers L and R (1 ≤ L ≤ R ≤ 109). They are the lower and upper borders of the number of stripes on the flag.

Output format:
Print a single number — the number of different flags that would satisfy the condition of the problem and would have from L to R stripes, modulo 1000000007.

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

Note:
In the first test the following flags exist (they are listed in the lexicographical order, the letters B, R, W, Y stand for Black, Red, White and Yellow correspondingly):

3 stripes: BWB, BYB, BYR, RWR, RYR, WBW, WBY, WRW, WRY, YBY, YRY (overall 11 flags).

4 stripes: BWBW, BWBY, BYBW, BYBY, BYRW, BYRY, RWRW, RWRY, RYBW, RYBY, RYRW, RYRY (12 flags).

That's why the answer to test 1 is equal to 11 + 12 = 23.

Example input:
3 4

Example output:
23

Example input:
5 6

Example output:
64

Editorial:
Lostborn
Contest: Codeforces Beta Round 76 (Div. 1 Only)
Difficulty rating: 2600
Tags: dp, math, number theory

Igor K. very much likes a multiplayer role playing game WineAge II. Who knows, perhaps, that might be the reason for his poor performance at the university. As any person who plays the game, he is interested in equipping his hero with as good weapon and outfit as possible.

One day, as he was reading the game's forum yet again, he discovered a very interesting fact. As it turns out, each weapon in the game is characterised with k different numbers: a1, ..., ak. They are called hit indicators and according to the game developers' plan they are pairwise coprime.

The damage that is inflicted during a hit depends not only on the weapon's characteristics, but also on the hero's strength parameter. Thus, if the hero's strength equals n, than the inflicted damage will be calculated as the number of numbers on the segment $${\bigl [}1,n{\bigr ]}$$, that aren't divisible by any hit indicator ai.

Recently, having fulfilled another quest, Igor K. found a new Lostborn sword. He wants to know how much damage he will inflict upon his enemies if he uses it.

Input format:
The first line contains two integers: n and k (1 ≤ n ≤ 1013, 1 ≤ k ≤ 100). They are the indicator of Igor K's hero's strength and the number of hit indicators.

The next line contains space-separated k integers ai (1 ≤ ai ≤ 1000). They are Lostborn sword's hit indicators. The given k numbers are pairwise coprime.

Output format:
Print the single number — the damage that will be inflicted by Igor K.'s hero when he uses his new weapon.

Please, do not use the %lld specificator to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specificator.

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

Example input:
20 3
2 3 5

Example output:
6

Example input:
50 2
15 8

Example output:
41

Editorial:
Eleven
Contest: Codeforces Round 459 (Div. 2)
Difficulty rating: 800
Tags: brute force, implementation

Eleven wants to choose a new name for herself. As a bunch of geeks, her friends suggested an algorithm to choose a name for her. Eleven wants her name to have exactly n characters.

Her friend suggested that her name should only consist of uppercase and lowercase letters 'O'. More precisely, they suggested that the i-th letter of her name should be 'O' (uppercase) if i is a member of Fibonacci sequence, and 'o' (lowercase) otherwise. The letters in the name are numbered from 1 to n. Fibonacci sequence is the sequence f where

- f1 = 1,
- f2 = 1,
- fn = fn - 2 + fn - 1 (n > 2).

As her friends are too young to know what Fibonacci sequence is, they asked you to help Eleven determine her new name.

Input format:
The first and only line of input contains an integer n (1 ≤ n ≤ 1000).

Output format:
Print Eleven's new name on the first and only line of output.

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

Example input:
8

Example output:
OOOoOooO

Example input:
15

Example output:
OOOoOooOooooOoo

Editorial:
Calculate the first x Fibonacci sequence elements, where x is the greatest integer such that fx ≤ n. Let s be a string consisting of n lowercase 'o' letters. Then for each i ≤ x, perform sfi = 'O'. The answer is s.
Pseudo code:
Total time complexity: $${\mathcal{O}}(n)$$