1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Ehab and a 2-operation task
Contest: Codeforces Round 525 (Div. 2)
Difficulty rating: 1400
Tags: constructive algorithms, greedy, math

You're given an array $$$a$$$ of length $$$n$$$. You can perform the following operations on it:

- choose an index $$$i$$$ $$$(1 \le i \le n)$$$, an integer $$$x$$$ $$$(0 \le x \le 10^6)$$$, and replace $$$a_j$$$ with $$$a_j+x$$$ for all $$$(1 \le j \le i)$$$, which means add $$$x$$$ to all the elements in the prefix ending at $$$i$$$.
- choose an index $$$i$$$ $$$(1 \le i \le n)$$$, an integer $$$x$$$ $$$(1 \le x \le 10^6)$$$, and replace $$$a_j$$$ with $$$a_j \% x$$$ for all $$$(1 \le j \le i)$$$, which means replace every element in the prefix ending at $$$i$$$ with the remainder after dividing it by $$$x$$$.

Can you make the array strictly increasing in no more than $$$n+1$$$ operations?

Input format:
The first line contains an integer $$$n$$$ $$$(1 \le n \le 2000)$$$, the number of elements in the array $$$a$$$.

The second line contains $$$n$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, $$$\dots$$$, $$$a_n$$$ $$$(0 \le a_i \le 10^5)$$$, the elements of the array $$$a$$$.

Output format:
On the first line, print the number of operations you wish to perform. On the next lines, you should print the operations.

To print an adding operation, use the format "$$$1$$$ $$$i$$$ $$$x$$$"; to print a modding operation, use the format "$$$2$$$ $$$i$$$ $$$x$$$". If $$$i$$$ or $$$x$$$ don't satisfy the limitations above, or you use more than $$$n+1$$$ operations, you'll get wrong answer verdict.

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

Note:
In the first sample, the array is already increasing so we don't need any operations.

In the second sample:

In the first step: the array becomes $$$[8,6,3]$$$.

In the second step: the array becomes $$$[0,2,3]$$$.

Example input:
3
1 2 3

Example output:
0

Example input:
3
7 6 3

Example output:
2
1 1 1
2 2 4

Editorial:
Ehab and another another xor problem
Contest: Codeforces Round 525 (Div. 2)
Difficulty rating: 2000
Tags: bitmasks, constructive algorithms, implementation, interactive

This is an interactive problem!

Ehab plays a game with Laggy. Ehab has 2 hidden integers $$$(a,b)$$$. Laggy can ask a pair of integers $$$(c,d)$$$ and Ehab will reply with:

- 1 if $$$a \oplus c>b \oplus d$$$.
- 0 if $$$a \oplus c=b \oplus d$$$.
- -1 if $$$a \oplus c<b \oplus d$$$.

Operation $$$a \oplus b$$$ is the bitwise-xor operation of two numbers $$$a$$$ and $$$b$$$.

Laggy should guess $$$(a,b)$$$ with at most 62 questions. You'll play this game. You're Laggy and the interactor is Ehab.

It's guaranteed that $$$0 \le a,b<2^{30}$$$.

Input format:
See the interaction section.

Output format:
To print the answer, print "! a b" (without quotes). Don't forget to flush the output after printing the answer.

Interaction format:
To ask a question, print "? c d" (without quotes). Both $$$c$$$ and $$$d$$$ must be non-negative integers less than $$$2^{30}$$$. Don't forget to flush the output after printing any question.

After each question, you should read the answer as mentioned in the legend. If the interactor replies with -2, that means you asked more than 62 queries and your program should terminate.

To flush the output, you can use:-

- fflush(stdout) in C++.
- System.out.flush() in Java.
- stdout.flush() in Python.
- flush(output) in Pascal.
- See the documentation for other languages.

Hacking:

To hack someone, print the 2 space-separated integers $$$a$$$ and $$$b$$$ $$$(0 \le a,b<2^{30})$$$.

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

Note:
In the sample:

The hidden numbers are $$$a=3$$$ and $$$b=1$$$.

In the first query: $$$3 \oplus 2 = 1$$$ and $$$1 \oplus 1 = 0$$$, so the answer is 1.

In the second query: $$$3 \oplus 1 = 2$$$ and $$$1 \oplus 2 = 3$$$, so the answer is -1.

In the third query: $$$3 \oplus 2 = 1$$$ and $$$1 \oplus 0 = 1$$$, so the answer is 0.

Then, we printed the answer.

Example input:
1
-1
0

Example output:
? 2 1
? 1 2
? 2 0
! 3 1

Editorial:
Ehab and a component choosing problem
Contest: Codeforces Round 525 (Div. 2)
Difficulty rating: 2400
Tags: dp, greedy, math, trees

You're given a tree consisting of $$$n$$$ nodes. Every node $$$u$$$ has a weight $$$a_u$$$. You want to choose an integer $$$k$$$ $$$(1 \le k \le n)$$$ and then choose $$$k$$$ connected components of nodes that don't overlap (i.e every node is in at most 1 component). Let the set of nodes you chose be $$$s$$$. You want to maximize:

$$$$$$\frac{\sum\limits_{u \in s} a_u}{k}$$$$$$

In other words, you want to maximize the sum of weights of nodes in $$$s$$$ divided by the number of connected components you chose. Also, if there are several solutions, you want to maximize $$$k$$$.

Note that adjacent nodes can belong to different components. Refer to the third sample.

Input format:
The first line contains the integer $$$n$$$ $$$(1 \le n \le 3 \cdot 10^5)$$$, the number of nodes in the tree.

The second line contains $$$n$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, $$$\dots$$$, $$$a_n$$$ $$$(|a_i| \le 10^9)$$$, the weights of the nodes.

The next $$$n-1$$$ lines, each contains 2 space-separated integers $$$u$$$ and $$$v$$$ $$$(1 \le u,v \le n)$$$ which means there's an edge between $$$u$$$ and $$$v$$$.

Output format:
Print the answer as a non-reduced fraction represented by 2 space-separated integers. The fraction itself should be maximized and if there are several possible ways, you should maximize the denominator. See the samples for a better understanding.

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

Note:
A connected component is a set of nodes such that for any node in the set, you can reach all other nodes in the set passing only nodes in the set.

In the first sample, it's optimal to choose the whole tree.

In the second sample, you only have one choice (to choose node 1) because you can't choose 0 components.

In the third sample, notice that we could've, for example, chosen only node 1, or node 1 and node 3, or even the whole tree, and the fraction would've had the same value (-1), but we want to maximize $$$k$$$.

In the fourth sample, we'll just choose nodes 1 and 3.

Example input:
3
1 2 3
1 2
1 3

Example output:
6 1

Example input:
1
-2

Example output:
-2 1

Editorial:
Ehab and a weird weight formula
Contest: Codeforces Round 525 (Div. 2)
Difficulty rating: 2800
Tags: data structures, trees

You're given a tree consisting of $$$n$$$ nodes. Every node $$$u$$$ has a weight $$$a_u$$$. It is guaranteed that there is only one node with minimum weight in the tree. For every node $$$u$$$ (except for the node with the minimum weight), it must have a neighbor $$$v$$$ such that $$$a_v<a_u$$$. You should construct a tree to minimize the weight $$$w$$$ calculated as follows:

- For every node $$$u$$$, $$$deg_u \cdot a_u$$$ is added to $$$w$$$ ($$$deg_u$$$ is the number of edges containing node $$$u$$$).
- For every edge $$$\{ u,v \}$$$, $$$\lceil log_2(dist(u,v)) \rceil \cdot min(a_u,a_v)$$$ is added to $$$w$$$, where $$$dist(u,v)$$$ is the number of edges in the path from $$$u$$$ to $$$v$$$ in the given tree.

Input format:
The first line contains the integer $$$n$$$ $$$(2 \le n \le 5 \cdot 10^5)$$$, the number of nodes in the tree.

The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$, the weights of the nodes.

The next $$$n-1$$$ lines, each contains 2 space-separated integers $$$u$$$ and $$$v$$$ $$$(1 \le u,v \le n)$$$ which means there's an edge between $$$u$$$ and $$$v$$$.

Output format:
Output one integer, the minimum possible value for $$$w$$$.

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

Note:
In the first sample, the tree itself minimizes the value of $$$w$$$.

In the second sample, the optimal tree is:

Example input:
3
1 2 3
1 2
1 3

Example output:
7

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

Example output:
40

Editorial:
Robbers' watch
Contest: Codeforces Round 359 (Div. 1)
Difficulty rating: 1700
Tags: brute force, combinatorics, dp, math

Robbers, who attacked the Gerda's cab, are very successful in covering from the kingdom police. To make the goal of catching them even harder, they use their own watches.

First, as they know that kingdom police is bad at math, robbers use the positional numeral system with base 7. Second, they divide one day in n hours, and each hour in m minutes. Personal watches of each robber are divided in two parts: first of them has the smallest possible number of places that is necessary to display any integer from 0 to n - 1, while the second has the smallest possible number of places that is necessary to display any integer from 0 to m - 1. Finally, if some value of hours or minutes can be displayed using less number of places in base 7 than this watches have, the required number of zeroes is added at the beginning of notation.

Note that to display number 0 section of the watches is required to have at least one place.

Little robber wants to know the number of moments of time (particular values of hours and minutes), such that all digits displayed on the watches are distinct. Help her calculate this number.

Input format:
The first line of the input contains two integers, given in the decimal notation, n and m (1 ≤ n, m ≤ 109) — the number of hours in one day and the number of minutes in one hour, respectively.

Output format:
Print one integer in decimal notation — the number of different pairs of hour and minute, such that all digits displayed on the watches are distinct.

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

Note:
In the first sample, possible pairs are: (0: 1), (0: 2), (1: 0), (1: 2).

In the second sample, possible pairs are: (02: 1), (03: 1), (04: 1), (05: 1), (06: 1).

Example input:
2 3

Example output:
4

Example input:
8 2

Example output:
5

Editorial:
Kay and Snowflake
Contest: Codeforces Round 359 (Div. 1)
Difficulty rating: 1900
Tags: data structures, dfs and similar, dp, trees

After the piece of a devilish mirror hit the Kay's eye, he is no longer interested in the beauty of the roses. Now he likes to watch snowflakes.

Once upon a time, he found a huge snowflake that has a form of the tree (connected acyclic graph) consisting of n nodes. The root of tree has index 1. Kay is very interested in the structure of this tree.

After doing some research he formed q queries he is interested in. The i-th query asks to find a centroid of the subtree of the node vi. Your goal is to answer all queries.

Subtree of a node is a part of tree consisting of this node and all it's descendants (direct or not). In other words, subtree of node v is formed by nodes u, such that node v is present on the path from u to root.

Centroid of a tree (or a subtree) is a node, such that if we erase it from the tree, the maximum size of the connected component will be at least two times smaller than the size of the initial tree (or a subtree).

Input format:
The first line of the input contains two integers n and q (2 ≤ n ≤ 300 000, 1 ≤ q ≤ 300 000) — the size of the initial tree and the number of queries respectively.

The second line contains n - 1 integer p2, p3, ..., pn (1 ≤ pi ≤ n) — the indices of the parents of the nodes from 2 to n. Node 1 is a root of the tree. It's guaranteed that pi define a correct tree.

Each of the following q lines contain a single integer vi (1 ≤ vi ≤ n) — the index of the node, that define the subtree, for which we want to find a centroid.

Output format:
For each query print the index of a centroid of the corresponding subtree. If there are many suitable nodes, print any of them. It's guaranteed, that each subtree has at least one centroid.

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

Note:
The first query asks for a centroid of the whole tree — this is node 3. If we delete node 3 the tree will split in four components, two of size 1 and two of size 2.

The subtree of the second node consists of this node only, so the answer is 2.

Node 3 is centroid of its own subtree.

The centroids of the subtree of the node 5 are nodes 5 and 6 — both answers are considered correct.

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

Example output:
3
2
3
6

Editorial:
Optimal Point
Contest: Codeforces Round 359 (Div. 1)
Difficulty rating: 2900
Tags: binary search, math

When the river brought Gerda to the house of the Old Lady who Knew Magic, this lady decided to make Gerda her daughter. She wants Gerda to forget about Kay, so she puts all the roses from the garden underground.

Mole, who lives in this garden, now can watch the roses without going up to the surface. Typical mole is blind, but this mole was granted as special vision by the Old Lady. He can watch any underground objects on any distance, even through the obstacles and other objects. However, the quality of the picture depends on the Manhattan distance to object being observed.

Mole wants to find an optimal point to watch roses, that is such point with integer coordinates that the maximum Manhattan distance to the rose is minimum possible.

As usual, he asks you to help.

Manhattan distance between points (x1,  y1,  z1) and (x2,  y2,  z2) is defined as |x1 - x2| + |y1 - y2| + |z1 - z2|.

Input format:
The first line of the input contains an integer t t (1 ≤ t ≤ 100 000) — the number of test cases. Then follow exactly t blocks, each containing the description of exactly one test.

The first line of each block contains an integer ni (1 ≤ ni ≤ 100 000) — the number of roses in the test. Then follow ni lines, containing three integers each — the coordinates of the corresponding rose. Note that two or more roses may share the same position.

It's guaranteed that the sum of all ni doesn't exceed 100 000 and all coordinates are not greater than 1018 by their absolute value.

Output format:
For each of t test cases print three integers — the coordinates of the optimal point to watch roses. If there are many optimal answers, print any of them.

The coordinates of the optimal point may coincide with the coordinates of any rose.

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

Note:
In the first sample, the maximum Manhattan distance from the point to the rose is equal to 4.

In the second sample, the maximum possible distance is 0. Note that the positions of the roses may coincide with each other and with the position of the optimal point.

Example input:
1
5
0 0 4
0 0 -4
0 4 0
4 0 0
1 1 1

Example output:
0 0 0

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

Example output:
3 5 9
3 5 9

Editorial:
Kay and Eternity
Contest: Codeforces Round 359 (Div. 1)
Difficulty rating: 2600
Tags: brute force, implementation, sortings

Snow Queen told Kay to form a word "eternity" using pieces of ice. Kay is eager to deal with the task, because he will then become free, and Snow Queen will give him all the world and a pair of skates.

Behind the palace of the Snow Queen there is an infinite field consisting of cells. There are n pieces of ice spread over the field, each piece occupying exactly one cell and no two pieces occupying the same cell. To estimate the difficulty of the task Kay looks at some squares of size k × k cells, with corners located at the corners of the cells and sides parallel to coordinate axis and counts the number of pieces of the ice inside them.

This method gives an estimation of the difficulty of some part of the field. However, Kay also wants to estimate the total difficulty, so he came up with the following criteria: for each x (1 ≤ x ≤ n) he wants to count the number of squares of size k × k, such that there are exactly x pieces of the ice inside.

Please, help Kay estimate the difficulty of the task given by the Snow Queen.

Input format:
The first line of the input contains two integers n and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 300) — the number of pieces of the ice and the value k, respectively. Each of the next n lines contains two integers xi and yi ( - 109 ≤ xi, yi ≤ 109) — coordinates of the cell containing i-th piece of the ice. It's guaranteed, that no two pieces of the ice occupy the same cell.

Output format:
Print n integers: the number of squares of size k × k containing exactly 1, 2, ..., n pieces of the ice.

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

Example input:
5 3
4 5
4 6
5 5
5 6
7 7

Example output:
10 8 1 4 0

Editorial:
Travelling Through the Snow Queen's Kingdom
Contest: Codeforces Round 359 (Div. 1)
Difficulty rating: 2800
Tags: bitmasks, brute force, divide and conquer, graphs

Gerda is travelling to the palace of the Snow Queen.

The road network consists of n intersections and m bidirectional roads. Roads are numbered from 1 to m. Snow Queen put a powerful spell on the roads to change the weather conditions there. Now, if Gerda steps on the road i at the moment of time less or equal to i, she will leave the road exactly at the moment i. In case she steps on the road i at the moment of time greater than i, she stays there forever.

Gerda starts at the moment of time l at the intersection number s and goes to the palace of the Snow Queen, located at the intersection number t. Moreover, she has to be there at the moment r (or earlier), before the arrival of the Queen.

Given the description of the road network, determine for q queries li, ri, si and ti if it's possible for Gerda to get to the palace on time.

Input format:
The first line of the input contains integers n, m and q (2 ≤ n ≤ 1000, 1 ≤ m, q ≤ 200 000) — the number of intersections in the road network of Snow Queen's Kingdom, the number of roads and the number of queries you have to answer.

The i-th of the following m lines contains the description of the road number i. The description consists of two integers vi and ui (1 ≤ vi, ui ≤ n, vi ≠ ui) — the indices of the intersections connected by the i-th road. It's possible to get both from vi to ui and from ui to vi using only this road. Each pair of intersection may appear several times, meaning there are several roads connecting this pair.

Last q lines contain the queries descriptions. Each of them consists of four integers li, ri, si and ti (1 ≤ li ≤ ri ≤ m, 1 ≤ si, ti ≤ n, si ≠ ti) — the moment of time Gerda starts her journey, the last moment of time she is allowed to arrive to the palace, the index of the starting intersection and the index of the intersection where palace is located.

Output format:
For each query print "Yes" (without quotes) if Gerda can be at the Snow Queen palace on time (not later than ri) or "No" (without quotes) otherwise.

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

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

Example output:
Yes
Yes
Yes
No
No
Yes

Editorial:
Unimodal Array
Contest: Codeforces Round 424 (Div. 2, rated, based on VK Cup Finals)
Difficulty rating: 1000
Tags: implementation

Array of integers is unimodal, if:

- it is strictly increasing in the beginning;
- after that it is constant;
- after that it is strictly decreasing.

The first block (increasing) and the last block (decreasing) may be absent. It is allowed that both of this blocks are absent.

For example, the following three arrays are unimodal: [5, 7, 11, 11, 2, 1], [4, 4, 2], [7], but the following three are not unimodal: [5, 5, 6, 6, 1], [1, 2, 1, 2], [4, 5, 5, 6].

Write a program that checks if an array is unimodal.

Input format:
The first line contains integer n (1 ≤ n ≤ 100) — the number of elements in the array.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1 000) — the elements of the array.

Output format:
Print "YES" if the given array is unimodal. Otherwise, print "NO".

You can output each letter in any case (upper or lower).

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

Note:
In the first example the array is unimodal, because it is strictly increasing in the beginning (from position 1 to position 2, inclusively), that it is constant (from position 2 to position 4, inclusively) and then it is strictly decreasing (from position 4 to position 6, inclusively).

Example input:
6
1 5 5 5 4 2

Example output:
YES

Example input:
5
10 20 30 20 10

Example output:
YES

Editorial:
Let use two variables pos1 и pos2. Initially pos1 = 0 and pos2 = n - 1.
After that we need to iterate through the given array from the left to the right and increase pos1 until the next element is strictly more than previous. After that we need to iterate through the given array from the right to the left and decrease pos2 until a[pos2 - 1] > a[pos2].
Now it is left only to check that all elements between positions pos1 and pos2 are equal to each other. If it is true the answer is "YES", otherwise, the answer is "NO".
Keyboard Layouts
Contest: Codeforces Round 424 (Div. 2, rated, based on VK Cup Finals)
Difficulty rating: 800
Tags: implementation, strings

There are two popular keyboard layouts in Berland, they differ only in letters positions. All the other keys are the same. In Berland they use alphabet with 26 letters which coincides with English alphabet.

You are given two strings consisting of 26 distinct letters each: all keys of the first and the second layouts in the same order.

You are also given some text consisting of small and capital English letters and digits. It is known that it was typed in the first layout, but the writer intended to type it in the second layout. Print the text if the same keys were pressed in the second layout.

Since all keys but letters are the same in both layouts, the capitalization of the letters should remain the same, as well as all other characters.

Input format:
The first line contains a string of length 26 consisting of distinct lowercase English letters. This is the first layout.

The second line contains a string of length 26 consisting of distinct lowercase English letters. This is the second layout.

The third line contains a non-empty string s consisting of lowercase and uppercase English letters and digits. This is the text typed in the first layout. The length of s does not exceed 1000.

Output format:
Print the text if the same keys were pressed in the second layout.

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

Example input:
qwertyuiopasdfghjklzxcvbnm
veamhjsgqocnrbfxdtwkylupzi
TwccpQZAvb2017

Example output:
HelloVKCup2017

Example input:
mnbvcxzlkjhgfdsapoiuytrewq
asdfghjklqwertyuiopzxcvbnm
7abaCABAABAcaba7

Example output:
7uduGUDUUDUgudu7

Editorial:
At first we need to support the correspondence of letters on keyboards. For example, it can be done with help of map < char, char > . Let's call it conformity.
Let the first layout equals to s1 and the second — s2. Now we need to iterate through the first string and make conformity[s1[i]] = s2[i]. Also we need to make conformity[toupper(s1[i])] = toupper(s2[i]), where function toupper(c) gives the lowercase letter c to the corresponding uppercase letter.
After that simply iterate through the given text. Let the current symbol is c. If c is a digit we need to print it. Otherwise, c is a letter, so we need to print conformity[c].