It's time to submit (your ac solutions)!
Teamscode has had a history of setting problems where outputting the sample output gives AC on the first problem. Examples of past problems include "Meeting Minutes," "Best Waifu," "Are You Busy," etc.
Now, it is time to submit to this new first problem of the Spring $$$2024$$$ contest. Is outputting the sample output enough to get AC?
The first and only line of input contains an integer $$$T$$$ $$$(0 \leq T \leq 10)$$$.
Output "YES" (without the quotes) if it is possible to get AC by outputting the sample output or "NO" otherwise.
0
YES
Unfortunately, the sample output is not "NO". If that were the case, it would be impossible to AC at all!
—
Problem Idea: 3366
Problem Preparation: 3366
Occurrences: Novice 1, Advanced 1
Jinshi loves his toys, and his two favorite toys are an array $$$a$$$ of length $$$n$$$ and a sequence of $$$m$$$ pairs of integers, the $$$i$$$'th being $$$x_i$$$ and $$$y_i$$$ $$$(1 \leq x_i, y_i \leq n)$$$. Whenever Jinshi is bored, he likes to try and sort $$$a$$$ with his $$$m$$$ pairs of integers. Jinshi will loop over the pairs in order from $$$1$$$ to $$$m$$$, and swap $$$a_{x_i}$$$ and $$$a_{y_i}$$$. He will be happy if after all $$$m$$$ swaps, $$$a$$$ becomes sorted in increasing order. Afterward, Jinshi will restore $$$a$$$ to what it was before all the swaps happened.
Maomao will mess with Jinshi over the following $$$q$$$ days, where on the $$$i$$$'th day, she will swap $$$a_{l_i}$$$ and $$$a_{r_i}$$$ $$$(1 \leq l_i, r_i \leq n)$$$. Without knowing Maomao has messed with his array, Jinshi will try to sort it every day after Maomao does the swap. Maomao will not restore $$$a$$$ after doing the swap. On each day, find out if Jinshi will successfully sort his array.
The first line of input contains three integers $$$n \ m \ q$$$ denoting the length of the array, the number of pairs, and the number of days Maomao will mess with Jinshi $$$(1 \leq n, m, q \leq 10^5)$$$.
The following line contains $$$n$$$ spaced integers, the $$$i$$$'th being $$$a_i$$$, denoting Jinshi's array $$$(1 \leq a_i \leq n)$$$.
The following $$$m$$$ lines contain two integers each, the $$$i$$$'th line containing $$$x_i \ y_i$$$ denoting the $$$i$$$'th pair of integers in Jinshi's $$$m$$$ pairs $$$(1 \leq x_i, y_i \leq n)$$$.
The following $$$q$$$ lines contain two integers each, the $$$i$$$'th line containing $$$l_i \ r_i$$$ denoting the pair of elements Maomao swaps on the $$$i$$$'th day $$$(1 \leq l_i, r_i \leq n)$$$.
—
Tests are numbered $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.
All odd-numbered tests satisfy that $$$a$$$ is a permutation. In other words, all the elements in $$$a$$$ will be unique.
Tests $$$1 - 10$$$ satisfy $$$n, m, q \leq 1000$$$.
The remaining tests do not satisfy any additional constraints.
Output a string of length $$$q$$$, the $$$i$$$'th character being $$$Y$$$ if Jinshi can sort his array on the $$$i$$$'th day or $$$N$$$ otherwise.
5 3 61 4 2 3 53 41 24 11 31 43 43 13 45 5
YNNNYY
5 1 71 2 1 2 42 32 41 22 33 44 11 22 3
YNNNNNY
On the first day, the array becomes $$$[2, 4, 1, 3, 5]$$$ after Maomao swaps $$$a_{1}$$$ and $$$a_{3}$$$. Jinshi will then attempt to sort his array, which changes as follows:
$$$[2, 4, 1, 3, 5] \rightarrow [2, 4, 3, 1, 5] \rightarrow [4, 2, 3, 1, 5] \rightarrow [1, 2, 3, 4, 5]$$$
Since Jinshi's array is sorted, the first character in the output string is $$$Y$$$.
—
Problem Idea: 3366
Problem Preparation: 3366
Occurrences: Novice 5, Advanced 2
You are given a string $$$s$$$ of length $$$n$$$. Determine if all subsequences of $$$s$$$ that have length $$$k$$$ are unique.
A subsequence of $$$s$$$ is defined as a sequence that can be obtained from $$$s$$$ by deleting some elements (possibly none), without changing the order of the remaining elements.
For instance, the subsequences of $$$trust$$$ of length $$$4$$$ are $$$trus$$$, $$$trut$$$, $$$trst$$$, and $$$rust$$$, all of which are unique.
But when considering subsequences of $$$threes$$$ of length $$$4$$$. The subsequence $$$tres$$$ occurs twice ($$$\underline{t}h\underline{re}e\underline{s}$$$ and $$$\underline{t}h\underline{r}e\underline{es}$$$).
The first line of input contains a single integer $$$T$$$ denoting the number of test cases $$$(1 \leq T \leq 10^3)$$$.
The first line of each test case contains two integers $$$n \ k$$$ denoting the length of the string and the length of subsequences to consider $$$(1 \leq k \leq n \leq 10^5)$$$.
The second line contains a string $$$s$$$ of length $$$n$$$ consisting only of lowercase English letters.
It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$3 \cdot 10^5$$$.
—
Tests in subtasks are numbered from $$$1 - 10$$$ with samples skipped. Each test is worth $$$\frac{100}{10} = 10$$$ points.
Tests $$$1 - 3$$$ satisfy $$$n \leq 10$$$.
Tests $$$4 - 5$$$ satisfy that the sum of $$$n$$$ across all test cases does not exceed $$$3366$$$.
The remaining tests do not satisfy any additional constraints.
For each test case, output "Yes" (without the quotes) if all subsequences of length $$$k$$$ are unique or "No" (without the quotes) otherwise.
115 4trust6 4threes6 4abcdba8 4sendhelp9 8imtrapped7 6inabase9 5mentuntil7 1ifinish9 7preparing8 3problems8 8heeeeelp
Yes No Yes No No Yes No No Yes Yes Yes
It can be proven that all $$$15$$$ subsequences of length $$$4$$$ of $$$abcdba$$$ are unique (by listing them out and reading over them carefully). Also I'm trapped in Tho$$$[$$$deleted$$$]$$$
—
Problem Idea: dutin
Problem Preperation: 3366
Occurrences: Novice 6, Advanced 3
You received a shipment of $$$N$$$ pandas labelled with numbers $$$x_1, x_2, \ldots, x_N$$$ from Mars ($$$N \leq 10^5$$$, $$$1 \leq x_i \leq 10^9$$$). Additionally, you have a magical zookeeper who has a favorite number $$$K$$$ ($$$K \leq 10^9$$$). The zookeeper will do the following exactly once:
- Pick two distinct pandas, say panda $$$i$$$ and panda $$$j$$$, and puts them to sleep.
- Concatenate the numbers on the labels of panda $$$i$$$ and panda $$$j$$$ to form a new number $$$y$$$.
- If $$$y$$$ is not divisible by $$$K$$$, then the zookeeper ships pandas $$$i$$$ and $$$j$$$ back to Mars.
Your task is to find the number of ordered pairs $$$(i, j)$$$ such that after performing the operation above, the zookeeper does not ship pandas $$$i$$$ and $$$j$$$ back to Mars.
Note: $$$i$$$ is not necessarily less than $$$j$$$. Also, the concatenation of $$$i$$$ and $$$j$$$ is different from the concatenation of $$$j$$$ and $$$i$$$.
A concatenation of numbers $$$x$$$ and $$$y$$$ is the number that is obtained by writing down numbers $$$x$$$ and $$$y$$$ one right after another without changing the order. For example, a concatenation of numbers $$$12$$$ and $$$3456$$$ is a number $$$123456$$$.
The first line contains an integer $$$T$$$ ($$$T \leq 100$$$), the number of test cases.
For each test case:
The first line contains two integers $$$N$$$ and $$$K$$$ ($$$1 \leq N \leq 10^5$$$, $$$1 \leq K \leq 10^9$$$) representing the number of pandas and the zookeeper's favorite number.
The second line contains $$$N$$$ space-separated integers $$$x_1, x_2, \ldots, x_N$$$ ($$$1 \leq x_i \leq 10^9$$$) representing the labels on the pandas.
It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$10^5$$$.
—
Tests in subtasks are numbered from $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.
Tests $$$1 - 5$$$ satisfy $$$N \leq 1000$$$, and the sum of $$$N$$$ over all test cases does not exceed $$$10^4$$$.
The remaining tests do not satisfy any additional constraints.
For each test case, output a single integer representing the number of ordered pairs $$$(i, j)$$$ such that after performing the operation, the zookeeper does not ship pandas $$$i$$$ and $$$j$$$ back to Mars. Output each testcase on a new line.
24 111 4 3 43 21 2 3
2 2
For the first test case, pairs $$$(2, 4)$$$ and $$$(4, 2)$$$ result in $$$y=44$$$ which is divisible by $$$11$$$.
For the second test case, pairs $$$(1, 2)$$$ and $$$(3, 2)$$$ work.
—
Problem Idea: yash belani
Problem Preparation: jay_jayjay
Occurrences: Novice 7, Advanced 4
Kyousuke is ordering sushi for Kirino. Sushi is free, but toppings cost money. The menu has $$$n$$$ toppings, each represented with a number $$$i$$$, where $$$i$$$ is a number from $$$1$$$ to $$$n$$$. Each topping has some price $$$a_i$$$. However, Kirino has a rule for each topping, where if Kyousuke orders some topping $$$i$$$ on the sushi he can't put some other topping $$$b_i$$$ on the sushi, because Kirino will slap him. What is the most expensive sushi Kyousuke can order that can satisfy Kirino?
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).
The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i \le 10^9$$$, $$$1 \le b_i \le n$$$) $$$-$$$ the price and the topping that doesn't go with the $$$i$$$th sushi, respectively.
—
There are $$$20$$$ tests. Each test is worth $$$\frac{100}{20}$$$ points.
Print one integer $$$-$$$ the most expensive sushi Kyousuke can order.
49 39 19 19 3
18
photographer: Hoshinomiya Yuna
—
Problem Idea: thehunterjames
Problem Preparation: thehunterjames
Occurrences: Novice 11, Advanced 5
You are given $$$n$$$ numbers $$$a_1, a_2, \dots, a_n$$$. How many numbers between $$$l$$$ and $$$r$$$ can be expressed in the form $$$\displaystyle\sum_{i=1}^{n} (a_i \oplus x)$$$, where $$$x$$$ is a nonnegative integer, and $$$\oplus$$$ denotes the bitwise XOR operation?
The first line consists of three integers $$$n$$$, $$$l$$$, and $$$r$$$ $$$(1 \leq n \leq 10^{5}, 0 \le l \le r \le 10^{18})$$$.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(0 \le a_i \le 10^5)$$$.
—
The first $$$5$$$ test cases (not including the sample) satisfy $$$n \le 100$$$, $$$a_i \le 100$$$, $$$0 \le l \le r \le 10^5$$$.
Print a single integer $$$-$$$ the number of reachable integers in the range $$$[l, r]$$$.
3 0 121 2 3
4
$$$x = 0$$$ gives a sum of $$$6$$$.
$$$x = 1$$$ gives a sum of $$$5$$$.
$$$x = 2$$$ gives a sum of $$$4$$$.
$$$x = 3$$$ gives a sum of $$$3$$$.
—
Problem Idea: thehunterjames
Problem Preparation: thehunterjames
Occurrences: Novice 9, Advanced 6
Mayoi Hachikuji has a habit of getting lost. The town she resides in can be modeled as a tree of $$$n$$$ nodes with strange weighted edges. Let $$$C_u(v)$$$ denote the weight of the edge from node $$$u$$$ to node $$$v$$$ when accessed from node $$$u$$$ (note that $$$C_u(v)$$$ is not necessarily equal to $$$C_v(u)$$$). When Mayoi is at node $$$u$$$, she will move to some node $$$v$$$ (which is adjacent to node $$$u$$$) with probability $$$\frac{C_u(v)}{\sum\limits_{\text{$$$v'$$$ is adjacent to node $$$u$$$}} C_u(v')}$$$ in $$$1$$$ step.
She has $$$q$$$ queries for you. Each query is in the form $$$s \ t$$$ where she wonders what the expected number of steps to reach node $$$t$$$ if she starts at node $$$s$$$. Since Mayoi isn't particularly good at math (or following directions), help her answer her queries!
The first line of input contains a single integer $$$T$$$ denoting the number of test cases $$$(1 \leq T \leq 3)$$$.
The first line of each test case contains two integers $$$n\ q$$$ denoting the number of nodes in the tree and the number of queries $$$(2 \leq n, q \leq 10^5)$$$.
The following $$$n-1$$$ lines contain four integers $$$u \ v \ C_u(v) \ C_v(u)$$$ denoting that there is an edge from node $$$u$$$ to node $$$v$$$ with cost $$$C_u(v)$$$ when accessed from node $$$u$$$ and cost $$$C_v(u)$$$ when accessed from node $$$v$$$ $$$(1 \leq u \leq v \leq n, 1 \leq C_u(v), C_v(u) \leq 3366)$$$. It is guaranteed that the edges form a tree.
The following $$$q$$$ lines each contain two integers $$$s \ t$$$ denoting the starting and ending nodes of Mayoi's query $$$(1 \leq s, t \leq n)$$$.
—
Tests in subtasks are numbered from $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.
Test $$$1$$$ satisfies $$$n, q \leq 10$$$.
Tests $$$2 - 3$$$ satisfy $$$n,q \leq 1000$$$.
Tests $$$4 - 5$$$ satisfy $$$t = 1$$$.
Tests $$$6 - 9$$$ satisfy $$$s = 1$$$.
Tests $$$10 - 13$$$ have the tree generated as follows: for each $$$i$$$ from $$$2$$$ to $$$n$$$, there is an edge from node $$$i$$$ to node $$$\lfloor \frac{i}{2} \rfloor$$$.
The remaining tests do not satisfy any additional constraints.
For each query, output a new line containing an integer $$$E$$$, denoting the expected number of steps modulo $$$998244353$$$. Let the answer be $$$\frac{x}{y}$$$. Output $$$E$$$ such that $$$x \equiv E \cdot y \pmod{998244353}$$$.
33 61 2 1 22 3 2 11 21 32 12 33 23 13 71 2 1 22 3 3 41 21 32 12 33 23 11 15 41 2 3 41 3 5 42 5 1 12 4 2 41 21 34 15 1
1 4 3 3 1 4 1 332748121 4 332748120 1 5 0 332748122 299473309 499122180 499122180
Problem Idea: dutin
Problem Preparation: 3366
Occurrences: Advanced 7
Waymo and Brian are discussing the winter 2023 seasonsals a string $$$s$$$ and will have $$$q$$$ different conversations. In some conversation, Brian will start talking about $$$s_{l \dots r}$$$, but Waymo will attempt to gaslight him into thinking he was talking about $$$s_{l' \dots r'}$$$ where $$$s_{l \dots r}$$$ and $$$s_{l' \dots r'}$$$ differ by exactly 1 element. Waymo loves to gaslight but he doesn't know the string well enough, so he asks you to construct an $$$l'$$$ and $$$r'$$$ for each $$$l \ r$$$ Brian talks about. Note that $$$r' - l' + 1 = r - l + 1$$$.
Note that two strings $$$a$$$ and $$$b$$$ of the same length differ by exactly $$$1$$$ element if and only if there exists some index $$$i$$$ such that $$$a_i \neq b_i$$$ and for all $$$j \neq i$$$, $$$a_j = b_j$$$.
The first line of input contains two integers $$$n$$$ and $$$q$$$ denoting the length of the string and the number of conversations $$$(1 \leq n \leq 7000, 1 \leq q \leq 10^6)$$$.
The second line of input contains the string $$$s$$$ of length $$$n$$$ and consists only of lowercase English letters.
The following $$$q$$$ lines each contain two integers $$$l$$$ and $$$r$$$, denoting the substring Waymo and Brian are talking about $$$(1 \leq l \leq r \leq n)$$$.
—
Tests in subtasks are numbered from $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$.
Tests $$$1 - 3$$$ satisfy $$$n, q \leq 100$$$.
Tests $$$4 - 7$$$ satisfy $$$n \leq 2000$$$.
Tests $$$8 - 10$$$ satisfy $$$q = n, l = 1$$$.
The remaining tests do not satisfy any additional constraints.
For each of the $$$q$$$ conversations, output a line containing two integers $$$l' \ r'$$$ denoting some valid answer as defined in the statement or $$$0$$$ $$$0$$$ if no such $$$l'$$$ and $$$r'$$$ exist. In the case that multiple valid $$$l'$$$ and $$$r'$$$ exist, output any of them.
7 6abaacba1 21 31 42 52 37 7
4 5 5 7 0 0 0 0 3 4 5 5
$$$s_{1 \dots 2} = ab$$$ and $$$s_{4 \dots 5} = ac$$$ differ by exactly $$$1$$$ element.
$$$s_{1 \dots 3} = aba$$$ and $$$s_{5 \dots 7} = cba$$$ differ by exactly $$$1$$$ element.
There exists no valid $$$l'$$$ and $$$r'$$$ that denote a substring that differs from $$$s_{1 \dots 4} = abaa$$$ by exactly $$$1$$$ element.
—
Problem Idea: 3366
Problem Preparation: 3366
Occurrences: Novice 12, Advanced 8
In Fireland, there are $$$n$$$ fires placed in a line fighting in a tournament, and the $$$i$$$-th fire has a power of $$$a_{i}$$$.
The tournament works as follows: If there are at least two fires remaining, the first two fires will fight.
When two fires with powers $$$x$$$ and $$$y$$$ fight, only three options can happen:
$$$1$$$ If $$$x$$$ $$$ \gt $$$ $$$y$$$, $$$y$$$ becomes disqualified.
$$$2$$$ If $$$x$$$ $$$ \lt $$$ $$$y$$$, $$$x$$$ becomes disqualified.
$$$3$$$ If $$$x$$$ $$$=$$$ $$$y$$$, both become disqualified.
Your task is to answer $$$q$$$ independent queries of the form:
Given $$$l$$$, $$$r$$$ and $$$x$$$, you have to find the index of the tournament's winner if each value in the range $$$[l, r]$$$ becomes changed to $$$x$$$, or report that nobody wins.
Check the sample explanations for a better understanding of the problem.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1 \leq t \leq 69)$$$. The description of the test cases follows.
The first line consists of two integers $$$n$$$ $$$(2 \leq n, q \leq 6.9 \cdot 10^{5})$$$ $$$-$$$ the number of fires and the number of queries, respectively.
Then follows $$$n$$$ integers $$$a_{i}$$$ $$$(-6.9 \cdot 10^{8} \leq a_{i} \leq 6.9 \cdot 10^{8})$$$ $$$-$$$ the fires powers.
The last $$$q$$$ lines consist of three integers $$$l$$$, $$$r$$$ and $$$x$$$ $$$(1 \leq l \leq r \leq n ; -6.9 \cdot 10^{8} \leq x \leq 6.9 \cdot 10^{8})$$$ $$$-$$$ the values of the queries.
It is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases do not exceed $$$6.9 \cdot 10^{5}$$$.
—
Testcases in subtasks are numbered from $$$1$$$ to $$$20$$$ with samples skipped.
Tests $$$1-3$$$: $$$(2 \leq n, q \leq 6.9 \cdot 10^{3})$$$ and it is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases do not exceed $$$6.9 \cdot 10^{3}$$$.
Tests $$$4-6$$$: $$$(2 \leq n, q \leq 6.9 \cdot 10^{4})$$$ and it is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases do not exceed $$$6.9 \cdot 10^{4}$$$.
Tests $$$7-20$$$: No additional constraints.
Each test is worth 5 points with samples skipped.
For each query, you have to output the index of the tournament's winner. If nobody wins the tournament, the answer is $$$n+1$$$.
25 51 2 1 4 31 1 64 4 32 3 41 3 52 4 32 2-1 -21 1 -11 2 0
1 6 4 3 6 1 3
For the first test case:
The answer to the first query is $$$1$$$ because the fire on position $$$1$$$ has the unique biggest power.
The answer to the third query is $$$4$$$ because the first fire loses against the second one, and when the second and the third fire fight, they both become disqualified. Finally, the fourth fire wins the fifth one and becomes the tournament's winner.
For the second test case:
The answer to the second query is $$$3$$$ because if $$$a_{0}$$$ and $$$a_{1}$$$ are equal, when they fight they both become disqualified.
—
Problem Idea: danx
Problem Preparation: danx
Occurrences: Advanced 9
Note that since the online judge runs a little faster than codeforces, the time limit here is 7 seconds as opposed to 5 seconds.
Waymo has been farming chips from the sniper-caster chip stage. The stage has a $$$p$$$ chance of dropping a sniper chip and a $$$1 - p$$$ chance of dropping a caster chip. Waymo only has use for sniper chips, and he can exchange exactly $$$x$$$ caster chips for exactly $$$y$$$ sniper chips (Waymo can exchange as many times as he wants provided he still has at least $$$x$$$ caster chips). Waymo only has the sanity to play the stage $$$n$$$ times. What is the expected number of sniper chips he can obtain?
The first line of input contains a single integer $$$T$$$, denoting the number of test cases $$$(1 \leq T \leq 20)$$$.
The first line of each test case contains four integers $$$a \ x \ y \ n$$$, denoting $$$p = \frac{a}{100}$$$, $$$x$$$ and $$$y$$$ as the caster to sniper chip conversion, and n as the number of times Waymo plays the stage $$$(0 \leq a \leq 100, 1 \leq y \leq x \leq 100, 1 \leq n \leq 10^{18})$$$.
—
Test in subtasks are numbered $$$1 \dots 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.
For all odd tests, $$$a = 50$$$.
For tests $$$1 - 2$$$, $$$x, y, n \leq 8$$$.
For tests $$$3 - 6$$$, the sum of $$$n$$$ across all test cases is $$$\leq 10^5$$$.
There are no additional constraints on the remaining tests.
For each test case, output one integer $$$E$$$, where $$$E$$$ is the expected number of sniper chips modulo $$$998244353$$$. Let the expected number of sniper chips be $$$\frac{s}{t}$$$, output $$$E$$$ where $$$E \cdot t \equiv s \pmod {998244353}$$$.
450 3 2 350 3 2 59 8 7 625 7 6 2
249561090 499122180 818560370 499122177
333 36 33 336610 50 30 10000023 47 26 123456789
872335076 227994141 125109249
Say a sniper chip is $$$a$$$ and a caster chip is $$$b$$$.
The first test case's expected value is as follows:
$$$aaa=3, aab=2, aba=2, abb=1, baa=2, bab=1, bba=1, bbb=2$$$
Each scenario is equally likely to occur.
$$$\frac{3 + 2 + 2 + 1 + 2 + 1 + 1 + 2}{8} = \frac{14}{8}$$$
$$$\frac{14}{8} \equiv 249561090 \pmod{998244353}$$$
For the second test case, $$$\frac{112}{32} \equiv 499122180 \pmod{998244353}$$$
—
Problem Idea: 3366
Problem Preparation: 3366
Occurrences: Advanced 10
Andrew was gifted a tree with $$$n$$$ nodes numbered from $$$1$$$ to $$$n$$$ and $$$q$$$ queries to answer. Each query consists of an integer $$$k$$$ between $$$1$$$ and $$$n$$$, inclusive, and $$$k$$$ different integers $$$x_1, x_2, \ldots, x_k$$$, each $$$x_i$$$ denoting the node numbered $$$x_i$$$.
The score of a forest is defined as the bitwise AND of the minimum values from each tree in the forest. After each query, Andrew's task was to print the maximum score of a forest obtained by removing some, possibly none, of the nodes given in the query. The score of an empty forest is $$$0$$$. When a node is removed, so are all the edges incident to it.
Andrew said that the problem was trivial and that he didn't want it, so he has now given it to you. Because you don't want to offend Andrew, you must now solve the problem.
Note: If you don't understand some graph theory terminology such as tree or forest, you can read about it from here.
The first line contains a single integer $$$t$$$, the number of test cases. ($$$1 \le t \le 10$$$).
The first line of each test case contains two integers $$$n$$$ and $$$q$$$ denoting the number of nodes and queries, respectively. ($$$1 \le n, q \le 5 \cdot 10^5$$$).
Then follow $$$n-1$$$ lines, each consisting of two integers $$$u$$$ and $$$v$$$, meaning that there is an edge between nodes $$$u$$$ and $$$v$$$. ($$$1 \le u, v \le n$$$; $$$u \neq v$$$). It is guaranteed that the edges form a tree.
Then follow $$$q$$$ lines, each containing an integer $$$k_i$$$ followed by $$$k_i$$$ integers $$$x_1 \lt x_2 \lt \ldots \lt x_{k_i}$$$, the nodes that can be removed in that query. ($$$1 \le k_i \le n$$$).
Additionally, it is guaranteed that the sum of $$$n$$$ and the sum of all $$$k_i$$$ over all test cases is at most $$$5 \cdot 10^5$$$.
—
Tests in subtasks are numbered from $$$1-20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.
Tests $$$1 - 10$$$ satisfy $$$q \leq 5$$$.
For each query, print a single integer denoting the maximum score of a forest that Andrew can obtain.
17 51 51 31 75 65 25 43 2 3 41 13 1 2 35 1 2 4 5 64 1 2 3 4
1 2 4 3 5
17 75 33 66 11 77 22 41 12 1 23 1 2 34 1 2 3 45 1 2 3 4 56 1 2 3 4 5 67 1 2 3 4 5 6 7
2 2 4 4 6 7 7
—
Problem Idea: Esomer
Problem Preparation: Esomer
Occurrences: Advanced 11
The difference between the Easy and Hard versions is the constraints on $$$T$$$ and $$$R$$$.
Utena really likes the number $$$3$$$. Let $$$f(x)$$$ count the number of $$$3$$$'s in the base-$$$10$$$ representation of $$$x$$$.
Given two integers $$$l$$$ and $$$r$$$ where $$$l \leq r$$$, compute $$$g(l, r)$$$, the sum of $$$f(x)$$$ for all $$$x$$$ such that $$$l \leq x \leq r$$$ and $$$0 \equiv x \pmod{3}$$$. That would have been the problem but Utena forgot what $$$l$$$ and $$$r$$$ were.
So given $$$L$$$ and $$$R$$$, compute the sum of $$$g(l, r)$$$ for $$$L \leq l \leq r \leq R$$$. Since this number may be very large, please find it modulo $$$998244353$$$.
The first line of input contains a single integer $$$T$$$, denoting the number of test cases $$$(1 \leq T \leq 10)$$$.
Each test case consists of two lines. The first line contains an integer $$$L$$$ and the second line contains an integer $$$R$$$ $$$(1 \leq L \leq R \leq 10^{10^5})$$$.
—
Tests in subtasks are numbered from $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.
Test $$$1$$$ satisfies $$$R \leq 100$$$.
Test $$$2 - 3$$$ satisfies $$$R \leq 1000$$$.
Tests $$$4 - 5$$$ satisfy $$$R \leq 10^5$$$.
Tests $$$6 - 8$$$ satisfy $$$L = 1, R = 10^k$$$ for some integer $$$k$$$.
Tests $$$9 - 11$$$ satisfy $$$L = 1$$$.
Tests $$$12 - 14$$$ satisfy $$$\lceil \log_{10}(R) \rceil \leq 10^3$$$.
The remaining tests do not satisfy any additional constraints.
For each test case, output a new line a containing single integer $$$S$$$, denoting the desired sum modulo $$$998244353$$$.
511011003040336633666633
24 14808 130 512 767342710
Problem Idea: 3366
Problem Preparation: 3366
Occurrences: Advanced 12