A Stanford researcher has been trying to figure out a new way to measure the happiness of undergraduate students. They surveyed $$$N$$$ students and stored their reported happiness levels in an array.
You are given an array of size $$$N$$$ with integer values. We want to partition the array into one or more contiguous subarrays. The happiness level of a partition is the sum of the bitwise XOR of the numbers in each subarray. We want to compute the maximum happiness and the minimum happiness possible with this array. Output the difference between these values.
Definitions: A subarray is defined as a contiguous segment of an array. In array: [4, 3, 7, 2, 1] some subarrays are [4, 3, 7] and [7, 2]. [4, 2, 1] is not a subarray.
The bitwise XOR (Exclusive Or), is an operator similar to addition. However, it is performed on each bit of a number. For each bit in a number, the XOR of the two bits are 0, if the arguments are the same, else the XOR is 1. XOR(0,0) = 0 XOR(1,1) = 0 XOR(1,0) = 1 XOR(0,1) = 1
The first line of input holds a single integer $$$N$$$ ($$$1\le N\le 10,000$$$). The next $$$N$$$ lines each contain a single value $$$v_i$$$ ($$$1\le v_i\le 2^{20}$$$), which are the values in the array.
Print, on a single line, an integer representing the difference between the minimum happiness and the maximum happiness attainable.
4 2 8 12 4
24
10 489 104 776 546 557 322 37 408 620 620
3846
Alice and Bob are engaged in a Stanford vs. Berkeley board game tournament! This round, they are playing Dots and Boxes. However, both had amnesia and lost track of who won each game. The good thing is, they wrote down a record of the sequence of moves played.
Given a sequence of moves from the game Dots and Boxes, determine which player made each move, and the score at the end of the game.
Alice and Bob play a game of dots and boxes, with Alice playing first.
Dots and Boxes is played on a square grid of dots. Play alternates, with each player connecting two adjacent dots with a vertical or horizontal line. If a player completes a square by drawing the fourth line of one or more of the 1x1 squares, the player marks the box with their name and must then make another move. Whoever completes the most unit squares wins.
The first line of input contains a single number, $$$n$$$, which is the horizontal and vertical size of the square of dots ($$$3 \le n \le 10)$$$. Following this is a sequence of moves, one per line, specified as the coordinates of the dots connected by each move. Each move is given as four integer values $$$x_1$$$ $$$y_1$$$ $$$x_2$$$ $$$y_2$$$ with all coordinate values between 1 and $$$n$$$, inclusive. The two dots described will always be adjacent; that is, $$$|x_1-x_2|+|y_1-y_2|=1$$$.
There will always be exactly $$$2n^2-2n$$$ moves; that is, every possible line will be drawn by the end of the game.
Your output will consist of two lines. The first line will contain a string with $$$2n^2-2n$$$ characters indicating who made the corresponding move, and in what order. A move made by Alice will be indicated by the character 'A' and a move made by Bob will be indicated by the character 'B'.
The second line will contain two integer values, giving the final score of the game. The first value will be Alice's score, and the second will be Bob's score. The sum of these two numbers should always sum to $$$(n-1)^2$$$, the total number of unit squares on the grid.
3 1 2 2 2 1 1 2 1 2 3 3 3 1 3 2 3 3 2 3 3 3 1 3 2 1 1 1 2 2 1 3 1 2 1 2 2 2 2 2 3 1 2 1 3 2 2 3 2
ABABABABAABB 1 3
4 2 4 3 4 2 1 2 2 1 3 2 3 1 3 1 4 2 2 3 2 2 2 2 3 4 1 4 2 2 1 3 1 3 1 4 1 4 3 4 4 2 3 2 4 1 1 1 2 1 2 2 2 3 1 3 2 3 2 4 2 3 4 4 4 4 2 4 3 1 1 2 1 3 3 4 3 2 3 3 3 3 2 3 3 3 3 3 4 1 2 1 3 1 4 2 4
ABABABABABABABBBABBABBBB 0 9
Stanford's football team is doing end-of-year performance reviews. Coach Sao is very upset with his team members for being late to practice! There are $$$S$$$ players on the team, numbered $$$1$$$ to $$$S$$$, and every time a player is late, he writes their number on the whiteboard. Looking at the whiteboard, they have been late $$$N$$$ times in total.
Coach Sao has decided to make the players do push-ups as punishment. Player $$$k$$$ has to count how many total times the players numbered $$$1$$$ to $$$k$$$ have been late, and then do that number of push-ups. MTL is wondering whether Coach Sao is too cruel to his players, so he asks him, "How many players do at most $$$x$$$ push-ups?" MTL is very forgetful, so he may ask Coach Sao up to $$$Q$$$ questions. He may ask multiple questions with the same $$$x$$$. Since $$$Q$$$ and $$$x$$$ may be large, help Coach Sao answer these questions!
The first line contains two space separated integers, $$$S$$$ and $$$N$$$ ($$$1 \leq S \leq 10^9$$$, $$$1\leq N \leq 10^5$$$).
The second line contains $$$N$$$ space-separated integers: the numbers on the whiteboard.
The third line contains an integer $$$Q$$$, ($$$1 \leq Q \leq 10^5$$$) the number of questions MTL will ask.
The next $$$Q$$$ lines represent the questions. Each question will be the integer $$$x$$$, ($$$0 \leq x \leq 10^9$$$) on one line.
For every question, output the answer in one line.
4 6 1 2 4 2 2 1 2 1 3
0 1
Sonic the hedgehog recently graduated from Stanford University and is off on a new mission: to catch the Evil Golden Bear. Unfortunately, Sonic has rolled into bit of a conundrum. He has to run through a city of civilians in order to catch the Bear. Help the hedgehog hunt him down without running over any civilians!
The city is represented by a 2D grid of size $$$N \times M$$$ and consisting of 1's and 0's:
To move across the grid, Sonic has only three options every second:
Note that Sonic must choose to accelerate or decelerate at any given second while moving at a positive speed. In other words, he cannot maintain the same positive speed for any two consecutive seconds.
After this decision, and within the same second, Sonic will move <speed> grid spaces in his current direction. None of the spaces he rolls through can contain a civilian, and he cannot move outside of the city limits.
Note that Sonic cannot reduce his speed below $$$0$$$, and he can only change directions when his speed is equal to 0.
If Sonic starts out at cell $$$(1, 1)$$$ facing South and with speed $$$0$$$, and the Golden Bear sits at cell (N, M), how fast can the hedgehog get to the Bear without hitting any civilians along the way?
The first line contains two space-separated positive integers, $$$1 \leq N \leq 400$$$ and $$$1 \leq M \leq 400$$$.
The next $$$N$$$ lines each contain a string of $$$M$$$ characters, describing the city.
It is guaranteed that the top left corner $$$(1, 1)$$$ and the bottom right corner $$$(N, M)$$$ will not contain civilians.
Output the smallest possible number of seconds it will take for the hedgehog to reach the bad guy, or $$$-1$$$ if it is impossible for the hedgehog to do so.
8 1 0 0 0 0 0 0 0 0
5
4 4 0001 0010 0100 1000
-1
In the first test case, sonic can follow the following sequence of moves to reach the bottom corner: 1. Accelerate (speed = 1) (2, 1) 2. Accelerate (speed = 2) (4, 1) 3. Decelerate (speed = 1) (5, 1) 4. Accelerate (speed = 2) (7, 1) 5. Decelerate (speed = 1) (8, 1)
In the second test case, there is a wall of civilians in the way, so Sonic cannot reach the Evil Golden Bear.
The Stanford Axe Committee, which is in charge of guarding the Stanford Axe, is holding tryouts for new members in preparation for the annual faceoff against Cal. Applicants are numbered 1 through $$$N$$$ and come to try out. As the committee lines everyone up to call them in for an interview, the Stanford tree waltzes by and issues the first challenge:
Rearrange yourselves such that the longest increasing subsequence is of length $$$X$$$ and the longest decreasing subsequence must be of length $$$Y$$$, or say it's impossible.
Can you help the applicants pass their first test?
Definition: A subsequence of an array is defined as any array that can be reachable by deleting some number of elements. For example, if we have array [4, 2, 7, 5, 1], valid subsequences include [4, 7, 1] and [2, 7], but not [2, 4] or [3, 7, 5].
The input consists of $$$3$$$ space separated integers, $$$N$$$, $$$X$$$, and $$$Y$$$ ($$$1 \leq X, Y \leq N \leq 10^3$$$).
Output one line containing your permutation of the integers $$$1$$$ to $$$N$$$. If there is no such permutation, output $$$-1$$$.
10 4 5
7 6 3 2 5 9 10 4 1 8
5 1 1
-1
Given a sequence of elements, a subsequence is a subset of these elements in the same order. An increasing subsequence means every element is greater than the element before it. For example, the largest increasing subsequence of $$$1, 2, 5, 4, 3, 6, 9, 7, 8$$$ is of length 6, such as $$$1, 2, 3, 6, 7, 8$$$.
After a difficult fiscal year, MTL is raising donation money from Stanford Alumni. He's starting with the alumni who live in Star City. Star City consists of $$$n$$$ houses, numbered $$$1$$$ to $$$n$$$, which are connected by $$$n-1$$$ two-way roads. Every house can be reached from every other house with some series of roads. And there is at most $$$1$$$ house with more than $$$2$$$ roads leaving it.
MTL will start driving from house $$$x$$$ and stop at house $$$y$$$ ($$$y$$$ does not need to be different from $$$x$$$). At each house, MTL asks the alumni to make a donation offer. Alumni like to contribute equally, so at the end of MTL's drive, each house will pay the same amount as the smallest offer made. Help MTL find a route that raises the most money!
The first line contains the integer $$$n$$$ ($$$1\leq n\leq 10^5$$$).
The second line contains $$$n$$$ space-separated integers, representing how much the alumni at the $$$i^{th}$$$ house offers to donate. All donations are from $$$1$$$ to $$$10^9$$$ dollars.
The next $$$n-1$$$ lines contain two space-separated integers $$$a$$$ and $$$b$$$, representing that a road connects $$$a$$$ and $$$b$$$. $$$a$$$ and $$$b$$$ will be within 1 and $$$n$$$.
Your output should consist of two lines.
On the first line, output the maximum amount of donation money MTL can raise.
On the second line, output two space-separated integers $$$x$$$ and $$$y$$$ so that the route from $$$x$$$ to $$$y$$$ makes the most money. If there are multiple solutions, output the one with the smallest $$$x$$$; if there are multiple with the same smallest $$$x$$$, give the solution with the smallest $$$y$$$.
5 1 2 3 4 5 1 2 1 3 3 4 3 5
9 4 5
6 6 5 4 3 2 1 1 2 2 3 3 4 4 5 5 6
12 1 3
William is competing in a gold mining contest against some Berkeley students. He's looking for gold nuggets buried in a giant field. The field can be modeled as an $$$N$$$ by $$$N$$$ grid of squares, where each grid square has the possibility of having golden nuggets buried underneath.
Since the field can be quite large, William bought a metal detector to aid in his search for gold. The metal detector can be used to find gold buried underneath the ground. In one use of the metal detector, it can find the number of gold nuggets buried under a $$$K$$$ by $$$K$$$ subgrid of the field. This subgrid must be axis-aligned and match exactly with the squares in the grid that form the field.
Unfortunately, since the metal detector is quite cheap, William can only use it once. Can you find help him find the maximum number of gold nuggets he can find?
Each test case begins with the integers $$$N, M, K$$$ $$$(1 \leq N, K \leq 10^9, 1 \leq M \leq 10^5).$$$
The next $$$M$$$ lines consist of two integers $$$x,y$$$ ($$$1 \leq x,y \leq N)$$$ denoting the coordinates of the square where a gold nugget can be found. Note that it is not guaranteed that coordinates are distinct, that is, more than one gold nugget can be buried underneath a given square.
A single integer, representing the maximum number of gold nuggets that the metal detector can find in one use.
5 5 3 1 1 2 2 1 2 4 5 5 5
3
5 3 1 2 2 3 3 2 2
2
Alice and Bob are competing to determine the champion of the annual Stanford vs. Berkeley Card Tournament. They are playing a modified version of the card game War.
The game works as follows: A deck of $$$2N$$$ cards numbered $$$1$$$ to $$$2N$$$ (no suites) are shuffled and dealt so Alice and Bob each have $$$N$$$ cards, face down. Alice and Bob take the top cards of their stacks and turn them face up at the same time. Whoever plays the card with the higher number wins a point. Both cards played are then discarded. Alice and Bob repeat this process until they have no cards remaining. The winner of the game is the player with the most points.
Just before the game starts, Bob leaves the room to turn in his CS homework. Alice takes advantage of this opportunity to look at her stack of cards and Bob's stack. She can re-order the cards in her stack and Bob's stack, but she cannot move cards from her stack to Bob's, or vice-versa. Given her stack and Bob's stack, what is the most number of points she can win after re-ordering the cards?
The first line of the input is a single integer, $$$N$$$ ($$$1 \leq N \leq 10^5$$$). The second line is a list of $$$N$$$ integers separated by spaces, representing Alice's stack of cards. The third line is a list of $$$N$$$ integers separated by spaces, representing Bob's stack of cards. All natural numbers from 1 to $$$2N$$$, inclusive, will be present exactly once in the second or third line.
The output should be one line with an integer which is the most number of points Alice can win after re-ordering her and Bob's stacks.
10 1 3 5 7 9 11 13 15 17 19 2 4 6 8 10 12 14 16 18 20
9
8 2 7 10 8 5 4 6 15 3 9 14 11 12 13 1 16
4
Stanford's unofficial mascot is the Tree! Each year, a secret ritual is held in Main Quad in order to honor the holiness of the Tree. During this ritual, $$$N$$$ trees are placed in a circle, each with varying height. The students gather inside of this circle and complete the ritual. However, last year the secret was spilled and made its way across the Bay to Berkeley's campus. The Berkeley students, being jealous that their mascot is just a bear, decided that they wanted to sabotage this auspicious ritual.
The Stanford Engineering students found out about this plot, and came up with a plan to prevent the Berkeley attack. They discovered that if they were able to make all of the trees in the circle the same height, then they could deploy an electronic barrier that prevents Berkeley Bears from entering campus.
It was a genius plan, but they needed to figure out how to make all of the trees the same height without killing the trees! Luckily, they were able to create a very complicated device that looked just like a pipe. The specifications of this device are too advanced to include in the description section of this problem. These pipes had the capability of transforming matter. In particular, if placed between two adjacent trees, a pipe was able to open a matter portal that averaged the heights of the two trees! This portal will never close, which means that if additional pipes are added, expanding the amount of trees that are connected, all of their values are averaged together.
More concretely, consider having three trees $$$A$$$, $$$B$$$ and $$$C$$$ in a circle, with heights 10, 20, and 3 respectively. If a pipe was added between trees $$$A$$$ and $$$B$$$ the resulting heights of the trees would be [15, 15, 3]. If now an additional pipe was added between trees $$$B$$$ and $$$C$$$ the trees' heights would be [11, 11, 11].
These pipes are really time consuming and expensive to make, so the Stanford Engineers want to use as few as possible. They need your help. Given $$$N$$$ numbers representing the initial heights of all of the trees, output the minimum number of pipes needed to be added between adjacent trees, such that the resulting heights of all trees are equal. It is guaranteed that the resulting height is an integer.
The first line contains a single integer $$$N$$$ ($$$ 1 \leq N \leq 5 \cdot 10^5$$$). The second line contains $$$N$$$ integers $$$a_i$$$ ($$$ 1 \leq a_i \leq 10^9$$$) representing the starting heights of the trees. Trees $$$i = 1$$$ and $$$i = N$$$ are adjacent to each other in the circle.
Output a single integer, which is the minimum number of pipes needed to be added to the trees such that the resulting heights of all trees are equal.
6 6 6 1 7 10 6
2
3 5 5 5
0
Stan Ford is organizing a programming contest, but it is being swarmed by a horde of Berkeley students! He needs to fence them in, but only has 3 straight pieces of woods of integer lengths $$$a, b, c$$$. Can you tell Stan if the fence pieces can be formed into a triangle with non-zero area?
The first line contains the number of test cases $$$N$$$ $$$(1 \leq N \leq 100)$$$. The next $$$N$$$ lines will contain 3 space separated integers $$$a$$$, $$$b$$$, and $$$c$$$ $$$(1\leq a,b,c \leq 10^9)$$$ which represent the lengths of the fence pieces.
Output $$$N$$$ lines. On each line, print 'Yes' if it is possible to arrange the 3 pieces of wood into a fence, otherwise print 'No' (without the quotes).
2 1 2 3 2 2 3
No Yes
You are trying to solve a puzzle posed by some Stanford students.
You have a line of marbles, with some white and some black. You can only remove marbles from either end of the line. What is the greatest number of white marbles you can remove, given that you are only allowed to remove at most $$$K$$$ black marbles? You can assume there are at least $$$K+1$$$ black marbles in the line.
The first line of the input contains 2 space separated integers $$$N$$$, ($$$1\leq N \leq 10^6$$$) and $$$K$$$, ($$$1 \leq K \lt N$$$). $$$N$$$ is the total number of marbles, and $$$K$$$ is the maximum number of black marbles you're able to remove. The second line of input is a string of length $$$N$$$, with the characters 'W' for white marbles and 'B' for black marbles.
Output a single integer representing the greatest number of white marbles you can remove.
10 3 WWWBBBBWWW
6
15 3 WWBBBWWWWWBBBBB
7
Stan Ford is a city planner who has been hired by MTL, Stanford's president, to solve a very important problem. Stan has been tasked with finding a new location for Stanford's campus. As lovely as Palo Alto is, Stanford has grown tired of being so close to Berkeley and wants to move to the great state of Kansas.
Within Kansas, there are $$$N$$$ cities, and $$$M$$$ one directional roads that connect cities. In Kansas, it is guaranteed that if you leave from a city, it is impossible to return to that city by traveling along the roads.
Stan Ford needs to find a city that is ambiguous to report back to MTL. A city, $$$u$$$, is ambiguous if for every other city $$$v$$$, Stan can either walk from $$$u$$$ to $$$v$$$, or from $$$v$$$ to $$$u$$$. During these walks, he can of course pass through other cities that aren't $$$u$$$ or $$$v$$$.
However, MTL is quite meticulous, and wants to make sure that he is able to consider all possible home cities for Stanford. Thus, he wants to know from Stan Ford, the number of ambiguous cities that exist in Kansas. Poor Stan is tired of walking, and asks for your help in counting the number of ambiguous cities!
The first line will contain two space separated integers $$$N$$$ and $$$M$$$ ($$$ 2 \leq N \leq 200,000$$$, $$$1 \leq M \leq 200,000$$$) which represents the number of cities and roads respectively. The next $$$M$$$ lines will contain two space separated integers $$$u$$$ and $$$v$$$ ($$$ 1 \leq u, v \leq N$$$) which means there is a road from city $$$u$$$ to city $$$v$$$.
Output a single integer, the number of ambiguous cities in the graph.
4 4 1 2 1 3 2 4 3 4
2
Stanford and Berkeley are having a plant growing contest. Luckily some of the Stanford team members remembered from Biology class that watering plants helps them grow. The strategy they want to employ in order to win, is to water all of their plants as quickly as possible.
The students have $$$N$$$ labelled plants arranged in a line. They have a few operations they can perform. They can either
The students can water each plant multiple times, but cannot perform more than one operation at a time. Compute the minimum amount of time needed to water each plant at least once.
The first line will contain four space separated integers $$$N$$$ ($$$1 \leq N \leq 5000$$$), $$$K$$$ ($$$ 1 \leq K \leq N$$$), $$$W$$$ ($$$1 \leq W \leq 10^9$$$), and $$$S$$$ ($$$1 \leq S \leq 10^9$$$) which represent the number of plants, the size of the subarray the sprinkler can water a time, the time it takes to operate the sprinkler, and the time it takes to swap two plants.
The second line of input will contain $$$N$$$ integers $$$t_i$$$ ($$$1 \leq t_x \leq 10^9, 1 \leq i \leq N$$$) which represents the amount of time it takes to water each plant individually.
Output a single integer, the minimum amount of time needed to water all plants at least once.
5 3 5 2 1 4 8 4 1
7
5 3 100 2 1 4 8 4 1
18
Sample 1: In the first sample, we should use the sprinkler on the middle three elements, and manually water the two plants on the end. Sample 2: In the second sample, it's now just cheaper to water all of the plants by hand.
Alice and Bob are in charge of the front row bleachers during the Big Game. The bleacher consists of $$$N$$$ seats which have numbers written on them. Each seat will only have one integer on it. Multiple seats may have the same number.
Alice and Bob decide that the Stanford students can take any even numbered seat and the Cal students can take an odd numbered seat.
The night before the game, Alice and Bob's supervisor decides that they want to make sure the seats alternate between Berkeley and Stanford students so they can make new friends.
Alice and Bob thus need to change some of the numbers written on the seats! For every seat, they decide they can add some non-negative integer (including 0) so that the resulting row of seats has numbers of alternating parity. The numbers they add need not be distinct. What's the minimum total sum of numbers they need to add?
Note: Parity simply refers to whether a number is odd or even. 2 has even parity, and 3 has odd parity.
The first line of input is a single integer N ($$$1 \leq N \leq 10^{5}$$$) which is the number of seats. The second line is a list of space separated integers $$$a_i$$$ ($$$ 1 \leq a_i \leq 10^3$$$), which each integer represents the number originally written on each seat.
The output should be an integer, representing the minimum total sum of numbers to be added.
7 4 1 34 99 62 5 56
0
4 1 1 3 3
2
Sample 1: The numbers are already alternating parity, so no numbers need to be added.
Sample 2: Alice and Bob can add 1 to either the first and third seats, which results in an array of [2, 1, 4, 3], or they can add 1 to the second and fourth seats which results in an array of [1, 2, 3, 4].