Darwin has discovered a rare new species of tortoises! He and his team of scientists have several different sites where they extracted DNA from tortoise remains. However, at each site, some of the nucleotide pairs are missing, and they need your help putting it back together.
We represent DNA strands as a string of nucleotides (letters 'A', 'T', 'G', 'C'); Darwin has some number of these strands. However, parts of it may be missing, denoted by the '.' character. Help Darwin reconstruct the most complete version of the DNA sequence as he can!
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) denoting the number of DNA strands. On each of the next $$$n$$$ lines is a string $$$s$$$ ($$$1 \le |s| \le 100$$$) consisting of the characters 'A', 'T', 'G', 'C', and '.'.
All strings are guaranteed to be the same length. Additionally, we guarantee that for all pairs of strings and for each index $$$i$$$, either both strings have the same character at index $$$i$$$, or at least one string has the '.' character at index $$$i$$$.
Output a single line denoting the most complete sequence (the least '.' possible) that is consistent with all sequences in the input.
3.ATTACAGCAAT..CAGCAATTAC...
AATTACAGC
3...T..TTG...
G.TT
In the first example, the most complete sequence is 'AATTACAGC'.
In the second example, the most complete sequence is 'G.TT'.
Scientists have been studying a variety of species, and they want to understand the evolutionary relationships between the different animals. They notice a very peculiar property: if species $$$A$$$ is an ancestor of species $$$B$$$, then the species name for $$$A$$$ is a suffix for a species name for $$$B$$$! Given a set of species names, can you determine which species in the list is an ancestor of all the other species? If no such species exists, print "Not found" (without quotes).
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) — the number of known species.
The following $$$n$$$ lines contain a single string $$$s_i$$$ ($$$1 \leq |s_i| \leq 1000$$$) — the name of the $$$i$$$th species. $$$s_i$$$ consists of the lowercase letters ('a'–'z') and hyphens ('-'). It is also guaranteed that all species names are distinct.
If one of these species is an ancestor of all the others, output the name of the species. Otherwise, output "Not found" without quotes.
4jayblue-jayred-jaypurplejay
jay
4cowsheepgoatfish
Not found
Darwin has been observing finches flying around the Galapagos Islands, and it is now mating season. For mating, the finches exhibit an interesting behavior: $$$n$$$ male finches will fly straight up and come back straight down as a flight display. The $$$i$$$th finsh starts at a horizontal location $$$l_i$$$ ($$$l_i$$$ can be negative) and reaches a height of $$$h_i$$$. Female finches will then fly to where the male landed and fan their tails to signal acceptance.
The wind will naturally affect where the male finch lands. There are $$$m$$$ jetstreams currently above the Galapagos. The $$$j$$$th jetstream is located at altitude $$$a_j$$$ and blows any finches at this height by $$$w_j$$$ units to the right ($$$w_j$$$ can be negative, blowing finches to the left). Male finches that go past a jetstream will be blown over both going up and coming down, while those peaking at the jetstream altitude will only be blown over once.
Natural female finches are adapted to adjusting for wind when locating the males, but Darwin rescued a baby finch that he will be releasing soon, and he needs to train this finch. Please provide the landing locations of each of the male finches that Darwin can communicate to his baby finch (don't worry about how, he's a trained scientist).
The first line contains $$$n$$$ $$$(1 \leq n \leq 10^5)$$$, the number of male finches, and $$$m$$$ $$$(0 \leq m \leq 10^5)$$$, the number of jetstreams.
Each of the next $$$n$$$ lines contain two integers $$$l_i$$$ and $$$h_i$$$ ($$$0 \leq |l_i|, h_i \leq 10^9$$$) – the starting location and max altitude of the $$$i$$$th finch.
Each of the next $$$m$$$ lines contain two integers $$$a_j$$$ and $$$w_j$$$ ($$$0 \leq a_j, |w_j| \leq 10^9$$$) — the altitude and strength of the $$$j$$$th jetstream.
Output one line containing the landing positions of each of the $$$n$$$ male finches in order.
3 15 22 4-2 64 2
5 4 2
Darwin is collecting samples at the Galapagos Islands to bring back Europe. He'd like to bring back the whole island for his research, but the Beagle has limited space!
He's choosing from $$$n\ (1 \leq n \leq 10^4)$$$ samples, each sample $$$i\ (1 \leq i \leq n)$$$ has:
- a weight $$$w_i\ (1 \leq w_i \leq 100)$$$ in kg
- relative research value $$$v_i\ (1 \leq v_i \leq 10^5)$$$
The Beagle has room for $$$m\ (0 \leq m \leq 100)$$$ kg in its main cargo hold, and features a special hold that can accommodate one item of any weight without counting towards the cargo limit.
Please output the max total research value that Darwin can bring back to the mainland.
The first line will contain two integers $$$n\ (1 \leq n \leq 10^4)$$$ and $$$m\ (0 \leq m \leq 100)$$$ — the number of samples.
The next $$$n$$$ lines will contain two integers $$$w_i\ (1 \leq w_i \leq 100)$$$ and $$$v_i\ (1 \leq v_i \leq 10^5)$$$ — the weight and relative research value for each sample.
A single integer that is the max total research value the beagle can carry.
6 102 22 22 23 13 16 3
10
Darwin is currently researching various traits of his $$$n$$$ finches that are each currently stored in their own sanctuary. He is trying to understand which finches might be evolutionarily related, so he wants to group them together based on common traits. Specifically, Darwin cares about $$$k$$$ traits of these finches, and has labeled every variant of each trait with a letter between 'a' and 'j'. There is a lot of coordination to be done in moving these finches around so Darwin needs your help processing and keeping track of all the information. Specifically, there are three types of queries he can request of you:
- Since he discovered that trait $$$j$$$ is a key indicator of genetic similarity, combine any groups with finches which share a value of this trait.
- Compute how many birds are currently in Finch $$$i$$$'s sanctuary (including Finch $$$i$$$ itself)?
- Compute how many birds are in the most populated sanctuary?
The first line contains three integers $$$n$$$, $$$k$$$, and $$$q$$$. ($$$1 \leq n, k, q \leq 10^5, nk \leq 10^6$$$) — the number of birds, the number of traits, and the number of queries, respectively.
The next $$$n$$$ lines contain a string $$$s_i$$$ ($$$|s_i| = k$$$) — the values of the $$$k$$$ traits of the bird, respectively. Every trait value is a character between 'a' and 'j'.
The next $$$q$$$ lines contain a description of the corresponding query. The line begins with an integer $$$t$$$ ($$$t \in \{1, 2, 3\}$$$.
- If $$$t = 1$$$, then the line contains another integer $$$j$$$ ($$$1 \leq j \leq k$$$) — the trait which finches should now also be grouped by.
- If $$$t = 2$$$, then the line contains another integer $$$i$$$ ($$$1 \leq i \leq n$$$) — the finch which the second query should be performed on.
- If $$$t = 3$$$, then there is nothing else on the line.
It is guaranteed that there is at least one query of type two or three. Note that queries of type 1 may be repeated.
Output the answers for the second and third queries in order on their own lines.
4 5 14abcdjacdeibcffhbffgg2 431 32 32 131 12 32 131 22 32 13
1 1 2 1 2 2 2 2 4 4 4
While in the Galapagos Islands, Darwin noticed a curious fact about the birds on the island. Each bird's beak length and wingspan add up to the same number $$$k$$$. There are $$$n$$$ resources on the island, each with some value $$$v$$$. The $$$i$$$th resource requires a wingspan of at least $$$w_i$$$ and a beak length of at least $$$b_i$$$ to reach. Darwin is curious about the best bird adapted to the environment. Find the maximum possible sum of resource values that is reachable by a bird with beak length and wingspan that adds up to $$$k$$$.
The first line contains two integers $$$n$$$ ($$$1 \leq n \leq 10^5$$$) and $$$k$$$ ($$$1 \leq k \leq 10^5$$$) — the number of resources and the sum of each bird's beak length and wingspan.
The next line contains $$$n$$$ integers, each representing the beak length $$$b_i$$$ ($$$1 \leq b_i \leq 10^5$$$) required to access the $$$i$$$th resource.
The next line contains $$$n$$$ integers, each representing the wingspan $$$w_i$$$ ($$$1 \leq w_i \leq 10^5$$$) required to access the $$$i$$$th resource.
The last line contains $$$n$$$ integers, each representing the value $$$v_i$$$ ($$$1 \leq v_i \leq 10^5$$$) of the $$$i$$$th resource.
Output a single integer — the maximum sum of resource values that can be acquired by a bird with a beak length and wingspan adding up to $$$k$$$.
5 62 2 3 3 45 4 2 2 13 2 4 5 2
11
One possible best bird has a beak length of 4 and a wingspan of 2. It can access the 3rd, 4th, and 5th resource, for a total sum of 11. It can be shown that this is the maximum.
Charles Darwin has made it to the Galapagos Islands, and is observing turtles - more specifically, there are $$$n$$$ ($$$1 \leq n \leq 200,000$$$) turtles with their nests (these turtles have nests) lined up in a row. They all lay an integer number of eggs; the $$$i$$$'th turtle's nest has $$$a_i$$$ ($$$0 \leq a_i \leq 10^9$$$) eggs. He also observes diversity in that no 2 turtles lay the same number of eggs. Darwin likes things to be ordered and is therefore displeased that the nests are not sorted in increasing order. He is allowed to do the following operation - he can choose $$$a_i, a_{i+1}, a_{i+2}$$$ and reorder them to be $$$a_{i+2}, a_i, a_{i+1}$$$ in place. Determine whether it is possible for Darwin to obtain a sorted row of nests (in increasing order) by doing this operation any number of times.
The first line will contain an integer $$$n$$$. The next line contains $$$n$$$ space separated integers $$$a_1, a_2 \cdots a_n$$$.
Output a single bit - $$$1$$$ if it is possible for Darwin to sort the nests, and $$$0$$$ if it is not.
33 1 2
1
41 2 4 3
0
Dr. Prakash recently learned about how the human brain evolved a marvelous ability to form, prune, and reshape connections between neurons. (He should have learned this awhile ago in medical school, but Dr. Prakash isn't the best medical student, or medical doctor for that matter.)
He would like to test this himself by performing some basic neurectomies on his victim patient and observing the results. He did receive consent to do this (like many of us, his patient did not read all the fine print before signing), but the medical board is still very much on his case due to the outcomes of his previous patients. As such, Dr. Prakash wants to avoid killing his patient (again), which happens if part of the brain becomes totally disconnected and unable to communicate with another part of the brain (a full lobotomy).
Dr. Prakash will make a single cut. Please help him identify which neurons he should definitely avoid with this cut if he wishes to keep his medical license (at least until the next ethics hearing).
The first line contains $$$n$$$ $$$(2 \leq n \leq m + 1)$$$ and $$$m$$$ $$$(1 \leq m \leq 2 * 10^5)$$$, the number of neurons representing the patient's brain, and the number of connections/synapses between neurons.
The next $$$m$$$ lines contain $$$i_m$$$ $$$(0 \leq i_m \lt 2^{32})$$$, a unique integer identifier for the synapse, and $$$n_1$$$ and $$$n_2$$$ $$$(0 \leq n_1, n_2 \lt n)$$$, denoting the two neurons that are connected. Please note that a pair of neurons may be connected by multiple synapses, and that $$$n1$$$ may equal $$$n2$$$.
It is guaranteed that the brain is connected at the start.
Print a single line of a sorted list of synapse identifiers that, if cut, will cause a brain partition. If there are none, print -1.
4 4212 3 0238 1 2394 2 0281 0 1
212
3 3101 0 1102 0 2103 2 1
-1