Code Sprint - 2 , Algorithmic Problems

This post is for all the self proclaimed geeks who love resolving complex algorithmic problems. Below are the questions  from  code sprint 2 an online coding contest. Time to overclock your brains. Happy coding.

The Living History

Coin toss

You have an unbiased coin which you want to keep tossing until you get N consecutive heads. You've tossed the coin M times and surprisingly, all tosses resulted in heads. What is the expected number of additional tosses needed until you get N consecutive heads? Input: The first line contains the number of cases T. Each of the next T lines contains two numbers N and M. Output: Output T lines containing the answer for the corresponding test case. Print the answer rounded to exactly 2 decimal places. Sample Input : 4 2 0 2 1 3 3 3 2 

Sample Output : 6.00 4.00 0.00 8.00

Permutation

This is an approximation solution type problem. Please read about this type of problem at the bottom before attempting. Given n, print a permutation(p) of (0,1,2...n-1) From the permutation p, you can create n-1 (x,y) coordinates, where x and y are consecutive pairs in the permutation. You are also given the n x n square matrix V. For each coordinate, you can find an associated value in the matrix V. (x and y are 0-indexed) 

Task : Given n and V, find the permutation p that maximizes the sum of the associated values of the consecutive pair coordinates Constraints: n <= 50 Input: First line contains n Next n lines contains n integers, forming the matrix V 

Output : Space separated permutation of (0,1,2....n-1)

Polygon

There are N points on X-Y plane with integer coordinates (x i , y i ). You are given a set of polygons with all of its edges parallel to the axes (in other words, all angles of the polygons are 90 degree angles and all lines are in the cardinal directions. There are no diagonals). For each polygon your program should find the number of points lying inside it (A point located on the border of polygon is also considered to be inside the polygon). Input: First line two integers N and Q. Next line contains N space separated integer coordinates (x i ,y i ). Q queries follow. Each query consists of a single integer M i in the first line, followed by M i space separated integer coordinates (x[i][j],y[i][j]) specifying the boundary of the query polygon in clock-wise order. Polygon is an alternating sequence of vertical line segments and horizontal line segments.

Polygon has M i edges, where (x[i][j],y[i][j]) is connected to (x[i][(j+1)%M i ], y[i][(j+1)%M i ].

For each 0 <= j < M i , either x[i][(j+1)%M i ] == x[i][j] or y[i][(j+1)%M i ] == y[i][j] but not both.

It is also guaranteed that the polygon is not self-intersecting.

Output : For each query output the number of points inside the query polygon in a separate line.

Sub-sequence Weighting
A sub-sequence of a sequence is a sequence which is obtained by deleting zero or more elements from the sequence. You are given a sequence A in which every element is a pair of integers i.e A = [ (a 1 , w 1 ) , (a 2 , w 2 ) ,...,(a N , w N )]. For a sub-sequence B = [ (b 1 , v 1 ) , (b 2 , v 2 ) , .... ,(b M , v M ) ] of the given sequence : We call it increasing if for every i ( 1 <= i < M ) , b i < b i+1 .

Weight(B) = v1 + v2 + ... + vM .

Task : Given a sequence, output the maximum weight formed by an increasing sub-sequence 

Input : First line of input contains a single integer C. C test-cases follow. First line of each test-case contains an integer N. Next line contains a 1 , ... , a N separated by a single space. Next line contains w 1 , ... , w N separated by a single space. 

Output : For each test-case output a single integer number: Maximum weight of increasing subsequences of the given sequence.

Crab Graphs
A crab is an undirected graph which has two kinds of vertices: 1 head, and K feet , and exactly K edges which join the head to each of the legs.( 1 <= K <= T, where T is given) Given an undirected graph, you have to find in it some vertex-disjoint sub-graphs each one of which is a crab . The goal is to select those crabs in such a way that the total number of vertices covered by them is maximized. Note: two graphs are vertex-disjoint if they do not have any vertex in common. 

Input : First line of input contains a single integer C. C test-cases follow. First line of each test-case contains three integers N, T, and M (the number of nodes, max number of feet in the crab graph, and number of edges, respectively). Each of next M lines contains two space separated v 1i , v 2i meaning that the there is an edge between vertexes v 1i and v 2i . Note that the graph doesn't have parallel edges or loops. 

Output : For each test-case, output a single integer indicating the maximum number vertices which can be covered by some vertex disjoint sub-graphs of graph which are crabs

Picking Cards

There are N cards on the table and each has a number between 0 and N. Let us denote the number on the ith card by c i . You want to pick up all the cards. The ith card can be picked up only if at least c i cards have been picked up before it. (As an example, if a card has a value of 3 on it, you can't pick that card up unless you've already picked up 3 cards previously) In how many ways can all the cards be picked up? Input: The first line contains the number of test cases T. T test cases follow. Each case contains an integer N on the first line, followed by integers c i ,...,c N on the second line. Output: Output T lines one corresponding to each test case containing the required answer for the corresponding test case. As the answers can be very big, output them modulo 1000000007. 

Count strings
A regular expression is used to describe a set of strings. For this problem the alphabet is limited to 'a' and 'b'.

We define R to be a valid regular expression if: 1) R is "a" or "b" 2) R is of the form "(R1R2)" where R1 and R2 are regular expressions 3) R is of the form "(R1|R2)" where R1 and R2 are regular expressions 4) R is of the form "(R1*)" where R1 is a regular expression.

Regular expressions can be nested, and will always have two elements in the parenthesis. ('*' is an element, '|' is not; basically, there will always be pairwise evaluation) Additionally, '*' will always be the second element; '(*a)' is invalid.

The set of strings recognised by R are as follows: 1) If R is "a", then the set of strings recognised = {a} 2) If R is "b", then the set of strings recognised = {b} 3) if R is of the form "(R1R2)" then the set of strings recognised = all strings which can be obtained by a concatenation of strings s1 and s2 where s1 is recognised by R1 and s2 by R2. 4) if R is of the form "(R1|R2)" then the set of strings recognised = union of the set of strings recognised by R1 and R2. 5) If R is of the form "(R1*)" then the the strings recognised are the empty string and the concatenation of an arbitrary number of copies of any string recognised by R1.

Task : Given a regular expression and an integer L, count how many strings of length L are recognized by it. Input: The first line contains the number of test cases T. T test cases follow. Each test case contains a regular expression R and an integer L. Output: Output T lines one corresponding to each test case containing the required answer for the corresponding test case. As the answers can be very big, output them modulo 1000000007.