Cindy's research project involves tracing the number of people infected by the Cordon Bleu virus, down to the minute. She has recorded the number of new cases for each of the first $$$N$$$ minutes. Specifically, she knows that $$$0$$$ people were infected at minute $$$0$$$, and she recorded that at the $$$i$$$th minute, $$$A_i$$$ more people were infected by the virus, for each $$$i$$$ from $$$1$$$ to $$$N$$$. It is guaranteed that the $$$A_i$$$ are non-negative integers.
Based on this, she constructed a second array $$$B$$$ of $$$N$$$ integers, the cumulative number of cases by the $$$i$$$th minute. That is, $$$B_i$$$ counts the total number of people infected on or before the $$$i$$$th minute.
Cindy keeps all her data in her laptop. Unfortunately, her laptop got infected by a (computer) virus and all the data in her hard drive got scrambled! Cindy also doesn't have any backups of her data, neither locally or on the cloud. How irresponsible! Always back up your data.
The original array $$$A$$$ was deleted. Cindy was able to recover the elements of $$$B$$$, but they were shuffled around randomly and ended up in the wrong order!
Given the elements of $$$B$$$ in some random order, help Cindy reconstruct the elements of the original array $$$A$$$, and give them in the correct order. It can be shown that $$$A$$$ can always be recovered, and furthermore that this answer is unique.
The first line of input contains a single integer $$$N$$$, the number of minutes that were tracked.
The second line of input contains $$$N$$$ space-separated integers, the elements of $$$B$$$ in some random order.
Output $$$N$$$ space-separated integers $$$A_1$$$, $$$A_2$$$, $$$\dots$$$, $$$A_N$$$ that are consistent with the values of $$$B$$$ given in the input.
$$$0 \le A_i \le 10^6$$$
Note that the constraint is given for $$$A$$$, not $$$B$$$.
Subtask 1 (50 points):
$$$1 \le N \le 5$$$
Subtask 2 (20 points):
$$$1 \le N \le 1000$$$
Subtask 3 (30 points):
$$$1 \le N \le 2\cdot 10^5$$$
5 3 1 4 1 5
1 0 2 1 1
We can show that if the values of $$$A$$$ are $$$\{1, 0, 2, 1, 1\}$$$, in that order, then we produce a cumulative array $$$B$$$ whose values can be rearranged to form $$$\{3, 1, 4, 1, 5\}$$$. We can show that this $$$A$$$ is unique.
The problem statements of Biodiverse Subsequence and Biodiverse Subarray are nearly identical, save for whether the sampled corals must form a subsequence or subarray of the given sequence. Despite this, the two are very different problems.
Biodiversity is one of the most important properties in any ecosystem, whether it's in a forest, a mangrove, or even the ocean. The Philippines is rich with species of flora and fauna that are endemic to the country. Cindy, an avid scuba diver, has accompanied a group of biologists that ventured to the Verde Island Passage to sample some coral species for their research. Of course, it is important that the samples that they choose properly reflect the diversity of marine life found at the Coral Triangle.
They find a row of $$$N$$$ corals and identify $$$K$$$ distinct species among them. We model this as a sequence of $$$N$$$ positive integers $$$A_1, A_2, \dots, A_N$$$. Each of the integers from $$$1$$$ to $$$K$$$ appears at least once, and these are the only integers to appear in the sequence. A sequence of numbers is called biodiverse if each of the integers from $$$1$$$ to $$$K$$$ appears at least once each in the sequence.
The researchers must choose a biodiverse subsequence of corals to sample from. A subsequence is any sequence that can be derived from the given sequence by deleting zero or more elements without changing the relative ordering of the remaining elements. In order to make a decision on which corals to sample, the researchers ask Cindy to count the number of biodiverse subsequences of $$$A$$$.
Help Cindy out?
The first line of input contains two space-separated integers $$$N$$$ and $$$K$$$, the number of corals and the number of distinct species, respectively.
The second line of input contains $$$N$$$ space-separated integers $$$A_1$$$, $$$A_2$$$, $$$\cdots$$$, $$$A_N$$$, where $$$A_i$$$ is the species of the $$$i$$$th coral in the row.
Output a single line containing a single integer, the number of biodiverse subsequences of $$$A$$$.
$$$1 \leq K \leq N \leq 60$$$
$$$1 \leq A_i \leq K$$$ for all $$$i$$$.
There exists an $$$i$$$ such that $$$A_i = k$$$ for all $$$k$$$ from $$$1$$$ to $$$K$$$.
Subtask 1 (40 points):
$$$N \leq 15$$$
Subtask 2 (20 points):
$$$N \leq 30$$$
Subtask 3 (20 points):
$$$K \leq 2$$$
Subtask 4 (20 points):
No further constraints.
4 2 1 2 1 2
9
14 9 3 1 4 1 5 9 2 6 5 3 5 8 9 7
189
The below diagram shows the nine biodiverse subsequences that the researchers can choose from in the first sample test case.
The problem statements of Biodiverse Subsequence and Biodiverse Subarray are nearly identical, save for whether the sampled corals must form a subsequence or subarray of the given sequence. Despite this, the two are very different problems.
Biodiversity is one of the most important properties in any ecosystem, whether it's in a forest, a mangrove, or even the ocean. The Philippines is rich with species of flora and fauna that are endemic to the country. Cindy, an avid scuba diver, has accompanied a group of biologists that ventured to the Verde Island Passage to sample some coral species for their research. Of course, it is important that the samples that they choose properly reflect the diversity of marine life found at the Coral Triangle.
They find a row of $$$N$$$ corals and identify $$$K$$$ distinct species among them. We model this as a sequence of $$$N$$$ positive integers $$$A_1, A_2, \dots, A_N$$$. Each of the integers from $$$1$$$ to $$$K$$$ appears at least once, and these are the only integers to appear in the sequence. A sequence of numbers is called biodiverse if each of the integers from $$$1$$$ to $$$K$$$ appears at least once each in the sequence.
To preserve the properties of the habitat, the researchers must choose a biodiverse subarray of corals to sample from. A subarray is a contiguous subsequence of elements $$$A_l, A_{l+1}, \dots A_r$$$ where $$$1 \leq l \leq r \leq N$$$. In order to make a decision on which corals to sample, the researchers ask Cindy to count the number of biodiverse subarrays of $$$A$$$.
Help Cindy out?
The first line of input contains two space-separated integers $$$N$$$ and $$$K$$$, the number of corals and the number of distinct species, respectively.
The second line of input contains $$$N$$$ space-separated integers $$$A_1$$$, $$$A_2$$$, $$$\cdots$$$, $$$A_N$$$, where $$$A_i$$$ is the species of the $$$i$$$th coral in the row.
Output a single line containing a single integer, the number of biodiverse subarrays of $$$A$$$.
$$$1 \leq K \leq N \leq 2\cdot 10^5$$$
$$$1 \leq A_i \leq K$$$ for all $$$i$$$.
There exists an $$$i$$$ such that $$$A_i = k$$$ for all $$$k$$$ from $$$1$$$ to $$$K$$$.
Subtask 1 (40 points):
$$$N \leq 100$$$
Subtask 2 (20 points):
$$$N \leq 2000$$$
Subtask 3 (20 points):
$$$K \leq 2$$$
Subtask 4 (20 points):
No further constraints.
4 2 1 2 1 2
6
14 9 3 1 4 1 5 9 2 6 5 3 5 8 9 7
3
The below diagram shows the six biodiverse subarrays that the researchers can choose from in the first sample test case.
Alice is madly in love with Bob and she hopes to impress him by beating him in yet another chocolate game.
Alice and Bob are supergenius, perfectly rational grandmaster prodigies who always make the optimal move in any game they play. Alice considers a game to be WINNABLE if there is some strategy she can follow so that she is guaranteed to win no matter what Bob does (so long as Alice plays correctly). Alice considers a game UNWINNABLE if Bob has a strategy he can follow so that she is guaranteed to lose no matter what she does (so long as Bob is playing correctly).
Bob is madly in love with Cindy, so he places $$$M$$$ cookies in the left pile and $$$N$$$ cookies in the right pile, since $$$M$$$ and $$$N$$$ are Cindy's favorite numbers.
Cindy is madly in love with Alice, so she will rig the game such that it will be WINNABLE for Alice, by taking some number of cookies from each pile. So that Bob does not notice the changes, she can only take at most $$$X$$$ cookies from the left pile, and at most $$$Y$$$ cookies from the right pile. Cindy can also choose not to take any cookies from either pile. You are also assured that $$$X \lt M$$$ and $$$Y \lt N$$$.
How many different ways can Cindy rig the game in Alice's favor? Formally, count the number of ordered pairs of integers $$$(x,y)$$$ such that $$$0 \leq x \leq X$$$ and $$$0 \leq y \leq Y$$$, and a game that initially begins with piles of size $$$M-x$$$ and $$$N-y$$$ is WINNABLE for Alice.
Input consists of a single line with four space-separated integers $$$M$$$, $$$N$$$, $$$X$$$, and $$$Y$$$.
Output a single integer, the number of different ways that Cindy can rig the game in Alice's favor.
It is recommended that Python users submit to PyPy for this problem.
$$$0 \leq X \lt M$$$
$$$0 \leq Y \lt N$$$
Subtask 1 (30 points):
$$$1 \leq M,N \leq 10$$$
Subtask 2 (20 points):
$$$1 \leq M,N \leq 100$$$
Subtask 3 (20 points):
$$$1 \leq M,N \leq 1000$$$
Subtask 4 (15 points):
$$$1 \leq M,N \leq 5\cdot 10^4$$$
Subtask 5 (15 points):
$$$1 \leq M,N \leq 5\cdot 10^6$$$
5 10 1 2
4
10 10 9 9
66
In the first sample test case, suppose Cindy took $$$x=0$$$ cookies from the left pile and $$$y=1$$$ cookies from the right pile. Then, the game will have pile sizes $$$5$$$ and $$$9$$$, which we can show is WINNABLE for Alice.
First, she eats $$$6$$$ cookies from the right pile, which she can do because $$$9-6 = 3$$$ and $$$3$$$ is a positive divisor of $$$9$$$.
Now, the pile sizes are $$$5$$$ and $$$3$$$. If Bob eats from the left pile, his only choice is to eat $$$4$$$ cookies from it; then, Alice eats $$$2$$$ cookies from the right pile. If Bob eats from the right pile, his only choice is to eat $$$2$$$ cookies it; then, Alice eats $$$4$$$ cookies from the left pile.
In either case, there is only $$$1$$$ cookie left in each pile on Bob's turn, so he loses.
We can show that the full list of solutions are $$$(0,0)$$$, $$$(0,1)$$$, $$$(0,2)$$$, and $$$(1,2)$$$ for the first sample test case.
As their act for their school's variety show, Alice and Bob are going to perform their own remix of the classic disco song Dancing Queen! Aside from the chorus, their remix has $$$N$$$ different verses to be sung by the two of them.
The verses are labeled $$$1, 2, 3, \dots, N$$$, in sequence. Each verse sung involves more and more fabulous outfits, choreography, pyrotechnics, disco lights, etc. Let's say that the fabulousness of the $$$k$$$th verse is exactly equal to $$$k$$$. Some of these verses will be performed by Alice, and the others will be performed by Bob. So that one does not overshadow the other, they wish to ensure that the total fabulousness of their verses is as fairly divided as possible.
Formally, let $$$A$$$ be the sum of the fabulousness of verses given to Alice, and let $$$B$$$ be the sum of the fabulousness of verses given to Bob. Find any way to distribute the verses between the two of them such that $$$|A-B|$$$ is minimal.
Input consists of a single line containing a single positive integer $$$N$$$.
First, output a line containing a single integer, the minimal value of $$$|A-B|$$$.
Then, output a line containing a string of $$$N$$$ characters, where the $$$k$$$th of these characters is A if the $$$k$$$th verse goes to Alice, and B if it goes to Bob. If there are multiple solutions, output any of them.
Subtask 1: (40 pts):
$$$1 \leq N \leq 15$$$
Subtask 2: (20 pts):
$$$1 \leq N \leq 100$$$
Subtask 3: (15 pts):
$$$1 \leq N \leq 1000$$$
Subtask 4: (25 pts):
$$$1 \leq N \leq 2\cdot 10^5$$$
3
0 AAB
10
1 BAAAAABABB
If there are $$$3$$$ verses, then we can make $$$|A-B|=0$$$ if we give Alice verses $$$1$$$ and $$$2$$$ while Bob gets verse $$$3$$$.
If there are $$$10$$$ verses, then we can prove that $$$|A-B|=1$$$ is the lowest we can make it. In the example, Alice gets verses $$$2, 3, 4, 5, 6$$$, and $$$8$$$, for a total fabulousness of $$$28$$$, while Bob gets verses $$$1, 7, 9$$$, and $$$10$$$, for a total fabulousness of $$$27$$$.
In both cases, it is equally valid if we gave Alice the verses we had given to Bob, and vice versa.
This is an interactive problem.
The PIPAC (Philippine Institute of Pure and Applied Chemistry) is an independent scientific institute which lies between Faura Hall and the School of Management in the Ateneo de Manila University. Despite residing in Ateneo, it is an independent entity from the university, so students are generally not permitted to enter the facilities. PIPAC occasionally hosts guided tours of their labs for those curious of what secrets lie behind its enigmatic white walls.
Alice is on one such tour, and when the organizers heard that she was a programmer, they decided to entertain her with a hands-on puzzle.
Alice is presented with $$$1000$$$ containers of unknown compounds, labeled $$$1, 2, 3, \dots, 1000$$$. Each container holds exactly one type of compound, and no compound appears in more than one different container.
She can choose any subset of the containers, take a sample from each, and dissolve all the samples together into one mixture. Then, she can take this mixture to the lab, where a high-tech computer then prints out a list of all the compounds identified in the mixture, in no particular order.
Alice's task is to identify the compound in each of the $$$1000$$$ containers. Using the high-tech computer is expensive and time-consuming, so Alice is challenged to use it as few times as possible. In particular, she is assured that her task is possible in 10 uses or less. She seems to be having some trouble—could you help her out?
The judge first outputs a single line containing a single integer $$$T$$$, the number of test cases; there will always be exactly $$$T=5$$$ test cases in this problem. Each test case then proceeds as follows.
The judge outputs a line containing a single integer $$$N$$$, the number of unknown compounds; there will always be exactly $$$N=1000$$$ compounds in this problem.
The judge begins by secretly generating $$$N$$$ distinct strings, the names of the $$$N$$$ compounds. Each name consists of no more than 3 upper or lowercase English letters, and no two different compounds share the same name. The names of the compounds are case-sensitive.
You have two types of queries available to you.
If you wish to use the machine, output a single line containing the word MIX. Then, indicate which containers you would like to test. First, output a positive integer $$$n$$$, from $$$1$$$ to $$$N$$$ inclusive, indicating the number of different containers you will be sampling from. Then, output $$$n$$$ distinct whitespace-separated integers, meaning a sample is to be taken from each of the containers with these labels.
The judge will then respond with a single line containing $$$n$$$ space-separated strings, the compounds identified in the mixture you sent in no particular order.
If you are ready to give your final answer, output a single line containing the word ANSWER. Then, output $$$N$$$ whitespace-separated strings, the names of the compounds in the containers from $$$1$$$ to $$$1000$$$ (in that order).
The judge will then respond with a single line containing a $$$0$$$ if you were incorrect, or a $$$1$$$ if you were correct. If your program receives a $$$0$$$, then no further input (for the rest of the test cases) will be given from the judge. In such a case, you should terminate immediately to prevent an Idleness Limit Exceeded verdict. If your program receives a $$$1$$$, then simply proceed with the next test case.
There will be exactly $$$T=5$$$ test cases.
If you identified any of the compounds incorrectly, you get $$$0$$$ points. Otherwise, let $$$Q$$$ be the maximum number of times you used the MIX query in any of the test cases. Then, scoring is as follows.
Subtask 1 (15 points): $$$Q \leq 1000$$$
Subtask 2 (15 points): $$$Q \leq 999$$$
Subtask 3 (15 points): $$$Q \leq 750$$$
Subtask 4 (10 points): $$$Q \leq 667$$$
Subtask 5 (10 points): $$$Q \leq 500$$$
Subtask 6 (10 points): $$$Q \leq 250$$$
Subtask 7 (9 points): $$$Q \leq 100$$$
Subtask 8 (8 points): $$$Q \leq 11$$$
Subtask 9 (8 points): $$$Q \leq 10$$$
For illustration, Alice is allowed a practice round with just one test case and only $$$4$$$ unknown compounds. Let's examine her sample interaction.
First, the judge informs her that there is only $$$1$$$ test case in the practice round with $$$4$$$ unknown compounds.
Contestant Judge
1
4
MIX
3
1 2 4
KBr ZnO NaH
MIX
2
3 4
ZnO CuS
MIX
1
1
KBr
ANSWER
KBr NaH CuS ZnO
1
Alice decides to MIX together $$$3$$$ different compounds by taking samples from containers $$$1$$$, $$$2$$$, and $$$4$$$.
The judge then responds that Alice's mixture contains KBr, ZnO, and NaH.
Alice then decides to MIX together $$$2$$$ different compounds by taking samples from containers $$$3$$$ and $$$4$$$.
The judge then responds that Alice's mixture contains ZnO and CuS.
Finally, Alice decides to MIX together just $$$1$$$ compound by taking a sample from container $$$1$$$.
The judge then responds that Alice's mixture contains KBr.
Alice is now confident in her logic and ready to ANSWER. She reports that,
The judge then responds with a $$$1$$$ to tell Alice that she is correct!
Bob is a huge fan of Swift—the programming language developed by Apple for creating iOS apps, of course! Bob even has a special playlist of songs which he only plays when he is coding in Swift.
Bob has $$$N$$$ songs on his music playlist, each with distinct song names. Currently, they are being played in some order, with the positions numbered $$$1$$$, $$$2$$$, $$$3$$$, $$$\dots$$$, $$$N$$$.
When Bob hits the shuffle button, he expects the order of the songs to be rearranged in a "sufficiently random" manner. To quantify this, Bob chooses some positive integer $$$K$$$, and expects each song to be at least $$$K$$$ places away from its original position. Formally, a reordering of the songs is called sufficiently random if and only if the following holds. For each song, let $$$x$$$ be its position in the original ordering, and $$$y$$$ be its position in the reordering. Then, $$$|x-y| \geq K$$$ must hold.
Given Bob's song list and the integer $$$K$$$, output the songs in a different order which he considers sufficiently random, or tell Bob that this is impossible. If there are multiple solutions, output any of them.
The first line of input contains two space-separated integers $$$N$$$ and $$$K$$$.
The second line of input contains the $$$N$$$ songs in Bob's playlist in their original order, separated by spaces. Each song name is a single word consisting of no more than 10 upper and lower case English letters.
If the task is impossible, output a single line containing the word NO. Otherwise, output a line containing the word YES, then output another line containing the same $$$N$$$ songs from the input, but in a sufficiently random order.
$$$1 \leq K \leq N$$$
$$$2 \leq N \leq 10^5$$$
Subtask 1 (45 points):
$$$N \leq 8$$$
Subtask 2 (15 points):
$$$K = 1$$$
Subtask 3 (40 points):
No further constraints.
4 1 august cardigan exile ricochet
YES ricochet exile cardigan august
6 2 LoveStory OurSong TrdrpsGtar Enchanted Fifteen UBelongWMe
YES Fifteen Enchanted LoveStory UBelongWMe TrdrpsGtar OurSong
In the first sample test case,
Cindy is excited to play the new video game based on the classic anime, Sort Art Online. The game is thankfully only an adaptation of the first arc, which is a normal computer-science-based MMORPG—no magic or guns. Many people justifiably consider Sort Art Online to be "one of the worst animes of all time" for a myriad of different reasons, but Cindy will always defend the first arc as being better than people give it credit for. The rest of the show is pretty bad, though.
She heard Alice really liked one of the recent arcs, so that's something, she supposes. Alice is the only reason why she's playing this game, anyway.
Anyway, Cindy is going to attempt the gauntlet, which is a post-game dungeon which requires her to defeat all of the bosses from the main story without any breaks in between. The gauntlet consists of $$$N$$$ different floors, each with an extra tough boss that must be defeated in order to reach the next floor. The bosses have difficulty $$$D_1$$$, $$$D_2$$$, $$$\dots$$$, $$$D_N$$$, given in the order Cindy must defeat them. Cindy begins the gauntlet with $$$S$$$ stamina. She can only challenge the $$$i$$$th boss once she has defeated all the bosses that come before it. She can only defeat the $$$i$$$th boss if she has at least $$$D_i$$$ stamina, and defeating the boss will deduct $$$D_i$$$ stamina from her total.
The only way Cindy can restore her stamina is by using potions. She may not bring any potions into the game mode, but each boss drops one such potion upon defeat which she can use. The potion dropped by the $$$i$$$th boss will restore $$$R_i$$$ stamina to Cindy if she chooses to use it. At any time, she can use any of the potions that were dropped by a boss she had already defeated (but she doesn't have to). Each potion can only be used at most once.
The potions are valuable loot which Cindy can sell for better gear. Thus, Cindy wants to know what is the minimum number of potions she needs to consume in order to defeat all $$$N$$$ bosses, if it is possible for her to beat all the bosses at all. If it is not possible, instead output the maximum number of bosses she can beat before running out of stamina.
The first line of input contains two space-separated integers $$$N$$$ and $$$S$$$, which are the number of bosses and Cindy's initial stamina, respectively.
The second line of input contains $$$N$$$ space-separated integers $$$D_1, D_2, \dots, D_N$$$, where $$$D_i$$$ is the difficulty of the $$$i$$$th boss.
The third line of input contains $$$N$$$ space-separated integers $$$R_1, R_2, \dots, R_N$$$, where $$$R_i$$$ is the health restored by the potion dropped by the $$$i$$$th boss.
If Cindy can beat all the bosses, first output a single line containing the word WIN, followed by another line containing the minimum number of potions she needs to consume in order to beat all the bosses.
If Cindy cannot beat all the bosses, first output a single line containing the word LOSE, followed by another line containing the maximum number of bosses that Cindy can beat before running out of stamina.
$$$1 \leq S \leq 10^9$$$
$$$1 \leq D_i \leq 10^9$$$
$$$1 \leq R_i \leq 10^9$$$
Subtask 1 (35 points):
$$$1 \leq N \leq 16$$$
Subtask 2 (35 points):
$$$1 \leq N \leq 1000$$$
Subtask 3 (30 points):
$$$1 \leq N \leq 2 \cdot 10^5$$$
4 5 2 3 4 5 3 1 9 9
WIN 3
4 1 1 90 10 1 1 99 88 101
LOSE 1
5 4 3 1 4 1 5 9 2 6 5 3
WIN 2
In the first sample test case, Cindy beats the first and second bosses and is left with $$$5-(2+3)=0$$$ stamina. In order to defeat the third boss, she needs to drink the potions dropped by the first two bosses. Then, to defeat the fourth boss, she needs to drink the potion dropped by the third boss. She does not need to drink the potion dropped by the fourth boss. In total, she needs to consume at least $$$3$$$ potions in order to beat all the bosses.
Note that if Cindy could have challenged the third boss first, then she could have finished the gauntlet by drinking only one potion. Unfortunately, Cindy is forced to challenge the bosses in the given order.
In the second sample test case, Cindy can only defeat the first boss, then gets stuck immediately. She loses, having beaten $$$1$$$ boss only.
Cindy has started exercising regularly and doing physical conditioning. Inspired by her favorite anime series, she decided to clean up a beach full of trash that people had been treating as a dumping site for their junk. It simultaneously functions as strength training, and a way for her to do some good for society!
There are $$$N$$$ pieces of junk in a single line. From left to right, the $$$i$$$th piece of junk has a height of $$$H_i$$$ and a weight of $$$W_i$$$; it is guaranteed that the heights of each object are distinct. Cindy wishes to sort the junk in increasing order of height. The only operation that Cindy can do is to pick up two adjacent objects and swap their positions in the line. Since the objects can be heavy, the total energy that Cindy expends is the product of the weights of the two objects. Formally, Cindy can swap the positions of the $$$i$$$th and $$$(i+1)$$$th objects, and doing so costs $$$W_i \times W_{i+1}$$$ units of energy.
What is the minimum amount of energy that Cindy needs to expend in order to sort the junk in ascending order of height?
The first line of input contains a single integer $$$N$$$, the number of pieces of junk.
The second line of input contains $$$N$$$ space-separated integers $$$H_1, H_2, \dots, H_N$$$, where $$$H_i$$$ is the height of the $$$i$$$th piece of junk.
The third line of input contains $$$N$$$ space-separated integers $$$W_1, W_2, \dots, W_N$$$, where $$$W_i$$$ is the weight of the $$$i$$$th piece of junk.
Output a single integer, the minimum amount of energy that Cindy needs to expend to sort the junk in increasing order of height.
It is recommended that Python users submit to PyPy for this problem.
$$$1 \leq N \leq 2\cdot 10^5$$$
$$$1 \leq H_i \leq 10^9$$$
$$$1 \leq W_i \leq 10^4$$$
It is guaranteed that $$$H_i \neq H_j$$$ for $$$i \neq j$$$.
Subtask 1 (35 points):
$$$N \leq 8$$$
Subtask 2 (15 points):
$$$N \leq 100$$$
Subtask 3 (20 points):
$$$N \leq 1000$$$
Subtask 4 (15 points):
All pieces of junk will have the same weight.
Subtask 5 (15 points):
No further constraints.
3 3 1 2 4 5 6
44
8 118 999 881 99 911 97 25 3 1 2 3 4 5 6 7 8
501
For the first sample test case, Cindy first swaps the objects of height $$$3$$$ and $$$1$$$, spending $$$4 \times 5 = 20$$$ energy. Then, she swaps the objects of height $$$3$$$ and $$$2$$$, spending $$$4 \times 6 = 24$$$ energy. The junk is now fully sorted in increasing order of height, and Cindy spent a total of $$$20+24 = 44$$$ energy.
Alice has encountered a puzzle room in a video game. To progress, she needs to slide some large cubes into their proper positions in order to activate a magic portal which leads deeper into the dungeon. The puzzle is also further complicated by large immovable obstacles and holes of different depths that are scattered throughout the room.
We can encode the contents of the room in a grid with $$$N$$$ rows and $$$M$$$ columns, and represent this grid with $$$N$$$ strings, each containing $$$M$$$ ASCII characters. The following are what each character corresponds to:
Alice can use magic to tilt the room in one of the four cardinal directions (north, south, east, or west). When she does so, the cubes move in the following manner,
Alice has a series of commands she wishes to execute. Each is described by a single direction, and involves tilting the room in the indicated direction until all cubes are no longer moving. A command can be represented by one of the characters N, S, E, or W, corresponding to the directions north, south, east, and west, respectively.
Alice gives you a string which contains all the commands she wishes to execute, in order from left to right. Output the state of the room after all her commands have been executed in the indicated order.
The first line of input contains two space-separated integers $$$N$$$ and $$$M$$$, the number of rows and the number of columns in the grid.
The next $$$N$$$ lines of input contain a string with $$$M$$$ characters. The $$$j$$$th character of the $$$i$$$th string corresponds to the space in the $$$j$$$th column of the $$$i$$$th row of the grid, as described in the problem statement.
This is followed by a single line containing a single string which describes the commands that Alice wishes to perform.
Output $$$N$$$ lines, each containing a string with $$$M$$$ characters, representing the state of the room after all of Alice's commands, in the same format as it is given in the input. If a cube ultimately occupies some space, output the color of that cube. Otherwise, output the open space, obstacle, or hole, in the same format as in the input. We point out that after all the commands, it may be possible to have a hole with capacity $$$0$$$, which we represent with the character 0.
$$$1 \leq N, M \leq 20$$$
Alice gives at least $$$1$$$ and at most $$$200$$$ commands.
Subtask 1 (15 points):
There are no holes or obstacles in the room.
Subtask 2 (15 points):
There are no holes in the room.
Subtask 3 (15 points):
Only S (south) commands will be given.
Subtask 4 (15 points):
Only S and N (south and north) commands will be given.
Subtask 5 (15 points):
Only S and E (south and east) commands will be given.
Subtask 6 (15 points):
Alice gives at most $$$10$$$ commands.
Subtask 7 (10 points):
No further constraints.
4 5 ACD.. B#... .E#.. #.... S
.C... A#D.. B.#.. #E...
4 5 ACD.. B#... .E#.. #.... SE
....C A#..D .B#.. #...E
5 3 AAA BBB CCC 124 ... S
... ... ... A01 BA.
In the first sample test case, we tilt the room so that all the cubes slide south.
In the second sample test case, first we make all the cubes slide south, just like in the first sample. Then, the next command is to tilt the room so all cubes slide east.
For the third sample test case, the diagram below shows the step-by-step process of the cubes sliding southwards and into the holes with various capacities.
The hole in the first column becomes fully filled, and is covered in the final state by the A cube over it. The hole in the second column becomes fully filled, and we can see its 0 in the final state; the A cube slides over it and rests at the bottom of the grid. The hole in the third column has all three cubes in its column slide into it, and it still has a capacity of 1 after that.
Everyone is excited to celebrate the new year and the (eventual) end of the pandemic with a bombastic Junior Prom! Unfortunately, people are a little too excited for it, and each student organization decided to host their own prom—plus, they all scheduled them to happen on the same weekend! This is a logistical nightmare for officers who are part of multiple orgs, since their presence is required at each of their org's events.
Alice has been enlisted to help resolve these scheduling conflicts.
There are $$$N$$$ students in the batch and $$$M$$$ different orgs that are holding a prom. The Office of Student Activities has given Alice the full list of officers of each org. Each org requires all of its officers to be present at its prom in order for it to run smoothly. Unfortunately, this might cause conflicts if the same member is needed at multiple different events. Since prom lasts until late into the evening, it is impossible for the same student to attend two different events if they both occur on the same night. The only leeway we have for rescheduling is that for each event, we can decide whether it will happen on Saturday or Sunday.
Alice must resolve these scheduling conflicts. For each of the org events, she must assign a date to it (either Saturday or Sunday) such that all org officers can attend their respective events with no conflict, or report that this is impossible. If there are multiple such valid assignments, choose any such that the maximum number of possible events are held on Saturday.
Help Alice out?
The first line of input contains two space-separated integers $$$N$$$ and $$$M$$$, the number of students and the number of orgs that are holding proms.
Each org is described with two lines (so $$$2M$$$ lines of input follow). The first line contains a single integer $$$r_i$$$, the number of officers in the $$$i$$$th org. The second line contains $$$r_i$$$ space-separated strings, where each string is the name of an officer of that org.
Contestants are recommended to use fast methods of input and output for this problem.
If the task is impossible, output NO on a single line. Otherwise, output YES.
If YES, output $$$M$$$ more lines describing when the prom of each org is scheduled. The $$$i$$$th line should contain the string Saturday if the prom of the $$$i$$$th org will be held on Saturday, and Sunday if it will be held on Sunday. The order of the orgs is the same as the order that they are given in the input.
If there are multiple solutions, output any such that the number of Saturday proms is maximized.
$$$1 \leq N \leq 2\cdot 10^5$$$
$$$1 \leq M \leq 2\cdot 10^5$$$
If $$$r_i$$$ is the number of members needed for the $$$i$$$th event, then $$$1 \leq \sum r_i \leq 4\cdot 10^5$$$.
Each student's name is distinct, consists only of upper or lower case letters, and is at most $$$4$$$ characters long.
The names in the list of officers for a particular org are all distinct, and each org has at least one officer.
At most $$$N$$$ distinct names will appear across all org officer lists.
Subtask 1 (25 points):
$$$M, N \leq 16$$$
$$$\sum r_i \leq 400$$$
Subtask 2 (25 points):
$$$\sum r_i \leq 400$$$
Subtask 3 (25 points):
$$$\sum r_i \leq 4000$$$
Subtask 4 (25 points):
No further constraints.
15 4 3 Dani Riri Vern 3 Dani Nate Chri 4 Luis Mark Rap Riri 5 Cis Fran Kev Kyle Vern
YES Sunday Saturday Saturday Saturday
16 5 3 Dani Joe JV 3 JV Lanc Lzro 3 Earl Nico Treb 3 Acad Joe Nico 3 Earl Karl Lzro
NO
In the first sample test case, we can show that there will be a conflict if we host all events on Saturday. However, if we host the first org event on Sunday and all other events on Saturday, then there will be no conflicts.
In the second sample test case, we can show by exhaustion that it is impossible to schedule the org events without there being at least one conflict.
What makes a good leader?
Bob reflected on that topic as he read Plato's Republic and Marcus Aurelius' Meditations. Plato believed in the ideal philosopher king, a ruler "who possesses both a love of wisdom, as well as intelligence, reliability, and a willingness to live a simple life". He goes on to further posit that for a utopia to be achieved, either the philosophers must become kings, or the kings must adequately and genuinely philosophize.
Bob then imagines the following (admittedly unrelated) thought experiment. Suppose we have $$$N$$$ philosophers, indexed $$$1$$$ to $$$N$$$, and whose leadership values are integers $$$A_1, A_2, \dots A_N$$$. We say that philosopher $$$i$$$ dominates philosopher $$$j$$$ if $$$A_i$$$ is divisible by $$$A_j$$$. Then, Bob decides that the philosopher king must be the philosopher who dominates all the other philosophers. If there are multiple possible philosopher kings, Bob chooses the one with the smallest index.
Given the leadership values of the philosophers, can you help Bob identify if any of them are fit to be philosopher king? If yes, identify who it should be.
Recall that we define an integer $$$a$$$ to be divisible by another integer $$$b$$$ if there exists some integer $$$k$$$ such that $$$a = kb$$$.
The first line of input contains a single integer $$$N$$$, the number of philosophers.
The second line of input contains $$$N$$$ space-separated integers, the leadership values $$$A_1, A_2, \dots, A_N$$$.
If there exists a philosopher king, output their index. Otherwise, output $$$-1$$$ to indicate that there is no philosopher king.
$$$1 \le A_i \le 10^9$$$
Subtask 1 (50 points):
$$$1 \le N \le 5$$$
Subtask 2 (20 points):
$$$1 \le N \le 1000$$$
Subtask 3 (30 points):
$$$1 \le N \le 2\cdot 10^5$$$
4 1 215 43 5
2
4 201 202 227 228
-1
5 224 224 224 224 224
1
In the first sample, we see that $$$215$$$ is divisible by $$$5$$$, $$$43$$$, and $$$1$$$, so philosopher $$$2$$$ is king.
In the second sample, we can show that none of the philosophers fit the criteria for king.
In the third sample, any of the philosophers satisfy the conditions, so we choose the one with smallest index, which is $$$1$$$.
The Philippines is home to more than 175 ethnolinguistic groups, with many indigenous peoples still carrying on their heritage through traditions which are hundreds of years old. Among these traditions is the weaving of fabric and textiles adorned with intricate geometric patterns which reflect the rich history and philosophies of the various indigenous peoples throughout the country.
Bob, inspired by these patterns, decided to create geometric patterns of his own, which he decided to call "L-Textiles". Of course, he is not skilled in weaving or even embroidery, so he will plan out his design on the computer first.
The fabric where the pattern is to be placed can be represented as a $$$2^N \times 2^N$$$ square unit grid. Bob envisions that the pattern with primarily consist of many L-shaped pieces which consist of three adjacent unit squares, all of the same color, in the shape of an "L" (see picture). The pieces can be rotated. Bob's L-shaped pieces come in 26 different colors, and he has an infinite amount of each color of piece.
Unfortunately, Bob realized that it is always impossible to completely cover the $$$2^N \times 2^N$$$ grid using only L-shaped tiles because its area (in square units) will never be divisible by 3. To fix this, he blacked out the $$$1 \times 1$$$ square located at $$$(x,y)$$$ (the square in the $$$x$$$th row from the top and the $$$y$$$th column from the left). Now, Bob desires to create a pattern that satisfies the following.
Bob has already made some patterns of his own, but now he challenges you to make some too! Of course, if the task is impossible, you must tell Bob that he made a mistake.
To aid in creating your pattern, you may download the following app.
Then, run the app by entering java -jar L-Painter.jar in the command line/terminal. You need to have a Java Runtime Environment of 8 or higher downloaded in order to use the app.The first line of input contains a single integer $$$N$$$.
The second line of input contains two space-separated integers $$$x$$$ and $$$y$$$.
If the task is impossible, output NO on a single line. Otherwise, output YES.
If YES, output $$$2^N$$$ more lines, each containing a string with $$$2^N$$$ characters. The $$$y$$$th character of the $$$x$$$th line should be the hash character #. Each other character must be an upper case English letter, representing the color of some L-shaped piece. An L-shaped piece is represented by three touching characters on the grid that are the same letter, in an L-shape. Two L-shaped pieces are considered the same color if (and only if) they are represented by the same letter.
$$$1 \leq N \leq 8$$$
$$$1 \leq x,y \leq 2^N$$$
Subtask 1 (20 points):
$$$N \leq 1$$$
Subtask 2 (15 points):
$$$N \leq 2$$$
Subtask 3 (15 points):
$$$N \leq 3$$$
Subtask 4 (15 points):
$$$N \leq 4$$$
Subtask 5 (20 points):
$$$x = y = 1$$$
Subtask 6 (15 points):
No further constraints.
2 1 3
YES CC#A CBAA ABBC AACC
3 5 7
YES AABBCCBB ADBAACAB DDCADDAA AACCADBB CADAAB#B CCDDBBAA BAABAABA BBABBABB
Here is Bob's pattern for the first sample test case.
Here is Bob's pattern for the second sample test case.
