Inspired by Piet Mondrian's colorful geometric paintings, Magikarp wants to turn his blank wall into a mural. He plans to begin with a large, eye-catching square. (He can worry about filling in the rest of the mural later.)
The wall is a rectangle $$$w$$$ units wide and $$$h$$$ units tall. Magikarp's square must fit entirely within the wall, with its sides parallel to the sides of the wall. It may touch the edges of the wall.
Example of a Mondrian painting. What is the maximum possible area of the square, in square units?
The first line contains two integers $$$w$$$ and $$$h$$$ ($$$1 \le w,h \le 10^3$$$) — the width and height of the wall, respectively.
Output a single integer — the maximum possible area of Magikarp's square, in square units.
3 5
9
8 2
4
6 6
36
In the first sample test case, Magikarp can paint a square with side length $$$3$$$. Its area is $$$3\times 3=9$$$ square units.
In the second sample test case, he can paint a square with side length $$$2$$$, giving an area of $$$2\times 2=4$$$ square units.
In the third sample test case, the entire wall is a square. Magikarp can use all of it, giving an area of $$$6\times 6=36$$$ square units.
A group of $$$n$$$ people (numbered $$$1$$$ to $$$n$$$) work on clay sculptures. Each person is either good (G) or bad (B) at sculpting.
$$$m$$$ sculptures were made, and each one was a collaboration between two different people. A sculpture turns out good if and only if both sculptors are good. If at least one of them is bad, it turns out bad.
You are given the result of every sculpture. Determine whether there is an assignment of G/B to all $$$n$$$ people consistent with every result. If there is, output any such assignment. If the results are contradictory (the sculptures were tampered with), output -1.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2\cdot 10^5$$$, $$$0 \le m \le 2\cdot 10^5$$$) — the number of people and sculptures, respectively.
Each of the next $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$) and a character $$$c$$$ (G or B), meaning sculptors $$$u$$$ and $$$v$$$ made a sculpture with result $$$c$$$ (G for good and B for bad).
If no valid assignment exists, output -1.
Otherwise, output $$$n$$$ lines. The $$$i$$$th line should contain G or B, the skill of person $$$i$$$. If several assignments are valid, output any of them.
4 31 2 B2 3 B1 4 G
G B B G
3 31 2 G2 3 G1 3 B
-1
For the first test case, the output is G B B G, so persons $$$1$$$ and $$$4$$$ are good, and persons $$$2$$$ and $$$3$$$ are bad.
All $$$3$$$ sculptures are consistent with this assignment.
For the second test case, it can be shown that no valid assignment exists.
Magikarp is trying out a new technique called Cubism. With a carefully arranged set of blocks, he can create three different images when viewed from different angles!
Magikarp has a grid of $$$n\times m\times k$$$ positions, measured along the $$$x$$$-, $$$y$$$-, and $$$z$$$-axes, respectively. Each position $$$(x,y,z)$$$, where $$$1\le x\le n$$$, $$$1\le y\le m$$$, and $$$1\le z\le k$$$, can contain at most one unit cube. Cubes may float freely and do not need to be connected.
When standing in front of the sculpture, $$$+x$$$ points to your right, $$$+y$$$ points forward into the sculpture, and $$$+z$$$ points upward. Each view is an orthogonal projection: its lines of sight are parallel to its viewing direction.
He has already chosen three images for his artwork:
An entry is # if at least one cube exists along its line of sight, and . if no cube exists along that line.
Find the maximum number of cubes Magikarp can place so that all three views match his chosen images exactly. If no such arrangement exists, output -1.
The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1\le n,m,k\le 300$$$) — the numbers of positions along the $$$x$$$-, $$$y$$$-, and $$$z$$$-axes, respectively.
The next $$$m$$$ lines each contain a string of $$$n$$$ characters — the top view.
The next $$$k$$$ lines each contain a string of $$$n$$$ characters — the front view.
The next $$$k$$$ lines each contain a string of $$$m$$$ characters — the right view.
Each character is either # or .. Each image is given row by row from top to bottom, with each row written from left to right, using the orientations defined above.
Output a single integer — the maximum number of cubes in an arrangement matching all three views, or -1 if no such arrangement exists.
2 2 2############
8
15 5 5###..#..##..##.#...#.#.#.#.#.##...###.##..##.#...#.#.#.#.#..###.#.#.#.#.#..#.#..#..##..##.#.#.#.#.#.#.#.###..###.##..##.#.#.#.#.#.#.#..#.#.#.#.#.#.#..#########################
139
3 3 3.####.#.#.#..###.#..###..##
-1
In the first sample, all eight positions can contain cubes.
In the second sample, the front and top views spell "KARP" and "CARP", respectively. A maximum of $$$139$$$ cube positions can be filled.
Second sample: front view ("KARP").
Second sample: top view ("CARP").
Second sample: filled right view.
Close-up of the sculpture in the second sample, or see a video here. In the third sample, the top view requires a cube with $$$x=1$$$ and $$$y=1$$$. The front view allows such a cube only at $$$z=1$$$, but the right view forbids a cube with $$$y=1$$$ and $$$z=1$$$. Therefore, no arrangement exists.
In honor of this contest being the UTPC x WiCS contest, and with International Girls Day on November 14th, the other UTPC officers decide to give Victoria a break from problem writing for the week. Victoria decides to use this break to string bracelets for the other officers.
She has a pile of beads in $$$k$$$ different colors, with $$$c_i$$$ beads of color $$$i$$$. A bracelet is made by stringing all of her beads in a row and fastening a clasp to each end. Because the clasps are different, a bracelet is read strictly from left to right, so she never rotates or flips it. Beads of the same color are identical, so two bracelets look the same only if they have the same color at every position.
Victoria wants to know how many different bracelets she could possibly string using all of her beads. Since this number can be enormous, help her compute it modulo $$$10^9 + 7$$$.
The first line contains a single integer $$$k$$$ ($$$1 \le k \le 2 \cdot 10^5$$$), the number of bead colors.
The second line contains $$$k$$$ integers $$$c_1, c_2, \ldots, c_k$$$ ($$$1 \le c_i$$$), where $$$c_i$$$ is the number of beads of color $$$i$$$. It is guaranteed that the total number of beads satisfies $$$\sum_{i=1}^{k} c_i \le 2 \cdot 10^5$$$.
Print a single integer, the number of distinct bracelets Victoria can string using all of her beads, modulo $$$10^9 + 7$$$.
21 1
2
31 2 1
12
15
1
In the first example, color $$$1$$$ is red and color $$$2$$$ is blue. Victoria has one bead of each color, so she can string them as $$$(1, 2)$$$ (red, blue) or $$$(2, 1)$$$ (blue, red), for $$$2$$$ bracelets.
In the second example, she has beads of colors forming the multiset $$$\{1, 2, 2, 3\}$$$. The 12 distinct bracelets are $$$(1, 2, 2, 3)$$$, $$$(1, 2, 3, 2)$$$, $$$(1, 3, 2, 2)$$$, $$$(2, 1, 2, 3)$$$, $$$(2, 1, 3, 2)$$$, $$$(2, 2, 1, 3)$$$, $$$(2, 2, 3, 1)$$$, $$$(2, 3, 1, 2)$$$, $$$(2, 3, 2, 1)$$$, $$$(3, 1, 2, 2)$$$, $$$(3, 2, 1, 2)$$$, and $$$(3, 2, 2, 1)$$$.
In the third example, every bead is the same color, so there is only one possible bracelet no matter how she strings them.
Mike Angel has a rectangular sheet of paper of width $$$a$$$ and height $$$b$$$. He wants to cut out a convex polygon with $$$n$$$ vertices.
The paper initially occupies the rectangle with corners $$$(0,0)$$$, $$$(a,0)$$$, $$$(a,b)$$$, and $$$(0,b)$$$. The polygon's vertices are distinct and listed in clockwise or counterclockwise order. Consecutive vertices are joined by edges, including the last and first vertices. The polygon is simple and convex, and no three of its vertices are collinear. The polygon lies entirely within the paper, and its vertices or edges may lie on the paper's boundary.
Mike can perform a series of double cuts. In each operation, he does the following to the piece of paper he currently has:
The chosen points may have non-integer coordinates and need not be vertices of the desired polygon. The two segments may lie on the same straight line, so a straight cut is also allowed as one double cut. Subsequent operations use only the piece kept after the previous operation.
Find the minimum number of double cuts needed so that the remaining piece is exactly the desired polygon. Mike may perform zero cuts.
The first line contains three integers $$$n$$$, $$$a$$$, and $$$b$$$ ($$$3 \le n \le 10^5$$$, $$$1 \le a,b \le 10^9$$$) — the number of vertices of the polygon, the width of the paper, and the height of the paper, respectively.
The second line contains $$$n$$$ integers $$$x_1,x_2,\ldots,x_n$$$ ($$$0 \le x_i \le a$$$) — the $$$x$$$-coordinates of the vertices in order.
The third line contains $$$n$$$ integers $$$y_1,y_2,\ldots,y_n$$$ ($$$0 \le y_i \le b$$$) — the $$$y$$$-coordinates of the vertices in the same order.
The vertices are distinct and form a simple, convex polygon in clockwise or counterclockwise order. No three vertices are collinear.
Output a single integer — the minimum number of double cuts needed to cut out the polygon.
3 1 20 1 11 0 2
1
In the sample, Mike can choose $$$P=(0,1)$$$, $$$A=(1,0)$$$, and $$$B=(1,2)$$$. Cutting along $$$PA$$$ and $$$PB$$$ leaves the desired triangle as one piece. The triangle differs from the original rectangle, so at least one cut is necessary. Thus, the answer is $$$1$$$.
The diagram below illustrates this double cut.

UTPC is making friendship bracelets for an upcoming fair.
There are $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) beads arranged in a row. The $$$i$$$-th bead has color $$$a_i$$$ ($$$1 \le a_i \le n$$$). A bracelet consists of a contiguous group of at least two beads, and the first and last beads in the bracelet must have the same color.
A bracelet containing $$$k$$$ beads earns $$$k$$$ dollars, but making a bracelet costs $$$c$$$ ($$$0 \le c \le 10^9$$$) dollars. You may make any number of bracelets, as long as no bead belongs to more than one bracelet. Beads not included in a bracelet earn nothing.
What is the maximum total profit you can earn? You may also choose to make no bracelets.
The first line contains two integers $$$n$$$ and $$$c$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le c \le 10^9$$$), the number of beads and the cost of assembling one bracelet.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$), where $$$a_i$$$ is the color of the $$$i$$$-th bead.
Print one integer: the maximum possible total profit from making non-overlapping valid bracelets.
9 21 2 1 3 3 4 4 3 9
4
One optimal choice is to make a bracelet using beads at positions $$$1$$$ through $$$3$$$, and another using beads at positions $$$4$$$ through $$$8$$$. Their profits are $$$3-2=1$$$ and $$$5-2=3$$$, for a total of $$$4$$$. The last bead is unused.
Johnny has recently been getting into origami, but he finds traditional square pieces of paper boring. He recently ordered an interesting piece of origami paper whose shape can be described as a connected set of unit squares from an $$$h \times w$$$ grid. Two squares count as connected if they share a side — squares that only touch at a corner don't count. Additionally, the paper may have holes in it.
Johnny wants to make the outline of the paper as simple as possible. To do so, he may fold the paper at most once, using a fold which must go along a horizontal or vertical grid line. Everything on one side of the fold line is flipped over onto the other side, and the paper may stick out past the original grid after folding. Overlapping parts count as a single part of the visible shape.
A side is a maximal straight segment of the boundary with paper on the same side throughout the segment. Count both the outer boundary and the boundaries around holes. Segments that meet only at a corner with paper on opposite sides count separately.
For example, the following $$$3\times 3$$$ grid has $$$10$$$ sides before folding: $$$6$$$ around the outside and $$$4$$$ around the central gap.
###
#.#
.##
Can you help Johnny to fold the paper such that the resulting outline has the least number of sides?
The first line contains two integers $$$h$$$ and $$$w$$$ ($$$1 \le h,w \le 300$$$) — the height and width of the grid, respectively.
Each of the next $$$h$$$ lines contains a string of $$$w$$$ characters, each with either . or #. A # means the square is part of the paper, and a . means it isn't.
It is guaranteed that at least one square is # and that all # squares are connected through shared sides.
Output a single integer — the minimum number of sides of the visible shape after making at most one fold.
3 4##..###.####
4
3 5..#..#####..#..
8
5 7########..#..##..#..##..#..########
8
In the first sample test case, Johnny can fold the first two columns onto the remaining columns to get a rectangle with $$$4$$$ sides.
In the second sample test case, the paper initially has $$$12$$$ sides. Folding the first row onto the remaining rows gives a T shape with $$$8$$$ sides.
In the third sample test case, Johnny can fold the first three columns onto the remaining four to get a rectangular frame with one hole. The outer boundary has $$$4$$$ sides, and the boundary of the hole has $$$4$$$ sides. This gives $$$4+4=8$$$ sides in total.
Dinny and Walrus are working on an arts and crafts project! They have $$$n$$$ popsicle sticks, where the $$$i$$$-th stick has a non-negative integer $$$a_i$$$ written on it.
To decide who gets to keep their masterpiece, they play a game. Dinny goes first, and the two players alternate turns until all popsicle sticks have been removed.
On each turn, the current player performs the following actions in order:
Both players start with a score of $$$0$$$. After all popsicle sticks have been removed, the player with the higher score wins. If both players have the same score, the game ends in a tie.
Assuming both players play optimally, determine whether Dinny wins, Walrus wins, or the game ends in a tie.
$$$^\dagger$$$The $$$\mathrm{MEX}$$$ (minimum excluded value) of an array is the smallest non-negative integer that is not in the array. For example:
The first line contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of popsicle sticks.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the numbers written on the popsicle sticks.
Output "Dinny", "Walrus", or "Tie", according to the winner. The capitalization of these names does not matter.
40 0 1 2
Dinny
31 2 3
Tie
In the first test case, one possible sequence of moves is:
Dinny finishes with $$$4$$$ points, while Walrus finishes with $$$1$$$ point. Therefore, Dinny wins.
In the second test case, since there is no stick labeled $$$0$$$, the MEX remains $$$0$$$ throughout the game. Neither player earns any points, so the game ends in a tie.
Gaeul is obsessed with kitsch items, and after lots of thrifting she's preparing to assemble them onto a hanging mobile. She already has a design in mind, but is struggling to put items onto it, and needs your help!
Gaeul's current design can be modeled as a tree with $$$n$$$ nodes rooted at node $$$1$$$. These nodes are either leaf nodes (which will contain an ornament) or internal nodes (which have negligible weight and don't hold ornaments). Currently, node $$$i$$$ has weight $$$w_i$$$, which is zero if it is an internal node. A node's balance factor is the total weight of all nodes in its subtree, and a node is "balanced" if all of its children have the same balance factor (all leaves are trivially balanced). Naturally, Gaeul's goal is to ensure that all nodes are balanced.
Gaeul's tree might be unbalanced right now, but she is able to add or remove material from individual ornaments. Formally, she has the ability to take any ornament and change its weight to any positive real number. Gaeul is in a rush, however, and can't afford to change too many ornaments, so she needs your help to find the minimum number she needs to change.
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$), the number of nodes.
The second line contains $$$n-1$$$ integers $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \le p_i \lt i$$$), where $$$p_i$$$ is the parent of node $$$i$$$. If $$$n=1$$$, this line is empty.
The third line contains $$$n$$$ integers $$$w_1, w_2, \ldots, w_n$$$, the weights of the nodes. If $$$i$$$ is an internal node then $$$w_i = 0$$$, otherwise it lies in the range $$$1 \le w_i \le 10^9$$$.
Output a single integer: the minimum number of ornaments that need to be changed.
61 1 2 4 40 0 1 0 1 1
1
61 1 1 2 20 0 1 1 1 5
2
15
0
The first sample test case is drawn below, where the red numbers represent ornament weights and the green numbers represent balance factors. By changing the ornament at node $$$3$$$ to weight $$$2$$$, the entire tree will be balanced.
In the second test case, one optimal solution involves changing nodes $$$5$$$ and $$$6$$$.
The third test case is a single ornament and thus trivially balanced.