You, as the great master of numbers, have been entrusted with an extremely important task, upon which, according to ancient prophecies, depends not only the fate of the contest scoreboard, but perhaps the entire computational universe. $$$ \\ $$$ In a certain kingdom of integers, there lives a noble set $$$S = \{1, 2, 3, \cdots, n\}$$$, where there are no repeated elements—each inhabitant is unique. However, recently, strange events have begun to occur in this set. $$$ \\ $$$ The great oracle, using the magical powers of foresight, has predetermined exactly how the first $$$m$$$ numbers of the final permutation will be arranged. These elements are already firmly fixed in their positions at the beginning of the future array—and they cannot be moved, for they are sealed by the will of fate. $$$ \\ $$$ Your task, O mighty arranger, is as follows: determine the order of the remaining $$$n-m$$$ elements $$$(p_{m+1}, p_{m+2}, \cdots, p_n)$$$ so that, after combining them with the predetermined prefix, the resulting permutation $$$p = [p_1, p_2, p_3, \cdots, p_n]$$$ is still valid (that is, contains all numbers from $$$1$$$ to $$$n$$$ exactly once), and at the same time, the number of inversions in it is as small as possible. $$$ \\ $$$ Definitions:
- A permutation of length $$$n$$$ is an array of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$, where each number appears exactly once.
- An inversion in a permutation is a pair of indices $$$(i, j)$$$ such that $$$(1 \le i \lt j \le n)$$$ and at the same time $$$(p_i \gt p_j)$$$.
The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \le m \lt n \le 10^{5})$$$—the total number of elements and the number of fixed numbers, respectively. $$$ \\ $$$ The second line contains $$$m$$$ distinct integers: $$$p_1, p_2, \cdots, p_m$$$, each of which belongs to the range from $$$1$$$ to $$$n$$$, and all are distinct.
Print $$$n-m$$$ integers—elements $$$p_{m+1}, p_{m+2}, \cdots, p_n$$$—such that the result $$$p = [p_1, p_2, p_3, \cdots, p_n]$$$ is a valid permutation, and the number of inversions in it is as small as possible.
10 7 5 1 2 9 3 4 6
7 8 10
5 4 1 2 3 4
5
You are given a football field in 3D space. A ball is initially placed at point $$$(x, y, z)$$$. In front of the ball, there is a goal — a rectangular box from point $$$(0, 0, 0)$$$ to $$$(A, B, C)$$$.
After a kick, the ball starts flying with initial speed $$$v$$$ in a direction defined by two angles:
- $$$\theta$$$ — horizontal angle in degrees,
- $$$\phi$$$ — vertical angle in degrees.
At each moment of time $$$t \ge 0$$$, the position of the ball is given by:
$$$X(t) = x + v \cdot \cos(\phi) \cdot \cos(\theta) \cdot t$$$
$$$Y(t) = y + v \cdot \cos(\phi) \cdot \sin(\theta) \cdot t$$$
$$$Z(t) = z + v \cdot \sin(\phi) \cdot t - \frac{1}{2} \cdot g \cdot t^2$$$
where $$$g = 9.81$$$ and angles are converted to radians:
$$$\theta_\text{rad} = \theta \cdot \pi / 180$$$, $$$\phi_\text{rad} = \phi \cdot \pi / 180$$$.
You need to determine whether the ball will ever enter the goal volume.
The ball is considered inside the goal if at some moment $$$t \ge 0$$$ its position $$$(X(t), Y(t), Z(t))$$$ satisfies all of the following:
$$$0 \le X(t) \le A$$$, $$$0 \le Y(t) \le B$$$, $$$0 \le Z(t) \le C$$$
One line contains 9 real numbers:
$$$x,y,z,A,B,C, \theta,\phi,v$$$
Where:
- $$$(x, y, z)$$$ — initial position of the ball,
- $$$(A, B, C)$$$ — size of the goal volume,
- $$$\theta$$$, $$$\phi$$$ — angles in degrees,
- $$$v$$$ — initial speed.
All values are real numbers such that $$$(0 \le x,y,z,A, B, C, v \le 1000)$$$ , $$$(0 \le \theta \le 360)$$$ and $$$ (-90 \le \phi \le 90) $$$.
Print YES if the ball enters the goal at some moment. Otherwise, print NO.
10 10 10 30 30 30 180 0 10
YES
100 100 100 10 10 10 0 0 1
NO
In the distant future, information is the most valuable resource. You are an elite cryptographer in the Intergalactic Intelligence Agency. Recently, a binary signal $$$s$$$ of length $$$n$$$ was intercepted—presumably a message from an enemy organization. According to intelligence, they use a special code $$$t$$$ of length $$$m$$$, which is inserted into transmitted signals to convey secret commands.
But there is a problem: due to cosmic interference, some bits may have been randomly corrupted. Now you face an important task: change the minimum number of bits in the signal $$$s$$$ so that the substring $$$t$$$ appears exactly $$$k$$$ times in it, for every possible $$$k$$$ from $$$0$$$ to $$$n - m + 1$$$.
The minimum number of changes is the number of 0 → 1 or 1 → 0 replacements you need to make in $$$s$$$ so that exactly $$$k$$$ occurrences of the substring $$$t$$$ appear in the modified version of $$$s$$$.
Headquarters is waiting for your report: for each $$$k$$$, what is the minimum cost (in changes) to obtain $$$k$$$ occurrences of $$$t$$$?
The first line contains two integers $$$n$$$ and $$$m$$$—the lengths of the binary strings $$$a$$$ and $$$b$$$, respectively $$$(1 \le m \le n \le 500)$$$. The second line contains the binary string $$$s$$$ of length $$$n$$$. The third line contains the binary string $$$t$$$ of length $$$m$$$.
Print $$$n - m + 2$$$ integers: Let $$$k$$$ be the number of occurrences of string $$$b$$$ in string $$$a$$$. Then the $$$(k+1)$$$-th printed number should be the minimum number of changes (replacements of 0 with 1 or 1 with 0) in string $$$s$$$ that are necessary so that string $$$t$$$ appears exactly $$$k$$$ times as a substring in $$$s$$$.
5 2 01010 10
2 1 0 -1 -1
k = 0 (to remove all occurrences of 10): You can change 1 symbol, for example, 01010 → 00000, then 10 will not occur at all. Answer: 2.
k = 1 (to leave one substring 10): The string 01010 can be left as is and one of the two occurrences can be changed. For example: 01010 → 01110. Answer: 1.
k = 2 (leave both occurrences): The original string already fits. No changes are needed. Answer: 0.
At Narxoz University, the Dean believes in perfect equality: every teacher must give the same number of lectures — no more, no less. Inspired by this fairness, a student named Aigerim defines a good segment of an array as follows:
> A segment is good if every distinct number in it appears exactly the same number of times.
You are given an array $$$a$$$ of length $$$n$$$, where each element represents the ID of a teacher assigned to a lecture. $$$ \\ $$$ You are also given $$$q$$$ queries. For each query, you are asked whether the segment of the array from position $$$l$$$ to $$$r$$$ (inclusive) is good.
Help Aigerim determine which segments follow the dean's rule of fairness.
The first line contains two integers $$$n$$$ and $$$q$$$ $$$(1 \le n,q \le 10^{5},q \bmod 5 = 0 )$$$ — the number of lectures and the number of queries.$$$ \\ $$$ The second line contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ $$$(1 \le a_i \le n)$$$— the teacher IDs assigned to each lecture.$$$ \\ $$$ Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ $$$(1\le l \le r \le n)$$$ — the boundaries of the segment being checked.
For each query, print yes if the segment is good, otherwise print no.
After printing the answers to a group of queries, do not forget to output the end of line and flush the output buffer. Otherwise, you may get the Idleness Limit Exceeded verdict. To flush the buffer, use:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- refer to the documentation for other languages.
You have to flush the output buffer after the $$$5$$$-th, $$$10$$$-th, $$$15$$$-th query (and so on), i. e. after each query with index divisible by $$$5$$$. After that, you can read the next group of queries.
7 51 2 3 4 4 5 51 51 44 54 72 3
no yes yes yes yes
Student Bekzat has $$$n$$$ balloons. Each balloon is either red (denoted by the symbol R) or blue (symbol B). He arranged them in a single row and wants to know:
Is it possible, by performing at most one swap of neighboring balloons, to achieve a configuration where after every red balloon immediately follows a blue one?
A single string $$$s$$$ $$$(2 \le |s| \le 100)$$$, consisting only of the symbols R and B.
Print YES if it is possible to obtain the correct sequence with one swap of neighboring balloons, otherwise print NO.
BR
YES
The Committee of the National Archeological Research in eXploration of Organized Zones (NARXOZ) found an old chest in the Almaty region. But there is a lock on the chest with the password that consists of $$$n$$$ positive numbers.
Luckily, scientists also found the correct version of this list — the one that opens the chest.
So, you are given the two lists of numbers: the password that is now on the lock and the password that opens the chest.
To change the current password into the correct one, you can use this operation:
- Choose an index $$$i$$$ such that $$$1 \le i \lt n$$$.
- Let $$$x$$$ = value at position $$$i$$$ before the operation. Let $$$y$$$ = value at position $$$i + 1$$$ before the operation.
- After the operation: The number at position $$$i$$$ becomes $$$y - 1$$$. The number at position $$$i + 1$$$ becomes $$$x + 1$$$.
You can repeat this operation as many times as needed. Your goal is to make the current list exactly the same as the correct list, using the smallest number of operations.
If it is not possible to make the two lists the same, output -1.
NARXOZ is holding a contest: the fastest person who solves this problem will get a great job offer. You want to win — so get to work!
The first line contains one integer $$$n$$$ ($$$1 \le n \le 3*10^5$$$) — the length of the password.
The second line contains $$$n$$$ positive integers — the current version of the password.
The third line contains $$$n$$$ positive integers — the correct version of the password.
All values of the integers are positive and do not exceed $$$10^9$$$.
Print one number — the minimum number of operations needed to turn the current list into the correct list. If it is impossible, print -1.
34 7 31 7 6
3
43 1 4 22 2 3 3
-1
In the first sample we can perform operations in the following order: Swap $$$(1, 2)$$$, swap $$$(2, 3)$$$ and swap $$$(1, 2)$$$. It can be shown, that there is no other option with less number of operations.
In the second sample there is no valid order of operations to get the correct version of the password from the current one.
At Narxoz University, the algorithms professor gave the students another puzzle. He wrote an array $$$A$$$ of length $$$n$$$ on the board, and also gave them an array $$$B$$$ of length $$$m$$$, which is called the reference sequence.
The students can apply the following specific cleaning operation to segments of array $$$A$$$:
- While the length of the current segment is greater than $$$m$$$, it is allowed to choose a position $$$i$$$ ($$$L \le i \lt R$$$) and delete the element $$$A_i$$$, but only if $$$A_i \ne A_{i+1}$$$.
The professor wants to know: how many segments $$$A[L..R]$$$ are there that can be cleaned so that the resulting array is $$$B$$$?
Help the Narxoz students solve the problem and earn an extra point on the exam!
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 100$$$, $$$m \le n$$$) — the lengths of arrays $$$A$$$ and $$$B$$$.
The second line contains $$$n$$$ integers $$$A_1, A_2, \dots, A_n$$$ ($$$1 \le A_i \le 10^9$$$).
The third line contains $$$m$$$ integers $$$B_1, B_2, \dots, B_m$$$ ($$$1 \le B_i \le 10^9$$$).
Print a single integer — the number of segments of array $$$A$$$ that can be transformed into array $$$B$$$ using the described operation.
3 2 1 1 2 1 2
2
Two students — Yerlan and Daulet — are passionate about mathematics and enjoy experimenting with numbers. One day, Yerlan chose a number $$$a$$$, and Daulet chose a number $$$b$$$. Together, they decided to compute the expression $$$a^2 - b^2$$$ and find out whether the result can be a prime number.
Recall that a prime number is an integer greater than 1 that is divisible only by 1 and itself. Help the students determine whether their result is a prime number.
The first line contains two integers $$$a$$$ and $$$b$$$ $$$(1 \le b \lt a \le 10^{12})$$$ — the numbers chosen by Yerlan and Daulet, respectively.
Print YES (without quotes) if the value of the expression is a prime number, otherwise print NO.
You may print each letter in any case (uppercase or lowercase).
2 1
YES
Today in the arena is Seduneon, and he is ready to go through the matrix to reach the final corner $$$(n, n)$$$, squeezing the maximum out of all bitwise ANDs! $$$ \\ $$$ You are given a square matrix of size $$$ n \times n $$$ consisting of non-negative integers. $$$ \\ $$$ Seduneon starts at the top-left corner of the matrix — cell $$$ (1,1) $$$ — and wants to reach the bottom-right corner — cell $$$ (n,n) $$$. $$$ \\ $$$ At each step, he can move either down or right. $$$ \\ $$$ The profit of a path is the bitwise AND of all numbers encountered along the path (including the starting and ending cells). $$$ \\ $$$ Your task is to find the maximum possible profit that Seduneon can obtain by choosing the optimal path.
The first line contains a single integer $$$ n $$$ $$$ (1 \le n \le 1000) $$$ — the size of the matrix. $$$ \\ $$$ The next $$$n$$$ lines each contain $$$n$$$ integers $$$ a_{i,j} $$$ $$$ (0 \le a_{i,j} \le 2^{26}-1) $$$ — the elements of the matrix.
Print a single number — the maximum possible profit (the AND of all numbers along the optimal path from $$$ (1,1) $$$ to $$$ (n,n) $$$ ).
3 7 3 3 6 3 7 4 4 4
4
5 66969516 62881771 41514568 11972118 43940139 57756114 60816879 60776426 34516231 9491106 59277745 6543967 60776122 62741759 45421615 11938623 3439903 5163738 67108333 65003244 24596084 58055461 47893159 41145539 60652974
60644520
At Narxoz University, the faculties are not just departments — they're part of a living, evolving structure.
There are $$$n$$$ faculties, arranged in a circular building. That means faculty $$$0$$$ is a neighbor of $$$n - 1$$$. Each faculty has a type — maybe it's economics, business, or even magic accounting — and each type is represented by an integer.
The university is equipped with high-tech portals that let you instantly travel between any two faculties of the same type.
But sometimes that's not enough. So you're allowed to build corridors between neighboring faculties — that is, between faculty $$$i$$$ and $$$(i + 1)$$$ $$$mod$$$ $$$n$$$. Once built, you can walk back and forth through them.
Also, faculties love to rebrand themselves. A faculty can suddenly change its type (maybe they switched to crypto-finance).
You'll receive $$$q$$$ requests — each being one of the following:
- $$$1$$$ $$$i$$$ $$$x$$$ — Faculty $$$i$$$ changes its type to $$$x$$$.
- $$$2$$$ $$$i$$$ — A corridor is built between faculty $$$i$$$ and $$$i + 1$$$ $$$mod$$$ $$$n$$$.
- $$$3$$$ $$$a$$$ $$$b$$$ — Check if you can travel from faculty $$$a$$$ to faculty $$$b$$$ using any number of corridors or portals.
Your task is to answer for each query of type 3, print YES if such travel is possible, or NO otherwise.
The first line contains two integers $$$n$$$ and $$$q$$$ — the number of faculties and the number of queries, respectively ($$$1 \le n, q \le 10^5$$$).
The second line contains $$$n$$$ integers: $$$t_0, t_1, ..., t_{n-1}$$$ — the initial types of the faculties ($$$0 \le t_i \lt 10^{18}$$$).
Each of the following $$$q$$$ lines describes a query in one of the following formats:
- $$$1$$$ $$$i$$$ $$$x$$$ ($$$0 \le i \lt n, 0 \le x \lt 10^{18}$$$)
- $$$2$$$ $$$i$$$ ($$$0 \le i \lt n$$$)
- $$$3$$$ $$$a$$$ $$$b$$$ ($$$0 \le a \le b \lt n$$$)
All queries of type $$$2$$$ are unique.
For each query of type $$$3$$$, print YES if $$$b$$$ can be reached from $$$a$$$ , otherwise NO.
3 3 0 0 2 2 2 3 0 2 1 0 0
YES
10 9 2 1 0 1 2 1 2 0 2 2 2 6 1 5 3 2 5 1 5 4 3 0 6 1 9 3 2 2 2 7 3 9 3
YES NO