Jesse has an integer $$$x$$$. He wants to find an integer $$$y$$$ ($$$0 \leq y \leq 100$$$) such that when you concatenate $$$(x+y)^2$$$ and $$$(x+y)^3$$$, you get a permutation of the digits $$$0\dots9$$$. More specifically, you get a sequence of digits where each digit $$$0...9$$$ occurs exactly once.
Can you help him find the integer?
For example, if $$$x = 27$$$, $$$y = 42$$$ would be a valid answer answer since $$$(27+42)^2 = 4761$$$ and $$$(27+42)^3 = 328509$$$. When you concatenate them, you get $$$4761328509$$$, which is a permutation of the digits $$$0...9$$$.
Note that leading zeroes are discarded before concatentation.
The first line contains a single integer $$$x$$$ ($$$0 \leq x \leq 50$$$)
Print a single integer $$$y$$$ ($$$0 \leq y \leq 100$$$) $$$-$$$ Jesse's desired integer. If there are multiple answers, print any.
27
42
The sample is the example explained in the statement.
Problem Credits: Eric Hsu
A binary string is a string that only contains 0 and 1. Mythreya wants you to make a binary string for him.
Mythreya defines the palindromicity of a binary string $$$s$$$ of length $$$n$$$ as the number of differences between a binary string $$$s$$$ and its reverse. More specifically, the palindromicity is the number of indices $$$1 \leq i \leq n$$$ such that $$$s_{i} \neq s_{n-i+1}$$$.
Determine if you can find a binary string of length $$$n$$$ with palindromicity of $$$k$$$, and if so output one such string for Mythreya.
The first line will contain $$$t$$$ ($$$1 \leq t \leq 10^4$$$), the number of testcases.
The next $$$t$$$ lines will each contain two integers $$$n, k$$$ ($$$1 \leq k \leq n \leq 2 \cdot10^5$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases won't exceed $$$2\cdot10^5$$$.
For each testcase, output NO if there does not exist a string containing only $$$0$$$ and $$$1$$$ with a palindromicity of $$$k$$$. Otherwise, output YES and a string of length $$$n$$$ satisfying $$$k$$$ on two separate lines.
34 27 38 6
YES 0111 NO YES 10101000
In the first testcase 0111 has a palindromicity of $$$2$$$, since it has exactly $$$2$$$ differences with 1110 at positions $$$1$$$ and $$$4$$$.
It can be shown there is no way to construct a valid string for the second testcase.
Problem Credits: Mythreya Dharani
Eric's $$$n$$$ red pandas have been mixed up!
They currently lie on the number line, occupying points $$$p_1, p_2, \dots p_n$$$. You are given the distance between all pairs of red pandas. Please help Eric figure out the order of the pandas.
The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 500)$$$, the number of test cases.
The first line of each test case contains an integer, $$$n$$$ $$$(1 \leq n \leq 1000)$$$.
Then the line after that contains $$$n$$$ integers, $$$p_1, p_2, \dots p_n$$$ $$$(1 \leq p_i \leq 10^9)$$$, given in increasing order.
Then $$$n$$$ lines follow. The $$$i$$$th of these lines will contain $$$n$$$ integers, $$$d_{i1}, d_{i2}, \dots d_{in}$$$, where $$$d_{ij}$$$ is the distance between red panda $$$i$$$ and red panda $$$j$$$. Note that a panda is distance $$$0$$$ from itself.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.
For each test case, output one line containing $$$n$$$ integers, $$$a_1, a_2, \dots, a_n$$$, where $$$a_i$$$ is the panda at point $$$p_i$$$. If there are multiple correct answers, output any.
231 2 30 1 21 0 12 1 041 3 8 90 6 2 56 0 8 12 8 0 75 1 7 0
3 2 1 3 1 4 2
For the first test case, both $$$[1, 2, 3]$$$ and $$$[3, 2, 1]$$$ are valid answers.
Problem Credits: Mythreya Dharani
Allen has an array $$$a$$$ with $$$n$$$ elements. He will perform the following operation as many times as he likes:
Select two distinct elements of the array and a number $$$x$$$, and bitwise XOR both elements by $$$x$$$. Formally, Allen can choose indices $$$i,j$$$ of his array ($$$1\leq i,j \leq n, i\neq j$$$) and a number $$$x$$$, and then set $$$a_i = a_i \oplus x$$$ and $$$a_j = a_j \oplus x$$$, where $$$\oplus$$$ denotes the bitwise XOR operation.
What is the minimum possible value of the maximum element in Allen's array after any number of operations?
The first line contains one integer $$$t$$$ $$$(1 \leq t \leq 10^4)$$$ — the number of test cases.
Each test case consists of a number $$$n$$$ $$$(2 \leq n \leq 2\cdot 10^5)$$$ – the size of the array.
The next line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(0 \leq a_i \lt 2^{30})$$$, the numbers in Allen's array.
It is guaranteed that the sum of all $$$n$$$ does not exceed $$$2\cdot 10^5$$$.
For each test case, output the minimum possible value of the maximum element in Allen's array.
251 4 2 5 731 2 3
4 0
In the first case, selecting $$$(i,j) = (4,5)$$$ and $$$x=1$$$ and then $$$(i,j) = (3,5)$$$ and $$$x=2$$$ results in $$$4$$$ being the maximum element. It can be shown that this is the minimum possible value of the maximum.
In the second case, selecting $$$(i,j) = (1,3)$$$ and $$$x=1$$$ and then $$$(i,j) = (2,3)$$$ and $$$x=2$$$ results in $$$0$$$ being the maximum element. It can be shown that this is the minimum possible value of the maximum.
For a positive integer $$$x$$$, define the cascading sum of $$$x$$$ as the sum of all of $$$x$$$'s nonempty prefixes.
For example, the cascading sum of $$$2023$$$ is $$$2023+202+20+2=2247$$$.
You are given $$$q$$$ queries, where each query gives you a positive integer $$$n$$$. For each query, output the number of positive integers $$$m$$$ such that $$$m \le n$$$ and $$$m$$$ is not the cascading sum of any number.
The first line consists of an integer $$$q$$$, the number of queries ($$$1 \leq q \leq 10^5$$$). The description of the queries follows.
The first line of each query contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^{18})$$$.
For each query, output the number of positive values which are not cascading sums and are at most $$$n$$$.
5 4 10 220 3000 3500
0 1 21 299 349
For the first query, $$$m = 1, 2, 3, 4$$$ are all cascading sums. For example, $$$3$$$ is the cascading sum of $$$3$$$. Therefore, there are $$$0$$$ values.
For the second query, $$$10$$$ is the only value which is not a cascading sum, so there is $$$1$$$ value.
Problem Credits: Anonymous Red Panda
Daniel has $$$n$$$ trees in his backyard, each numbered from $$$1$$$ to $$$n$$$, and he is currently in the tree numbered $$$1$$$. These trees are very special, and can grow cereal on them! When Daniel is hungry, he travels from tree to tree and eats cereal from the trees that he reaches. Furthermore, each tree has a different type of cereal on it, and he would like to eat as many different varieties of cereal as possible.
Unfortunately, traveling from tree to tree takes a lot of energy. Specifically, traveling from tree $$$a$$$ to tree $$$b$$$ takes $$$a | b$$$ energy, where $$$|$$$ denotes the bitwise OR operator. However, once he has traveled on a path from $$$a$$$ to $$$b$$$, it no longer takes energy for it to travel on that path.
Recently, the cereal trees have been taking a long time to regrow their cereal, meaning every day, there is exactly one cereal tree that has no cereal on it. Daniel is trying to plan his meals for the next $$$d$$$ days. On a day $$$i$$$, he knows that there will be no cereal on tree $$$t_i$$$, and therefore will decide to skip visiting that tree that day. It is guaranteed that tree $$$1$$$ is never skipped. Note that each day is independent of other days - an empty tree on day $$$1$$$ will not stay empty on day $$$2$$$, and paths traveled on day $$$1$$$ reset on day $$$2$$$.
Daniel is very lazy, so can you help him figure out the smallest amount of energy he can spend to reach all cereal-bearing trees for each of the next $$$d$$$ days?
The first line of input contains $$$2$$$ integers $$$n$$$ ($$$2\le n \le 10^5$$$) and $$$d$$$ ($$$1\le d \le 10^5$$$). Then $$$d$$$ lines follow.
Each of these $$$d$$$ lines contains one integer $$$t_i$$$ ($$$2\le t_i \le n$$$).
For each value of $$$t_i$$$ from the input, output onto separate lines the minimum amount of energy Daniel can spend to reach all cereal-bearing trees each day.
5 2 3 4
13 11
When tree $$$3$$$ has no cereal, Daniel can use paths $$$1-2$$$, $$$1-4$$$, and $$$5-4$$$, leading to a total energy of $$$3 + 5 + 5 = 13$$$.
When tree $$$4$$$ has no cereal, Daniel can use paths $$$1-2$$$, $$$2-3$$$, and $$$1-5$$$, leading to a total energy of $$$3 + 3 + 5 = 11$$$.
Problem Credits: Daniel Kim
Michael has gotten the internship of a lifetime! He will be working (unpaid, obviously) at Thomas' zoo in the red panda enclosure.
The enclosure can be described as a tree of $$$n$$$ nodes, rooted at node $$$1$$$. Each node contains a house which has exactly one red panda in it. Every afternoon, Michael will be in charge of organized nap-time for the pandas, which involves all $$$n$$$ red pandas reaching the root of the tree to take a nap. It works as follows:
- In one second, Michael may let any number of pandas out of their homes. Then, all pandas that have been let out of their home, other than those at the root, climb up one node in the tree towards the root. The process repeats until Michael has placed all $$$n$$$ pandas.
- If two red pandas ever occupy the same node other than the root, they will start a fight, so this cannot happen.
Note that the panda that lives in node $$$1$$$ must still be let out of its house to join the other pandas (and hug them).
Michael wants to accomplish this task as fast as possible, so he can eat his lunchtime Raisin Brain cereal. What is the minimum time (in seconds) that it will take for Michael to finish placing all pandas, and what is a possible way he can achieve it? Note that Michael will be finished once he places the last panda, not when all pandas reach the root.
The problem has $$$t$$$ ($$$1 \leq t \leq 10^4$$$) independent test cases.
For each test case, the first line will contain $$$n$$$ ($$$2 \leq n \leq 2\cdot10^5$$$). The next $$$n - 1$$$ lines contain the edges of the tree. Each line will have two integers, $$$u$$$ and $$$v$$$, meaning there is an edge between nodes $$$u$$$ and $$$v$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$2 \cdot 10^5$$$.
For each test case, print the minimum number of seconds it will take Michael to place the pandas.
Then, in a new line, print $$$i$$$ integers, where the $$$i$$$-th integer is the second during which Michael should let out the panda in node $$$i$$$. If there are multiple possible solutions, print any.
241 23 24 151 21 33 45 3
1 1 1 1 1 2 1 1 1 1 2
For the first test case, Michael can release all pandas at once.
For the second test case, Michael can't release all pandas at once since the pandas at nodes $$$4$$$ and $$$5$$$ will start a fight.
Problem Credits: Allen Wu
Jesse and Jerry are in outer space! Unfortunately, they have gotten lost and ended up on either side of a huge asteroid range.
There are $$$n$$$ asteroids in a row, numbered $$$1, 2, \ldots, n$$$. The $$$i$$$-th asteroid from the left has a size $$$s_i$$$.
Jesse starts to the left of asteroid $$$1$$$, and Jerry starts to the right of asteroid $$$n$$$. They are both floating in space, so we say that they start standing on asteroids of size $$$0$$$.
Jesse always wants to outdo Jerry, so he is only happy if he's standing on an asteroid at least as large as the one Jerry's standing on. Formally, if Jesse is standing on asteroid $$$a$$$ and Jerry is standing on asteroid $$$b$$$, Jesse is only happy if $$$s_b \le s_a$$$.
They also want to stand on the same asteroid (they need to plan CerealCodes!). To help them, you are allowed to send them instructions, each consisting of a single character:
- A: tell Jesse to move to the asteroid on his right;
- B: tell Jerry to move to the asteroid on his left.
You will send them these instructions as a string of length $$$n+1$$$, consisting of the letters A and B.
Find the lexicographically maximum string of instructions that brings Jesse and Jerry together while keeping Jesse happy at all times.
A string $$$s$$$ of length $$$n+1$$$ is lexicographically greater than a string $$$t$$$ of length $$$n+1$$$ if and only if the following holds:
- in the first position where $$$s$$$ and $$$t$$$ differ, the string $$$s$$$ has a letter that appears later in the alphabet than the corresponding letter in $$$t$$$.
There will be $$$t$$$ ($$$1 \leq t \leq 1000$$$) independent test cases.
The first line of each test case contains $$$n$$$, the number of asteroids ($$$1 \le n \le 5000$$$).
The second line of each test case contains $$$n$$$ integers $$$s_1, s_2, \ldots, s_n$$$ ($$$1 \le s_i \le 10^9$$$) — the sizes of the asteroids.
The sum of $$$n$$$ over all test cases will not exceed $$$5000$$$.
For each test case, print a string of length $$$n+1$$$, representing the lexicographically maximum sequence of instructions satisfying the conditions above.
275 2 6 5 3 4 111
ABAABBBB AB
Here is the optimal path of traversal:
- First, Jesse moves to asteroid $$$1$$$. $$$0 \le a_1$$$, so Jesse is happy;
- Next, Jerry moves to asteroid $$$7$$$. $$$a_7 \le a_1$$$, so Jesse is happy;
- Jesse then moves to asteroid $$$2$$$. $$$a_7 \le a_2$$$, so Jesse is happy;
- Jesse moves again to asteroid $$$3$$$. $$$a_7 \le a_3$$$, so Jesse is happy.
Problem Credits: Mythreya Dharani and Eric Hsu
Ryan loves to eat Honey Nut Cereal, but there is a shortage of honey. To get honey, you obviously need to pollinate the flowers.
A flower of size $$$n$$$ resides on a square grid of length $$$2n + 1$$$. The rows are numbered $$$1\dots2n+1$$$ from top to bottom, and the columns are numbered $$$1\dots2n+1$$$ from left to right. The center of the flower is at the cell in row $$$n + 1$$$ and column $$$n + 1$$$. Any cell with a Manhattan distance $$$x$$$ from the center such that $$$1 \leq x \leq n$$$ contains a petal. Note that the center doesn't contain a petal. Below is an example of such a flower.
a flower of size $$$3$$$ You want to cover only the petals of the flower with L-shaped pieces such as the one below. Each petal should be covered by exactly one L-shaped piece. An L-shaped piece is a $$$2\times2$$$ square with one cell removed. You may rotate it however you choose.
L-shaped piece Tell Ryan if it is possible to pollinate the flower, and if it is, give him a valid configuration of L-shaped pieces that pollinates the flower.
The first line of input contains $$$t$$$, the number of test cases ($$$1 \leq t \leq 500$$$).
Each test case will be one line of input, containing $$$n$$$ ($$$1 \leq n \leq 1000$$$), the size of the flower. It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.
If it is possible to pollinate the flower, print an integer $$$l$$$, denoting the number of L-shapes you will use. If it is impossible, print -1.
If it is possible, you must print another $$$l$$$ lines, each describing an L-shaped piece you use. Each line should contain six integers, $$$x_1$$$ $$$y_1$$$ $$$x_2$$$ $$$y_2$$$ $$$x_3$$$ $$$y_3$$$, where ($$$x_1$$$, $$$y_1$$$), ($$$x_2$$$, $$$y_2$$$), and ($$$x_3$$$, $$$y_3$$$) are the cells taken up by the L-shaped piece if ($$$x$$$, $$$y$$$) refers to the cell at row $$$x$$$ and column $$$y$$$.
12
4 3 1 3 2 4 2 1 3 2 2 2 3 2 4 3 4 3 5 4 3 4 4 5 3
Here is an example of a pollinated flower of size $$$2$$$.
Problem Credits: Ariel Shehter