Extremum Permutations
Let's consider a permutation P = {p1, p2, ..., pN} of the set of N = {1, 2, 3, ..., N} elements . P is called a magic set if it satisfies both of the following constraints: Given a set of K integers, the elements in positions a1, a2, ..., aK are less than their adjacent elements, i.e., pai-1 > pai < pai+1 Given a set of L integers, elements in positions b1, b2, ..., bL are greater than their adjacent elements, i.e., pbi-1 < pbi > pbi+1 How many such magic sets are there? Input Format
View Solution →Square Subsequences
Square Subsequences A string is called a square string if it can be obtained by concatenating two copies of the same string. For example, "abab", "aa" are square strings, while "aaa", "abba" are not. Given a string, how many (non-empty) subsequences of the string are square strings? A subsequence of a string can be obtained by deleting zero or more characters from it, and maintaining the relative order of the remaining characters. Input Format The first line contains the number of test
View Solution →Dorsey Thief
Mr. Dorsey Dawson recently stole X grams of gold from ACME Jewellers. He is now on a train back home. To avoid getting caught by the police, he has to convert all the gold he has into paper money. He turns into a salesman and starts selling the gold in the train. There are N passengers who have shown interest in buying the gold. The ith passenger agrees to buy ai grams of gold by paying vi dollars. Dawson wants to escape from the police and also maximize the profit. Can you help him maximize
View Solution →Mining
There are n gold mines along a river, and each mine i produces wi tons of gold. In order to collect the mined gold, we want to redistribute and consolidate it amongst exactly k mines where it can be picked up by trucks. We do this according to the following rules: You can move gold between any pair of mines (i.e., i and j, where 1 <= i <j <= n). All the gold at some pickup mine i must either stay at mine i or be completely moved to some other mine, j. Move w tons of gold between the mine at
View Solution →Police Operation
Roy is helping the police department of his city in crime fighting. Today, they informed him about a new planned operation. Think of the city as a 2D plane. The road along the X-axis is very crime prone, because n criminals live there. No two criminals live at the same position. To catch these criminals, the police department has to recruit some police officers and give each of them USD h as wages. A police officer can start his operation from any point a, drive his car to point b in a str
View Solution →