Abdulrahman and Hazem are playing a game. They have an array $$$a$$$ of $$$n$$$ integer numbers. Abdulrahman will choose $$$p$$$ indices $$$x_1, x_2, \dots x_p$$$ and Hazem will choose $$$q$$$ indices $$$y_1, y_2, \dots y_q$$$ where no index is chosen by both players. I.e. $$$x_i \ne y_j: 1 \le i \le p, 1 \le j \le q$$$.
After choosing their indices, let us denote the score of the players as the sum of the integers he chose from the array:
- Abdulrahman's score as $$$S_a = \sum_{i=1}^{i=p}a_{x_i}$$$
- Hazem's score as $$$S_b = \sum_{i=1}^{i=q}a_{y_i}$$$
Now given $$$P$$$ and $$$Q$$$ find the maximum value for $$$S_a - S_b$$$ if Abdulrahman cannot choose more than $$$P$$$ index and Hazem cannot choose more than $$$Q$$$ index ($$$p \le P$$$, $$$q \le Q$$$)
The first line of input contains one integer $$$T$$$ ($$$1 \le T \le 10^5$$$) denoting the number of testcases.
The first line of each testcase contains three space-seperated integers $$$N$$$ ($$$1 \le n \le 10^5$$$), $$$P$$$ and $$$Q$$$ ($$$0 \le P,Q \le n$$$)
The second line of each testcase contains $$$n$$$ space-seperated integers $$$a_1,a_2,...,a_N$$$ ($$$-10^9 \le a_i \le 10^9$$$)
Its guaranteed that the sum of $$$n$$$ over all testcases is less than or equal to $$$10^5$$$.
Print the maximum value for $$$S_a - S_b$$$ Abdulrahman and Hazem can obtain.
33 1 1-2 0 23 1 26 3 -45 0 210 -6 -9 8 -7
4 10 16
You are given a tree $$$T$$$ with $$$n$$$ vertices. Edge $$$i$$$ $$$(1 \le i \le n-1)$$$ connects vertices $$$u_i$$$ and $$$v_i$$$, $$$T$$$ is rooted at $$$x$$$ $$$(1 \le x \le n)$$$
You have to construct the lexicographically smallest $$$n$$$-permutation $$$p$$$ such that the following condition holds:
- If $$$u$$$ is an ancestor to $$$v$$$, $$$p_u \lt p_v$$$.
Note: Ancestors of the vertex $$$u$$$ are all vertices on the path from the root $$$x$$$ to the vertex $$$u$$$ , except the vertex $$$u$$$ itself.
The first line contains integers $$$n$$$ and $$$x$$$ $$$(2 \le n \le 2 \cdot 10^5)$$$ — the number of vertices in the tree and the root.
The next $$$n-1$$$ lines contain integers $$$u_i$$$ and $$$v_i$$$ $$$(1 \le v_i, u_i \le n)$$$ — the vertices that the $$$i$$$-th edge connects.
It is guaranteed that this set of edges forms a tree.
The lexicographically smallest $$$n$$$-permutation that satisfies the given condition
5 3 3 5 1 5 1 2 4 1
3 4 1 5 2
10 3 5 4 8 3 4 6 5 3 7 9 1 3 5 10 2 9 9 8
2 5 1 7 6 8 9 3 4 10
For the first example:
For the second example:
It's no secret that coming up with a balanced problemset for the SYPUCPC is really hard so the problemsetters needs your help!!
The current problemset has $$$N$$$ problems, Problem with index $$$i$$$ has difficulty of $$$A_i$$$.
We define the overall difficulty of the problemset by the average difficulty of all problems in that problemset, more formally the overall dificulty can be calculated as: $$$\frac{\sum_{i=1}^{i=M}B_i}{M}$$$ where $$$M$$$ is the number of problems in the problemset and $$$B_i$$$ is the difficulty of the $$$i_{th}$$$ problem.
Your task is to remove some (possibly none) problems from the given problemset to acheive the minimum possible overall difficulty.
Note: A problemset must at least have one problem, which means you can't just remove every single problem and call it a day.
The first line of input contains one integer $$$T$$$ ($$$1 \le T \le 10^5$$$) denoting the number of testcases.
The first line of each testcase contains one integer $$$N$$$ ($$$1 \le N \le 10^5$$$)
The second line of each testcase contains $$$N$$$ space-seperated integers $$$A_1,A_2,...,A_N$$$ ($$$800 \le A_i \le 4000$$$)
Its guaranteed that the sum of $$$N$$$ over all testcases is less than or equal to $$$10^5$$$.
Print the minimum overall difficulty you can obtain after removing some problems
224000 8003969 969 969
800 969
Mohanad likes AtCoder.jp, which is a superior Japanese programming contest site.
One of the factors that make AtCoder.jp a great website is its short problem statements. Therefore, in true AtCoder.jp fashion, this problem statement is as short as possible.
Given a permutation $$$p$$$ of length $$$n$$$, let $$$P$$$ be an array of permutations that contains all permutations lexicographically greater than or equal to $$$p$$$, sorted by their order. Let $$$A$$$ be the concatenation of $$$P$$$.
How many swaps will bubble sort algorithm make to sort $$$A$$$?
The answer may be large, so output it modulo $$$10^9+7$$$.
(Check out the notes for bubble sort code).
The first line contains $$$n$$$ ($$$2 \le n \le 2000$$$).
The second line contains a permutations $$$p$$$.
The number of swaps the above code will make to sort $$$A$$$ modulo $$$10^9+7$$$.
3 3 1 2
8
6 3 4 2 1 6 5
1355278
In the first test case:
$$$P = [[3,1,2],[3,2,1]]$$$
$$$A = [3,1,2,3,2,1]$$$
Bubble Sort C++ code:
Naseem owns a jewelry shop and likes to show his most beautiful pearls at the storefront on a $$$n \times n$$$ board. The rows are numbered from $$$1$$$ to $$$n$$$ from top to bottom and the columns are numbered from $$$1$$$ to $$$n$$$ from left to right. Each pearl has its own size. Naseem has an infinite amount of pearls of each size
Naseem thinks that the board looks good if he can fill the board with pearls so that choosing any two pearls on adjacent cells in the board, the sum of their sizes would be the same for any other pair of pearls on adjacent cells. Two cells are considered adjacent if they share a side
Initially, the board is empty. At each second, Naseem will add a pearl to an empty cell, remove a pearl from a cell or replace a pearl on a cell. More formally, Naseem will choose a cell on the $$$x_{th}$$$ row and $$$y_{th}$$$ column and a pearl of size $$$v$$$, remove the pearl on the cell if it exists, and put a pearl of size $$$v$$$ on the cell if $$$v \ne 0$$$. Otherwise, if $$$v = 0$$$ he leaves the cell empty.
Naseem wants to know if the board looks good after each second. He is a busy guy because he keeps counting the money he gets from the shop, so can he help him doing so?
The first line of the input contains two space-separated integer numbers $$$n$$$ and $$$q$$$ $$$(1 \le n, q \le 10^5)$$$. The size of the board and the number of seconds Naseem will make changes on the board, respectively.
The next $$$q$$$ lines of the input each contains $$$3$$$ integer numbers $$$x$$$, $$$y$$$ and $$$v$$$ ($$$1 \le x, y \le n, 0 \le v \le 10^9$$$), where $$$x$$$ and $$$y$$$ are the coordinates of the cell on the board and $$$v$$$ is the size of the pearl he will put on the cell. If $$$v = 0$$$, then he will leave the cell empty
For each second, print YES if the board is good. Otherwise, print NO. Note that the case of the each letter
You can output the answer in any case (upper or lower). For example, the strings yEs, yes, Yes, and YES will be recognized as positive responses.
3 4 1 1 1 2 3 4 1 2 3 1 2 1
YES YES NO NO
3 5 2 1 1 1 3 4 2 1 1 2 2 3 2 2 0
YES YES YES NO YES
Since the author of this problem is too lazy to write a problem statement, he will provide you with the problem sketch only.
You're given an array $$$a$$$ of length $$$n$$$ consisting of zeros and ones, and an integer $$$k$$$.
You can perform no more than $$$n$$$ operations. In one operation, you take a range of length exactly $$$k$$$ and flip its values, making every $$$0$$$ a $$$1$$$ and every $$$1$$$ a $$$0$$$.
More formally, in each operation you can choose a value $$$l$$$ ($$$1 \le l \le n-k+1$$$) then do the assignment $$$a_i := 1-a_i$$$ for every $$$i$$$ such that $$$l \le i \le l+k-1$$$
Your task is to modify the array so that it contains no more than $$$\lfloor\frac{k}{2}\rfloor$$$ zeros.
Print the sequence of operations. If there are multiple answers, print any.
The first line contains two integers, $$$n$$$ and $$$k$$$, where $$$(1 \leq k \leq n \leq 10^6)$$$.
The second line contains $$$n$$$ integers, $$$a_i$$$, where $$$(0 \leq a_i \leq 1)$$$.
The first line contains a number, $$$m$$$, which represents the number of operations.
The second line contains $$$m$$$ integers, which represent the left side of each range.
If there are multiple answers, you can print any.
3 2 1 0 1
0
4 2 0 0 0 0
2 1 3
in the first test you don't need to do any operations.
in the second test you can just do operations in [1,2] and [3,4].
Mohammad Nour and Marcel are close friends. One day Nour borrowed from Marcel some money.
After a few weeks, Nour decided to return the money to his friend, But unfortunately Marcel forgot how much it was. We all know that Nour is a funny person so he took advantage of this opportunity and decided to play with Marcel.
He gave him a huge number $$$a$$$, and asked him to split this number into at least $$$k$$$ numbers (parts), such that each digit belongs to exactly one part and each part contains no more than 9 consecutive digits
The $$$GCD$$$ of the numbers Marcel got after making the operation above is the amount of money Nour borrowed.
Marcel is a cunning, he wants the answer to be maximal possible, so help him to split the number $$$a$$$ such that the $$$GCD$$$ of its parts as big as possible.
The greatest common divisor, $$$GCD(a,b)$$$, of two positive integers $$$a$$$ and $$$b$$$ is the biggest integer that is a divisor of both $$$a$$$ and $$$b$$$.
Please note that: $$$GCD(0,x) = x$$$
The first line of the input contains two integers $$$n$$$ and $$$k$$$ $$$(1 \le k \le {10^3}, 1 \le n \le {2 \times 10^3} )$$$ the length of $$$a$$$ and the minimum size of numbers Marcel should get.
The second line contains the number $$$a$$$ without leading zeros
Print -1 if Marcel can't split the number according to the conditions above. Otherwise print the maximum amount of money he can get.
8 2 63021002
2
9 3 303252015
15
3 4 150
-1
In the first test case, one of the optimal solutions is dividing the string into $$$630210$$$ and $$$02$$$ such that $$$GCD$$$ of them is $$$2$$$.
In the second test case, you can split the string into $$$30$$$, $$$32520$$$ and $$$15$$$.
Abo Abdo Smoothies is a famous smoothies shop in Damascus. Naseem likes his smoothies so much that he doesn't miss getting a fresh Emperor whenever he goes to Damascus (Like when he invited Moussa, Arthur and a fourth person who is not a judge so we can't mention their name, to a quick refreshing smoothie after the HIAST camp)
Abo Abdo has $$$m$$$ types of smoothies on their menu. Naseem went with his $$$n$$$ friends to Damascus and decided to pay Abo Abdo a visit. Naseem asked each friend about their preference and each friend $$$i$$$ chose one item $$$b_i$$$ from the menu as their preference.
Naseem went to place an order and totally forgot what his friends' preferences were, so he chose $$$n$$$ smoothies randomly, where the type of the $$$i_{th}$$$ smoothie he ordered is $$$a_i$$$, and went back to his friends.
To minimize the upset friends, Naseem is interested in finding the maximum number of friends that can possibly get the same smoothie as their preference. More formally, Naseem wants to distribute the $$$n$$$ smoothies he ordered on his $$$n$$$ friends so that the number of friends that their preference $$$b_i$$$ matches the smoothie they got $$$a_j$$$ is maximized.
Naseem is busy spending time with the fourth person. Can you find the number instead of him?
The first line of the input contains two space-separated integer numbers $$$n$$$ and $$$m$$$ $$$(1 \le n, m \le 10^5)$$$. The number of Naseem's friends and the number of types of smoothies Abo Abdo has on his menu, respectively.
The second line of the input contains $$$n$$$ space-separated integer numbers $$$a_1, a_2, \dots a_n$$$, where $$$a_i$$$ is the type of the $$$i_{th}$$$ smoothie Naseem ordered.
The third line of the input contains $$$n$$$ space-separated integer numbers $$$b_1, b_2, \dots b_n$$$, where $$$b_i$$$ is the type the $$$i_th$$$ friend prefers.
Print a single line containing a single integer number. The maximum number of friends that got a smoothie matching their preference.
33 21 1 22 2 13 11 1 11 1 14 42 3 2 24 1 1 4
2 3 0
In the first test case, Abo Abdo has two types of smoothies on their menu and Naseem has three friends. Naseem ordered two smoothies of type $$$1$$$ and one smoothie of type $$$2$$$, while two of his friends prefer the smoothie of type $$$2$$$ and one of his friends prefers the smoothie of type $$$1$$$. He can satisfy two friends, the one who prefers the first type and one of the friends who prefer the second type, leaving one friend who prefer second type with a smoothie of the first type, so the answer is $$$2$$$.
Yazan created a new game for us hopefully it's easy
You are given a binary grid with n rows and m columns. (each cell is $$$0$$$ or $$$1$$$), you can select one cell with value equal to $$$1$$$ and turn all its neighbors' value to $$$1$$$, you can only do this operation once (two cells are considered to be neighboring if they have a common edge or corner).
If you can turn all values to 1 print WIN otherwise print LOSE
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
In the above example we can select $$$cell(2,3)$$$ and turn all it's neighbors to $$$1$$$ so all values will be equal to $$$1$$$ ($$$cell(i,j)$$$ represent the cell in the i-th row and j-th column).
The first line contains two positive integers n and m ($$$ 1 \le n,m \le 500$$$) the number of rows and the number of columns, respectively.
The following $$$n$$$ lines contain $$$m$$$ integers each, the $$$j$$$-th element in the $$$i$$$-th line $$$a_{i,j}$$$ is the number written in the $$$j$$$-th cell of the i-th row ($$$ 0 \le a_{i,j} \le 1 $$$).
If you can turn all values to 1 print "WIN" (without quotes). Otherwise print "LOSE".
4 4 1 0 0 1 1 1 1 0 1 0 0 1 1 1 1 1
WIN
2 5 1 0 0 0 1 1 0 0 0 1
LOSE
KaitoKid is, obviously, a kid. He's interested in mathematics despite his young age. Today, he was trying to count.
KaitoKid starts counting from one. At the first second, he always says one. At each of the next seconds, he either says the next number of the one he said the second before, or gets lost and starts counting from one again.
More formally, KaitoKid will count for $$$n$$$ seconds. At each second $$$i$$$ he says the number $$$a_i$$$ where:
- If $$$i=1$$$, $$$a_i=1$$$.
- Otherwise, $$$a_i = 1$$$ or $$$a_i = a_{i-1} + 1$$$
As a grandmaster at a young age, that looked so easy to do, so he decided to find the sum of the sum of the $$$k$$$ lexicographically smallest arrays he could possibly say, modulo $$$10^9+7$$$
The first line of the input contains two space-separated integer numbers $$$n$$$ and $$$k$$$ $$$(1 \le n \le 10^5), (1 \le k \le 10^9)$$$
It is guaranteed that $$$k$$$ is always less than or equal to the number of possible arrays
Output a single integer number. The sum of the sum of the $$$k$$$ lexicographically smallest arrays he could possibly say modulo $$$10^9+7$$$
3 3
11
As $$$n = 3$$$, the possible arrays he can say in lexicographical order are:
- 1 1 1
- 1 1 2
- 1 2 1
- 1 2 3
Their sums are $$$3, 4, 4, 6$$$, respectively. The sum of the lexicographically smallest $$$3$$$ is $$$3+4+4 = 11$$$, Hence, the answer is $$$11$$$
Given three integers $$$a$$$, $$$b$$$ and $$$d$$$, find minimum non-negative integer k such that:
- $$$a.b^k$$$ is divisible by $$$d$$$
- $$$a+(b.k)$$$ is divisible by $$$d$$$
If such number doesn't exist print $$$-1$$$.
You have to answer $$$t$$$ independent test cases.
The first line contains one integer $$$t$$$ ($$$ 1 \le t \le 10^5$$$) — the number of queries.
Then q lines follow, each containing three integer $$$a_i, b_i$$$ and $$$d_i (1 \le a_i,b_i,d_i \le 10^9)$$$
For each query print one integer: the answer to this query.
If the answer does not exist, print $$$-1$$$.
612 1 42 6 124 2 82 4 89 3 272 6 64
0 -1 2 -1 6 21
The earth is a coordinate plane and your job is to protect it.
Given $$$K$$$ (the number of people on earth), you have to make a sheild to protect them.
Find the minimum integer radius of a circle which is centered in the $$$(0,0)$$$ coordinates and can contain $$$K$$$ person knowing that a person can only stand on integer coordinates and two people can't stand in the same spot.
Note 1: A person can stand in the center of the circle.
Note 2: The person is considered protected if he's inside the cricle or at the boundary of the circle.
The only line contains one integer $$$K$$$ ($$$ 2 \le K \le 10^9$$$) — the number of people on earth.
Print one integer: the minimum integer circle radius that we need to protect all $$$K$$$ citizens of the earth.
2
1
6
2
13
2
Kubernetes is a container orchestration system for automating software deployments, and google wants your help to maintain a highly available Kubernetes cluster.
A Kubernetes cluster is a group of $$$N$$$ nodes (machines) that are used to run applications, each node has a capacity of $$$c_i$$$ pods (a pod is an instance of an application).
We have $$$M$$$ applications and each application has a number of pods $$$a_j$$$ that needs to be run on the cluster to make sure that its users have a nice experience, for example a widely used application like google search must have a lot of instances running, while another small application like google keep doesn't need that much instances to keep users happy.
We define for each application a value called $$$availability_j$$$ which is equal to the minimum number of pods from the application $$$j$$$ running on the same node after distrubution for example:
Here we have 3 nodes with capacities $$$5,4,5$$$ respectively and 3 applications:
- Application 1: 7 pods (1 to 7) with availability of 2 (node 2 is only running 2 pods from this application)
- Application 2: 5 pods (8 to 12) with availability of 1 (all nodes are running 2 pods from this application except for node 2)
- Application 3: 1 pod (pod 13) with availabilito of 0 (there is only one pod in node 3 so nodes 1 and 2 have zero pods running from this application)
Now your job is determine the maximum possible value for $$$\min_{1 \le j \le M}(availability_j)$$$
Note: Its guaranteed that all applications can be deployed in the cluster
The first line of the input contains $$$N$$$ and $$$M$$$ ($$$1 \le N,M \le 10^5$$$) the number of nodes, and the number of applications respectively.
The second line of the input contains $$$N$$$ integer representing the capacity of each node ($$$1 \le c_i \le 10^9$$$)
The third line of the input contains $$$M$$$ integer representing the number of pods ($$$1 \le a_j \le 10^9$$$)
Its guaranteed that $$$\sum_{j=1}^{j=M}{a_j} \le \sum_{i=1}^{i=N}{c_i}$$$
Print one integer that represents the maximum possible value for $$$\min_{1 \le j \le M}(availability_j)$$$
3 3 5 4 5 7 5 1
0
4 3 9 9 8 9 8 10 10
2
Kaitokid is afraid of fish and has never been on a lake trip because of it. However, his friends want to surprise him with a lake trip, but they need to find a lake with no fish so that Kaitokid can join them.
Help Kaitokid's friends plan a surprise lake trip by determining which lakes are suitable for him to visit.
You are given the number of fish in each lake. For each lake, determine whether it is suitable for Kaitokid to visit or not. If a lake has no fish, it is suitable for Kaitokid to visit. Otherwise, it is not suitable for him to visit.
The first line of the input contains an integer $$$T$$$ $$$(1 \le T \le 10^4)$$$, the number of lakes.
For each lake you are given a single integer $$$x$$$ $$$(0 \le x \le 100)$$$, representing the number of fish in that lake.
For each lake, print YES if it is suitable for kaitokid to visit; otherwise, print NO.
You may print each letter in any case (YES, yes, Yes will all be recognized as positive answer, NO, no and nO will all be recognized as negative answer).
3150
No No Yes