Busy Beaver is trying to get into MIT. Instead of taking the SAT, he thinks he can do better — three times better, as he sets out to solve 3-SAT! He's found a truly marvelous solution, but unfortunately, the margins of his application were too narrow to contain it. So, he came up with his own version of the problem, but he needs your help solving it:
Let $$$n, m$$$ be positive integers. There are $$$n$$$ variables $$$x_1, \dots, x_n$$$ taking values in $$$\{0, 1\}$$$. A clause is a product of three variables $$$x_a \cdot x_b \cdot x_c$$$ with indices $$$1 \leq a \leq b \leq c \leq n$$$. You are given an expression that is a sum of $$$m$$$ such clauses. For example, one such expression in four variables with three clauses could be $$$$$$x_1 \cdot x_2 \cdot x_3 + x_1 \cdot x_3 \cdot x_4 + x_2 \cdot x_3 \cdot x_4.$$$$$$ Determine if it is possible to choose the values $$$x_1, \dots, x_n$$$ such that the resulting expression is odd.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1 \leq t \leq 10^5)$$$. The description of the test cases follows.
The first line of each test case contains two integers $$$n, m$$$ ($$$1 \leq n, m \leq 10^5$$$).
The next $$$m$$$ lines of each test case describe each of the clauses in the sum. The $$$i^{\mathrm{th}}$$$ of them consists of three space separated integers $$$a_i, b_i, c_i$$$ ($$$1 \leq a_i \leq b_i \leq c_i \leq n$$$), denoting that the $$$i^{\mathrm{th}}$$$ clause of the sum is $$$x_{a_i} \cdot x_{b_i} \cdot x_{c_i}$$$.
It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases do not exceed $$$10^5$$$.
For each test case, output one line containing the string YES if there exists a setting of the $$$x_i$$$ to make the expression odd, and NO otherwise. You can print each letter in any case. For example, yes, Yes, YeS will all be recognized as a positive answer.
Then, if you responded with YES, print a second line consisting of space separated integers $$$x_1, \dots, x_n$$$ ($$$x_i = 0$$$ or $$$1$$$) that makes the expression evaluate to an odd number. If there are multiple possible solutions, print any of them.
You will receive $$$50\%$$$ of the points for each subtask if the YES/NO responses are correct, but the provided values of $$$x_i$$$ are not. For each testcase, you must output exactly $$$n$$$ values of $$$x_i$$$ for partial credit.
24 31 2 31 3 42 3 43 21 2 31 2 3
YES 1 1 1 1 NO
The first test case is identical to the example in the problem statement. In this expression, setting all of the variables to $$$1$$$ makes the expression equal to $$$1 + 1 + 1 = 3$$$, which is odd.
In the second test case, the given expression is $$$x_1 \cdot x_2 \cdot x_3 + x_1 \cdot x_2 \cdot x_3$$$. It can be shown that no setting of $$$x_1, x_2, x_3$$$ makes this expression odd.
Tim the Busy Beaver has signed up for a pistol class in order to pass their PE requirement and wants to be an elite marksman. The MIT shooting range has $$$N$$$ $$$(1 \leq N \leq 3 \cdot 10^5)$$$ lanes numbered from $$$1$$$ to $$$N$$$. Lane $$$i$$$ currently has $$$A_i$$$ $$$(0 \leq A_i \leq 5 \cdot 10^5)$$$ targets lined up in a row. It is guaranteed that there is at least one target in the entire range.
Tim's practice gun has an infinite number of bullets, and he needs to shoot down every target. Before each shot, Tim will pick a lane and fire $$$1$$$ shot down that lane. Once a target is hit, it will be knocked down and will never come back up.
However, Tim's aim is terrible, so every odd-numbered shot will hit the first target in the lane, while every even-numbered shot will miss the first target in the lane and hit the second one (if it exists). The first shot is shot $$$1$$$.
Tim is not allowed to fire a shot that does not hit any target, as it would damage the wall behind the targets. Help Tim find a sequence of shots that will knock down every target, or state that no such sequence exists.
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 1000)$$$: the number of test cases. The description of the test cases follows.
Each of the $$$t$$$ testcases consists of $$$2$$$ lines. The first line contains $$$N$$$, the number of lanes. The second line contains $$$N$$$ spaced integers $$$A_1,A_2,\cdots, A_n$$$, indicating the number of targets in each lane.
It is guaranteed that the sum of $$$A_i$$$ across all test cases is no more than $$$5\cdot 10^5$$$.
It is guaranteed that the sum of $$$N$$$ across all test cases is no more than $$$3 \cdot 10^5$$$.
For each testcase, output "YES" if there exists a sequence of shots that hits every target, or "NO" if no such sequence exists. 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.
Let $$$A$$$ be the sum of $$$A_i$$$ in the testcase (note that $$$A$$$ may be different for different test cases). If such a sequence exists, output on a separate line a sequence of $$$A$$$ space-separated integers $$$l_1,l_2,\cdots, l_A$$$, where $$$l_i$$$ is the lane that Wabbit should fire the $$$i$$$-th shot at. If there are multiple solutions, print any of them.
You will receive $$$50\%$$$ of the points for each subtask if the YES/NO responses are correct, but the provided values of $$$l_i$$$ are not. For each testcase, you must output exactly $$$A$$$ values of $$$l_i$$$ for partial credit.
3131251 1 1 1 1
YES 1 1 1 NO NO
In the first test case, there is only $$$1$$$ lane with $$$3$$$ targets, and Wabbit can knock down all targets by firing 3 shots at lane $$$1$$$. If the targets are $$$A,B$$$ and $$$C$$$ from front to back, the first shot will knock down $$$A$$$, the second shot will miss $$$B$$$ and knock down $$$C$$$, and the last shot will knock down $$$B$$$.
In the second test case, there is only $$$1$$$ lane with $$$2$$$ targets. The first shot at lane $$$1$$$ will hit the front target, but the second shot will not knock down the remaining target as it will miss. Thus, no sequence of shots exists for this test case.
In the third test case, there are $$$5$$$ lanes with $$$1$$$ target each. The first shot at any lane will hit the target at that lane, but the second shot will not be able to hit any other target. Thus, no sequence of shots exists for this test case.
Busy Beaver is making a new language for his linguistics class! He has already decided that his language will have an alphabet whose letters are the integers $$$1, \ldots, NM$$$ in that order; now he wants to make some words for the language.
Because Busy Beaver is interested in statistics, he wants to control the frequencies of letters appearing in words, so he has chosen a multiset $$$a$$$ of size $$$NM$$$ of letters from his alphabet. He will now form $$$N$$$ words each with $$$M$$$ letters such that each letter from $$$a$$$ is used exactly once (i.e. if a given letter $$$x$$$ appears exactly $$$k$$$ times in $$$a$$$, then it is used exactly $$$k$$$ times across all $$$N$$$ words).
After forming the words, Busy Beaver plans to organize them into a dictionary, so he will lexicographically sort his $$$N$$$ words to produce the sequence of words $$$s_1, \ldots, s_N$$$. Busy Beaver likes strings to be lexicographically small, so for each $$$k$$$ from $$$1$$$ to $$$N$$$ he wants to know the lexicographically minimum possible value of $$$s_k$$$ over all choices of words.
Note that the answer for each $$$s_k$$$ is independent; for example, the choice of words so that $$$s_1$$$ is minimized may be different from the choice of words so that $$$s_2$$$ is minimized.
The first line contains two positive integers $$$N, M$$$ ($$$1 \leq NM \leq 10^6$$$).
The second line contains $$$NM$$$ integers $$$a_1, \ldots, a_{NM}$$$ composing the multiset $$$a$$$ ($$$1 \leq a_j \leq NM$$$).
For each $$$k$$$ from $$$1$$$ to $$$N$$$, output the minimum possible value of $$$s_k$$$ on its own line as a sequence of space-separated integers.
4 31 1 2 2 3 3 4 4 5 5 6 6
1 1 2 1 2 3 2 2 3 2 3 4
3 412 4 4 4 1 1 4 4 6 4 1 4
1 1 1 4 1 4 4 4 1 4 4 12
4 512 7 17 3 6 11 9 2 17 7 1 6 9 12 6 3 9 12 2 15
1 2 2 3 3 2 2 3 3 6 2 3 6 7 7 3 3 6 6 6
1 11
1
In the first sample, the following choices of words minimize each of $$$s_k$$$:
By choosing the words $$$112, 233, 445, 566$$$, we get that $$$s = 112, 233, 445, 566$$$, so $$$s_1 = 112$$$ as desired.
By choosing the words $$$123, 456, 123, 456$$$, we get that $$$s = 123, 123, 456, 456$$$, so $$$s_2 = 123$$$ as desired.
By choosing the words $$$166, 155, 344, 223$$$, we get that $$$s = 155, 166, 223, 344$$$, so $$$s_3 = 223$$$ as desired.
By choosing the words $$$234, 234, 156, 156$$$, we get that $$$s = 156, 156, 234, 234$$$, so $$$s_4 = 234$$$ as desired.
It can be shown that in all of these cases there is no way to choose the words so that the respective $$$s_k$$$ is even lexicographically smaller.
A majority element of a sequence of positive integers is a number equal to at least half of its elements.
Call a sequence good if all of its nonempty contiguous segments have at least one majority element. For example, $$$[1, 2, 1, 1, 3]$$$ is good, since segments such as $$$[1, 1, 3]$$$, $$$[1, 2]$$$, and $$$[2, 1, 1, 3]$$$ all have majority elements, but $$$[1, 2, 1, 3]$$$ is not good because $$$[2, 1, 3]$$$ does not have a majority element.
Given a string consisting of 1, 2, 3, and ?, count the number of ways to form a good sequence of $$$1$$$, $$$2$$$, and $$$3$$$'s by changing each ? to one of $$$1$$$, $$$2$$$, and $$$3$$$. Output the answer modulo $$$10^9 + 7$$$.
The first line contains an integer $$$N$$$ ($$$3 \le N \le 200$$$), the length of the string.
The second line contains a string of length $$$N$$$, consisting of 1, 2, 3, and ?.
Output the remainder when the answer is divided by $$$10^9 + 7$$$.
3???
21
312?
2
41?11
3
512213
0
10???1??????
1735
For the first sample, the only arrays (out of $$$3^3 = 27$$$ possible ones) that are not good are $$$[1, 2, 3]$$$ and its permutations, so the answer is $$$27 - 3! = 21$$$.
For the second sample, $$$[1, 2, 1]$$$ and $$$[1, 2, 2]$$$ are good, but not $$$[1, 2, 3]$$$.
For the third sample, $$$[1, 1, 1, 1]$$$, $$$[1, 2, 1, 1]$$$, and $$$[1, 3, 1, 1]$$$ are all good.
For the fourth sample, since $$$[1, 2, 2, 1, 3]$$$ is not good, the answer is zero.
You are given a directed graph $$$G$$$ with $$$N$$$ nodes and $$$M$$$ edges, where each edge has an integer weight in $$$[0,9]$$$. Check if there exists an infinitely long walk from node $$$1$$$ where, if we view the weights as the digits of a decimal number, this number converges to an irrational number. (Formally, if the weight of the $$$i^\text{th}$$$ edge is $$$d_i$$$, then the condition is that $$$0.\overline{d_1 d_2 d_3 \dots}$$$ is irrational.)
The graph can have self loops, contain multiple edges between the same pair of nodes, and be disconnected.
The first line contains an integer $$$T$$$ ($$$1 \le T \le 2 \cdot 10^5$$$), the number of test cases.
The first line of each test case contains two integers $$$N, M$$$ ($$$1 \le N, M \le 2 \cdot 10^5$$$), the number of nodes and edges in $$$G$$$, respectively.
The $$$i^\text{th}$$$ of the next $$$M$$$ lines of each test case contains three integers $$$a_i, b_i, d_i$$$ ($$$1 \le a_i, b_i \le N$$$, $$$0 \le d_i \le 9$$$), indicating an edge from $$$a_i$$$ to $$$b_i$$$ with weight $$$d_i$$$.
It is guaranteed that the sum of $$$N$$$ over all test cases and the sum of $$$M$$$ over all test cases both do not exceed $$$2 \cdot 10^5$$$.
Output $$$T$$$ lines, each containing either Yes or No (case insensitive).
34 41 2 11 2 12 3 23 1 32 41 1 01 2 12 1 12 2 06 61 2 41 3 52 4 62 5 76 6 86 6 9
No Yes No
In the first test case, all infinitely long walks from node $$$1$$$ correspond to the number $$$0.\overline{123123\dots} = \frac{41}{333}$$$, which is rational. Therefore, it's not possible to obtain an irrational number.
In the second test case, all numbers with digits $$$0$$$ and $$$1$$$ are obtainable.
In the third test case, there does not exist an infinitely long walk from node $$$1$$$.