Ayoub has two strings $$$a$$$ and $$$b$$$ and he should do this operation exactly once with these strings.
He should pick two integers $$$x$$$ and $$$y$$$ $$$(x \neq y)$$$, such that after swapping $$$a_x$$$ with $$$a_y$$$ and $$$b_x$$$ with $$$b_y$$$, string $$$a$$$ becomes lexicographically greater than string $$$b$$$.
Is there there any possible way to do it?
The first line contains one integer $$$n$$$ $$$(2 \leq n \leq 10^{5})$$$.
The second line contains the string $$$a$$$ of size $$$n$$$.
The third line contains the string $$$b$$$ of size $$$n$$$.
All characters in both strings are lowercase English letters.
If there is no way to do the swap so that string $$$a$$$ is lexicographically greater than string $$$b$$$ print NO on a line.
Otherwise, print YES on a line. On a new line print two integers $$$x$$$ and $$$y$$$ $$$(1 \leq x , y \leq n)$$$ $$$(x \neq y)$$$.
3 abc abc
NO
3 zzz aaa
YES 2 3
Jaber is a superhero, he always helps people who are in trouble.
He lives in a city described as a sequence of $$$n$$$ consecutive buildings, the height of the $$$i_{th}$$$ buildings is $$$h_i$$$. The floors are numbered starting from the ground floor $$$0$$$ and ending with the last floor $$$h_i$$$.
Jaber will do $$$m$$$ missions, in the $$$i_{th}$$$ mission he will be at the $$${i_1}^{th}$$$ building on the $$${f_1}^{th}$$$ floor, and he has to save someone in the $$${i_2}^{th}$$$ building on the $$${f_2}^{th}$$$ floor.
In one move Jaber can do one of these movements.
1- If Jaber is not at the ground floor he can go down (from the $$$i_{th}$$$ floor to the $$${i - 1}_{th}$$$ floor).
2- If Jaber is not on the last floor, he can go up (from the $$$i_{th}$$$ floor to the $$${i + 1}_{th}$$$ floor).
3- If Jaber is on the ground floor he can go to the ground floor of any of the adjacent buildings.
4- If Jaber is on the last floor he can go to the last floor of any adjacent buildings if the height of that building is strictly less than the current building height.
As a super-hero, Jaber has a superpower, Jaber can choose any segment of consecutive building and decrease their heights by a non-negative integer $$$l$$$, but he should satisfy some rules:
1- $$$l$$$ should be strictly less than the heights of all buildings in the chosen segment.
2- The starting and the ending buildings ($$$i_1$$$ and $$$i_2$$$) mustn't be included in the chosen segment.
3- The value of $$$l$$$ is bounded by an integer $$$k$$$,$$$(1 \leq l \leq k)$$$. Since Jaber's power is limited, after every mission the buildings will return to their original height.
Now you should tell Jaber for every mission what is the minimum possible time to reach the $$${f_2}^{th}$$$ floor in $$${i_2}^{th}$$$ building from the $$${f_1}^{th}$$$ floor in th $$${i_1}^{th}$$$ building.
The first line of input contains two integers $$$n$$$ and $$$m$$$ which are the number of buildings and the number of missions $$$(2 \leq n \leq 2 \times 10 ^ {5})$$$ $$$(1 \leq m \leq 2 \times 10 ^ {5})$$$.
The next line contains $$$n$$$ integers, the $$$i_{th}$$$ one is $$$h_i$$$, which is the height of the $$$i_{th}$$$ building $$$(1 \leq h_i \leq 5 \times 10 ^ {8})$$$.
For the next $$$m$$$ lines, every line will contain five integers $$$i_1$$$ $$$f_1$$$ $$$i_2$$$ $$$f_2$$$ $$$k$$$ $$$(1 \leq i_1 , i_2 \leq n)$$$ $$$(i_1 \neq i_2)$$$ $$$(0 \leq f_1 \leq h_{i_1})$$$ $$$(0 \leq f_2 \leq h_{i_2})$$$ $$$(1 \leq k \leq 5 \times 10 ^ {8})$$$ , which the description of every mission.
Print $$$m$$$ lines, the $$$i_{th}$$$ should be the answer of the $$$i_{th}$$$ mission.
4 1 10 5 9 12 1 10 3 0 4
3
You are given an integer $$$n$$$, and you have initially two integers $$$a$$$ and $$$x$$$, $$$a = 1$$$, $$$x=0$$$.
You need to find the minimum number of operations in order to make the value of $$$x$$$ equal to the value of $$$n$$$.
In one operation you can do one of these operations:
1- Increase the value of $$$x$$$ by $$$a$$$, $$$x=x+a$$$.
2- Change the value of $$$a$$$ into $$$x$$$, then increase the value of $$$x$$$ by $$$a$$$, $$$a=x$$$, $$$x=x+a$$$.
Can you find the answer?
The first line of input contains one integer $$$t$$$ $$$(1 \leq t \leq 50)$$$
For each of the next $$$t$$$ lines, the input will contain one integer $$$n$$$ $$$(1 \leq n \leq 10^{9})$$$.
For each test case print it's answer on a line.
4 1 2 3 4
1 2 3 3
You are given an undirected graph with $$$n$$$ nodes and $$$m$$$ edges.
The graph doesn't contain self-loops but it may contain multiple edges.
There is a number $$$a_i$$$ attached to the $$$i_{th}$$$ $$$(1 \leq i \leq n)$$$ node.
You can do the following operation once: Choose a set of nodes and a value $$$x$$$ $$$(0 \leq x \lt 2 ^ {20})$$$ and change all the values of the nodes in the set from $$$a_i$$$ into $$$a_i \bigoplus x$$$.
You should choose any set and any value $$$x$$$ so that for each edge the values of the nodes connected with that edge are different.
Is it possible?
The first line of input contains two integers $$$n$$$ and $$$m$$$, which are the number of nodes and the number of edges $$$(1 \leq n , m \leq 3 \times 10 ^ {5})$$$.
The second line contains $$$n$$$ integers, the $$$i^{th}$$$ one is $$$a_i$$$ which is the value attached to the $$$i^{th}$$$ node $$$(0 \leq a_i \lt 2 ^ {20})$$$.
The next $$$m$$$ lines will contain two integers for each $$$u$$$ and $$$v$$$, $$$(1 \leq u , v \leq n)$$$ $$$(u \neq v)$$$, which means that there is an edge between nodes $$$u$$$ and $$$v$$$.
it is guaranteed that the given graph doesn't contain self-loops but it may contain multiple edges.
If there is no way to choose a set and a value $$$x$$$, print $$$-1$$$.
Otherwise print two integers $$$k$$$ and $$$x$$$ on the first line, which is the size of the chosen set and the chosen value, $$$(1 \leq k \leq n)$$$ $$$(0 \leq x \lt 2 ^ {20})$$$.
In the second line print $$$k$$$ integers, which describes the chosen nodes in the set.
Make sure that no node appears more than one time in the set.
3 3 1 1 1 1 2 2 3 1 3
-1
3 3 1 1 2 1 2 2 3 1 3
1 1 2
5 4 1 2 3 4 5 1 2 1 3 1 4 4 5
0 1
There are 2 circles the first circle has a radius of $$$r_1$$$ and the second one has a radius of $$$r_2$$$.
Find the area of the grey area, in the figure.
The first line contains one integer $$$t$$$ $$$(1 \leq t \leq 10 ^ {5})$$$, which is the number of test cases.
For the next $$$t$$$ lines, the input will contains two integers for each, $$$r_1$$$ and $$$r_2$$$ $$$(1 \leq r_1 , r_2 \leq 10 ^ {6})$$$, which is the radius of the first circle and the radius of the second circle.
For every test case print the answer on a line.
the relative error is $$$10^{-3}$$$.
2 10 5 5 10
1.7565653168 2.3212820551
You are given four integers $$$n$$$, $$$m$$$, $$$s$$$, $$$x$$$.
You should construct an array of size $$$n$$$, such that:
1)All elements are integers between 0 and $$$m$$$.
2)The sum of the array should be $$$s$$$.
3)The xor sum of the array should be $$$x$$$.
Can you?
The first line of input contains one integer $$$t$$$ $$$(1 \leq t \leq 10 ^ {5})$$$ which is the number of test cases.
For each test case, the input will contain four integers $$$n$$$, $$$m$$$, $$$s$$$, $$$x$$$ $$$(1 \leq n \leq 10^{5})$$$ $$$(0 \leq m \lt 2 ^ {30})$$$ $$$(0 \leq s \leq 10 ^ {18})$$$ $$$(0 \leq x \lt 2 ^ {30})$$$.
The sum of $$$n$$$ overall test cases will not exceed $$$3 \times 10^{5}$$$.
For each test case, if there were no way to construct the array, print $$$-1$$$; otherwise, print an array of size $$$n$$$ that satisfies the rules on a line.
3 4 4 15 7 4 4 4 4 4 4 15 1
4 4 4 3 4 0 0 0 -1
You are given an array $$$b$$$ of size $$$m$$$.
An array $$$a$$$ of size $$$n$$$ is built from $$$b$$$ by the following formula:
for every $$$i$$$ $$$(0 \leq i \lt n)$$$ $$$a[i] = b[i$$$ $$$mod$$$ $$$m]$$$.
You should find a sub-array from the array $$$a$$$ with a sum equal to $$$k$$$ and minimum possible size.
The arrays are 0 indexed.
The first line of input contains one integer $$$t$$$ which is the number of test cases.
For every test case :
The First line contains three integers $$$m$$$ $$$n$$$ $$$k$$$, which are the size of array $$$b$$$ and the size of array $$$a$$$ and the needed sum $$$(1 \leq m \leq 10 ^ {5})$$$ $$$(m \leq n \leq 10 ^ {9})$$$ $$$(-10^{18} \leq k \leq 10^{18})$$$.
The second line contains $$$m$$$ integers, the $$$i_{th}$$$ one is $$$b_i$$$ $$$(-10^{9} \leq b_i \leq 10 ^{9})$$$, which is the $$$i_{th}$$$ element in array $$$b$$$.
it is guaranteed that the sum of $$$m$$$ between all test cases will not exceed $$$3 \times 10^{5}$$$.
For every test case : If there is no sub-array of sum $$$k$$$ print $$$-1$$$ on a line.
Otherwise print two integers $$$l$$$ and $$$r$$$ $$$(1 \leq l \leq r \leq n)$$$ which is a sub-array with minimal possible size and sum equal to $$$k$$$.
If there is more than one answer print the sub-array with minimum possible $$$l$$$.
2 3 5 0 1 1 -3 5 5 10 1 1 1 2 2
0 3 -1
You are given an undirected graph that contains $$$n$$$ nodes and $$$m$$$ edges, the graph doesn't contain self-loops or multiple edges and it doesn't have to be connected.
You should give a direction for every edge (make the graph directed), so that the in-degree of the $$$i_{th}$$$ node is equal $$$a_i$$$. If $$$a_i$$$ is equal to $$$-1$$$ then the in-degree of the $$$i_{th}$$$ node can be anything.
the in-degree of a node is the number of edges the ends in that node.
Can you solve the problem?
The first line of input contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n, m \leq 2000)$$$, which are the number of nodes and the number of edges.
The second line of input contains $$$n$$$ integers, the $$$i_{th}$$$ one is $$$a_i$$$ $$$(-1 \leq a_i \leq m)$$$, which is the needed in-degree.
When $$$a_i = -1$$$ then this node's in degree can be anything.
For the next $$$m$$$ lines, the input will contain two integers $$$u$$$ and $$$v$$$, $$$(1 \leq u , v \leq n)$$$ $$$(u \neq v)$$$, which means that there is an undirected edge between nodes $$$u$$$ and $$$v$$$.
The graph doesn't contain self-loops or multiple edges.
If there is no answer print NO on a line.
otherwise print YES and print $$$m$$$ lines.
print every edge in a directed order, for example, if you had an edge between nodes $$$a$$$ and $$$b$$$.
If you printed $$$a$$$ $$$b$$$, that means that the edge goes from node $$$a$$$ and ends at node $$$b$$$.
You can print the edges in any order.
5 5 1 2 1 -1 0 1 2 1 3 2 3 3 4 4 5
YES 1 2 3 1 3 2 4 3 5 4
5 5 1 2 1 -1 1 1 2 1 3 2 3 3 4 4 5
YES 1 2 3 1 3 2 4 3 4 5
The given graph in both samples :
After making the graph directed in the first sample :
After making the graph directed in the second sample :
Given the length $$$n$$$ of an array $$$A$$$ such that all $$$A_i$$$ $$$=$$$ $$$0$$$ for all $$$1 \leq i \leq n$$$.
You need to answer $$$q$$$ queries of two types:
1) $$$1$$$ $$$l$$$ $$$r$$$ print 1 if all values of $$$A_i$$$, such that $$$l \leq i \leq r$$$, are equal.
2) $$$2$$$ $$$l$$$ $$$r$$$ $$$a$$$ $$$b$$$ update the range $$$l$$$ $$$r$$$ with the arithmetic progression $$$a + b*(i - l)$$$.
For example if $$$l=2$$$, $$$r=5$$$, $$$a=4$$$, and $$$b=3$$$ then:
$$$A_2 = A_2 + 4$$$
$$$A_3 = A_3 + 4 + 3$$$
$$$A_4 = A_4 + 4 + 2*3$$$
$$$A_5 = A_5 + 4 + 3*3$$$
First line contains two integers $$$n$$$ and $$$q$$$ $$$(1 \leq n,q \leq 2*10^5)$$$.
Each of the next q lines follow one of two formates:
1) $$$1$$$ $$$l$$$ $$$r$$$ $$$(1 \leq l \leq r \leq n)$$$
2) $$$2$$$ $$$l$$$ $$$r$$$ $$$a$$$ $$$b$$$ $$$(-10^8 \leq a,b \leq 10^8)$$$
For each query of the second type print $$$1$$$ if the range is made up of the same value and $$$0$$$ if it's not.
5 3 2 1 3 4 1 1 1 3 1 4 5
0 1
Jaber is a policeman of a city that can be described by a grid of size $$$n \times m$$$, where every cell in that grid contains a house of one of the civilians.
At night every person in the city should go sleep and should turn the lights of their house off.
As a policeman Jaber should check the lights of every house in that city.
Jaber checks every row and every column in that city exactly once, in the order written on a paper with Jaber.
Every time Jaber checks a row or a column, he counts the number of houses that has their lights turned on. If he found more than one house with lights turned on he becomes sad.
Also every time he checks a row or a column, he makes sure that every house in that row or column will turn off their lights.
Ayoub doesn't remember exactly the description of the city, but he remembers in every row the number of houses that will have their lights on.
Ayoub wants to know if it is possible to have a city with that description and has at least one correct order.
The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n , m \leq 1000)$$$.
The second line contains $$$n$$$ integers, the $$$i_{th}$$$ one is $$$a_i$$$ $$$(0 \leq a_i \leq m)$$$, which is the number of houses that will have their lights on in the $$$i_{th}$$$ row.
If there is no possible answer print NO on a line, otherwise print YES.
if there is an answer you should print $$$n$$$ lines, the $$$i_{th}$$$ line should contain $$$m$$$ characters, the $$$j_{th}$$$ character should be 1 if the house in the $$$i_{th}$$$ row $$$j_{th}$$$ column has their lights on, and 0 otherwise.
make sure that the number of 1's in the $$$i_{th}$$$ row is equal to $$$a_i$$$.
then you should print $$$n + m$$$ lines, which is a correct order of rows and columns that won't make Jaber sad.
in every line you should print
row $$$x$$$ or col $$$x$$$.
make sure that every row and column appears exactly once.
4 4 1 0 0 0
YES 1000 0000 0000 0000 row 1 col 1 row 2 col 2 row 3 col 3 row 4 col 4
4 4 2 1 1 1
YES 1010 1000 0100 0001 col 3 row 1 col 1 row 2 col 2 row 3 row 4 col 4
Ayoub hates King Mahmoud, who is the king of a very large kingdom that is famous for planting very tall trees.
King Mahmoud started a new plan to plant $$$n$$$ trees, so he planted $$$n$$$ seeds in $$$n$$$ consecutive places. Initially, the height of every tree is $$$0$$$ units.
Every year the height of every tree increases by one unit, but in some years Ayoub comes and chooses exactly $$$k$$$ non-intersecting sub-arrays of trees and attack them with his dragon.
When a tree is attacked the seed won't be affected, so it can grow again, but its height becomes "0".
King Mahmoud came after $$$m$$$ years and found that the height of the $$$i_{th}$$$ tree is $$$h_i$$$ units.
King Mahmoud noticed that in some years Ayoub's dragon came and attacked the plants. King Mahmoud became very angry and decided to attack Ayoub with his army.
Ayoub is very powerful with his dragon but King Mahmoud has a strategy to take down Ayoub, but he needs to know the minimum possible $$$k$$$ so that the heights of the trees are correct.
King Mahmoud knows that Ayoub attacked at least once, it can also happen that Ayoub attacked immediately after they planted the seeds in the first year.
It can happen that there is no possible $$$k$$$, in that case, Ayoub has cheated and used a different way to attack King Mahmoud's plants, in this case, King's Mahmoud strategy will fail so he won't attack Ayoub.
The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n \leq 10 ^ {6})$$$ $$$(1 \leq m \leq 10 ^ {9})$$$.
The second line contains $$$n$$$ integers, the $$$i_{th}$$$ one is $$$h_i$$$ which is the height of the $$$i_{th}$$$ $$$(0 \leq h_i \leq m)$$$ plant after $$$m$$$ years.
If there is no possible $$$k$$$ print -1, otherwise print the minimum possible $$$k$$$ on a line.
4 3 3 3 3 3
1
4 3 0 0 0 0
1
4 2 2 1 1 2
1
4 2 2 1 2 1
2
In SPC cheating is allowed, but any way Kilani likes to check if the participants are cheating or not, (especially Omar and Wesam :P)
In SPC you can only submit codes in one programming languages which is Abu elayayeeeb programming language,a language developed by Ayoub
Ayoub didn't finish developing it yet but he created 4 commands
define $$$x$$$
$$$a = b + c$$$
read $$$x$$$
print $$$x$$$
Every command should be on one line. Kilani thinks that two students cheated if and only if you can rename the variables so that the first code becomes exactly the same as the second code.
You are given two codes, did they cheat?
The first line contains one integer $$$n$$$ $$$(1 \leq n \leq 1000)$$$, which is the number of lines of the first code.
The next $$$n$$$ lines will contain one of four commands.
define $$$x$$$
$$$a$$$ = $$$b$$$ + $$$c$$$
read $$$x$$$
print $$$x$$$
Where $$$x$$$, $$$a$$$, $$$b$$$ and $$$c$$$ are a names of variables.
The first line contains one integer $$$m$$$ $$$(1 \leq m \leq 1000)$$$, which is the number of lines of the second code.
The next $$$m$$$ lines will contain one of four commands.
define $$$x$$$
$$$a$$$ = $$$b$$$ + $$$c$$$
read $$$x$$$
print $$$x$$$
where $$$x$$$, $$$a$$$, $$$b$$$ and $$$c$$$ are a names of variables.
It's guaranteed that before using any variable it will be defined, and the name of every variable will contain lowercase English letters of length at most 10, and no variable is defined twice.
The variables can't be one of the reserved word(define, print, read).
if they cheated print YES otherwise print NO.
5 define a define b define c a=b+c print a 5 define a define b define c a=c+b print a
NO
5 define a define b define c a=b+c print a 5 define a define c define b a=c+b print a
YES
5 define a define b define c a=b+c print a 5 define a define b define c a=b+c print a
YES