Who prepared this problem?
It is guaranteed the answer is one of the following, "Bossologist", "thoams", "dutin", "waymo", "james", "Esomer", "brian_is_strong", "alternet", or "danx".
The first line of input will contain one integer $$$T$$$, the current testcase $$$(0 \leq T \leq 10)$$$. This is for the judger to use.
Output one of the $$$9$$$ strings listed above, denoting who prepared this problem.
0
Bossologist
Ruby will win!
Also did you know that its possible to get WA on the samples for outputting the sample output?
—
Problem Idea: dutin
Problem Preparation: james
Occurrences: Novice $$$1$$$, Advanced $$$1$$$
MgRonalds recently received an upgrade with self-order kiosks!
You are given a stack of $$$n$$$ integers, $$$p_{1 \dots n}$$$ where $$$p_1$$$ is the bottom of the stack and $$$p_n$$$ is the top. Determine the minimum $$$k$$$ such that it is possible to pop $$$k$$$ elements off the back of the stack and re-insert them in sort order so that the stack is sorted in ascending order.
The first line of input contains a single integer $$$T$$$, the number of testcases $$$(1 \leq T \leq 6633)$$$. $$$T$$$ testcases follow.
The first line of a testcase contains a single integer $$$n$$$, the number of elements in the stack.
The following line contains $$$n$$$ spaced integers $$$p$$$, the elements in the stack $$$(1 \leq p_i \leq n)$$$. It is guaranteed that all $$$p_i$$$ are distinct.
It is also guaranteed that the sum of $$$n$$$ across all testcases will not exceed $$$2 \cdot 10^5$$$.
—
Tests in subtasks are numbered from $$$1 - 10$$$ with samples skipped. Each test is worth an equal amount of points.
For tests $$$1 - 5$$$, the sum of $$$n$$$ across all testcases will not exceed $$$3366$$$.
For each testcase, output one integer $$$k$$$ on a new line denoting the minimum number of elements that need to be popped in order to sort the stack.
5 3 1 2 3 2 2 1 4 4 3 2 1 4 1 4 2 3 7 1 2 3 6 4 7 5
0 2 4 3 4
In the first testcase, the stack is already sorted.
In the second testcase, the entire stack must be popped off to be sorted in the correct order.
In the fourth testcase, it is only necessary to pop off the last $$$3$$$ elements $$$[1, 4, 2, 3] \rightarrow [1] \rightarrow [1, 2, 3, 4]$$$.
—
Problem Idea: 3366
Problem Preparation: 3366
Occurrences: Novice $$$2$$$
For a given string, find the lexicographically largest palindromic subsequence of the string.
A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:
- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.
A string $$$t$$$ is a subsequence of a sequence $$$s$$$ if $$$t$$$ can be obtained from $$$s$$$ by the deletion of several (possibly, zero or all) elements.
Each test contains multiple testcases. The first line contains the number of testcases $$$t$$$ ($$$1\leq t\leq 10^5$$$). This is followed by $$$t$$$ lines — the description of the testcases.
Each line contains a single string $$$s$$$ ($$$1\leq \lvert s\rvert \leq 2\cdot 10^5$$$) — the string to find the lexicographically largest palindromic subsequence of. The string will only contain lowercase latin letters.
It is guaranteed that the sum of $$$\lvert s\rvert$$$ over all testcases does not exceed $$$5\cdot 10^5$$$.
—
Testcases in subtasks are numbered $$$1$$$ to $$$20$$$ with samples skipped.
Test $$$1-5$$$: The sum of $$$\vert s\rvert$$$ does not exceed $$$5\cdot 10^3$$$.
Test $$$6-20$$$: No additional constraints.
Each test is worth $$$5$$$ points with samples skipped.
For each test case, print a string — the lexicographically greatest palindromic subsequence.
4kaoeubbabaaacreativesamplecase
k u bbb v
— Problem Idea: dutin Problem Preparation: dutin Occurrences: Novice 3
Janma and Tascantos were talking with Tusianoli about another math query problem:
There are $$$q$$$ queries of the form $$$(l, r, x)$$$, and for each query you have to output the number of pairs of integers $$$(a, b)$$$ where $$$l \leq a \leq b \leq r$$$ and $$$f(a, b) = x$$$.
$$$f(a, b) = a + b + |a - b|$$$ where $$$|a-b|$$$ means absolute value of $$$a-b$$$.
Please help them to solve the problem.
The first line consists in one integer $$$q$$$ $$$(1 \leq q \leq 2 \cdot 10^{5})$$$ — the number of queries.
Then follows $$$q$$$ lines with with three integers $$$(l, r, x)$$$. $$$(1 \leq l \leq r \leq 10^{18})$$$, $$$(1 \leq x \leq 10^{18})$$$ — the values previously described at the statement.
—
Testcases in subtasks are numbered from $$$1$$$ to $$$20$$$ with samples skipped.
Test $$$1$$$: $$$(q = 1)$$$ and $$$(1 \leq l \leq r \leq 1000)$$$.
Tests $$$2-20$$$: No additional constraints.
Each test is worth 5 points with samples skipped.
Output the number of pairs for each query.
2 2 6 8 3 9 5
3 0
All possible pairs for the first query are: $$$(2, 4)$$$, $$$(3, 4)$$$ and $$$(4, 4)$$$
There are not suitable pairs for the second query.
—
Problem Idea: danx
Problem Preparation: danx
Occurrences: Novice 4
TeamsCode's problem setters are very evil and enjoy creating problems for others, so they have kidnapped Litusiano and given him a chance to escape if he is clever enough to solve their task. The task consists of the following:
Litusiano knows the address of the building, denoted by $$$x$$$, in which they are keeping him and he needs to transmit it to his savior Danx. The TeamsCode problem setters have designed a system for him to get in contact with Danx, who is trying to rescue him, and tell him the address of the building. Unfortunately, this system can only transmit information through clues. Each clue is a triplet of the form $$$(a, b, c)$$$, which means that $$$|a - b|$$$ is divisible by $$$x$$$ if $$$c = 1$$$, or not divisible if $$$c = 0$$$.
Unfortunately, Litusiano is not clever enough to transmit the address, so he has asked you to help him transmit the address.
You must output an integer $$$k$$$, the minimum number of clues needed to determine the value $$$x$$$. Additionally, you must a provide a set of clues of size $$$k$$$ such that Danx can know the value $$$x$$$.
In the original contest, the problem didn't ask for a construction. That was because it's hard to implement custom checkers for the TeamsCode judge, but we intended to ask for a construction to make sure that the idea is right.
On the first line there's an integer $$$t (1 \le t \le 10^{3}) $$$ $$$-$$$ the number of tests.
For each test, there's one line containing the integer $$$x$$$. $$$(1 \le x \le 10^{6})$$$.
For each test, output an integer $$$k \le 10^3$$$, the minimum number of clues needed to leave exactly one possible value of $$$x$$$. Then, on each of the following $$$k$$$ lines output three integers $$$a$$$, $$$b$$$ and $$$c$$$, representing each of the clues. $$$(1 \le a, b \le 10^9; c \in \{0, 1\})$$$.
2 1 5
1 2 3 1 2 3 8 1 1 3 0
—
Problem Idea: Esomer
Problem Preparation: Esomer
Occurrences: Novice 9, Advanced 2
After seeing the problem set for the 2024 Spring TeamsCode contest, Chessbot has no trust. This is not ideal so to gain more trust he goes to $$$N$$$ different testers which each have a certain value $$$a_i$$$ (which may be negative). As Chessbot goes through the testers he keeps a "trust score" which is initially $$$0$$$. Every time he goes to a tester, he can either add or multiply that tester's value to his trust score. What is the maximum amount of trust Chessbot can achieve if he goes through all the testers in order from $$$1$$$ to $$$N$$$.
* Note that it is possible for Chessbot to have negative trust.
The first line contains the integer $$$T$$$ ($$$1 \leq T \leq 10^4$$$) denoting the number of test cases.
The first line of every test case contains the integer $$$N$$$ ($$$1 \leq N \leq 100$$$) where $$$N$$$ is the amount of testers Chessbot goes to.
The next line of each test case contains $$$N$$$ space separated integers $$$a_1, a_2, \cdots, a_N$$$ ($$$-1000 \leq a_i \leq 1000)$$$ denoting the value of each tester.
Testcases in subtasks are numbered from $$$1$$$ to $$$20$$$ with samples skipped.
Testcases $$$1-5$$$: All $$$a_i$$$ are non-negative.
Testcases $$$6-20$$$: No additional constraints.
For each case, a single integer describing the maximum trust Chessbot can achieve.
Note that the answer is guaranteed to fit in a 64 bit integer.
4 4 4 0 1 2 3 3 -2 -2 4 -2 -4 -2 -8 3 2 -10 4
10 12 128 4
For the first test case, it is optimal to add the first $$$3$$$ values, then multiply for the fourth one.
In the second test case, to get the maximum you add the first value, then multiply for the next two values.
For the third test case, add the first value and multiply the next three.
For the fourth and final test case, multiply the first two values then add the third.
—
Problem Idea: Bossologist
Problem Preparation: Bossologist
Occurrences: Novice 5
Thomas is trying to do his math homework! Tired of Thomas constantly solving his homework too quickly and having fun in class, his math teacher has decided to assign him a large number of easy problems to keep him busy. Thomas could finish his homework first, but his stamina is capping in Honkai Star Rail. As a result, he has asked you to help him finish his math homework!
There are $$$t$$$ ($$$1\leq t\leq 2\cdot 10^5$$$) math problems that Thomas must solve. Each can be expressed as $$$3$$$ integers, $$$x$$$, $$$y$$$, and $$$z$$$ ($$$1\leq x,y,z\leq 10^8$$$). For each problem, Thomas must find the maximum value of $$$(v+x)\oplus (v+y)$$$, where $$$0\leq v \lt z$$$ and $$$\oplus$$$ denotes the bitwise XOR operation.
In the first line, there is the single value $$$t$$$. In each of the following $$$t$$$ lines are $$$3$$$ integers, denoting $$$x$$$, $$$y$$$, and $$$z$$$ in that order respectively.
Test cases are enumerated from $$$1$$$ to $$$20$$$. Note the the data will not include samples.
Tests $$$1$$$-$$$5$$$: $$$x,y,z\leq 100$$$
Tests $$$6$$$-$$$8$$$: $$$x,y,z\leq 1000$$$
Tests $$$9$$$-$$$20$$$: No additional constraints.
Output $$$t$$$ lines, the $$$i$$$-th line containing one integer denoting the solution to the $$$i$$$-th problem.
5 7 5 5 5 6 8 3 3 3 1 3 2 5 1 5
14 15 0 6 12
5 7 3 4 7 2 2 4 7 8 2 5 3 0 4 5
12 11 15 7 12
For the first multitest of the first sample, $$$x=7$$$, $$$y=5$$$, and $$$z=5$$$. The possible values for $$$v$$$ are $$$0,1,2,3,$$$ and $$$4$$$. The values of $$$(v+x)\oplus (v+y)$$$ for each value of $$$v$$$ are $$$2$$$, $$$14$$$, $$$14$$$, $$$2$$$, and $$$2$$$ respectively. The minimum value among them is $$$2$$$, and it is the answer to this multitest.
Manuel and Felix have been searching for a good math problem all night before the TeamsCode Contest, and they've found it!
Omer has two arrays $$$a$$$ and $$$b$$$, permute $$$b$$$ to minimize the sum of $$$a[k] \cdot b[k]$$$ where $$$(i \leq k \leq j)$$$ for every subarray $$$[i, j]$$$.
In other words, you have to minimize the value of the following expression: $$$\sum_{i = 0}^{n-1} \sum_{j = i}^{n-1} \sum_{k = i}^{j} a_{k} \cdot b_{k}$$$
The first line consists in one integer $$$n$$$ $$$(2 \leq n \leq 10^{5})$$$ — the number of elements in both arrays.
The second line consists in $$$n$$$ integers $$$a_{0}, ..., a_{n-1}$$$ $$$(-100 \leq a_{i} \leq 100)$$$ — the values of the elements in $$$a$$$.
The third line consists in $$$n$$$ integers $$$b_{0}, ..., b_{n-1}$$$ $$$(-100 \leq b_{i} \leq 100)$$$ — the values of the elements in $$$b$$$.
—
Testcases in subtasks are numbered from $$$1$$$ to $$$20$$$ with samples skipped.
Tests $$$1-2$$$: $$$(1 \leq n \leq 6)$$$.
Tests $$$3-20$$$: No additional constraints.
Each test is worth 5 points with samples skipped.
Output the minimum possible value after permuting $$$b$$$.
3 5 4 -1 4 3 2
65
You can permute $$$b$$$ to obtain $$$(3, 2, 4)$$$ and minimize the answer.
—
Problem Idea: danx
Problem Preparation: danx
Occurrences: Novice 6
For a given integer $$$n$$$, find the number of palindromic sequences of positive integers with a sum of $$$n$$$ that contains at least one occurrence of the number $$$k$$$. Output the answer modulo $$$p$$$, where $$$p$$$ is given in the input.
Each test contains multiple testcases. The first line contains the number of testcases $$$t$$$ ($$$1\leq t\leq 10^6$$$). This is followed by $$$t$$$ lines — the description of the testcases.
Each line contains three integers $$$n$$$, $$$k$$$, and $$$p$$$ ($$$1\leq k\leq n\leq 10^6$$$,$$$10^8\leq p\leq 2\cdot 10^9$$$) — the sum of the sequence, the required number, and the number to take the answer modulo of, respectively. The number $$$p$$$ is guaranteed to be a prime.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.
—
Testcases in subtasks are numbered $$$1$$$ to $$$20$$$ with samples skipped.
Test $$$1-10$$$: The sum of $$$n$$$ does not exceed $$$5\cdot 10^3$$$.
Test $$$6-20$$$: No additional constraints.
Each test is worth $$$5$$$ points with samples skipped.
For each test case, print one integer — the desired value modulo $$$p$$$.
48 2 99824435312 12 199999994310 4 59253806942 2 100000007
9 1 7 1999923
For the first sample, $$$[2,2,2,2]$$$, $$$[3,2,3]$$$, and $$$[1,1,2,2,1,1]$$$ are examples of sequences that work. Sequences that do not work include $$$[2,3,2]$$$, $$$[3,3,3]$$$, $$$[2,3,1,1,1]$$$, and $$$[4,4]$$$.
— Problem Idea: dutin Problem Preparation: dutin Occurrences: Novice 7, Advanced 3
Bossologist is tired of attending both weekly TeamsCode meetings, so now he's making the other problem setters go for him! Problem ideas are discussed in meetings which occur every $$$N$$$ days in an "$$$N$$$-day week," with days of the week being numbered $$$1,2,\dots,N-1, N, 1, 2,\dots$$$ There are $$$M$$$ problem setters (not including Bossologist) the $$$i$$$-th of which go to $$$p_i$$$ different meetings a week.
When a problem idea is made, Bossologist is in charge of going to the meetings and making sure the other problem setters are "aware," or informed of the idea. At first none of the setters are "aware," but they become "aware" by attending the same meeting as either Bossologist or another aware problem setter. A meeting is called "productive" if Bossologist or at least one aware setter attends that meeting. Bossologist would like to figure out the minimum amount of meetings he must attend given that all meetings within $$$N$$$ days of an idea's conception must be productive.
The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N$$$, $$$M \leq 10^5$$$) denoting the number of days in the week and the number of problem setters respectively.
The next $$$M$$$ lines contain several space separated integers. The first one $$$p_i$$$ ($$$1 \leq p_i \leq N$$$) decribes the number of meetings problem setter $$$i$$$ is attending. The next $$$p_i$$$ integers denote the days of the week that problem setter $$$i$$$ attends meetings (in sorted order). The sum of all $$$p_i$$$ is guaranteed to be less than or equal to $$$5 \cdot 10^5$$$.
Testcases in subtasks are numbered from $$$1$$$ to $$$20$$$ with samples skipped.
Testcases $$$1−5$$$: $$$N$$$, $$$M \leq 1000$$$.
Testcases $$$6−20$$$: No additional constraints.
$$$N$$$ lines, where the $$$i$$$-th line is a single integer representing the minimum number of meetings Bossologist must attend if a problem idea is conceived on the $$$i$$$-th day of the week.
* Note that days in which no problem setter attends a meeting are not counted toward the answer
4 3 2 1 3 2 3 4 2 2 4
2 2 1 2
If a problem idea is created on day $$$1$$$ or $$$2$$$, Bossologist has to attend the meetings on days $$$1$$$ and $$$2$$$.
If a problem idea is created on day $$$3$$$, Bossologist has to attend the meeting on days $$$3$$$.
If a problem idea is created on day $$$4$$$, Bossologist has to attend the meeting on days $$$1$$$ and $$$4$$$.
—
Problem Idea: Bossologist
Problem Preparation: Bossologist
Occurrences: Novice 11, Advanced 5
"I don't know everything, I only know what I know." Let's find out if she knows about permutations that have the same med, mex, and median!
The median of a $$$1$$$-index sorted array $$$a$$$ of length $$$n$$$ is defined in this problem as follows: let $$$x = \frac{n+1}{2}$$$ ($$$x$$$ is not necessarily an integer), then the median is $$$\frac{a_{\lfloor x \rfloor} + a_{\lceil x \rceil} }{2}$$$. The mex of an array is the minimum excluded or the minimum positive integer which is not present.
A nonempty sequence is good if the mex of that sequence and the median of that sequence are equal. Let the value of a good sequence be the mex (and median) of that sequence. There is a permutation $$$p$$$ of all the integers from $$$1$$$ to $$$n$$$. We want to know over all permutations $$$p'$$$ of $$$p$$$ the number subarrays of $$$p'$$$ which are good sequences with value $$$x$$$ for each $$$x$$$ $$$(1 \leq x \leq n)$$$. This is something she knows, but is it something you know?
The first line will contain one integer $$$T$$$, the number of testcases $$$(1 \leq T \leq 5)$$$.
The first line of each testcase contains one integer, $$$n$$$ the length of permutations that are being considered $$$(1 \leq n \leq 10^5)$$$.
—
Tests in subtasks will be numbered from $$$1 - 20$$$ with samples skipped.
Test $$$i$$$ will satisfy $$$n \leq \min(10^5, 2^i)$$$.
For each testcase, output one line of $$$n$$$ integers where the $$$i$$$-th integer is the number of good sequences with value $$$i$$$ over all permutations of $$$1,2, \dots n$$$. Since these numbers may be very large, please find them modulo $$$998244353$$$.
5 1 2 3 4 15
0 0 0 0 4 0 0 12 0 0 0 662064978 677633922 778530699 797769592 212803401 839917327 662064978 0 0 0 0 0 0 0
The subarrays which are good subsequences of value $$$2$$$ of the permutation $$$1, 2, 3$$$ are as follows:
$$$[1, 3]$$$ in $$$[1, 3, 2]$$$
$$$[1, 3]$$$ in $$$[2, 1, 3]$$$
$$$[3, 1]$$$ in $$$[2, 3, 1]$$$
$$$[3, 1]$$$ in $$$[3, 1, 2]$$$
—
Problem Idea: 3366
Problem Preparation: 3366
Occurrences: Novice $$$10$$$, Advanced $$$4$$$
Thomas has set an easy tree problem! I can even tell you what it is:
There is a tree with $$$n$$$ nodes rooted at node $$$1$$$, each initially painted with color $$$a_i$$$. However, this color scheme is extremely ugly, and Thomas wants to paint it to make it beautiful instead. He wants each node to be painted with color $$$b_i$$$ in the end. However, this is a tree, so the paint will trickle down from a certain node, painting the entire subtree. It will cost $$$c_i$$$ dollars for Thomas to paint node $$$i$$$ and its entire subtree any color. Whenever Thomas paints a node, it will override any preexisting painted nodes in its subtree - the color of a node is the color of the last operation applied to it (or any of its ancestors). What is the minimum number of dollars Thomas needs to spend to paint the entire tree the colors that he wants?
I actually have been informed that I understood the problem wrong and created a new problem, so I am stuck preparing it instead. However, this is too hard for me to solve and my stamina is capping, so instead you will solve this problem for me!
As the input is extremely large, it is advised to use a form of fast input and output.
- C++/Java: Codeforces Blog
- Python: Codeforces Blog
The first line of the input will contain one integer $$$t$$$, the number of test cases.
Each test case will consist of $$$5$$$ lines.
The first line contains integer $$$n$$$ $$$(1\leq n\leq 200000)$$$. It is guaranteed that the sum of $$$n$$$ over all multitests is less than or equal to $$$2.5\cdot 10^6$$$.
The second line contains $$$n-1$$$ integers, with the $$$i$$$-th integer representing the parent of the $$$i+1$$$-th node of the tree.
The third line contains $$$n$$$ integers, with the $$$i$$$-th integer representing $$$c_i$$$ $$$(1\leq c_i\leq 10^9)$$$.
The fourth line contains $$$n$$$ integers, with the $$$i$$$-th integer representing $$$a_i$$$ $$$(1\leq a_i\leq 10^6)$$$.
The fifth line contains $$$n$$$ integers, with the $$$i$$$-th integer representing $$$b_i$$$ $$$(1\leq b_i\leq 10^6)$$$.
Test cases are enumerated from $$$1$$$ to $$$20$$$. Note that the data will not include samples.
Tests $$$1-5$$$: $$$t\leq 1000$$$, $$$n\leq 12$$$
Tests $$$6-20$$$: No additional restrictions
For each test case on its own line, output one integer representing the answer for that test case. The answer may not fit in a $$$32$$$ bit integer.
3 5 1 1 2 4 1 3 2 2 2 2 2 1 3 4 2 4 1 2 1 5 1 4 5 1 2 2 1 0 1 1 4 1 1 4 1 3 1 5 5 5 3 4 1 1 3 4 3 3 0 3 3 2 2 5 3 4 2 2 1
7 4 4
1 10 1 2 2 4 5 3 6 3 7 4 2 2 2 4 3 2 1 1 4 2 1 1 1 3 2 1 3 2 4 2 3 3 4 3 3 2 5 4 1
16
In the first multitest in the first sample, the most optimal sequence of operations is painting node $$$1$$$ color $$$2$$$ with cost $$$1$$$ and then painting node $$$2$$$ color $$$1$$$ with cost $$$1$$$. After painting node $$$1$$$ color $$$2$$$, node $$$1$$$ and node $$$2$$$ are both color $$$2$$$, as node $$$2$$$ is in the subtree of node $$$1$$$. Then, painting node $$$2$$$ color one ends in the desired color configuration.
In the second multitest in the first sample, the most optimal sequence of operations is painting node $$$2$$$ with color $$$4$$$, then painting node $$$4$$$ with color $$$2$$$, and then painting node $$$5$$$ with color $$$1$$$, with costs $$$3$$$, $$$2$$$, and $$$2$$$ for a total of $$$7$$$.
—
Problem Idea: hyforces
Problem Preparation: hyforces
Occurrence: Novice $$$12$$$, Advanced $$$6$$$
Or so she thought until she fell into large amounts of debt and now has to wrap gifts for a living.
Ruby has $$$n$$$ ($$$1 \le n \le 10^5$$$) gifts. The $$$i$$$-th gift is represented by a rectangle in $$$2$$$d space having a bottom left vertex of ($$$x_i, y_i$$$) and top right vertex of ($$$x_i', y_i'$$$) ($$$0 \le x_i \lt x_i' \le 10^5$$$, $$$0 \le y_i \lt y_i' \le 10^5$$$). Recently, Aqua has told Ruby to be more organized, so she has already sorted the rectangles by their right side. In other words, $$$x_{i - 1}' \le x_i'$$$ for all $$$i \gt 1$$$.
Ruby wants to use gift wrapping to completely cover her gifts. Each gift wrap is also represented by a rectangle in $$$2$$$d space, and Ruby can choose to create these rectangles however she wants as long as they don't overlap and each gift can only belong to a single gift wrap. Ruby is given a bonus if the amount of gift wrap she uses is small, so she wants to minimize the total area of gift wrap used. In other words, Ruby wants to find the minimum total area of non-intersecting rectangles such that each gift is completely contained by exactly one rectangle.
However, Ruby has always been an overachiever (unlike Akane), so she also wants to find the minimum total area of gift wrap to cover every gift from $$$1 \dots i$$$ for all $$$i$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 3$$$). The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ ($$$1 \le n \le 10^5$$$) representing the number of gifts.
The $$$i$$$-th of the next $$$n$$$ lines of each test case contains four integers $$$x_i$$$, $$$y_i$$$, $$$x_i'$$$, and $$$y_i'$$$ ($$$0 \le x_i \lt x_i' \le 10^5$$$, $$$0 \le y_i \lt y_i' \le 10^5$$$, $$$x_{i - 1}' \le x_i'$$$), denoting the coordinates of the gift.
—
For test cases $$$1$$$ - $$$5$$$, it is guaranteed that $$$n \le 5000$$$.
There are no restrictions on the remaining test cases.
For each test case, output $$$n$$$ lines, the $$$i$$$-th of which denotes the minimum area of gift wrap needed to cover every gift from $$$1 \dots i$$$.
1 5 3 3 4 8 0 0 5 1 4 0 5 5 5 6 8 7 6 2 8 4
5 10 40 43 47
Problem Idea: oursaco
Problem Preparation: oursaco
Occurrences: Advanced 9
Rin knows that the universe can still be saved using a set of extremely powerful artifacts scattered through time across the entire multiverse. The entire multiverse and all of its states through time can be represented as a tree of size n, with nodes each representing a multiverse(at its own exact point in time), originating from a single point, the root, or Akasha. Rin starts at Akasha. The artifacts are located at certain nodes in this tree. As time moves forwards, depending on random events within the world, the state of the universe will begin to change. When the universe changes, it will move away from the root and towards one of its children states - the children on the tree. It will slowly move away until it reaches the ends of time - the leaves of the tree. With the power of Kaleidoscope, Rin is able to dictate the result of these tiny random fluctuations, thus letting her choose which path the current universe moves down. Unfortunately, she is unable to reverse time, and as a result is unable to move upwards in the tree - she must wait for the natural flow of time to take her down the tree. However, it is obvious that not all required artifacts can be reached if she can only move forward in time and away from the root. There is a solution to this though, and Rin realizes that the end of time is the same as the beginning - by reaching any of the leaves of the tree, she can return to Akasha, the beginning of time and the root. Since she is very impatient and doesn't want to get bored, Rin wants to know, given the set of universes she must reach to retrieve all the artifacts, the minimum number of epochs she must spend to collect all the artifacts. When Rin waits to descend one edge down the tree of time, she spends one epoch. However, it costs her no epochs to return to the root.
However, there is a special twist to make Rin's (and your) life harder. Rin doesn't actually know if each of the artifacts will appear. She does not even know the number that must appear - but she knows that no matter how many there are, she must retrieve each one. The probability an artifact occurs at node $$$i$$$ on the tree is $$$p_i$$$. She now wants you to calculate the expected value of the minimum number of epochs she must spend collecting the artifacts that do appear and return to Akasha at the end to Save The Timeline.
However, there is a second special twist to make everyone's lives even harder! Rin actually does have some information about what artifacts appear - but she is unsure of whether each piece of information is true. As a result, she asks you to compute the expected value of the minimum time she must spend in the case that each piece of information is true(the pieces of information are independent of each other). Each piece of information is made up of an integer $$$k$$$ and a set $$$S$$$ of size $$$k$$$, where Rin knows that all the nodes in set $$$S$$$ will have an artifact. The probabilities of any other artifacts appearing at nodes outside of that set remain the same. For each of $$$q$$$ queries, each consisting of a piece of information, calculate the expected value of the minimum number of epochs Rin will spend to collect all the artifacts that appear. All probabilities and expected values are computed under modulo $$$998244353$$$.
Here is a TLDR for all the people who don't care about saving the world:
You are given a tree of size $$$n$$$ rooted at node $$$1$$$. A node is active with probability $$$p_i$$$. The "cost" of a set of active nodes is the minimum number of epochs it takes to reach each node in the active set moving along the edges of the tree according to the following rules:
- You will start, and must end at, the root.
- It costs $$$1$$$ epoch to travel from a parent to child on the tree (again, rooted at node $$$1$$$).
- It costs $$$0$$$ epochs to move from any leaf of the tree to the root.
Answer $$$q$$$ queries about the expected value of the cost of the set of active nodes. Each query contains an additional set of nodes $$$S$$$, where it is guaranteed that every node in that set will be active(the probabilities of other nodes not in $$$S$$$ being active remains unchanged, and each query is independent of the other queries). All probabilities and expected values are computed under modulo $$$998244353$$$. For more details, refer to the sample explanation.
The first line of the input contains one integer $$$t$$$ $$$(1\leq t\leq 200)$$$, which is the number of multitests in the input.
Each individual multitest starts with one line containing two integers, $$$n$$$ $$$(1\leq n\leq 10^6)$$$ and $$$q$$$ $$$(1\leq q\leq 10^6)$$$, the size of the tree and the number of queries respectively.
The second line contains $$$n$$$ integers separated by spaces, representing $$$p_i$$$ $$$(0\leq p_i\leq 998244353)$$$ for each node.
The third to $$$n+1$$$ lines each contain two integers $$$u$$$ and $$$v$$$ $$$(1\leq u,v\leq n)$$$ separated by spaces representing the edges of the tree.
The $$$n+2$$$ to $$$n+q+1$$$ lines each begin with one integer $$$k$$$ $$$(0\leq k\leq n)$$$. Following that(in the same line) are $$$k$$$ distinct integers separated by spaces, each in the range $$$[1,n]$$$, representing the set of nodes in the corresponding query.
It is guaranteed that the $$$0\leq \sum n , \sum k , \sum q \leq 10^6$$$ over all multitests in one test case.
—
Test cases are enumerated from $$$1$$$ to $$$20$$$. Note that the data will not include samples.
Tests $$$1$$$-$$$5$$$: ($$$1\leq t\leq 100$$$, $$$1\leq n\leq 10$$$)
Tests $$$6$$$-$$$10$$$: ($$$1\leq \sum n\leq 5\cdot 10^3$$$,$$$1\leq\sum q,\sum k\leq 10^4$$$)
Tests $$$11$$$-$$$15$$$: ($$$1\leq \sum n\leq 2.5 \cdot 10^5$$$,$$$1\leq\sum q,\sum k\leq 2.5\cdot 10^5$$$))
Tests $$$16$$$-$$$20$$$: No additional constraints
For each multitest, output $$$q$$$ lines, each containing one integer representing the answer to the queries made in order.
1 3 2 1 665496236 499122177 1 2 2 3 0 1 2
665496237 2
2 4 4 460452453 858229637 612540950 778705078 2 1 3 4 4 1 4 3 2 4 1 2 3 1 1 4 3 1 3 2 4 4 531941972 134585184 7809514 711761406 2 1 3 2 4 1 4 1 2 4 3 3 1 2 3 4 1 4 2 3 3 4 2 1
3 858229639 858229639 3 3 711761408 3 3
In the first sample, there is a tree of size $$$3$$$, rooted at $$$1$$$ with an edge to $$$2$$$ then to $$$3$$$. The probabilities of node $$$1$$$, node $$$2$$$, and node $$$3$$$ being active respectively are $$$1$$$, $$$\frac{2}{3}\equiv 2(3^{-1})\equiv 665496236 \mod 998244353$$$, and $$$\frac{1}{2}\equiv 1(2^{-1})\equiv 499122177\mod 998244353$$$.
In the first query, there are no forced active nodes. However, since $$$p_1=1$$$, it is always active. There are $$$4$$$ cases: if node $$$2$$$ and node $$$3$$$ are both active (probability $$$\left(\frac{2}{3}\right)\left(\frac{1}{2}\right)$$$), if node $$$2$$$ is active but node $$$3$$$ is not (probability $$$\left(\frac{2}{3}\right)\left(1-\frac{1}{2}\right)$$$), if node $$$3$$$ is active but node $$$2$$$ is not (probability $$$\left(1-\frac{2}{3}\right)\left(\frac{1}{2}\right)$$$), and if neither node $$$2$$$ nor $$$3$$$ are active (probability $$$\left(1-\frac{2}{3}\right)\left(1-\frac{1}{2}\right)$$$). If no node is active, the minimum cost is $$$0$$$, as by not moving from the root all the active nodes are reached. If either node $$$2$$$ or $$$3$$$ is active, the minimum cost is $$$2$$$, as you must move from node $$$1$$$ downwards and then, to reach the root once again, reach node $$$3$$$ and teleport back to node $$$1$$$. As a result, the answer to this query is $$$\left(1-\left(1-\frac{2}{3}\right)\left(1-\frac{1}{2}\right)\right) (2)+\left(1-\frac{2}{3}\right)\left(1-\frac{1}{2}\right)(0)=\frac{5}{3}\equiv 5(3^{-1})\equiv 665496237 \mod 998244353$$$.
In the second query, node $$$2$$$ is forced to be active. Note that this query is completely independent of the previous one. Again, $$$p_1=1$$$ so node $$$1$$$ is active as well. In this case, no matter whether node $$$3$$$ is active or not, the minimum cost is $$$2$$$ with the path $$$1\rightarrow 2\rightarrow 3\rightarrow 1$$$, so the answer is simply $$$2$$$.
—
Problem Idea: hyforces
Problem Preparation: hyforces
Occurrences: Advanced $$$7$$$
The $$$n$$$ CodeCode problem testers each solved all $$$t$$$ problems on the contest! Each problem tester gives feedback by giving a range of numbers $$$[l_i, r_i]$$$ for the difficulty. From each range a random real number is selected. What is the expected value of the range of the final numbers that are chosen for each problem?
A range of a set of values is the maximum difference between any two values.
The first line contains two integers $$$n$$$ and $$$t$$$ ($$$n \le 200$$$, $$$t \le 10$$$), the number of problem testers who gave feedback and number of problems, respectively. The description of each test case follows.
Each of the next $$$n$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$0 \le l_i \le r_i \le 3500$$$)— the ranges of difficulty for the problem.
Print $$$t$$$ lines, each with the expected value of the range of the final dataset of the difficulties. Round your answer to the nearest ten thousandth.
To round in C, you can use printf("%.4lf", var);
To round in C++, you can use std::cout«std::fixed«std::setprecision(4)«var«endl;
To round in Python, you can use round(var, 4)
3 3 900 900 800 1000 1000 1100 800 800 3300 3500 0 3500 800 800 0 3500 3499 3500
175.0000 2693.3333 2790.9286
For the first test case, there are two possibilities:
While the first problem tester gives a difficulty of $$$900$$$, the second problem tester gives a lower difficulty from $$$800$$$ to $$$900$$$. The third problem tester gives a difficulty from $$$1000$$$ to $$$1100$$$. The expected value of the range is $$$200$$$.
The first problem tester gives the difficulty $$$900$$$. The second problem tester gives a difficulty from $$$900$$$ to $$$1000$$$. The third problem tester gives a difficulty from $$$1000$$$ to $$$1100$$$. The expected value of the range is $$$150$$$.
Since these two happen with equal probability, the expected value of the range is $$$175$$$.
—
Problem Idea: thehunterjames
Problem Preparation: thehunterjames, codicon
Occurrences: Advanced $$$8$$$
Omer has given you $$$n$$$ intervals by its endpoints $$$[l_{i}$$$, $$$r_{i}]$$$ and two groups, $$$A$$$ and $$$B$$$, initially empty.
For each interval, you can do at most one of the following operations:
1 Insert the interval into group $$$A$$$.
2 Insert the interval into group $$$B$$$.
At the end, every pair of intervals of the same group must intersect in at least one point. There aren't any restrictions for pairs of intervals of different groups.
Your task is to maximize the size of the smallest group.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1 \leq t \leq 1000)$$$. The description of the test cases follows.
The first line consists in one integer $$$n$$$ $$$(2 \leq n \leq 3 \cdot 10^{5})$$$ — the number of intervals.
Then follows $$$n$$$ lines which consists in two integers $$$l_{i}$$$ and $$$r_{i}$$$ $$$(1 \leq l_{i} \leq r_{i} \leq 10^{9})$$$ — the endpoints of the intervals.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^{5}$$$.
—
Testcases in subtasks are numbered from $$$1$$$ to $$$20$$$ with samples skipped.
Tests $$$1-3$$$: $$$(2 \leq n \leq 500)$$$ and it is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$500$$$.
Tests $$$4-7$$$: $$$(2 \leq n \leq 3000)$$$ and it is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3000$$$.
Tests $$$8-12$$$: $$$(2 \leq n \leq 10^{5})$$$ and it is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^{5}$$$.
Tests $$$13-20$$$: No additional constraints.
Each test is worth $$$5$$$ points with samples skipped.
For each testcase, output one integer per line, the maximum possible size of the smallest group.
2 5 4 7 1 8 7 12 2 6 13 13 2 69 69 69 69
2 1
For the first testcase, a possible distribution would be $$$A$$$ = $$$([2, 6], [4, 7])$$$ and $$$B$$$ = $$$([1, 8], [7, 12])$$$.
For the second testcase, the unique possible distribution is $$$A$$$ = $$$([69, 69])$$$ and $$$B$$$ = $$$([69, 69])$$$.
—
Problem Idea: danx
Problem Preparation: danx
Occurrences: Advanced 10
Define a beautiful matrix as a $$$2\times n$$$ matrix, such that every entry of the matrix is either a $$$0$$$ or a $$$1$$$ and every $$$2\times k$$$ submatrix has a sum of $$$s$$$.
For instance, for $$$n=4$$$, $$$k=2$$$, $$$s=2$$$, $$$[1010; 1010]$$$ and $$$[1000;0111]$$$ are beautiful and $$$[1001;0111]$$$, $$$[010;101]$$$, and $$$[0000;1110]$$$ are not beautiful.
Count the number of beautiful matrices for given $$$n$$$, $$$k$$$, and $$$s$$$ modulo $$$998\,244\,353$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1\leq t\leq 20$$$). This is followed by $$$t$$$ lines — the description of the test cases.
Each line contains three integers $$$n$$$, $$$k$$$, and $$$s$$$ ($$$1\leq n\leq 10^{18}$$$, $$$1\leq k\leq \min(n, 10^6)$$$, $$$0\leq s\leq 2k$$$) — the size of the matrix, the size of the submatrix, and the sum of the submatrix.
It is guaranteed that the sum of $$$k$$$ over all test cases does not exceed $$$5\cdot 10^6$$$.
—
Testcases in subtasks are numbered $$$1$$$ to $$$20$$$ with samples skipped.
Test $$$1$$$: The sum of $$$n$$$ does not exceed $$$10$$$.
Test $$$2-3$$$: The sum of $$$k$$$ does not exceed $$$5\cdot 10^3$$$.
Test $$$4-5$$$: $$$k$$$ divides $$$n$$$.
Test $$$6-15$$$: The sum of $$$k$$$ does not exceed $$$5\cdot 10^5$$$.
Test $$$16-20$$$: No additional constraints.
Each test is worth $$$5$$$ points with samples skipped.
For each test case, print a single integer — the number of beautiful matricies modulo $$$998\,244\,353$$$.
43 2 16 4 26 4 610 6 7
6 56 56 4360
222272727425 175432 76534472306406606064 254312 432752
933599753 43127063
— Problem Idea: dutin Problem Preparation: dutin Occurrences: Advanced 12
Because climate change is a hoax $$$^{\text{[citation needed]}}$$$, Alice has decided to enter the lucrative business of oil drilling. There are $$$n$$$ deposits of oil scattered across the $$$2$$$-d coordinate plane, numbered $$$1$$$ through $$$n$$$. The $$$i$$$-th deposit is at coordinate $$$(x_i, y_i)$$$ and has $$$w_i$$$ units of oil.
Alice can enclose some oil deposits with a perimeter to secure drilling rights. The profit from such a perimeter is the total amount of oil minus the cost of the perimeter. The cost of a perimeter of length $$$k$$$ is given by the expression $$$m\dot k+c$$$, where $$$m$$$ and $$$c$$$ are given constants. Help Alice find the maximum profit she can make.
Each test contains multiple testcases. The first line contains the number of testcases $$$t$$$ ($$$1\leq t\leq 20$$$). The description of the test cases follows.
The first line of each testcase contains three integers $$$n$$$,$$$m$$$,and $$$c$$$ ($$$1\leq n\leq 400$$$, $$$0\leq m,c\leq 10^9$$$) — the number of oil deposits and the parameters of the cost function, as described above.
The $$$i$$$-th of the next $$$n$$$ lines contains three integers $$$x_i,y_i,w_i$$$ ($$$\lvert x_i\rvert, \lvert y_i\rvert\leq 10^9, 1\leq w_i\leq 10^9$$$) — the location and amount of oil of the $$$i$$$-th deposit. Note that the positions of deposits may not be distinct.
It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$500$$$.
—
Testcases in subtasks are numbered $$$1$$$ to $$$40$$$ with samples skipped.
Test $$$1-6$$$: The sum of $$$n$$$ does not exceed $$$20$$$.
Test $$$7-12$$$: All $$$w_i$$$ have the same value.
Test $$$13-40$$$: No additional constraints.
The test are worth an alternating $$$2$$$ or $$$3$$$ points with samples skipped.
For each test case, print a single floating point value — the maximum profit that Alice can earn by building one perimeter.
Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.
Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.
13 10 01 1 52 6 35 5 1
5.000000
32 2 01 1 1003 3 1004 0 01 1 12 4 14 2 14 4 13 1 1001 1 21 2 22 1 2
188.686292 4.000000 -97.414214
36 2 51 1 54 3 22 5 35 6 63 4 74 5 36 3 16 4 55 4 47 5 31 1 16 3 57 1 615 2 107 5 21 3 92 5 105 4 132 6 171 1 1111 2 33 4 34 2 126 9 12 7 110 8 33 3 81 5 1411 5 2
2.000000 5.000000 58.163779
Problem Idea: dutin Problem Preparation: dutin Occurrences: Advanced 11
After passing away from a chronic illness induced by data structure problems, Hiraku is isekaied into another world with a peaceful life as a farmer.
Hiraku's field can be represented as an $$$N$$$ by $$$M$$$ grid where each cell is a unit of farmland. The cell in the lower left is $$$(1, 1)$$$ and the cell in the upper right is $$$(N, M)$$$.
For each of the $$$A$$$ days of the plowing season, Hiraku will use his Almighty Farming Tool (AFT) to till a subrectange of his field.
Then for each of the $$$B$$$ planting days, Hiraku will try to plant a new type of seed on a certain subrectangle of his field. The seed can only be planted on cells that have been tilled at least $$$k$$$ times. He wants you to answer his query of how many cells in the rectangle could have that seed planted on it.
Considering this problem will not induce a chronic illness in you by data structure problems, help him answer his surveys!
The first line of input contains four integers $$$N$$$ $$$M$$$ $$$A$$$ $$$B$$$ $$$(1 \leq N, M, A, B \leq 10^5)$$$.
The following $$$A$$$ lines of input will contain four integers $$$x_1$$$ $$$y_1$$$ $$$x_2$$$ $$$y_2$$$ $$$(1 \leq x_1 \leq x_2 \leq N, 1 \leq y_1 \leq y_2 \leq M)$$$ denoting that he will till all cells $$$(x, y)$$$ such that $$$x_1 \leq x \leq x_2, y_1 \leq y \leq y_2$$$.
The following $$$B$$$ lines of input wil contain five integers $$$x_1$$$ $$$y_1$$$ $$$x_2$$$ $$$y_2$$$ $$$k$$$ $$$(1 \leq x_1 \leq x_2 \leq N, 1 \leq y_1 \leq y_2 \leq M, 1 \leq k \leq 5)$$$ denoting that he will consider all cells $$$(x, y)$$$ such that $$$x_1 \leq x \leq x_2, y_1 \leq y \leq y_2$$$ for that seed and the $$$k$$$ that seed requires.
—
Testcases in subtasks are numbered $$$1 \dots 20$$$ with samples skipped. Each testcase is worth the same amount of points.
For tests $$$1 - 2$$$, all inputted numbers will be $$$\leq 500$$$.
For tests $$$3 - 4$$$, there will be exactly one query of $$$1$$$ $$$1$$$ $$$N$$$ $$$M$$$ $$$5$$$.
For tests $$$5 - 7$$$, all queries will have $$$x_1 = x_2$$$.
For tests $$$8 - 9$$$, the rectangle tilled will always have $$$y_1 = y_2$$$.
For test $$$10$$$, the rectangle tilled will always be $$$1$$$ $$$1$$$ $$$N$$$ $$$M$$$.
For tests $$$11-18$$$, the $$$i$$$'th test will have $$$k$$$ be at most $$$\lceil \frac{i - 10}{2} \rceil$$$.
There are no additional constraints on the remaining tests.
Output $$$B$$$ lines, the $$$i$$$'th containing a single integer denoting the number of cells the $$$i$$$'th type of plant can be planted on.
7 6 5 6 1 1 3 3 2 3 4 3 1 2 1 3 2 1 7 6 2 2 6 6 1 1 7 6 5 1 1 7 6 4 2 1 7 1 3 3 3 5 6 2 1 2 3 4 1 4 3 6 5 3
0 2 0 12 8 1
After all $$$A$$$ days of tilling, the amount of times each cell has been tilled is as follows.
1 2 2 0 0 0
2 3 4 2 2 2
2 3 4 2 2 2
1 2 3 2 2 2
1 2 2 2 2 2
1 2 2 2 2 2
1 1 1 1 1 1
For the first query, no cells have been tilled $$$5$$$ times, so the answer is $$$0$$$.
For the second query, cells $$$(2, 3)$$$ and $$$(3, 3)$$$ have been tilled twice, so the answer is $$$2$$$.
For the last query, cell $$$(4, 3)$$$ is the only valid cell, so the answer is $$$1$$$.
—
Problem Idea: oursaco
Problem Preparation: oursaco, 3366
Occurrences: Advanced 13