Mr. Rumb visits a prosthetist because his arms have gone numb. The prosthetist can assemble replacements, but their numbered components are out of order. Apparently, even getting a helping hand requires some assembly.
Formally, the labels on the components form a permutation$$$^{\text{∗}}$$$ $$$p$$$ of length $$$n$$$. Mr. Rumb can program a machine to perform the following operation exactly once:
The chosen indices do not have to be consecutive. For example, suppose $$$p = [1, {\color{red}{6}}, 3, {\color{red}{4}}, 5, {\color{red}{2}}]$$$. If you choose indices $$$2$$$, $$$4$$$, and $$$6$$$, the elements shown in red are reversed, and $$$p$$$ becomes $$$[1, {\color{red}{2}}, 3, {\color{red}{4}}, 5, {\color{red}{6}}]$$$.
Determine whether Mr. Rumb can sort $$$p$$$ in increasing order.
$$$^{\text{∗}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$).
The second line contains a permutation $$$p_1, p_2, \ldots, p_n$$$ of the integers from $$$1$$$ to $$$n$$$.
For each test case, output YES if it is possible to sort $$$p$$$ in increasing order after performing exactly one operation. Otherwise, output NO.
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.
51144 2 3 143 4 1 252 1 3 5 461 6 3 4 5 2
YESYESNONOYES
In the first test case, choose the only index. Reversing a single element does not change the permutation, so the requirement to perform exactly one operation is satisfied.
In the second test case, choose indices $$$1$$$ and $$$4$$$. The resulting permutation is $$$[1, 2, 3, 4]$$$.
In the fifth test case, choose indices $$$2$$$, $$$4$$$, and $$$6$$$. Notice that the chosen indices are not consecutive.
Mr. Knife has drafted $$$n$$$ absurd posts for a channel on a chat platform. His goal is to farm pill emoji reactions. Unfortunately, the channel's pill-farming bot uses an unnecessarily elaborate scoring rule.
The drafts have absurdity ratings $$$a_1, a_2, \ldots, a_n$$$, which may be negative. Mr. Knife must publish exactly $$$m$$$ drafts in their original order. Their ratings form a subsequence$$$^{\text{∗}}$$$ $$$b$$$ of $$$a$$$ with length $$$m$$$.
His pill score starts at $$$0$$$. When he publishes the $$$i$$$-th chosen draft, the bot changes his score by $$$i \cdot (b_i - b_{i-1})$$$, where $$$b_0 = 0$$$. A negative change deducts points, and the score is allowed to become negative. Thus, his final pill score is $$$$$$ \sum_{i = 1}^{m} i \cdot (b_i - b_{i - 1}). $$$$$$
What is the maximum pill score Mr. Knife can obtain by choosing which drafts to publish?
$$$^{\text{∗}}$$$A sequence $$$a$$$ is a subsequence of a sequence $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) elements from arbitrary positions.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le m \le n \le 2 \cdot 10^5$$$) — the number of drafts and the number of posts Mr. Knife must publish.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^7 \le a_i \le 10^7$$$) — the absurdity ratings of the drafts.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, print one integer — the maximum pill score Mr. Knife can obtain by publishing exactly $$$m$$$ drafts in their original order.
65 30 8 1 7 34 30 -4 10 -24 20 5 -2 46 30 9 8 7 6 51 173 25 -100 4
203410157108
In the first test case, Mr. Knife can publish the drafts with ratings $$$[0, 1, 7]$$$. His final pill score is $$$$$$ 1 \cdot (0 - 0) + 2 \cdot (1 - 0) + 3 \cdot (7 - 1) = 20. $$$$$$
In the second test case, he can publish the drafts with ratings $$$[0, -4, 10]$$$. The second post deducts points, but the third post more than makes up for it. His final pill score is $$$$$$ 1 \cdot (0 - 0) + 2 \cdot (-4 - 0) + 3 \cdot (10 - (-4)) = 34. $$$$$$
Madam Madamant is expecting a baby and already planning a skating dynasty in which every parent is a stronger skater than their children.
Formally, Madamant has $$$n$$$ labeled skaters. Skater $$$v$$$ has an integer rating $$$a_v$$$, and all ratings are pairwise distinct. A possible dynasty is represented by a rooted tree on these skaters.
Let $$$r$$$ be the root of the tree. For every skater $$$v \ne r$$$, let $$$p_v$$$ be the parent of $$$v$$$. The dynasty is valid if $$$a_v \lt a_{p_v}$$$ for every $$$v \ne r$$$.
The cost of a valid dynasty is $$$$$$ \sum_{v \ne r} (a_{p_v} - a_v). $$$$$$
Two dynasties are different if their roots are different or if the parent of at least one skater is different.
Find the sum of the costs of all valid dynasties Madamant can form, modulo $$$998\,244\,353$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of skaters.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — their ratings.
It is guaranteed that all $$$a_i$$$ are pairwise distinct.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, print one integer — the sum of the costs of all valid dynasties, modulo $$$998\,244\,353$$$.
511031 2 344 1 3 221 100000000052 7 1 10 4
05271755646414
In the second test case, the skater with rating $$$3$$$ must be the root. The parent of the skater with rating $$$2$$$ must be the skater with rating $$$3$$$, while the skater with rating $$$1$$$ can choose either of the other skaters as their parent. The two valid dynasties have costs $$$2$$$ and $$$3$$$, so the answer is $$$5$$$.
In the fourth test case, there is only one valid dynasty. Its cost is $$$10^9 - 1 = 999\,999\,999$$$, whose remainder modulo $$$998\,244\,353$$$ is $$$1\,755\,646$$$.
Someone has chopped up Dr. Agos's chickens. Furious, he turns to the one thing that still brings him comfort: his OLED screen. Today, he wants almost all of it black.
The screen has a single row of $$$n$$$ pixels. Its pattern is represented by a binary string $$$s$$$; $$$s_i = 0$$$ means that the $$$i$$$-th pixel is dark, and $$$s_i = 1$$$ means that it is lit.
Dr. Agos finds a contiguous segment of pixels irritating if, when read from left to right as a binary integer, its value is divisible by $$$3$$$. More precisely, the segment from position $$$l$$$ to position $$$r$$$ ($$$1 \le l \le r \le n$$$) has value $$$$$$ \sum_{i=l}^{r} s_i \cdot 2^{r-i}. $$$$$$ Leading zeroes are allowed. A segment consisting only of dark pixels has value $$$0$$$, which is also divisible by $$$3$$$.
Let $$$f(s)$$$ be the number of irritating segments. Segments with different pairs of endpoints $$$(l,r)$$$ are counted separately, even if their pixel patterns are identical.
Dr. Agos wants a pattern with at most three lit pixels that minimizes $$$f(s)$$$ among all binary strings of length $$$n$$$, including strings with more than three ones. Help him construct such a pattern.
We can show that an answer always exists.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.
The only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of pixels in the row.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, print a binary string $$$s$$$ of length $$$n$$$ describing Dr. Agos's screen. It must contain at most three ones and minimize $$$f(s)$$$ among all binary strings of length $$$n$$$.
If there are multiple solutions, print any of them.
6123456
1 11 101 0101 10101 010100
For $$$n=1$$$, Dr. Agos can light the only pixel, giving $$$s=\mathtt{1}$$$. The only segment has value $$$1$$$, so it is not irritating and $$$f(s)=0$$$.
For $$$n=2$$$, he can light both pixels, giving $$$s=\mathtt{11}$$$. The whole row has binary value $$$3$$$ and is irritating, while each individual pixel has value $$$1$$$. Thus, $$$f(s)=1$$$. Every binary string of length $$$2$$$ has at least one irritating segment, so this is optimal.
The displayed patterns are not necessarily unique.
This is the Easy version of the problem. The difference between the versions is that in this version, $$$1 \le n \le 3000$$$. You can hack only if you solved all versions of this problem.
Antigun and Lamus have flooded Madamant's house. She wants them to make the water levels equal while removing as little water as possible.
Formally, the initial water levels are given by an array $$$a = [a_1, a_2, \ldots, a_n]$$$. For each hypothetical cleanup, Antigun and Lamus select a non-empty subsequence$$$^{\text{∗}}$$$ $$$b$$$ of $$$a$$$. They may perform the following operation on $$$b$$$ any number of times, possibly zero:
Let $$$f(b)$$$ be the maximum integer $$$x$$$ such that, after some sequence of operations, every element of $$$b$$$ is equal to $$$x$$$.
Find the sum of $$$f(b)$$$ over all non-empty subsequences $$$b$$$ of $$$a$$$, modulo $$$998\,244\,353$$$. Subsequences formed by different choices of indices are counted separately, even if their values are equal.
Each subsequence is considered independently, starting from its original values.
$$$^{\text{∗}}$$$A sequence $$$a$$$ is a subsequence of a sequence $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) elements from arbitrary positions.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 3000$$$). The description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3000$$$) — the length of the array $$$a$$$.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the elements of $$$a$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3000$$$.
For each test case, print one integer — the sum of $$$f(b)$$$ over all non-empty subsequences $$$b$$$ of $$$a$$$, modulo $$$998\,244\,353$$$.
41142 4 4 442 3 4 463 6 1 1 1 1
1373472
In the first test case, the only non-empty subsequence is $$$[1]$$$, and no operation is needed. Therefore, its contribution is $$$f([1]) = 1$$$.
In the second test case, the $$$2^3 - 1 = 7$$$ non-empty subsequences containing only occurrences of $$$4$$$ contribute $$$4 \cdot 7 = 28$$$. The subsequence $$$[2]$$$ contributes $$$2$$$. Each of the $$$7$$$ subsequences containing the value $$$2$$$ and at least one occurrence of $$$4$$$ has $$$f(b) = 1$$$. Hence, the answer is $$$28 + 2 + 7 = 37$$$.
This is the Hard version of the problem. The difference between the versions is that in this version, $$$n \le 3\cdot 10^5$$$. You can hack only if you solved all versions of this problem.
Antigun and Lamus have flooded Madamant's house. She wants them to make the water levels equal while removing as little water as possible.
Formally, the initial water levels are given by an array $$$a = [a_1, a_2, \ldots, a_n]$$$. For each hypothetical cleanup, Antigun and Lamus select a non-empty subsequence$$$^{\text{∗}}$$$ $$$b$$$ of $$$a$$$. They may perform the following operation on $$$b$$$ any number of times, possibly zero:
Let $$$f(b)$$$ be the maximum integer $$$x$$$ such that, after some sequence of operations, every element of $$$b$$$ is equal to $$$x$$$.
Find the sum of $$$f(b)$$$ over all non-empty subsequences $$$b$$$ of $$$a$$$, modulo $$$998\,244\,353$$$. Subsequences formed by different choices of indices are counted separately, even if their values are equal.
Each subsequence is considered independently, starting from its original values.
$$$^{\text{∗}}$$$A sequence $$$a$$$ is a subsequence of a sequence $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) elements from arbitrary positions.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 300\,000$$$) — the length of the array $$$a$$$.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the elements of $$$a$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$300\,000$$$.
For each test case, print one integer — the sum of $$$f(b)$$$ over all non-empty subsequences $$$b$$$ of $$$a$$$, modulo $$$998\,244\,353$$$.
41142 4 4 442 3 4 463 6 1 1 1 1
1373472
In the first test case, the only non-empty subsequence is $$$[1]$$$, and no operation is needed. Therefore, its contribution is $$$f([1]) = 1$$$.
In the second test case, the $$$2^3 - 1 = 7$$$ non-empty subsequences containing only occurrences of $$$4$$$ contribute $$$4 \cdot 7 = 28$$$. The subsequence $$$[2]$$$ contributes $$$2$$$. Each of the $$$7$$$ subsequences containing the value $$$2$$$ and at least one occurrence of $$$4$$$ has $$$f(b) = 1$$$. Hence, the answer is $$$28 + 2 + 7 = 37$$$.
Hacks are disabled on this problem.
We are excited to introduce a new language for this Codeforces round: the Deranged Calculator language (DC).
The DC language is a simplified programming language with some weird constraints. It only supports a single expression on one line and only has a single positive integer $$$n$$$ as input. The syntax of the expression is similar to that of most programming languages (in fact, the expression is valid Python), but it is very limited:
A derangement of $$$n$$$ numbers is a permutation of those numbers in which none of the numbers appears in its original position. For example, the derangements of the sequence $$$[1, 2, 3]$$$ are $$$[2, 3, 1]$$$ and $$$[3, 1, 2]$$$.
You are given a single integer $$$k$$$. Your job is to make a valid DC program that, for every integer $$$n$$$ ($$$2 \le n \le k$$$), calculates the number of derangements of the sequence $$$[1, 2, \ldots, n]$$$, when $$$n$$$ is given as input to the DC program. The length of the program should not exceed $$$10\,000$$$ characters.
A local testing tool is provided to help you develop your solution. It can be found under Contest Materials.
The only line of input contains a single integer $$$k$$$ ($$$k \in \{2,3,50\}$$$).
Your DC program should output the correct number of derangements for all integers $$$n$$$ such that $$$2 \le n \le k$$$.
Output a valid DC expression on a single line. The expression should only consist of the characters round()+-*/ and the length of the expression should not exceed $$$10\,000$$$ characters.
Your expression will be run on all integers $$$n$$$ such that $$$2 \le n \le k$$$. For each such run, the DC expression should not divide by $$$0$$$ at any time, and its value must be the number of derangements of $$$n$$$.
2
n-n/n
3
n+round(n-n*(n/(n+n)))-n
For the first example, n-n/n is a valid DC program that calculates $$$n-1$$$. The number of derangements for $$$n=2$$$ is $$$1$$$, so this program correctly computes the answer for $$$n=2$$$.
In the second example, a slightly overcomplicated expression is used, which shows all the features of the language in action. For $$$n=3$$$, the value of the expression is: $$$3+\text{round}(3-3 \cdot(\frac{3}{3+3}))-3 = \text{round}(3 - \frac{3}{2}) = \text{round}(\frac{3}{2}) = \text{round}(1.5)=2$$$. It correctly calculates the number of derangements of the sequence $$$[1,2,3]$$$. For $$$n=2$$$ it can be verified that the value of the expression becomes $$$1$$$.