Hard Programming Challenges

Advanced Calculator
Difficulty: Hard	Test Cases: 10	Published: 2014-03-20
Summary Create an advanced calculator
Description The goal of this challenge is to create an advanced calculator. The following operations should be supported with their order (operator precedence):    Pi          Pi number     e           Euler's number     sqrt()      Square root     cos()       Cosine     sin()       Sine     tan()       Tangent     lg()        Decimal logarithm     ln()        Natural logarithm 1   ()          Brackets 2   ||          Absolute value, e.g. |-5 - 10| 3   !           Factorial 4   -           Unary minus 5   ^           Exponent 6   *, /, mod   Multiply, Divide, Modulus, e.g. 5 mod 2 = 1 (left-to-right precedence) 7   +, -        Add, Subtract (left-to-right precedence) Only integers will be provided to the modulus function. Each number in input expression is greater than -20,000 and less than 20,000. Each output number is greater than -20,000 and less than 20,000. If output number is a float number it should be rounded to the 5th digit after the dot. E.g 14.132646 gets 14.13265, 14.132644 gets 14.13264, 14.132645 gets 14.13265. If output number has less than 5 digits after the dot you don't need to add zeros. E.g. you need to print 16.34 (and not 16.34000) if the answer is 16.34. And you need to print 16 (and not 16.00000) if the answer is 16. Note: do NOT use any kind of eval function.
Input Your program should read lines from standard input. Each line is one test case. Each line contains a mathematical expression.
Output Print out the result of the calculation.

Climbing Stairs 2
Difficulty: Hard	Test Cases: 12	Published: 2022-01-27
Summary Count the number of ways to climb to the top of a staircase
Description You are climbing a staircase with n total stairs. Every time you take a step, you can climb either 1 or 2 stairs. In how many distinct ways can you climb to the top?
Input Your program should read lines from standard input. Each line contains a positive integer n which is the total number of stairs: n <= 1000 For example: 3
Output Print out a single integer which is the number of different ways to climb to the top of the staircase. For example: 3 See the attachments tab for an image representation of 3 ways to climb on top of the staircase having 3 steps.
Attachments

Closest Pair
Difficulty: Hard	Test Cases: 3	Published: 2012-10-08
Summary Given a set of points in a two dimensional space, you will have to find the distance between the closest two points.
Description Credits: Programming Challenges by Steven S. Skiena and Miguel A. Revilla You will be given the x/y co-ordinates of several locations. You will be laying out 1 cable between two of these locations. In order to minimise the cost, your task is to find the shortest distance between a pair of locations, so that pair can be chosen for the cable installation.
Input Your program should read lines of text from standard input. The input consists of several sets of input. Each set of input starts with an integer N (0<=N<=10000), which denotes the number of points in this set. The next N lines contain the coordinates of two-dimensional points. For a set of 5 points, there would be 6 lines. The first line would contain the number 5 and then next 5 lines would be the points. The first of the two numbers denotes the X-coordinate and the latter denotes the Y-coordinate. The input is terminated by a line containing only 0. This line should not be processed. The value of the coordinates will be less than 40000 and non-negative.
Output For each set of input print a single line to standard output containing a floating point number (with four digits after the decimal point) which denotes the distance between the closest two points. If there are no such two points in the input whose distance is less than 10000, print the line INFINITY.

Computer Terminal
Difficulty: Hard	Test Cases: 2	Published: 2014-03-21
Summary Print text to terminal with control sequences
Description In this problem you are writing the software for a small terminal with a 10-row, 10-column display (perhaps for a point-of-sale terminal). Rows and columns are numbered 0 through 9. The character that introduces a control sequence is ^ , the circumflex. The character (or in one case, the two characters) immediately following the control sequence introducer will direct your software in performing its special functions. Here is the complete list of control sequences you will need to interpret: ^c - clear the entire screen; the cursor row and column do not change ^h - move the cursor to row 0, column 0; the image on the screen is not changed ^b - move the cursor to the beginning of the current line; the cursor row does not change ^d - move the cursor down one row if possible; the cursor column does not change ^u - move the cursor up one row, if possible; the cursor column does not change ^l - move the cursor left one column, if possible; the cursor row does not change ^r - move the cursor right one column, if possible; the cursor row does not change ^e - erase characters to the right of, and including, the cursor column on the cursor's row; the cursor row and column do not change ^i - enter insert mode ^o - enter overwrite mode ^^ - write a circumflex (^) at the current cursor location, exactly as if it was not a special character; this is subject to the actions of the current mode (insert or overwrite) ^DD - move the cursor to the row and column specified; each D represents a decimal digit; the first D represents the new row number, and the second D represents the new column number No illegal control sequences will ever be sent to the terminal. The cursor cannot move outside the allowed screen locations (that is, between row 0, column 0 and row 9, column 9). When a normal character (not part of a control sequence) arrives at the terminal, it is displayed on the terminal screen in a manner that depends on the terminal mode. When the terminal is in overwrite mode (as it is when it is first turned on), the received character replaces the character at the cursor's location. But when the terminal is in insert mode, the characters to the right of and including the cursor's location are shifted right one column, and the new character is placed at the cursor's location; the character previously in the rightmost column of the cursor's row is lost. Regardless of the mode, the cursor is moved right one column, if possible.
Input Your program should read lines from standard input. Each test case consists of multiple lines. The first line is the number of lines in the test case N. The next N lines contain the symbols described above.
Output Print the result of the terminal commands.

Da Vyncy
Difficulty: Hard	Test Cases: 10	Published: 2014-03-20
Summary Recreate a document from a set of fragments.
Description Prologue ============= You were reading The Da Vyncy Code, the translation of a famous murder mystery novel into Python. The Code is finally revealed on the last page. You had reached the second to last page of the novel, and then you went to take a bathroom break. While you were in the bathroom, the Illuminati snuck into your room and shredded the last page of your book. You had 9 backup copies of the book just in case of an attack like this, but the Illuminati shredded the last page from each of the those books, too. Then they propped up a fan, aimed it at the remains, and turned it on at high-speed. The last page of your book is now in tatters. However, there are many text fragments floating in the air. You enlist an undergraduate student for a 'summer research project' of typing up these fragments into a file. Your mission: reassemble the last page of your book. Assignment ============= (adapted from a problem by Julie Zelenski) Write a program that, given a set of fragments (ASCII strings), uses the following method (or a method producing identical output) to reassemble the document from which they came: At each step, your program searches the collection of fragments. It should find the pair of fragments with the maximal overlap match and merge those two fragments. This operation should decrease the total number of fragments by one. If there is more than one pair of fragments with a maximal overlap, you may break the tie in an arbitrary fashion. Fragments must overlap at their start or end. For example: - "ABCDEF" and "DEFG" overlap with overlap length 3 - "ABCDEF" and "XYZABC" overlap with overlap length 3 - "ABCDEF" and "BCDE" overlap with overlap length 4 - "ABCDEF" and "XCDEZ" do *not* overlap (they have matching characters in the middle, but the overlap does not extend to the end of either string). Fear not - any test inputs given to you will satisfy the property that the tie-breaking order will not change the result, as long as you only ever merge maximally-overlapping fragments. Bonus points if you can come up with an input for which this property does not hold (ie, there exists more than 1 different final reconstruction, depending on the order in which different maximal-overlap merges are performed) -- if you find such a case, submit it in the comments to your code! All characters must match exactly in a sequence (case-sensitive). Assume that your undergraduate has provided you with clean data (i.e., there are no typos).
Input Your program should read lines from standard input. Each line represents a test case. Each line contains fragments separated by a semicolon, which your assistant has painstakingly transcribed from the shreds left by the Illuminati. You may assume that every fragment has length at least 2 and at most 1022 (excluding the trailing newline, which should *not* be considered part of the fragment).
Output Print out the original document, reassembled.

Detecting Cycles
Difficulty: Hard	Test Cases: 3	Published: 2012-10-08
Summary Detecting loops within a sequence.
Description Given a sequence, write a program to detect cycles within it.
Input Your program should read lines of text from standard input. Each line will contain a sequence of space delimited numbers, which can have multiple digits (e.g., 12). Ignore empty lines.
Output For each line of input, print to standard output the first cycle you find. Ensure that there are no trailing spaces on each line you print.

Discount Offers
Difficulty: Hard	Test Cases: 10	Published: 2014-03-20
Summary Determine optimal pairing of customers with products
Description Our marketing department has just negotiated a deal with several local merchants that will allow us to offer exclusive discounts on various products to our top customers every day. The catch is that we can only offer each product to one customer and we may only offer one product to each customer. Each day we will get the list of products that are eligible for these special discounts. We then have to decide which products to offer to which of our customers. Fortunately, our team of highly skilled statisticians has developed an amazing mathematical model for determining how likely a given customer is to buy an offered product by calculating what we call the "suitability score" (SS). The top-secret algorithm to calculate the SS between a customer and a product is this: 1. If the number of letters in the product's name is even then the SS is the number of vowels (a, e, i, o, u, y) in the customer's name multiplied by 1.5. 2. If the number of letters in the product's name is odd then the SS is the number of consonants in the customer's name. 3. If the number of letters in the product's name shares any common factors (besides 1) with the number of letters in the customer's name then the SS is multiplied by 1.5. Your task is to implement a program that assigns each customer a product to be offered in a way that maximizes the combined total SS across all of the chosen offers. Note that there may be a different number of products and customers. You may include code from external libraries as long as you cite the source.
Input Your program should read lines from standard input. Each line is a comma delimited set of customer names followed by a semicolon, and then a comma delimited set of product names. Assume the input is ASCII encoded.
Output Print out the maximum total score to two decimal places.

Distinct Subsequences
Difficulty: Hard	Test Cases: 10	Published: 2014-03-20
Summary Determine the number of distinct subsequences within a string.
Description A subsequence of a given sequence S consists of S with zero or more elements deleted. Formally, a sequence Z = z1z2..zk is a subsequence of X = x1x2...xm, if there exists a strictly increasing sequence of indices (i) of X such that for all j=1,2,...k we have Xi = Zj. E.g. Z=bcdb is a subsequence of X=abcbdab with corresponding index sequence <2,3,5,7>
Input Your program should read lines from standard input. Each line contains two comma separated strings. The first is the sequence X and the second is the subsequence Z.
Output Print out the number of distinct occurrences of Z in X as a subsequence.

Distinct Triangles
Difficulty: Hard	Test Cases: 6	Published: 2013-12-13
Summary Find the number of distinct triangles formed in a graph
Description Alice the archaeologist has just entered the tomb of the Pharaoh. She turns on her flashlight and notices an undirected graph painted on the wall, with V nodes and E edges. Suddenly, the stone door behind her slams shut. Fortunately, Alice knows the way out - she must place N pebbles upon the altar to re-open the door, where N is the number of triangles in the graph. Example: 0--1 | /| |/ | 2--3 N is two in this graph.
Input Your program should read lines from standard input. The input begins with a line containing two integers, V and E (1 <= V, E <= 1000), separated by a space. Then, E lines follow, each containing two integers separated by space, representing two vertices connected by an undirected edge. Each vertex is in the range (0 <= vertex < V).
Output Print a line containing the number of distinct triangles formed over three vertices and edges in the graph.

Efficient Delivery
Difficulty: Hard	Test Cases: 10	Published: 2014-03-20
Summary Load your tankers with oil
Description A shipping company is providing oil delivery between two continents using tankers. They’re trying to increase their efficiency by keeping their ships in port to wait for additional oil to prevent setting to sea only partially loaded. As a logistician, the challenge for you will be to determine all variations of efficient delivery based on the available tankers and the total amount of oil in barrels needed to achieve maximum efficiency. A tanker's carrying capacity is expressed in barrels of oil that it can take on board. E.g. Some company has only two kind of tankers with the capacity of 2 and 5 barrels and the amount of oil to be transferred is 12 barrels. In this case there are two options of efficient delivery: 1. load 6 tankers with the capacity of 2. [6,0] 2. load 1 tanker with the capacity of 2 and 2 tankers with the capacity of 5. [1,2] If this company had three kind of tankers with the capacity of 6, 7, 8 barrels and 10 barrels of oil to be transferred then there would be no option for efficient delivery and the minimum amount of oil needed would be 12 [6,0,0] so the answer in this case is 2. So you see that if there is no option to load the tankers effectively, you need to find out the minimum amount of oil which needs to be added to the given quantity to make the efficient delivery possible.
Input Your program should read lines from standard input. Each line contains rows with available tankers in brackets in sorted order, and the amount of oil after a comma. The number of tankers is in range [2, 5] A tanker's capacity is in range [2, 10000] barrels Oil amount is in range [1, 200000] barrels
Output Print out all possible variations of efficient delivery in sorted order if the efficient delivery exists. Otherwise, print out the amount of oil to be added.

Find Min
Difficulty: Hard	Test Cases: 10	Published: 2014-03-20
Summary Facebook Hacker Cup 2013 problem.
Description Credits: This problem appeared in the Facebook Hacker Cup 2013 Hackathon. John decided to play with arrays. Did you know that hackers enjoy playing with arrays? John has a zero-based index array, m, which contains n non-negative integers. However, only the first k values of the array are known to him, and he wants to figure out the rest. John knows the following: for each index i, where k <= i < n, m is the minimum non-negative integer which is *not* contained in the previous *k* values of m. For example, if k = 3, n = 4 and the known values of m are [2, 3, 0], he can figure out that m[3] = 1. John is very busy making the world more open and connected, as such, he doesn't have time to figure out the rest of the array. It is your task to help him. Given the first k values of m, calculate the nth value of this array. (i.e. m[n - 1]). Because the values of n and k can be very large, we use a pseudo-random number generator to calculate the first k values of m. Given positive integers a, b, c and r, the known values of m can be calculated as follows: m[0] = a m = (b * m[i - 1] + c) % r, 0 < i < k
Input Your program should read lines from standard input. Each line contains 6 comma separated positive integers which are the values of n,k,a,b,c,r in order.
Output Print out the nth element of m for each test case.

Find My Cousin
Difficulty: Hard	Test Cases: 5	Published: 2019-04-02
Summary Seek relatives in a tree
Description Search a family tree for all cousins of the person requested. A cousin is defined as any child of the parent's sibling. In other words, a first cousin in the same generation. For example: Ben and Mike are Siblings Ben's Children are Lisa and Sally Mike's Children are John and Mark
Input The first line of input is the name of the person for which to find cousins. Each subsequent line represents a generation (in order) with names separated by a comma. A pipe separates the sets of siblings within each generation. Following the example: Ben,Mike Lisa,Sally|John,Mark There will never be more than two children of a given parent and each generation will be completely described, including empty spaces.
Output A sorted list of cousins. If the result is empty, print NULL.

Following Integer
Difficulty: Hard	Test Cases: 8	Published: 2012-10-08
Summary Determine the next number in a sequence
Description Credits: This challenge has appeared in a past google competition You are writing out a list of numbers. Your list contains all numbers with exactly i digits in its decimal representation which are equal to i, for each i between 1 and 9, inclusive. You are writing them out in ascending order. For example, you might be writing every number with two '1's and one '5'. Your list would begin 115, 151, 511, 1015, 1051. Given N, the last number you wrote, compute what the next number in the list will be. The number of 1s, 2s, ..., 9s is fixed but the number of 0s is arbitrary.
Input Your program should read lines of text from standard input. Each line will contain a single integer n < 10^6.
Output For each input integer n, print to standard output the next integer in the list, one integer per line.

Hot Pursuit
Difficulty: Hard	Test Cases: 8	Published: 2019-11-15
Summary Calculate a travel time for a curvilinear motion
Description A dog is chasing a cat on a large field, with a single big tree growing on it. The cat wants to escape on the tree and runs towards it in a straight line at a fixed speed. The dog is not clever enough to devise a strategy of interception and always runs directly towards the cat at a fixed speed, constantly changing direction as the cat runs to the tree. Given initial positions and velocities of the animals and the position of the tree, calculate if the cat can escape. If not, calculate the time before the dog captures the cat. To escape successfully the cat has to reach the tree before being caught by the dog. If they get to the tree simultaneously the cat is captured. Note that you can simulate curvilinear movement with a series of transitional rectilinear movements. In every such short term update, you need to calculate the cat's displacement in a straight line towards a tree and the dog's displacement in a straight line towards the cat.
Input The first line contains two real numbers: x and y coordinates of the tree. The second line contains three real numbers: x and y coordinates of the initial position of the cat, and the cat's velocity. The third line contains three real numbers: x and y coordinates of the initial position of the dog, and the dog's velocity. For example: 0.0 -5.0 -15.0 10.0 2.0 15.0 10.0 3.0 All coordinates are in meters and velocities are in meters per second. All real numbers have exactly one digit after the decimal point.
Output Print the time in seconds that has passed since the start of the pursuit until the moment when the cat is captured or print Escaped if the cat escapes successfully. Print the time as a real number with exactly one digit after the decimal point.

Lights Out
Difficulty: Hard	Test Cases: 10	Published: 2013-12-23
Summary Given an N by M board of lights and the condition that switching a light toggles all surrounding lights, determine how many switches it will take to turn all the lights off.
Description Bob operates all electronic lights at the circus. Lately, there is a defective circuit board that is causing him some problems. The circuit board controls a rectangular box filled with N by M lights, each of which may be on or off depending on the lighting needs of the performers. However, each time he presses the button to toggle a particular light on or off, the circuit board toggles not only that light, but also the lights above, below, to the left, and to the right of the light. O = light is on . = light is off Examples:   .O..    .... OOO. -> ....  (toggle the light on row 2, column 2) .O..    .... OOO.    .... .O.. -> ....  (toggle the light on row 1, column 2) ....    .... ....    ..OO    ...O    ....    .... .O.. -> .O.O -> ..O. -> ...O -> .... ....    ....    ..O.    ..OO    .... (toggle lights as follows: row 1, column 4; row 2, column 3; row 2, column 4; and row 3, column 4) Bob needs to turn off all the lights. Write a program that prints the minimum number of times he must press a button on the board so that all the lights turn off, or -1 if it is not possible.
Input The input begins with two integers on a line, N and M (1 <= N,M <= 10), separated by a space. Then, N lines follow, each with M characters either '.' or 'O', indicating a light that is current off or a light that is currently on, respectively.
Output Print a line containing the minimum number of clicks that will turn off all the lights, or -1 if it is not possible to turn off all the lights within N*M clicks.

Longest Common Subsequence
Difficulty: Hard	Test Cases: 3	Published: 2012-10-08
Summary LCS between two strings.
Description Given two strings, write a program to determine the longest common subsequence between them. Each string can have a maximum length of 50 characters. Note, this subsequence need not be contiguous.
Input Your program should read lines of text from standard input. Ignore empty lines. Each non-empty line will contain two semicolon-separated strings. You can assume that there is only one unique subsequence per line.
Output For each line of input, print to standard output the longest common subsequence. Ensure that there are no trailing spaces on each line you print.

Maximum Flow
Difficulty: Hard	Test Cases: 11	Published: 2020-08-21
Summary Calculate the maximum flow in the flow network
Description A flow network is a directed graph where each edge has a certain capacity. Every edge can pass some amount of flow through itself, which doesn't exceed the edge capacity. Write a program to calculate a maximum flow through the flow network. There are N nodes in the graph indexed from 0 to (N - 1). The source node has index 0, the sink node has index (N - 1). The capacity of each edge is greater than zero.
Input The first line contains a positive integer, the number of nodes in the graph N. Each additional line describes one edge of the graph with three integers. The first two numbers are the indices of adjacent nodes, and the edge is directed from the first vertex in the pair to the second. The last number is the capacity of the edge. For example: 4 0 1 12 0 2 10 1 2 2 1 3 10 2 3 12
Output A single integer, which is the maximum possible flow through the network from the source node to the sink node.

Median Filter Root Sequences
Difficulty: Hard	Test Cases: 7	Published: 2019-10-04
Summary Count the number of root sequences for the standard median filter
Description In digital signal processing, a sampled discrete-time signal has the following characteristics defined for a median filter of window width 2N + 1: A constant neighborhood is a region of at least N + 1 consecutive identical values An edge is a strictly increasing or decreasing sequence, surrounded on both sides by constant neighborhoods of different values An impulse is a sequence of at most N values that are different from the surrounding constant neighborhoods having the same value An oscillation is any sequence of values that is not part of a constant neighborhood, an edge, or an impulse Note that constant neighborhoods are not included in edges and impulses. The constant neighborhood preceding the edge must have a value different from the value of the constant neighborhood following the edge. But for the impulse, preceding and following constant neighborhoods must have equal values. The image below illustrates a signal with: five constant neighborhoods two edges one impulse one oscillation If applying a filter of half-width N = 2: segments 1, 3, 5, 7, 9 are constant neighborhoods segments 4 and 8 are edges segment 2 is an impulse segment 6 is an oscillation See the attachments tab for a diagram of this example Write a program that will analyze an input signal by counting the number of constant neighborhoods, edges, and impulses it contains.
Input The first line contains an integer N which is a filter window half-width. The second line has comma-delimited samples of the input signal, which are integer values. For example: 2 0,0,0,2,2,0,0,0,1,2,2,3,4,5,5,5,6,7,8,5,6,6,6,6,5,4,3,2,1,1,1
Output Print out three comma-delimited numbers: A count of constant neighborhoods in the signal A count of edges A count of impulses For example: 5,2,1
Attachments

Median Filter Signal Oscillations
Difficulty: Hard	Test Cases: 7	Published: 2019-11-15
Summary Count the number of signal oscillations for the standard median filter
Description In digital signal processing, a sampled discrete-time signal has the following characteristics defined for a median filter of window width 2N + 1: A constant neighborhood is a region of at least N + 1 consecutive identical values An edge is a strictly increasing or decreasing sequence, surrounded on both sides by constant neighborhoods of different values An impulse is a sequence of at most N values that are different from the surrounding constant neighborhoods having the same value An oscillation is any sequence of values that is not part of a constant neighborhood, an edge, or an impulse Note that constant neighborhoods are not included in edges and impulses. The constant neighborhood preceding the edge must have a value different from the value of the constant neighborhood following the edge. But for the impulse, preceding and following constant neighborhoods must have equal values. The image below illustrates a signal with: five constant neighborhoods two edges one impulse one oscillation If applying a filter of half-width N = 2: segments 1, 3, 5, 7, 9 are constant neighborhoods segments 4 and 8 are edges segment 2 is an impulse segment 6 is an oscillation See the attachments tab for a diagram of this example Write a program that will analyze an input signal by counting the number of oscillations it contains.
Input The first line contains an integer number N which is a filter window half-width. The second line has comma-delimited samples of the input signal, which are integer values. For example: 2 0,0,0,2,2,0,0,0,1,2,2,3,4,5,5,5,6,7,8,5,6,6,6,6,5,4,3,2,1,1,1
Output Print out the number of oscillations. For example: 1
Attachments

Message Decoding
Difficulty: Hard	Test Cases: 2	Published: 2012-10-08
Summary Decode an encoded message
Description Credits: This challenge has appeared in a past ACM competition. Some message encoding schemes require that an encoded message be sent in two parts. The first part, called the header, contains the characters that can be present in the message. The second part contains a pattern that represents the message.You must write a program that can decode messages under such a scheme. The heart of the encoding scheme for your program is a sequence of "key" strings of 0's and 1's as follows: 0,00,01,10,000,001,010,011,100,101,110,0000,0001,. . .,1011,1110,00000, . . . The first key in the sequence is of length 1, the next 3 are of length 2, the next 7 of length 3, the next 15 of length 4, etc. If two adjacent keys have the same length, the second can be obtained from the first by adding 1 (base 2). Notice that there are no keys in the sequence that consist only of 1's. The keys are mapped to the characters in the header in order. That is, the first key (0) is mapped to the first character in the header, the second key (00) to the second character in the header, the kth key is mapped to the kth character in the header. For example, suppose the header is: AB#TANCnrtXc Then 0 is mapped to A, 00 to B, 01 to #, 10 to T, 000 to A, ..., 110 to X, and 0000 to c. The encoded message contains only 0's and 1's and possibly carriage returns, which are to be ignored. The message is divided into segments. The first 3 digits of a segment give the binary representation of the length of the keys in the segment. For example, if the first 3 digits are 010, then the remainder of the segment consists of keys of length 2 (00, 01, or 10). The end of the segment is a string of 1's which is the same length as the length of the keys in the segment. So a segment of keys of length 2 is terminated by 11. The entire encoded message is terminated by 000 (which would signify a segment in which the keys have length 0). The message is decoded by translating the keys in the segments one-at-a-time into the header characters to which they have been mapped.
Input Your program should read lines of text from standard input. Ecah line consists of a header and a message. The length of the header is limited only by the fact that key strings have a maximum length of 7 (111 in binary). Note that neither 0 nor 1 will occur in the header. If there are multiple copies of a character in a header, then several keys will map to that character. The encoded message contains only 0's and 1's, and it is a legitimate encoding according to the described scheme. That is, the message segments begin with the 3-digit length sequence and end with the appropriate sequence of 1's. The keys in any given segment are all of the same length, and they all correspond to characters in the header. The message is terminated by 000. Your program should accept the first argument as the filename and read the contents of this file as the test data, according to the conditions above.
Output For each data set, print to standard output the decoded message, one message per line.

Minesweeper
Difficulty: Hard	Test Cases: 10	Published: 2014-03-20
Summary Find the mines within a M*N matrix.
Description You will be given an M*N matrix. Each item in this matrix is either a '*' or a '.'. A '*' indicates a mine, whereas a '.' does not. The objective of the challenge is to output a M*N matrix where each element contains a number (except the positions which actually contain a mine which will remain as '*') which indicates the number of mines adjacent to it. Notice that each position has at most 8 adjacent positions e.g. left, top left, top, top right, right, ... In the first sample test case, the matrix: * * . . . . . . . . . * . . . becomes * * 1 0 0 3 3 2 0 0 1 * 1 0 0
Input Your program should read lines from standard input. Each line contains M,N, a semicolon and the M*N matrix in row major form.
Output Print out the new M*N matrix (in row major form) with each position(except the ones with the mines) indicating how many adjacent mines are there.

Minimum Path Sum
Difficulty: Hard	Test Cases: 10	Published: 2014-03-20
Summary Calculate the minimum sum of a path through a matrix.
Description You are given an n*n matrix of integers. You can move only right and down. Calculate the minimal path sum from the top left to the bottom right
Input Your program should read lines from standard input. Each test case consists of multiple lines. The first line will have the value of n (the size of the square matrix). This will be followed by n rows of the matrix. (Integers in these rows will be comma delimited).
Output Print out the minimum path sum for each matrix.

Package Problem
Difficulty: Hard	Test Cases: 10	Published: 2014-03-20
Summary Put as many things into a package as possible
Description You want to send your friend a package with different things. Each thing you put inside of a package has such parameters as index number, weight and cost. The package has a weight limitation. Your goal is to determine which things to put into the package so that the total weight is less than or equal to the package limit and the total cost is as large as possible. You would prefer to send a package which has less weight if there is more than one package with the same price. This is a variation of the Knapsack problem.
Input Your program should read lines from standard input. Each line contains the weight that a package can take (before the colon) and the list of things you need to pick from. Each thing is enclosed in parentheses where the 1st number is a thing's index number, the 2nd is its weight and the 3rd is its cost. Max weight any package can take is <= 100. There might be up to 15 things you need to choose from. Max weight and max cost of any thing is <= 100.
Output For each set of things produce a list of things (their index numbers separated by comma) that you put into the package. If none of the items will fit in the package, print a hyphen (-).

Palindromic Ranges
Difficulty: Hard	Test Cases: 6	Published: 2012-10-08
Summary Find out a range of palindromic numbers
Description A positive integer is a palindrome if its decimal representation (without leading zeros) is a palindromic string (a string that reads the same forwards and backwards). For example, the numbers 5, 77, 363, 4884, 11111, 12121 and 349943 are palindromes. A range of integers is interesting if it contains an even number of palindromes. The range [L, R], with L <= R, is defined as the sequence of integers from L to R (inclusive): (L, L+1, L+2, ..., R-1, R). L and R are the range's first and last numbers. The range [L1,R1] is a subrange of [L,R] if L <= L1 <= R1 <= R. Your job is to determine how many interesting subranges of [L,R] there are.
Input Your program should read lines of text from standard input. Each line will contain two positive integers, L and R (in that order), separated by a space.
Output For each line of input, print out the number of interesting subranges of [L,R]

Play with DNA
Difficulty: Hard	Test Cases: 10	Published: 2014-03-20
Summary Beware of what you're outputting
Description The following problem is related to bioinformatics tasks. In order to help in DNA research you will be asked to write an algorithm to find all occurrences of the DNA segment in a given DNA string. But that would be too easy for you. So please write an algorithm to find all occurrences of segment S in DNA string, with maximum allowed mismatches of M. By mismatch, we mean the minimum of total number of substitutions, deletions, insertions necessary to perform on the DNA slice in order to completely match the given segment. You need to look at the DNA slices with the same length as a given pattern. E.g. the segments 'AGTTATC' -> 'AGTATGC' have only 2 mismatches. For the DNA string 'CGCCCGAATCCAG' and the segment 'CCC' the first match with the maximum allowed mismatch of '1' is 'CGC', the second one is 'GCC', the third one is 'CCC' and so on. For the given segment 'CCC', the DNA string 'CGCCCGAATCCAG' and the maximum allowed mismatch of '1' the list of the matches is 'CGC GCC CCC CCG TCC CCA' The DNA string length is in range [100, 300] The M is in range [0, 40] The segment S length is in range [3, 50]
Input Your program should read lines from standard input. Each line contains a segment of DNA, the maximum allowed mismatches M and the DNA string, separated by whitespace.
Output Print out all the occurrences of a segment S in the DNA string in order from the best match, separated by whitespace, taking into account the number of allowed mismatches. If there are several segments with the equal matches, print them in alphabetical order. Print out 'No match' if there is no such occurrence.

Poker Hands
Difficulty: Hard	Test Cases: 10	Published: 2014-03-20
Summary Compare two poker hands.
Description In the card game poker, a hand consists of five cards and are ranked, from lowest to highest, in the following way: High Card: Highest value card. One Pair: Two cards of the same value. Two Pairs: Two different pairs. Three of a Kind: Three cards of the same value. Straight: All cards are consecutive values. Flush: All cards of the same suit. Full House: Three of a kind and a pair. Four of a Kind: Four cards of the same value. Straight Flush: All cards are consecutive values of same suit. Royal Flush: Ten, Jack, Queen, King, Ace, in same suit. The cards are valued in the order: 2, 3, 4, 5, 6, 7, 8, 9, Ten, Jack, Queen, King, Ace. If two players have the same ranked hands then the rank made up of the highest value wins; for example, a pair of eights beats a pair of fives. But if two ranks tie, for example, both players have a pair of queens, then highest cards in each hand are compared; if the highest cards tie then the next highest cards are compared, and so on.
Input Your program should read lines from standard input. Each line contains 2 hands (left and right). Cards and hands are separated by space.
Output Print out the name of the winning hand or "none" if the hands are equal.

Prefix expressions
Difficulty: Hard	Test Cases: 4	Published: 2012-10-08
Summary Evaluating a prefix expression.
Description Write a program to evaluate prefix expressions.
Input Your program should read lines of text from standard input. Each line is a prefix expression with tokens delimited by a single space. You may assume that the only operators appearing in the input are '+', '*', and '/'.
Output For each input expression, evaluate it and print to standard output the result, one result per line.

Register Allocation
Difficulty: Hard	Test Cases: 11	Published: 2019-10-04
Summary Calculate the minimum number of registers required to allocate variables
Description In computer architecture, a processor register is a small storage element which provides the fastest way to access data. When the computer program is compiled, the compiler must assign variables holding the data to a limited number of registers to improve the execution time. This process is called a register allocation. One approach to solving the register allocation problem is to use an interference graph. This is a graph in which vertices represent variables and edges connect pairs of variables that are used in the program at the same time. With this representation, the register allocation is reduced to graph coloring, so that adjacent vertices have different colors. Each color used in the graph represents a single register. If k colors are used to color the whole graph then k registers are required to cache the given set of variables. Imagine a simple case where at most ten variables are used in the program and the processor has only four registers. Write a program to calculate the minimum number of registers required to allocate all variables.
Input An adjacency list of the interference graph. Each line describes one vertex of the graph, which is a space-delimited list of variable names. The first element of the list is the name of the current variable, and all other elements are the variables that are adjacent to the current. For example: a b c d b a c e c a b d e d a c e e b c d See the attachments tab for a diagram of this example
Output The number of registers required for the allocation of all variables or Overflow when more than four registers are required.
Attachments

Repeated Substring
Difficulty: Hard	Test Cases: 5	Published: 2012-10-08
Summary Find the longest repeated substring in a given text
Description You are to find the longest repeated substring in a given text. Repeated substrings may not overlap. If more than one substring is repeated with the same length, print the first one you find.(starting from the beginning of the text). NOTE: The substrings can't be all spaces
Input Your program should read lines of text from standard input. Each line contains a string.
Output For each set of input print a single line to standard output which is the longest repeated substring. If there is none, print out the string NONE.

Seat your team
Difficulty: Hard	Test Cases: 10	Published: 2014-03-20
Summary Place the employees in a new office
Description Your team is moving to a new office. In order to make it feel comfortable on a new place you decided to give the possibility to pick the places where they want to sit. After the team visited the new office, each team member gave you a list of working places that he/she would like to occupy. Your goal is to determine a possibility of making all of your team members feel comfortable according to those lists. All working places in the new office are numbered from 1 to N. And each team member gave you the list which contained the places in unsorted order.
Input Your program should read lines from standard input. Each line contains an integer N of available places in the office as the first number, and the lists of places that have been chosen by each team member. These lists are enclosed by square brackets.
Output Print out the simple "Yes" or "No" answer for the following question: "Is there a possibility to make all of your team members feel comfortable at the new office?".

Shelter for Rabbits
Difficulty: Hard	Test Cases: 12	Published: 2020-08-21
Summary Calculate a maximum number of rabbits that can find a shelter
Description N rabbits live in the forest. Every evening, before the sunset, the rabbits must hide in holes for the night to avoid danger in the darkness. There are M holes scattered throughout the forest. Each hole has a certain capacity, so a limited number of rabbits can use it as a shelter. Given the conditions before sunset, calculate the maximum number of rabbits that can hide for the night. Assume that every rabbit runs at a constant speed and can cover up to S meters before darkness. In other words, a rabbit can hide in time if the distance between rabbit and hole is less than or equal to S.
Input The first line of input contains three positive numbers N, M, and S: N - number of rabbits M - number of holes S - distance that every rabbit has time to cover before darkness N and M are integers. S is a real number. The next N lines contain two real numbers each: x and y coordinates of each rabbit. The last M lines have three numbers each: x and y coordinates followed by the capacity of each hole. Real numbers have exactly one digit after the decimal point. All numbers are separated with a space character. For example: 3 2 5.0 0.0 6.0 0.0 2.0 8.0 2.0 4.0 4.0 1 10.0 4.0 2
Output A single integer showing the maximum number of rabbits that can hide safely.

Single Destination - Shortest Path
Difficulty: Hard	Test Cases: 10	Published: 2019-11-15
Summary Find the shortest paths to one destination vertex from other vertices in the directed graph
Description Write a program to find the shortest paths in a directed graph to one destination vertex from all other vertices where the destination is reachable. Edges of the graph have no weights and the length of the path is the number of edges between two vertices. If the destination vertex is not reachable from some other vertex, the path between them is equal to infinity. Every vertex in the graph has a unique string name consisting of alphanumeric characters (UTF-8).
Input The first line of input contains the name of the destination vertex. The second line has a list of edges. Every edge is described as a comma-delimited pair of names of adjacent vertices. The edge is directed from the first vertex in the pair to the second. Edges are separated with a semicolon in the list. For example: F A,B;B,C;C,A;D,B;C,D;D,E;E,F;F,B;F,H;G,C;G,E;G,F;G,H See the image of this graph in the attachments tab.
Output Print each possible path on a single line as a vertex name and a positive integer that is the length of the shortest path from this vertex to the destination. Separate the vertex name and path length with a space. If there is no path from the vertex, print INF instead of the integer length. Sort lines in alphabetical order of vertex names and do not include the destination vertex in the output. For example: A 5 B 4 C 3 D 2 E 1 G 1 H INF
Attachments

Skyscrapers
Difficulty: Hard	Test Cases: 10	Published: 2014-03-20
Summary Outline skyscrapers in a city
Description You are to design a program which helps you in drawing the skyline of a city. You are given the locations of the buildings represented by triples (L, H, R) where L and R are left and right coordinates of the building and H is the height of the building. All buildings are rectangular in shape and they are standing on a very flat surface. See the attachments tab for diagrams showing the image representation of buildings and the skyline of the city. On the first diagram the buildings are represented by the following triples: (1,2,3); (2,4,6); (4,5,5); (7,3,11); (9,2,14); (13,7,15); (14,3,17) The drawing line as shown on the second diagram is described by the following sequence: 1 2 2 4 4 5 5 4 6 0 7 3 11 2 13 7 15 3 17 0
Input Your program should read lines from standard input. Each line is one test case. Each test case will contain the list of triples semicolon separated. H is in range (1, 100) max(x-coordinate) <= 10000 number of buildings <= 1000
Output The output must describe the drawing line as a vector where X is an x-coordinate of a point where the line is changing its direction from horizontal to vertical, and H is a height of the vertical line. You're drawing continuously by starting at the bottom of the first left building and finishing at the bottom of the right building. So for each test case print out the drawing line in a way as it is shown below.
Attachments

Spiral Printing
Difficulty: Hard	Test Cases: 4	Published: 2012-10-08
Summary Print out a 2D array in spiral order
Description Write a program to print a 2D array (n x m) in spiral order (clockwise)
Input Your program should read lines of text from standard input. Each line contains three semicolon-delimited items. The first is 'n'(rows), the second is 'm'(columns), and the third is a single space delimited list of characters/numbers in row major order.
Output Print out the matrix in clockwise fashion, one per line, space delimited.

Strassen Matrix Multiplication
Difficulty: Hard	Test Cases: 7	Published: 2019-04-02
Summary Multiply matrices and find components of Strassen Algorithm
Description The Strassen Algorithm is a divide and conquer algorithm that reduces matrix multiplication to a series of operations that use block matrices of a smaller size. Let X, Y be two square matrices of size n x n. We want to calculate their product Z. The first step would be to divide X and Y into equal quadrants of size : Next step is to calculate 7 temporary components: And finally, these 7 components can be combined with additions and subtractions to form the final result Z: Write a program to calculate the components  and matrix product using the Strassen Algorithm.
Input Two lines with space-delimited elements of X and Y matrices in row-major order. All elements are integers. The first line contains X, the second line contains Y. For example: 5 5 2 6 2 6 6 2 1 7 3 9 1 1 8 8 2 8 7 1 4 4 0 1 8 7 0 7 6 1 4 6
Output Write matrix product on the first line and components on the next 7 lines. Elements in each matrix must be space-delimited and in row-major order. For example: 82 80 59 60 88 84 22 62 108 66 43 83 118 76 39 106 15 -55 -10 -42 44 115 32 104 72 96 54 108 36 -30 64 -32 128 260 132 290 -38 -35 -76 -70 28 26 29 34

String List
Difficulty: Hard	Test Cases: 6	Published: 2012-10-08
Summary Create a new string from constituent alphabets
Description Credits: Challenge contributed by Max Demian. You are given a number N and a string S. Find all of the possible ways to write a string of length N from the characters in string S.
Input Your program should read lines of text from standard input. Each line is in the format N,S where N is a positive integer and S is a string.
Output For each line of input, print to standard output a comma separated list of all of the possible ways to write a string of length N from the characters in string S, one list per line.

String Permutations
Difficulty: Hard	Test Cases: 2	Published: 2012-10-08
Summary Print out all permutations of a string.
Description Write a program that finds all the permutations of a string.
Input Your program should read lines of text from standard input.
Output For each line of input, print to standard output all permutations of the string, comma separated, in alphabetical order, one output string per line.

String Searching
Difficulty: Hard	Test Cases: 8	Published: 2012-10-08
Summary Determine if substring match exists.
Description You are given two strings. Determine if the second string is a substring of the first. The second string may contain an asterisk (*) which should be treated as a wild card that matches zero or more characters. The asterisk can be escaped by a \ char in which case it should be interpreted as a literal * character. The strings can contain English letters and numbers, *, and \.
Input Your program should read lines of text from standard input. Each line will contain two strings separated by a comma.
Output For each line of input, if the second string is a substring of the first, print "true" (lowercase). Otherwise print "false" (lowercase), one per line.

String Substitution
Difficulty: Hard	Test Cases: 2	Published: 2012-10-08
Summary Create a new string by replacing substrings within it
Description Credits: This challenge was contributed by Sam McCoy Given a string S, and a list of strings of positive length, F1,R1,F2,R2,...,FN,RN, proceed to find in order the occurrences (left-to-right) of Fi in S and replace them with Ri. All strings are over alphabet { 0, 1 }. Searching should consider only contiguous pieces of S that have not been subject to replacements on prior iterations. An iteration of the algorithm should not write over any previous replacement by the algorithm.
Input Your program should read lines of text from standard input. Each line will contain a string, then a semicolon, and then a list of comma separated strings.
Output For each line of input, print out the string after substitutions have been made. Here are the transitions for the above example: 10011011001 => 10100111001 [replacing 0110 with 1001] => 10100110 [replacing 1001 with 0] => 11100110 [replacing 10 with 11] => 11100110

Strongly Connected Components
Difficulty: Hard	Test Cases: 12	Published: 2020-11-19
Summary Find strongly connected components of a directed graph
Description In graph theory, a directed graph is called strongly connected if there is a path in both directions between any two vertices within it. The strongly connected component (SCC) of the directed graph is its subgraph that is strongly connected, and is maximal with this property: no additional edges or vertices from the original graph can be included in the subgraph without breaking its property of being strongly connected. In other words, the SCC is a subgraph of maximum size such that for any pair of its vertices u and v there is a path from u to v and also a path from v to u. Write a program that finds the strongly connected components of a directed graph with N vertices. Vertices are indexed with continuous integer numbers from 0 to ( N - 1). See the attachments tab for an example of the graph with marked SCCs.
Input The first line contains a positive integer N, the number of vertices in the graph. Each additional line describes one edge of the graph with two space-delimited integer indices. The edge is directed from the vertex with the first index to the vertex with the second index. For example: 6 2 4 4 3 5 4 1 0 3 2 0 5 1 2 5 1
Output Print strongly connected components of the given graph, one component per line. Every strongly connected component should be described as a space-delimited list of vertex indices it consists of. Indices in the list must be sorted in ascending order. The lines must also be printed in ascending order. The first line describes the component that starts with vertex 0, next line describes the component that starts with the next higher index, and so on. For example: 0 1 5 2 3 4
Attachments

Strongly Connected Components - Simple
Difficulty: Hard	Test Cases: 12	Published: 2020-11-19
Summary Find strongly connected components of the directed graph
Description In graph theory, a directed graph is called strongly connected if there is a path in both directions between any two vertices within it. The strongly connected component (SCC) of the directed graph is its subgraph that is strongly connected, and is maximal with this property: no additional edges or vertices from the original graph can be included in the subgraph without breaking its property of being strongly connected. In other words, the SCC is a subgraph of maximum size such that for any pair of its vertices u and v there is a path from u to v and also a path from v to u. Write a program that finds the strongly connected components of a directed graph with N vertices. Vertices are indexed with continuous integer numbers from 0 to (N - 1) . One of the possible methods to find SCCs of the graph G is a Kosaraju's algorithm. There are three steps in it: Build a Grev graph inverting the arcs of the original graph G. Run dfs_loop on the graph Grev remembering search finishing order f(v) for every vertex. Loop iterates over unexplored nodes in the graph from (N - 1) to 0 Run dfs_loop on the original graph G processing vertices in decreasing order of values f(v). dfs_loop is a loop that starts a depth-first search (DFS) from unexplored vertices of the graph. The difference between steps 2 and 3 is only in the order of the vertex processing and some bookkeeping. The second step tracks finishing order and the third step tracks the source node index for every DFS call (the index of the node from which the DFS starts). Every call to the DFS in the third step explores nodes of one SCC and dfs_loop discovers all SCCs of the graph one by one. The pseudocode of the dfs_loop and dfs functions can be represented like so: dfs_loop(graph G)     finish_counter = 0     dfs_source = 0     for not explored node u in graph         dfs_source = u         dfs(graph, u) dfs(graph G, node u)     mark u as explored     set SCC index of the node u = dfs_source     for each not explored node v reachable from u         dfs(graph, v)     finish_counter++     set f(u) = finish_counter Let's look at how to apply the Kosaraju's algorithm to find SCCs of the graph from the attachments tab. The first step, as described earlier, is to construct a reversed graph. The dfs_loop of the second step triggers an initial DFS from node 5 and that DFS explores reachable nodes 0 and 1 in the reversed graph. The second iteration of dfs_loop starts the DFS from node 4 (unexplored node with the highest index) and explores nodes 2 and 3. The order in which the DFS finishes the nodes exploration in step 2 of the algorithm is {1, 0, 5, 3, 2, 4}. The third step starts DFS from node 4, which is the last processed node in the previous step. This DFS run discovers nodes 3 and 2, they form the first SCC {4, 3, 2}. Then dfs_loop proceeds with DFS starting from node 5, and explores nodes 1 and 0. So the second discovered SCC is {5, 1, 0}.
Input The first line contains a positive integer N, the number of vertices in the graph. Each additional line describes one edge of the graph with two space-delimited integer indices. The edge is directed from the vertex with the first index to the vertex with the second index. For example: 6 2 4 4 3 5 4 1 0 3 2 0 5 1 2 5 1
Output Print out strongly connected components of the given graph, one component per line. Every strongly connected component should be described as a space-delimited list of vertex indices it consists of. Indices in the list must be sorted in ascending order. The lines must also be printed in ascending order. The first line describes the component that starts with vertex 0, next line describes the component that starts with the next higher index, and so on. For example: 0 1 5 2 3 4
Attachments

Symmetry of a Binary Tree
Difficulty: Hard	Test Cases: 12	Published: 2019-11-15
Summary Check whether a binary tree is symmetric
Description Write a program to check whether a binary tree is symmetric or not. A tree is symmetric if its data and shape remain unchanged when it is reflected around the root node. Consider two examples below. The following tree is symmetric:     __7__    /          5       5  / \     /    4   9   9   4 The following tree is not symmetric:     6    /      3   3  /   / 8   8
Input A string containing the pre-order traversal of the binary tree to be inspected. The nodes are traversed in the following order: Node Left subtree Right subtree. Any absent child (NULL pointer) of a given node is marked with a # character in the traversal. The input string is a space-delimited mix of integers and # characters. There will be no trailing # characters in the string, it will always end with the value of the last node in the tree traversal. Tree nodes will contain integer values only. The first example above, which is symmetric, would be described as: 7 5 4 # # 9 # # 5 9 # # 4
Output Print True if the binary tree is symmetric. Otherwise, print False.

Telephone Words
Difficulty: Hard	Test Cases: 4	Published: 2012-10-08
Summary Print out the words corresponding to a telephone number
Description Given a 7 digit telephone number, print out all the possible sequences of letters that can represent the given telephone number. Note that in a standard phone keypad 0 and 1 do not have any letters associated with them. All 0's and 1's in the telephone number should be retained in the sequence of letters. You may use the following mapping between numbers and characters 0=>0, 1=>1, 2=>abc, 3=>def, 4=>ghi, 5=>jkl, 6=>mno, 7=>pqrs, 8=>tuv, 9=>wxyz
Input Your program should read lines from standard input. Each line contains a 7 digit telephone number.
Output Print to standard output the words that can produce the telephone number, alphabetically sorted and comma delimited.

Text Dollar
Difficulty: Hard	Test Cases: 9	Published: 2012-10-08
Summary Print out the text dollar amount of a given quantity
Description Credits: This challenge has been authored by Terence Rudkin You are given a positive integer number. This represents the sales made that day in your department store. The payables department however, needs this printed out in English. NOTE: The correct spelling of 40 is Forty. (NOT Fourty)
Input Your program should read lines of text from standard input. Each line contains a positive integer.
Output For each set of input print a single line to standard output which is the english textual representation of that integer. The output should be unspaced and in CamelCased. Always assume plural quantities. You can also assume that the numbers are < 1000000000 (1 billion). In case of ambiguities eg. 2200 could be TwoThousandTwoHundredDollars or TwentyTwoHundredDollars, always choose the representation with the larger base i.e. TwoThousandTwoHundredDollars.

Text to Number
Difficulty: Hard	Test Cases: 10	Published: 2014-03-20
Summary Convert English text representation of a number to a decimal number
Description You have a string which contains a number represented as English text. Your task is to translate these numbers into their integer representation. The numbers can range from -999,999,999 to 999,999,999. The following is an exhaustive list of English words that your program must account for: negative, zero, one, two, three, four, five, six, seven, eight, nine, ten, eleven, twelve, thirteen, fourteen, fifteen, sixteen, seventeen, eighteen, nineteen, twenty, thirty, forty, fifty, sixty, seventy, eighty, ninety, hundred, thousand, million
Input Your program should read lines from standard input. Each line contains an English of a number. Negative numbers will be preceded by the word, "negative". The word "hundred" is not used when "thousand" could be. E.g. 1500 is written "one thousand five hundred", not "fifteen hundred".
Output Print the decimal representation of the number.

Transport Network - Minimum Cut
Difficulty: Hard	Test Cases: 7	Published: 2019-10-04
Summary Find a minimum cut of the graph representing the transport network
Description In a strategy game, a player's base has a transportation network, which is used for interactions between all the base facilities. While the player is constructing and developing their base, their opponent is planning an attack. The first step in this attack is to determine the weakest link between the facilities of the base. Then, attack the weak spot to cut the base into two pieces. Write a program to find the most vulnerable part of the transportation network. The number of roads connecting these two pieces must be the minimum possible. The transport network consists of nodes representing buildings and roads that connect nodes. Every building has an integer index from 0 to n assigned to it.
Input Each line of input describes the connections of a single building with others in the network using a space-delimited list of integer indices. The first element of the list is the index of the current building, and all other elements are the indices of the buildings that are directly connected by roads with the current building. For example: 0 1 5 1 0 2 5 2 1 3 4 3 2 4 4 2 3 5 0 1 The first row means that the building with index 0 is connected to buildings 1 and 5. The second row describes that there are roads from building 1 to buildings 0, 2, and 5. See the attachments tab for a diagram of this example
Output Write out two space-delimited, sorted lists representing the complete result of the network cut. The first line lists the nodes of the network containing the node with index 0. The second line describes the other side of the split. For example: 0 1 5 2 3 4
Attachments

Type Ahead
Difficulty: Hard	Test Cases: 4	Published: 2012-10-08
Summary Building a type ahead feature
Description Your task is to build a type-ahead feature for an upcoming product. When the user enters a word or set of words, we want to be able to "predict" what they're going to type next with some level of accuracy. We've chosen to implement this using the N-Gram algorithm defined here http://en.wikipedia.org/wiki/N-gram. Your program should return a tuple of predictions sorted high to low based on the prediction score (up to a maximum of three decimal places, or pad with zeroes up to three decimal places i.e. 0.2 should be shown as 0.200), (if predictions share the same score, they are sorted alphabetically.) Words should be split by whitespace with all non-alphanumeric characters stripped off the beginning and end. Prediction scores are calculated like this: Occurrences of a word after an N-gram / total number of words after an N-gram e.g. for an N-gram of length 2: ONE TWO ONE TWO THREE TWO THREE "TWO" has the following predictions: THREE:0.666,ONE:0.333 "THREE" occurred 2 times after a "TWO" and "ONE" occurred 1 time after a "TWO", for a total of 3 occurrences after a "TWO". Your program will run against the following text. You may hardcode it into your program: Mary had a little lamb its fleece was white as snow; And everywhere that Mary went, the lamb was sure to go. It followed her to school one day, which was against the rule; It made the children laugh and play, to see a lamb at school. And so the teacher turned it out, but still it lingered near, And waited patiently about till Mary did appear. "Why does the lamb love Mary so?" the eager children cry;"Why, Mary loves the lamb, you know" the teacher did reply."
Input Your program should read lines of text from standard input. Each line contains a number followed by a string, separated by a comma. The number is the n-gram length. The string is the text from the user. You will be predicting the text following this string.
Output For each line of input print a single line to standard output which is the predictions for what the user is going to type next.

Ugly Numbers
Difficulty: Hard	Test Cases: 11	Published: 2012-10-08
Summary Count the number of expressions that can be created from a number
Description Credits: This challenge has appeared in a google competition. Once upon a time in a strange situation, people called a number ugly if it was divisible by any of the one-digit primes (2, 3, 5 or 7). Thus, 14 is ugly, but 13 is fine. 39 is ugly, but 121 is not. Note that 0 is ugly. Also note that negative numbers can also be ugly; -14 and -39 are examples of such numbers. One day on your free time, you are gazing at a string of digits, something like: 123456 You are amused by how many possibilities there are if you are allowed to insert plus or minus signs between the digits. For example you can make: 1 + 234 - 5 + 6 = 236 which is ugly. Or 123 + 4 - 56 = 71 which is not ugly. It is easy to count the number of different ways you can play with the digits: Between each two adjacent digits you may choose put a plus sign, a minus sign, or nothing. Therefore, if you start with D digits there are 3^(D-1) expressions you can make. Note that it is fine to have leading zeros for a number. If the string is '01023', then '01023', '0+1-02+3' and '01-023' are legal expressions. Your task is simple: Among the 3^(D-1) expressions, count how many of them evaluate to an ugly number.
Input Your program should read lines of text from standard input. Each line will consist of a non-empty string containing only the characters '0' through '9'. Each string is no more than 13 characters long.
Output For each input string, print to standard output the number of expressions that evaluate to an ugly number, one number per line.

Word Search
Difficulty: Hard	Test Cases: 10	Published: 2014-03-20
Summary Find if a word exists in a grid
Description Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are those directly neighboring either horizontally or vertically. The same letter cell may not be used more than once. The board to be used may be hard coded as: A B C E S F C S A D E E
Input Your program should read lines from standard input. Each line contains a word.
Output Print out True if the word exists in the board, False otherwise.