Vivian needs us to pick up her Golden Retriever, Bo, from a dog park filled with Corgis. However, we're not good at identifying dog breeds, and she only told us that Bo is the tallest dog at the park. The dog park is represented as a 2D grid, where a '.' denotes an empty space and any nonzero digit $$$h$$$ represents a dog at that position with height $$$h$$$. The height of each dog is indicated by a single-digit positive integer.
Write a program to assist Vivian in finding Bo by determining the row and column number of the tallest dog in the park. The park is guaranteed to have at least one dog, and there is guaranteed to be a unique tallest dog.
The first line contains two integers, $$$N$$$ and $$$M\ (1 \leq N, M \leq 100)$$$, representing the number of rows and number of columns, respectively, in the dog park.
The next $$$N$$$ lines contain $$$M$$$ characters each, representing the 2D grid of the dog park. Each character is either '.' (empty space) or a non-zero digit (1-9) representing a dog's height.
Output two integers, separated by a single space, representing the row and column number of the tallest dog, Bo.
7 7..6..2.65...55...7.2............26......1.2...5..
3 4
Bo, being the tallest dog, has height 7, and is in the $$$3^\text{rd}$$$ row and $$$4^\text{th}$$$ column.
Alex and his corgi are going on a hike! They are traversing a 1-dimensional hiking path of length $$$N$$$ where each position $$$i\ (1 \leq i \leq N)$$$ has elevation $$$e_i$$$.
He's curious about the view at different locations along the hike. Specifically, he has $$$q$$$ queries where he's wondering if location $$$j$$$ is visible from location $$$i$$$, which is the case when there's no location between $$$i$$$ and $$$j$$$ with an elevation greater than or equal to the max of $$$e_i$$$ and $$$e_j$$$. For each query, determine if location $$$j$$$ is visible from location $$$i$$$.
The first line will contain two space-separated integers, $$$N\ (1 \leq N \leq 10^5)$$$ and $$$q\ (1 \leq q \leq 100)$$$, denoting the length of the hiking path and the number of queries, respectively.
The second line will contain $$$N$$$ space separated integers $$$e_1, e_2, \dots e_N\ (1 \leq e_i \leq 10^9)$$$ representing the elevations of the $$$N$$$ positions in the hiking path.
The final $$$q$$$ lines will each contain two space-separated integers $$$i$$$ and $$$j\ (1 \leq i, j \leq N)$$$, representing a query.
Output $$$q$$$ lines, each containing a single string "yes" or "no" (case insensitive), representing the result of a query.
9 69 6 3 3 4 6 1 4 81 61 33 43 75 86 9
yes yes yes no no yes
Corgis are interesting. They have genes - but in a world of Corgis, the genes are not expressed by the standard 'ATCG' bases, but rather, there are $$$26$$$ bases, each represented by a unique lowercase English letter.
You, a genetic scientist, are here to understand a corgi's genes. Since genetic diversity is viewed to be beneficial to a corgi's health, you are specifically looking for "interesting" sub-genes (substrings) of a corgi's genes that do not contain more than two of any single gene (letter). You additionally want the sub-genes to be "interesting" – in this case, you want palindrome sub-genes (a palindrome is a string which is read the same forwards as it is backwards).
However, the sub-genes' lengths are quite long, and you are lazy. Develop a program that helps you count the number of distinct "interesting" sub-gene ranges that do not contain more than two of the same gene, given the corgi's gene formation.
One line containing $$$n\ (1\leq n\leq 5\cdot 10^4)$$$ continuous lowercase English letters, representing the gene of the corgi.
A single integer, representing the number of non-empty palindromic sub-genes where no more than two of the same gene is present.
ababa
8
In this case, there are $$$8$$$ distinct ranges that satisfy the "palindrome" and "no more than 2 of each letter" requirements: [1,1]; [2,2]; [3,3]; [4,4]; [5,5]; [1,3]; [2,4]; [3,5].
Observe that [1,5]="ababa" is not valid since it contains 3 instances of the letter a.
Somewhere in the town of Lean, a highly intelligent Corgi named Dog assists her owner in computer science research. They are currently dabbling in proof verification, where the structure of a proof can be represented as a rooted tree with $$$n$$$ nodes numbered from $$$1$$$ to $$$n$$$. In this tree, we call root node $$$1$$$ the "goal" and all other nodes as "subgoals" derived from the goal. There is an edge from node $$$a$$$ to node $$$b$$$ if $$$b$$$ is directly derived from $$$a$$$. This time, Dog's owner is working on a peculiar proof.
Example: A proof structure as a rooted tree This proof is composed of multiple steps.
During a single step of verification, only one leaf node can be solved, and any valid leaf node can be chosen. A leaf node $$$s$$$ that is solved is removed from the tree and the following changes occur:
After the gray node is removed, two copies of the ancestor node and its children are appended to the root node in purple. Her owner comments that the proof seems endless. However, Dog knows that a proof terminates when there are no more subgoals to solve, i.e. when the tree is reduced to the single root node. In order to ease the burden of her owner's work, Dog wants to figure out the minimum number of steps needed to terminate the proof given the current proof structure. Please help her compute this modulo $$$10^9+7$$$.
The input is a rooted tree describing the current proof structure.
The first line contains an integer $$$n\:(1 \leq n \leq 10^5)$$$.
The next $$$n-1$$$ lines contain the edges of the tree. The $$$i$$$-$$$th$$$ line contains integers $$$a_i, b_i\: (1 \leq a_i, b_i\leq n; a_i\neq b_i)$$$ — the vertices connected by an edge of the tree.
A single integer representing the minimum number of steps needed to terminate the proof, modulo $$$10^9+7$$$.
51 22 32 41 5
14
71 22 32 44 54 61 7
122
In the first test case, we can do the following,
On step 2, we create two purple copies of the subgraph after removing the grey leaf node.
For steps 3-13, we continue choosing a node to remove, and creating two copies of the remaining subgraph.
On step 14, we remove the last leaf node, successfully reaching termination.
The Corgi Adoption Center has an adorable selection of corgis with various fur color combinations. Today is adoption day, and they want all of the corgis to be taken home to a loving home. They have gathered them all in a circle to show them all off to their potential new owners. The center has noticed in the past, that no owner likes to have more than 2 distinct fur colors (among their own corgis) in total. Furthermore, in the circle, the corgis are placed next to their friends, and the adoption center wants to avoid separating friends too much. So every individual can adopt a single contiguous segment of the circle. What is the minimum number of compassionate individuals the center needs to guarantee that all corgis are adopted?
The first line will contain a single integer $$$N\ (1 \leq N \leq 10^6)$$$ indicating how many corgis are in the circle. The following $$$N$$$ lines will each contain 1 or 2 lowercase letters indicating the fur colors of each corgi. Note: The $$$n$$$th corgi is next to the $$$1$$$st in the circle.
The output is a single integer indicating the minimum number of individuals needed to adopt all the corgis.
7ababbcdc
2
6acdcab
2
Sample 1:
One person can adopt Corgis 1 - 4 since this has a total of 2 colors: a, b. A second person can adopt Corgis 5 - 7 since this has a total of 2 colors: c, d. Thus, 2 people are needed minimum.
Sample 2:
One person can adopt Corgis 1, 5, and 6 (since the circle wraps around) since this has the 2 colors: a, b. A second person can adopt Corgis 2, 3, and 4 since this has a total of 2 colors: c, d. Thus, 2 people are needed.
Alice has started a dog walking service to earn a little extra income! She is able to walk up to 2 dogs a day, 7 days a week. Luckily, Alice has a lot of friends with dogs who need them to be walked on different days of the week and are willing to pay different amounts of money for the job to be completed. Alice has a list of $$$N$$$ friends, who need their dog to be walked for 0 to 7 days of the week. Alice can not choose the same job twice, as her friends only have one dog each. Can you help Alice determine the maximum amount of money she can make a week?
The first line contains an integer $$$N\ (1 \leq N \leq 100)$$$ the number of friends Alice has.
The next $$$N$$$ lines will have eight integers each: the first seven integers will represent the days of the week; a 1 will indicate that the dog needs to be walked on that day and a 0 will indicate the dog does not need to be walked on that day. The eigth integer will be the amount of money, $$$m\ (1 \leq m \leq 10^5)$$$ that the job pays.
Output one integer representing the maximum amount of money Alice can make in a week
4 1 0 1 0 1 0 1 10 0 1 0 1 0 1 0 5 1 1 1 1 1 1 1 100 1 0 0 0 0 0 0 100
205
At your last Thanksgiving get-together, your clumsy cousin accidentally let your corgi loose in the neighborhood park! The neighborhood park can be modeled as a fenced-in $$$N \times M$$$ square, which we represent as a 2D grid. Your corgi currently occupies the corner (0, 0), and the exit to the park is located at $$$(N, M)$$$.
Your family is interspersed throughout the park at various points $$$(x_i, y_i)$$$. You may call out to any of your family members to help catch your corgi; each family member has some agility $$$r_i$$$. If the corgi enters the circle centered at this person $$$(x_i, y_i)$$$ with radius $$$r_i$$$, then the person can catch the corgi.
Your corgi will attempt to avoid all family members, and cannot escape the park except through the exit. If your corgi manages to make it to the exit $$$(N, M)$$$ without being caught by a family member, then it will escape. What's the minimum number of family members you need to guarantee that your corgi will not escape?
The first line contains three integers $$$N, M, K$$$, where $$$N \times M$$$ $$$(1 \le N, M \le 10^9)$$$ gives the dimensions of the park, and $$$K$$$ $$$(1 \le K \le 10^3)$$$ denotes the number of family members.
The next $$$K$$$ lines each consist of three integers $$$x_i, y_i, r_i$$$ ($$$0 \le x_i \le N, 0 \le y_i \le M, 1 \le r_i \le 10^9$$$) denoting the position $$$(x_i, y_i)$$$ and the agility $$$r_i$$$ of the $$$i$$$th family member.
Output a single integer, the minimum number of family members needed to guarantee that your corgi will not escape, or -1 if it is impossible to guarantee.
10 8 102 2 13 5 18 2 26 7 21 2 12 6 12 2 17 5 16 4 14 0 1
3
8 8 42 2 13 8 21 0 13 5 1
1
The first sample test case can be visualized as follows. The green circles represent the family members that should be used to prevent your corgi from escaping. 
Alice is baking treats for her two corgis, Bob and Charlie!
For some strange reason, Alice has arranged the $$$N$$$ treats she has baked in a tree structure. Each of the $$$N$$$ treats has an associated tastiness, with the $$$i^\text{th}$$$ treat having tastiness $$$t_i$$$.
Bob and Charlie will now play a game as follows:
As corgis are known to be extremely clever dogs, Bob and Charlie are both master logicians acting in their own best interest, which is to eat treats with maximum total tastiness. Alice is now curious, just how much will the total tastiness of the treats Bob eats be? Can you help her figure it out?
The first line of input will contain a single integer $$$N\ (2 \leq N \leq 20)$$$, denoting the number of treats Alice has baked. It is guaranteed that $$$N$$$ is even.
The next line will contain $$$N$$$ space-separated integers, $$$t_1, t_2, \dots, t_N\ (1 \leq t_i \leq 2 \cdot 10^9)$$$, denoting the tastiness of each treat.
The following $$$N - 1$$$ lines will each contain two space separated integers $$$u$$$ and $$$v\ (1 \leq u, v \leq N, u \neq v)$$$ indicating that there is an edge between the $$$u^\text{th}$$$ treat and the $$$v^\text{th}$$$ treat. It is guaranteed that these edges form a tree.
Output a single integer denoting the total tastiness of the treats Bob eats, assuming that both he and Charlie act optimally.
41 2 10 1001 23 24 2
11
41 10 50 1001 23 24 2
51
The first sample test case looks like the following:
Optimally, Bob will choose the treats with tastiness 10 and 100 and then the treats with tastiness 1 and 2. Charlie will choose the treats with tastiness 100 and 2, leaving Bob with the treats worth 10 and 1 tastiness, for a total of 11.
The second sample test case looks like the following:
Bob's strategy should now be to choose the treats with tastiness 1 and 10, and then the treats with tastiness 50 and 100. Charlie will choose the treats with tastiness 10 and 100, leaving Bob with the treats worth 1 and 50 tastiness, for a total of 51.