Swap Permutation

You are given an array A = [1, 2, 3, ..., n]: 1.How many sequences (S1) can you get after exact k adjacent swaps on A? 2.How many sequences (S2) can you get after at most k swaps on A? An adjacent swap can be made between two elements of the Array A, A[i] and A[i+1] or A[i] and A[i-1]. A swap otherwise can be between any two elements of the array A[i] and A[j] ∀ 1 ≤ i, j ≤ N, i ≠ j. Input Format First and only line contains n and k separated by space. Constraints 1 ≤ n ≤ 25

View Solution →

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 →