Once upon a time in a boring class of electronic systems, $$$\textit{Kifah}$$$ and $$$\textit{Ali}$$$ were sitting there talking about the problem set of Al-Baath contest. Kindhearted $$$\textit{Ali}$$$ came up with a cute probability problem and told $$$\textit{Kifah}$$$ about it. Since $$$\textit{Kifah}$$$ doesn't like cute problems, he couldn't prevent himself from making some changes to make it a little bit harder. And here is the problem.
In this problem, you will be given an array $$$a_1,a_2,...,a_n$$$. Imagine an array $$$b_1,b_2,...,b_n$$$ where $$$b_i \in [1, a_i]$$$ with a uniform distribution. A subarray of $$$b$$$ is one of its contiguous subsequences (i.e. an array $$$[b_l,b_{l+1},...,b_r]$$$ for some integers $$$l$$$ and $$$r$$$ such that $$$1 \le l \le r \le n$$$).
We define the function $$$f(l, r, x)$$$ of the subarray $$$[b_l,b_{l+1},...,b_r]$$$ as the probability of $$$max([b_l,b_{l+1},...,b_r]) \le x$$$.
You will be asked two types of queries:
- Type 1: replace $$$a_p$$$ with $$$v$$$ for the given integers $$$p$$$ and $$$v$$$.
- Type 2: find $$$f(l, r, x)$$$ for the given integers $$$l$$$, $$$r$$$, and $$$x$$$.
It can be shown that this answer can always be expressed as a fraction $$$P/Q$$$ where $$$P, Q$$$ are coprime integers and $$$Q \neq 0 \bmod 10^9+7$$$. Output the value of $$$(P \cdot Q^{-1})$$$ modulo $$$10^9+7$$$.
The first line contains a single integer $$$Tc$$$ $$$(1 \le Tc \le 10^5)$$$ — the number of test cases.
The first line of each test case contains a single integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ — the size of the array $$$a$$$.
The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ $$$(1 \le a_i \le 10^5)$$$.
The third line of each test case contains a single integer $$$q$$$ $$$(1 \le q \le 10^5)$$$ — the number of queries.
Each of the following $$$q$$$ lines has one of two types:
- Type 1: $$$1$$$ $$$p$$$ $$$v$$$ where $$$(1 \le p \le n,$$$ $$$ 1 \le v \le 10^5)$$$ — the position of the replaced integer and the new value, respectively.
- Type 2: $$$2$$$ $$$l$$$ $$$r$$$ $$$x$$$ where $$$(1 \le l \le r \le n,$$$ $$$ 1 \le x \le 10^5)$$$ — the required parameters to define $$$f(l, r, x)$$$.
It is guaranteed that the sum of $$$n$$$ and $$$q$$$ over all test cases doesn't exceed $$$10^5$$$.
For each query of the type $$$2$$$, print $$$f(l, r, x)$$$.
131 2 321 2 62 1 3 3
500000004
1532 45 12 43 3652 1 5 172 2 4 131 3 10002 1 4 402 2 5 55
242668409 929198973 340051682 135000001
You are given three integers $$$x, y, z$$$ and a string $$$S$$$ consisting of $$$n$$$ lowercase English letters.
For four integers $$$l_1$$$, $$$r_1$$$, $$$l_2$$$, $$$r_2$$$ where $$$(1 \lt l_1 \le r_1 \lt l_2 \le r_2 \lt n)$$$, let's define the function $$$F$$$ as follows:
You need to find four integers $$$l_1, r_1, l_2, r_2$$$ where $$$(1 \lt l_1 \le r_1 \lt l_2 \le r_2 \lt n)$$$ that maximize the value $$$F(l_1, r_1, l_2, r_2)$$$ and satisfy the following conditions:
- The substring $$$S[l_1 ... r_1]$$$ is equal to a prefix of the string $$$S$$$.
- The substring $$$S[l_2 ... r_2]$$$ is equal to a suffix of the string $$$S$$$.
Note that $$$S[l...r]$$$ is a substring of the string $$$S$$$ that starts from position $$$l$$$ and ends at position $$$r$$$, more formally $$$S[l...r] = S_{l} S_{l+1} ... S_{r-1} S_{r}$$$, and if $$$l \gt r$$$ then $$$S[l..r]$$$ is an empty string.
If there are no integers $$$l_1, r_1, l_2, r_2$$$ satisfying the mentioned conditions, print $$$0$$$.
The first line contains four integers $$$n,x,y,z$$$ $$$(4 \le n \le 10^6, 1 \le x,y,z \le 10^9)$$$ — where $$$n$$$ is the number of letters in the string $$$S$$$.
The second line contains the string $$$S$$$, consisting of $$$n$$$ lowercase English letters.
Output a single integer — the maximum possible value of the function $$$F$$$, and if there are no integers $$$l_1, r_1, l_2, r_2$$$ satisfying the mentioned conditions, print 0.
14 5 10 1abreabqqytpsyt
32
5 2 3 5aaaaa
10
In the first test, the four integers are $$$l_1 = 5, r_1 = 6, l_2 = 9, r_2 = 10$$$.
$$$S[5...6] = ab$$$ which equals to a prefix of $$$S$$$.
$$$S[9...10] = yt$$$ which equals to a suffix of $$$S$$$.
$$$(6-5)*5 + (10-9)*10 + (9-6)*1 + 10 + 5 - 1 = 32$$$.
You are given a grid of $$$(n * m)$$$ points , each point contains a hidden box. When you collect it, you either gain some experience points "XPs" , or you lose some for being a horrible greedy player.
The grid has a guardian who won't let you take more than $$$k$$$ boxes. Moreover, each $$$n$$$ points forming a column has its own guardian. This guardian won't let you open more than $$$i$$$ boxes in the column numbered $$$i$$$ (in column number $$$x$$$, you can collect at most $$$x$$$ boxes).
You want to level-up, so you want to gather as much XPs as possible.
* Columns are indexed $$$1$$$ based ($$$i$$$ : $$$1$$$ $$$2$$$ $$$3$$$ ... $$$m$$$)
The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ $$$(1 \le n*m \le 10^6) , (0 \le k \le n*m)$$$, the dimensions of the grid and the maximum number of boxes you can take.
Follow $$$n$$$ lines, each containing $$$m$$$ separated integers: $$$ a_{i1} , a_{i2} , ... , a_{im}$$$ $$$(-10^9 \le a_{ij} \le 10^9)$$$, the value of each box in the grid.
Print a single integer, the maximum amount of XPs you can get.
1 1 1 1000
1000
5 2 10 8 6666 5 1000 6 8457 9699 88889 125 0
107045
3 3 6 2 -1 5 -2 3 3 4 5 6
26
Aghiad and Aram love math so much. They consider playing video games, sports, and any other activity rather than math a waste of time. But sometimes they get bored from their math problems and want to do something fun without wasting their time. To kill boredom, they came up with a math game that will let them have some fun and waste no time. They write down an array consisting of $$$n$$$ integers. They play in turns, in each turn:
- First, Aghiad can choose an element at position $$$i$$$ $$$(1 \le i \lt n)$$$.
- Then Aram can choose an element at position $$$j$$$ $$$(i \lt j \le n)$$$.
The first line of the input contains a single integer $$$t$$$ ($$$1 \le T \le 10^4 $$$) — the number of test cases in the test.
The first line of each case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of elements in the array.
The second line of each case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_j \le 10^9$$$) — the elements of the array.
It is guaranteed that the sum of the values of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output the score that Aghiad and Aram would achieve if they play the game.
232 1 133 3 2
1 3
In the first testcase:
In the second testcase, all the pairs satisfy the condition of getting a point.
$$$\textit{Kifah}$$$ heard that some contestants in Al-Baath University doesn't know how to read an integer in c++. So he prepared a hard test to find out.
you will read an integer $$$n$$$, so we make sure you are a good programer. Then, you can ask the jury the verdict you want. You can print "AC" (without quotes) if you want "Accepted" verdict, or you can print any thing else.
The only line has one integer $$$n$$$ $$$(1 \le n \le 1000)$$$ some nonsense integer.
Print "AC" (without quotes) if you want "Accepted" verdict. Otherwise, print any thing.
Hint: You are here to get Accepted.
5
AC
$$$Abdullah$$$ and his friend $$$Kifah$$$ live in a real country called $$$BP$$$, which has $$$n$$$ cities that can be described as a weighted tree rooted at node $$$1$$$.
$$$kifah$$$ wants to buy some presents for his girlfriend but unfortunately he doesn't have any money, so he will borrow some money from his friend $$$Abdullah$$$.
$$$Abdullah$$$ is a good friend, so he will help $$$Kifah$$$.
Abdullah works as a TAXI driver. For a ride from city $$$a$$$ to city $$$b$$$ (note that city $$$b$$$ must be in the subtree of the $$$a$$$, more formally the city $$$a$$$ must lie on the simple path between city $$$1$$$ and city $$$b$$$), $$$Abdullah$$$ earns an amount of money equal to the sum of weights in the simple path between $$$a$$$ and $$$b$$$ , and he spends hours equal to the number of edges in the simple path between $$$a$$$ and $$$b$$$.
$$$Kifah$$$ loves his girlfriend so much and wants to buy her $$$q$$$ presents.
$$$Abdullah$$$ will give you the construction of the country and then for each present he will tell you the city $$$city_i$$$ that he is currently located in and the price $$$p_i$$$ of the present that $$$Kifah$$$ wants to buy. Can you tell him the minimum possible number of hours required to make money more than or equal to $$$p_i$$$. If it's impossible to earn that amount of money just print $$$-1$$$.
The first line contains an integer $$$n (1 \le n \le 10^5)$$$, the number of the cities in $$$BP$$$.
The next $$$n-1$$$ lines describe the roads. The $$$i_{th}$$$ line contains three integers $$$u_i$$$, $$$v_i$$$ and $$$w_i$$$ $$$(1 \le u_i,v_i \le n, u_i \neq v_i, 1 \le w_i \le 10^9 )$$$, meaning that there is an edge between the nodes $$$u_i$$$ and $$$v_i$$$ with weight $$$w_i$$$.
The next line contains a single integer $$$q$$$ $$$(1 \le$$$ $$$q \le 10^5)$$$, the number of presents that $$$Kifah$$$ wants to buy for his girlfriend.
For the following $$$q$$$ lines, the $$$i_{th}$$$ line contains two integers $$$city_i, p_i$$$ $$$(1 \le city_i \le n, 1 \le p_i \le 10^{18})$$$ meaning that $$$Abdullah$$$ will start from $$$city_i$$$ and wants to earn an amount of money more than or equal to $$$p_i$$$.
For each present, print the minimum possible number of hours required to make money more than or equal to $$$p_i$$$ if $$$Abdullah$$$ started the ride from $$$city_i$$$, or if it's impossible to earn that amount of money, just print $$$-1$$$.
51 2 32 3 42 4 23 5 631 62 115 2
2 -1 -1
To buy the first present, $$$Abdullah$$$ can go from city $$$1$$$ to city $$$3$$$ spending $$$2$$$ hours, and earning an amount of money equal to $$$7$$$ which is greater than $$$6$$$.
For the second present, the maximum amount of money $$$Abdullah$$$ can earn is $$$10$$$ by having a ride to the city $$$5$$$, $$$10$$$ is lower than $$$11$$$, so the answer is $$$-1$$$.
For the third present, $$$Abdullah$$$ can't go to any city (because there are no cities in the subtree of the city $$$5$$$), so the answer is $$$-1$$$.
$$$Da7doo7$$$ believed he had mastered competitive programming contests, so he decided to turn his attention to playing basketball.
$$$Da7doo7$$$ intends to shoot $$$n$$$ balls into the basket. The probability of him scoring the first shot is $$$\frac{p_0}{q_0}$$$.
For subsequent shots, his probability of scoring depends on whether he made the previous shot or not:
If he scored shot $$$i-1$$$, the probability of scoring shot $$$i$$$ is $$$\frac{p_1}{q_1}$$$.
If he missed shot $$$i-1$$$, the probability of scoring shot $$$i$$$ is $$$\frac{p_2}{q_2}$$$.
$$$Da7doo7$$$ is asking for your help to find the expected value of the number of balls that will score.
We can show that the answer can be written in the form $$$\frac{P}{Q}$$$ where $$$P, Q$$$ are coprime integers and $$$Q \neq 0 \bmod 998244353$$$. Output the value of $$$(P \cdot Q^{-1})$$$ modulo $$$998244353$$$.
The first line contains a single integer $$$T$$$ ($$$1 \le T \le 5 \times 10^4$$$) — the number of testcases.
The first line of each testcase contains an integer $$$n$$$ ($$$1 \le n \le 10^{12}$$$) — the number of balls he will shoot.
The second line of each testcase contains six integers $$$p_0,q_0,p_1,q_1,p_2,q_2$$$ ($$$0 \le p_0,p_1,p_2 \le 10^{3}$$$ , $$$1 \le q_0,q_1,q_2 \le 10^{3}$$$).
An integer representing the expected value of the number of balls that will score, modulo $$$998244353$$$.
525 10 2 10 3 10107 10 5 10 2 1051 5 7 10 9 101001 1 1 10 1 110000000075 100 55 100 23 100
249561089 965715715 403450441 210477862 330198862
$$$Ali$$$ wanted to make a very hard problem, so he thought really hard and after a week of continuous work, he came up with this problem:
You have a set $$$M$$$ containing all numbers from $$$1$$$ to $$$n$$$. In one operation, you can choose an integer $$$x$$$ and subtract it from all numbers that are greater than or equal to it. If a number becomes zero, you remove it from the set. What is the minimum number of operations required to make the set empty?
The only line of input contains one integer $$$n$$$ $$$(1 \le n \le 100)$$$ ,as described in the problem.
Print one integer, the minimum number of operations required to make the set empty.
1
1
2
2
47
6
In the first example, the set is $$$\{1\}$$$ so we choose $$$x=1$$$, and after this operation, the set will be empty.
In the second example, the set is: $$$\{1,2\}$$$, we can choose $$$x=2$$$ so the set will become: $$$\{1\}$$$ ,and after that we choose $$$x=1$$$.
The setter of this problem hates long statements' problems, so the problem is:
The Score of array $$$b$$$ of size $$$m$$$ equals: $$$$$${\sum_{i = 1}^{m-1} gcd(b_i,b_{i+1})}$$$$$$
You are given an array $$$a$$$ of $$$n$$$ integers and an integer $$$k$$$.
You need to find a non-empty subsequence $$$a_{i_1}$$$, $$$a_{i_2}$$$, ..., $$$a_{i_m}$$$ with maximum Score such that:
$$$i_j \lt i_{j+1}$$$ and $$$i_{j+1}$$$ - $$$i_j$$$ $$$\le$$$ $$$k$$$ for all 1 $$$\le$$$ $$$j$$$ $$$\le$$$ $$$m - 1$$$.
Print the Score of this subsequence.
The first line contains a single integer $$$t (1 \le t \le 100)$$$ — the number of testcases.
Then the descriptions of t testcases follow.
The first line of each testcase contains two integers $$$n$$$ and $$$k$$$— the size of the array $$$a$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) and $$$k$$$ explained above ($$$1 \le k \le n - 1$$$).
The second line consists of $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 4 \cdot 10^5$$$). It's guaranteed that the sum of $$$n$$$ over all testcases won't exceed $$$2 \cdot 10^5$$$.
Output for each testcase the maximum Score.
25 12 4 8 16 325 22 4 1 16 32
30 22
In an imaginary country called IM, there are $$$n$$$ cities and $$$m$$$ directed roads. However, these roads may not connect all the cities.
$$$\textit{Kifah}$$$ has been a resident of IM for many years and knows the country well. On a sunny morning, while chatting with his friend $$$\textit{Abdullah}$$$, a claim was made. $$$\textit{Abdullah}$$$ stated that he had moved to IM but was unsure of his exact location. Skeptical, $$$\textit{Kifah}$$$ didn't believe him and demanded proof. In response, $$$\textit{Abdullah}$$$ provided a set of city pairs, asserting that for each pair, there exists a path starting from the first city and ending at the second, passing through $$$\textit{Abdullah's}$$$ current city.
Can you help $$$\textit{Kifah}$$$ to check if there is any contradiction in $$$\textit{Abdullah's}$$$ claims.
In this Problem you will be given a graph consists of $$$n$$$ nodes and $$$m$$$ directed edges. Note that the graph may not be connected, but it is guaranteed that there is no multi-edges or self-loops.
Then you will be given a set of $$$q$$$ pairs of nodes $$$(a, b)$$$ that claims: there is a path starts from $$$a$$$, ends at $$$b$$$ and passes by the city where $$$\textit{Abdullah}$$$ is. These paths may traverse nodes or roads multiple times.
Your goal is to help $$$\textit{Kifah}$$$ determine whether $$$\textit{Abdullah's}$$$ claims hold without contradiction, thus verifying his honesty.
The first line contains a single integer $$$Tc$$$ $$$(1 \le Tc \le 5 \cdot 10^4)$$$ — the number of test cases.
The first line of each test case contains two integers $$$n, m$$$ $$$(1 \le n \le 5 \cdot 10^4,$$$ $$$1 \le m \le min(n \cdot (n-1), 10^5))$$$ — the number of vertices and edges in the graph respectively.
For the following $$$m$$$ lines, each line contains two integers $$$(u, v)$$$ $$$(1 \le u,$$$ v $$$\le n)$$$, describing a directed edge from vertex $$$u$$$ to vertex $$$v$$$. It is guaranteed that there are no multi-edges or self-loops in the graph.
The next line contains a single integer $$$q$$$ $$$(1 \le q \le 5 \cdot 10^4)$$$, the number of pairs $$$\textit{Abdullah}$$$ provided.
For the following $$$q$$$ lines, each line contains two integers $$$(a, b)$$$ $$$(1 \le a,$$$ b $$$\le n)$$$, describing a claim that says: There is a path starts from $$$a$$$, ends at $$$b$$$ and pass by the city where $$$\textit{Abdullah}$$$ is. These paths may traverse nodes or roads multiple times.
It is guaranteed that both the sum of $$$n$$$ and $$$q$$$ over all test cases doesn't exceed $$$5 \cdot 10^4$$$.
It is guaranteed that the sum of $$$m$$$ over all test cases doesn't exceed $$$10^5$$$.
For each test case, output "YES" (without quotes) if $$$\textit{Kifah}$$$ can't find any contradiction in $$$\textit{Abdullah's}$$$ claims, and "NO" (without quotes) otherwise.
24 31 22 33 421 32 45 41 22 34 35 321 35 4
YES NO
In the first testcase, both nodes $$$2$$$ and $$$3$$$ meet the claims. For node $$$2$$$ the path $$$1 \rightarrow 2 \rightarrow 3$$$ meets the first pair $$$(1, 3)$$$, and the path $$$2 \rightarrow 3 \rightarrow 4$$$ meets the second pair $$$(2, 4)$$$. So we can't say that $$$\textit{Abdullah}$$$ is a Liar, that's why we provide "YES".
In the second testcase, there is no node that meets the constraints. For the first pair in the constraints $$$(1, 3)$$$ the only path that meets this constraint is $$$1 \rightarrow 2 \rightarrow 3$$$. On the other hand, for the second pair in the constraints $$$(5, 4)$$$, there is no path that can start from $$$5$$$ and end at $$$4$$$. So we can say that $$$\textit{Abdullah}$$$ is a Liar because there is a contradiction, that's why we provide "NO".
$$$Ali$$$ is playing a very boring game called BOX. In this game, you have a box that contains $$$x$$$ coins, and there is a road which contains $$$n$$$ checkpoints where you can get or lose coins. The road can be represented as an array $$$a$$$ containing $$$n$$$ integers where $$$a_i$$$ represents the amount of coins that you may gain or lose at the $$$ith$$$ checkpoint. You start at the beginning of the road "at index $$$0$$$". The game goes as follows:
You start at index zero with an initial amount of coins equals to $$$x$$$. You start visiting the checkpoints from left to right without skipping any of them and with the capability of ending the game any time you want.
At each checkpoint, you get or lose an amount of coins defined by $$$a_i$$$. If at any point, the total amount of coins you have becomes negative, you lose the game.
You can do this operation only for once: pay $$$c$$$ coins "if you have them" and choose an index $$$i$$$ where $$$i$$$ is after your current checkpoint, then reverse the subsegment $$$[i,n]$$$.
The goal of the game is to maximize the amount of coins you have. Ali isn't very good at this kind of game (he only plays shooters) so he asked you to help him. Can you find the maximum amount of coins Ali can get?
The first line contains three integers: $$$n,x,c$$$ $$$(1 \le n \le 10^6) , (0 \le x,c \le 10^9)$$$, number of checkpoints, the initial value of coins in the box, and the cost of flipping a segment.
The second line contains $$$n$$$ integers, $$$a_1 , a_2, ... , a_n$$$ $$$(-10^9 \le a_i \le 10^9)$$$
Print one integer, the maximum amount of coins Ali can get.
4 0 1 1 -2 3 4
7
13 19 22 12 30 -1 15 -55 -9 17 5 -4 6 -15 10 15
87
In the first example, we move to the first checkpoint and add it to $$$x$$$, so now $$$x=1$$$, then we pay $$$c=1$$$ and flip the subsegment $$$[2,4]$$$, so the array becomes: $$$[$$$$$$1$$$ $$$4$$$ $$$3$$$ $$$-2$$$$$$]$$$, now we move to the second and the third checkpoints and then we end the game, so the final result will be: $$$x=0+1-1+4+3=7$$$.