Note: The only difference between the easy and the medium version is the arrangement of seats.
Abu Shehab travels very often; sometimes he goes to 7alab to see Abu elNoor, and sometimes he goes to Palestine to give them weapons and help them. Meanwhile, Shareefeh stays alone at home.
She reads lots of books, and she was thinking how beautiful this world is. She wants to visit many places like Abu Shehab does. After begging Abu Shehab several times to take her, he finally agreed and booked a trip on a special airplane.
This airplane has a unique seating arrangement: it consists of rows, each row with two sections side-by-side with an aisle in between, and each section has three seats. There are a total of n rows.
Shareefeh, observing the passengers boarding, notices a fascinating seating pattern: People seemed to be intentionally leaving empty seats around themselves. Specifically, they avoided sitting in seats directly besides another passenger, including those directly across the aisle.
That means if a person is seated on the left side of the aisle, people will also avoid sitting in the corresponding seat on the right side of the aisle, as if extending their personal space across sections.
Abu Shehab informs her that $$$m$$$ people are boarding. Since she thinks people don't like sitting next to each other, she defines the happiness of the plane as the total number of adjacent seat pairs where exactly one seat is occupied and the other is empty.
What is the maximum possible happiness of the plane across all possible ways of seating $$$m$$$ people on a plane with $$$n$$$ rows?
one arrangement of 4 rows and 12 passengers (It doesn't have to be optimal) The first line of input will contain one integer $$$T$$$ $$$(1 \leq T \leq 10^5)$$$, which is the number of test cases.
Each test case contain one line,
The only line of input will contain two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n \leq 10^8)$$$, $$$(1 \leq m \leq 10^8)$$$, which represent the number of rows in the airplane and the number of people boarding, respectively.
Each test case print contain one line which is the maximum happiness or print $$$-1$$$ when the jet does not fit $$$m$$$ peoples.
54 1215 510 1755 556 75
20 10 34 110 -1
Counting empty seats means for every person you count the empty adjacent seats to the person's left, and right, and you can count the same empty seat, for different people, multiple times.
Note: This is the same as easy version in the ROUND 16 contest but in this version for each team you need to find out all possible ranks for the team. Also some constraints are different.
Abu Hatem has a very famous coffee shop. Sometimes, they play games, and it becomes very competitive. Abu Hatem is also very keen on shabab el7ara; he always takes care of them and wishes them all the best. For that reason, he decided to teach shabab el7ara competitive programming so they can get jobs in the best companies.
Also, Abu Hatem wants to create competitive and fun events, so he decided to organize a programming contest called AbuHatemCPC.
Ma2moon beik is not just 3meel from frensawi; he also works in a big tech company as a recruiter. One of the things he was thinking about when he entered Haret AlDabe3 was finding good and skilled programmers for his company.
So he decided to come to AbuHatemCPC to view the contest and see how shabab el7ara performed, as well as to headhunt skilled and smart contestants.
Ma2moon beik arrived at the contest just after it ended, and he saw the final scoreboard but without the results of the submissions in the blind hour.
AbuHatemCPC had 25 problems, and its duration was (4 + 1) hours. In the first 4 hours, the submission results were public to all contestants, but in the last hour, only the team that made the submission could see its result (whether it was accepted or not).
When Ma2moon beik saw the scoreboard, he could see, for each team, the number of problems they solved before the blind hour and their time penalty. He could also see, for each team, the submissions they made in the blind hour as pending submissions.
When revealing the results, they would use the contest resolver to show whether each pending submission was accepted or not.
Now, each pending submission has two possibilities: to be accepted or not. If it is accepted, it will increase the number of solved problems for that team by 1 and increase the time penalty by some known amount.
The rank of each team is equal to $$$1$$$ plus the number of teams that solved a strictly greater number of problems or solved the same number of problems with a strictly lower time penalty. (If two teams solved the same number of problems with the same time penalty, they would have the same rank.)
Now, Ma2moon beik is wondering, for each team, considering all possible outcomes of the pending submissions, what is the possible ranks this team can get. Can you help him?
The first line will contain one integer $$$t$$$ $$$(1 \leq t \leq 100)$$$, which is the number of test cases.
For each test case:
The first line will contain one integer $$$n$$$ $$$(1 \leq n \leq 100)$$$, which is the number of contestants.
Then, for each contestant, the input will contain two lines. For the $$$i_{th}$$$ contestant:
The first line will contain three integers $$$x_i$$$, the number of problems solved before the blind hour, $$$y_i$$$, the number of pending submissions in the blind hour, and $$$p_i$$$, the time penalty of the problems solved before the blind hour. It is guaranteed that $$$(0 \leq x_i + y_i \leq 25)$$$ and $$$(0 \leq p_i \leq 10^4)$$$. It is guaranteed that if the number of solved problems before blind hour ($$$x_i$$$) is $$$0$$$, the time penalty before blind hour ($$$p_i$$$) will also be $$$0$$$.
The second line will contain $$$y_i$$$ integers, the $$$j_{th}$$$ one denoted as $$$a_{i,j}$$$ $$$(240 \leq a_{i,j} \leq 300)$$$ , which represents the time penalty the contestant will receive if the result of that pending submission is accepted.
It is guaranteed that the sum of $$$n$$$ across all test cases will not exceed $$$100$$$.
For each test case, print $$$n$$$ lines. in the $$$i_{th}$$$ line, print $$$n$$$ characters where each character is either 0 or 1, where the $$$j_{th}$$$ character in the $$$i_{th}$$$ line is $$$1$$$ if it is possible for the $$$i_{th}$$$ team to have a rank equal to $$$j$$$.
143 0 10003 0 20003 0 30002 1 500300
1100 0110 0011 1001
First example:
Final scoreboard before if the pending submission wasn't accepted:
Final scoreboard before if the pending submission was accepted:
In the previous season, Shareefeh convinced Abu Shehab to plant a tree in Ard El Dyar. Over time, the tree grew larger and now consists of $$$n$$$ nodes.
Interestingly, Shareefeh's tree has leaves — and while everyone in Haret El Dabe3 knows what a leaf is, we'll redefine it here just in case Abo Bader forgets again: a leaf is a node that has no children.
One day, Em Zeki came over to chat with Shareefeh about life. During the conversation, Shareefeh asked her to talk about Em Sam3o Mart El7ares, and why she's currently the talk of the town in Haret El Dabe3 — clearly showing that Shareefeh was feeling jealous. It's worth noting that Abo Khater had a crush on Em Sam3o Mart El 7ares.
Em Zeki told Shareefeh that Em Sam3o, Mart El 7ares, had recently solved an impressive problem that caught everyone's attention. Feeling a bit competitive, Shareefeh decided she wanted to do something similar — but using her own tree. The challenge was this: Shareefeh needed to find out how many leaves she could choose from her tree such that the set $$$S$$$ that contains of the Lowest Common Ancestor (LCA) of every pair of selected leaves has $$$x$$$ unique nodes. Note that Shareefeh might not be able to accomplish this and reach the level of Em Sam3o Mart El 7ares — in that case, print -1.
Note that Shareefeh's tree is rooted at node $$$1$$$.
The Lowest Common Ancestor (LCA) is defined between two nodes v and w as the lowest node in the tree that has both v and w as descendants.
For example in following tree which is rooted at node $$$1$$$:
LCA between nodes $$$4$$$ and $$$6$$$ is $$$2$$$.
LCA between nodes $$$8$$$ and $$$3$$$ is $$$7$$$.
LCA between nodes $$$5$$$ and $$$7$$$ is $$$7$$$.
LCA between nodes $$$4$$$ and $$$8$$$ is $$$1$$$.
The first line of input will contain one integer $$$T$$$, which is the number of test cases $$$(1 \leq T \leq 10^4)$$$.
For each test case
The first line of input contain two integers $$$n$$$ and $$$x$$$ $$$(2 \leq n, x \leq 2 \cdot 10^5)$$$ — denotes the number of nodes the tree has and the number of unique LCAs required.
The next $$$n − 1$$$ lines of each test case contain two integers each — $$$u$$$, $$$v$$$ indicating an edge between $$$u$$$ and $$$v$$$ $$$(1 \le u,v \le n)$$$ representing a tree.
It is guaranteed that the sum of $$$n$$$ across all test cases will not exceed $$$2 \cdot 10^5$$$.
For each test case print the minimum number of leaves needed to achieve $$$x$$$ unique lowest common ancestors (LCAs). Or print -1 in case there is no answer
35 21 21 33 43 55 22 13 14 35 23 32 13 1
3 -1 -1
First test case
LCA of $$$4$$$ and $$$5$$$ is $$$3$$$.
LCA of $$$4$$$ and $$$2$$$ is $$$1$$$.
LCA of $$$5$$$ and $$$2$$$ is $$$1$$$.
The set $$$S$$$ is equal to {$$$1$$$, $$$3$$$}, which contains two elements.
Note: The only difference between the easy and the medium version is the arrangement of seats.
Abu Shehab travels very often; sometimes he goes to 7alab to see Abu elNoor, and sometimes he goes to Palestine to give them weapons and help them. Meanwhile, Shareefeh stays alone at home.
She reads lots of books, and she was thinking how beautiful this world is. She wants to visit many places like Abu Shehab does. After begging Abu Shehab several times to take her, he finally agreed and booked a trip on a special airplane.
This airplane has a unique seating arrangement: it consists of rows, and each section has three seats. There are a total of n rows.
Shareefeh, observing the passengers boarding, notices a fascinating seating pattern: People seemed to be intentionally leaving empty seats around themselves. Specifically, they avoided sitting in seats directly beside another passenger, even across section boundaries (left and right across the aisle).
Abu Shehab informs her that $$$m$$$ people are boarding. Since she thinks people don't like sitting next to each other, she defines the happiness of the plane as the total number of adjacent seat pairs where exactly one seat is occupied and the other is empty.
What is the maximum possible happiness of the plane across all possible ways of seating $$$m$$$ people on a plane with $$$n$$$ rows?
The first line of input will contain one integer $$$T$$$ $$$(1 \leq T \leq 10^5)$$$, which is the number of test cases.
Each test case contain one line,
The only line of input will contain two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n \leq 10^8)$$$, $$$(1 \leq m \leq 10^8)$$$, which represent the number of rows in the airplane and the number of people boarding, respectively.
Each test case print contain one line which is the maximum happiness or print $$$-1$$$ when the jet does not fit $$$m$$$ peoples.
415 510 1755 556 75
10 20 110 -1
Counting empty seats means for every person you count the empty adjacent seats to the person's left and right and you can count the same empty seat, for different people, multiple times.
Note: The only difference between the easy and the hard version is the constraints.
Moon had the worst breakup ever, again. His ex was way smarter than him, which devastated him. So, he needed advice from the one and only Apple, again. Apple decided to take Moon to Abu Issam for help.
Moon said, "4 JAYYED."
Apple introduced Moon to Abu Issam, and as Moon began to open up, Abu Issam sighed and said, "lek majnoon enta lek moon, MAJNOOOON"
Abu Issam gave Moon an array $$$a$$$ of $$$n$$$ integers and told Moon that he needed to create a new array $$$b$$$ such that for each pair of indices $$$i$$$, $$$j$$$ $$$(1 \le i, j \le n)$$$ append $$$a_i \cdot a_j$$$ to the new array $$$b$$$.
To forget his ex, Moon needs to find the $$$\operatorname{MEX ABO EL JABER}$$$ of $$$b$$$. Can you please help Moon?
Note: The $$$\operatorname{MEX ABO EL JABER}$$$ (Minimum EXcluded ABO EL JABER value) of an array is the smallest positive integer that is not in the array. For example:
The first line of input contains one integer $$$n (1 \le n \le 2\cdot10^6)$$$ — the length of the array.
The second line of input contains $$$n$$$ integers $$$a_i(1 \le a_i \le 10^8)$$$ — the elements of the array.
For each test case, print the $$$\operatorname{MEX}$$$ of the new array $$$b$$$.
71 2 3 4 5 6 7
11
52 4 6 8 10
1
63 6 4 12 48 36
1
Moon is once again asking for your help in solving this problem.
Abu Ghalib locked Abu Issam in his Barbour and clinic shop using a lock with a secret $$$n$$$-digit code. We know the code is a number $$$x$$$.
When you buy these types of locks, they come with two things: the $$$n$$$-digit passcode $$$x$$$ and a hint. The hint is given in the form of two $$$n$$$-digit numbers, $$$L$$$ and $$$R$$$, where $$$(L \leq x \leq R)$$$, indicating that the passcode is between $$$L$$$ and $$$R$$$ inclusive.
Usually, people memorize the value of $$$x$$$ and then erase it to safely use the lock. However, Abu Ghalib was lazy, and he might have left some digits of $$$x$$$ visible on the lock.
Now, Abu Issam can see some $$$n$$$-digit patterns representing $$$L$$$, $$$R$$$, and $$$x$$$. In the pattern for $$$x$$$, some positions show a digit $$$(0\text{-}9)$$$, while other positions show a question mark $$$?$$$, indicating an unknown digit.
Let $$$S$$$ be the set of all possible $$$n$$$-digit codes that match the visible pattern on the lock (by replacing each $$$?$$$ with a digit) and fall within the inclusive range from $$$L$$$ to $$$R$$$. Abu Issam must open the lock before Shabab Al7ara discovers that he sleeps in the store. He has only one attempt and decides to use his lucky number $$$k$$$.
He will try the $$$k_{th}$$$ smallest number in the set $$$S$$$. If the set $$$S$$$ contains fewer than $$$k$$$ numbers, then the $$$k_{th}$$$ smallest number does not exist, and Abu Issam will be caught. In this case, print $$$-1$$$.
The first line of input contains one integer $$$T$$$, representing the number of test cases $$$(1 \leq T \leq 10^5)$$$.
For each test case:
The first line contains two integers $$$n$$$ $$$(1 \leq n \leq 18)$$$ and $$$k$$$ $$$(1 \le k \le 10^{18})$$$, denoting the number of digits in $$$x$$$, $$$L$$$, and $$$R$$$, and the lucky number respectively.
The second line contains a string $$$x$$$, consisting of digits $$$(0-9)$$$ and question marks $$$(?)$$$, where $$$?$$$ indicates an unknown digit.
The third and fourth lines each contain strings $$$L$$$ and $$$R$$$ respectively, indicating the inclusive range $$$(L \le x \le R)$$$ within which the password must lie.
For each test case, find the $$$k_{th}$$$ smallest n-digit number (it can have leading zeroes) in the set $$$S$$$. If the set $$$S$$$ contains fewer than $$$k$$$ numbers, the $$$k_{th}$$$ smallest doesn't exist; in this case, print $$$-1$$$.
35 6?78?2517826345118 3948349??????????????????0000000000000000009999999999999999993 2123100200
57852 000000000003948348 -1
Note: The only difference between the easy and the hard version is the constraints.
Moon had the worst breakup ever, again. His ex was way smarter than him, which devastated him. So, he needed advice from the one and only Apple, again. Apple decided to take Moon to Abu Issam for help.
Moon said, "4 JAYYED."
Apple introduced Moon to Abu Issam, and as Moon began to open up, Abu Issam sighed and said, "lek majnoon enta lek moon, MAJNOOOON"
Abu Issam gave Moon an array $$$a$$$ of $$$n$$$ integers and told Moon that he needed to create a new array $$$b$$$ such that for each pair of indices $$$i$$$, $$$j$$$ $$$(1 \le i, j \le n)$$$ append $$$a_i \cdot a_j$$$ to the new array $$$b$$$.
To forget his ex, Moon needs to find the $$$\operatorname{MEX ABO EL JABER}$$$ of $$$b$$$. Can you please help Moon?
Note: The $$$\operatorname{MEX ABO EL JABER}$$$ (Minimum EXcluded ABO EL JABER value) of an array is the smallest positive integer that is not in the array. For example:
The first line of input contains one integer $$$n (1 \le n \le 10^5)$$$ — the length of the array.
The second line of input contains $$$n$$$ integers $$$a_i(1 \le a_i \le 10^5)$$$ — the elements of the array.
For each test case, print the $$$\operatorname{MEX}$$$ of the new array $$$b$$$.
71 2 3 4 5 6 7
11
52 4 6 8 10
1
63 6 4 12 48 36
1
Moon is once again asking for your help in solving this problem.