All Subsets

The following Python program generates all ordered subsets of a list. This method is very useful in brute-force approach of solving a problem

def generateSubsets(A, n, sub=[]):
    if n == 0:
        print(sub)
        return
    generateSubsets(A, n-1, sub)
    generateSubsets(A, n-1, [A[n-1]] + sub)

A = list(map(int, input().split()))
generateSubsets(A, len(A))

Input:
1 2 3 4

Output:
[]
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]
[4]
[1, 4]
[2, 4]
[1, 2, 4]
[3, 4]
[1, 3, 4]
[2, 3, 4]
[1, 2, 3, 4]

Sorted List to Complete Binary Tree

The following Python program creates a balanced Binary Tree from a given sorted list Θ(length of sorted list)

class SortedBST:
    class Node:
        def __init__(self, val):
            self.value = val
            self.left = None
            self.right = None
   
    def __init__(self, nos):
        self.nos = nos
        self.root = None
        self.root = self.initBST(self.root, 0, len(nos) - 1)
  
    def initBST(self, node, low, high):
        mid = (low + high) >> 1
        node = self.Node(self.nos[mid])
        if low < mid:
            node.left = self.initBST(node.left, low, mid-1)
        if high > mid:
            node.right = self.initBST(node.right, mid+1, high)
        return node
  
    def BFS(self):
        from collections import deque
        q = deque()
        q.append(self.root)
        while(q):
            qv = q.popleft()
        print(qv.value)
        if qv.left != None:
            q.append(qv.left)
        if qv.right != None:
            q.append(qv.right)
 
sortedList = sorted(list(map(int, input().split())))
sortedBst = SortedBST(sortedList)
sortedBst.BFS()

Round A APAC Test 2014

Cut Tiles

Problem

Enzo is doing renovation for his new house. The most difficult part is to buy exactly the right number of tiles. He wants N tiles of different sizes. Of course they have to be cut from the tiles he bought. All the required tiles are square. The lengths of side of the tiles are 2^S₁, 2^S₂, ..., 2^S_N. He can only buy a lot of tiles sized M*M, and he decides to only cut tiles parallel to their sides for convenience. How many tiles does he need to buy?

Input

The first line of the input gives the number of test cases: T. T lines follow. Each line start with the number N and M, indicating the number of required tiles and the size of the big tiles Enzo can buy. N numbers follow: S₁, S₂, ... S_N, showing the sizes of the required tiles.

Output

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the number of the big tiles Enzo need to buy.

The solution for the problem is written in Java

import java.io.File;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class CutTiles {   
    Scanner in;
    int T, N, M;
    Integer[] S;
 
    int solve() {
        byte limit = (byte) Math.floor(Math.log(M)/Math.log(2));
        int tiles = 1, newN = 0;
        double eaten = 0; 
  
        N = in.nextInt();
        M = in.nextInt();
        S = new Integer[N];
        for (int i=0; i<N; i++) {
            S[i] = in.nextInt();
            assert S[i] <= limit;
        }
        Arrays.sort(S, new Comparator<Integer>() {
            public int compare(Integer a, Integer b) {
                return b-a;
            }
        });
  
        for (int i=0; i<N; i++) {
            long powS = (long) Math.pow(2, S[i]);
            long sqs = (M / powS) * (M / powS);
            if (sqs - eaten/powS/powS < 1) {
                if (newN == 0)
                    tiles++;
                S[newN++] = S[i];
            }
            else 
                eaten += powS * powS;
   
            if (i == N-1 && newN > 0) {
                N = newN;
                eaten = newN = 0;
                i = -1;
            }
        }
        return tiles;
    }
    void input() {
        in = new Scanner(System.in);
        T = in.nextInt();
        for (int test=1; test<=T; test++) {
            System.out.print("Case #"+test+": ");
            System.out.println(solve());
        }
    }
 
    public static void main(String[] args) {
        new CutTiles().input();
    }
}

The complexity of the program is O(no. of tiles required * N)

Largest Span

GATE 2006 : Given two arrays of numbers a₁,...,a_n and b₁,...b_n where each number is 0 or 1, the fastest algorithm to find the largest span(i, j) such that
a_i+a_i+1+ ... + a_j = b_i + b_i+1 + ... + b_j 

#include <stdio.h>
#include <malloc.h>
void printArray(int *a, int start, int end)
{
    while(start++ <= end)
        printf("%d ", a[start-1]);
    printf("\n");
}
void changeStartEnd(int *a, int *b, int *start, int *end, int *sum, int *next1)
{//O(1)
    if(b[*start]==1 && a[*start]==0)
        ++*start;
    else if(b[*end]==1 && a[*end]==0)
        --*end;
    else if(b[*start]==a[*start])
        ++*start;
    else if(b[*end]==a[*end])
        --*end;
    else if(next1[sum[*end-1]] > next1[sum[*start]])
        --*end;
    else
        ++*start;
}
void largestSpan(int *a, int *b, int n)
{
    int    *sumA = malloc(n*sizeof(int));
    int    *sumB = malloc(n*sizeof(int));
    int  *next1A = malloc(n*sizeof(int));
    int  *next1B = malloc(n*sizeof(int));
    int *onePtrA = malloc(n*sizeof(int));
    int *onePtrB = malloc(n*sizeof(int));
    int i, j, k, start=1, end=n-1, diffA, diffB;
    sumA[0]=0; sumB[0]=0;
  
    for (i=1, k=1, j=1; i<n ;i++)
    {
        sumA[i]=sumA[i-1]+a[i];
        sumB[i]=sumB[i-1]+b[i];
        if(a[i]==1)
            onePtrA[k++]=i;
        if(b[i]==1)
            onePtrB[j++]=i;
    } //O(n)
    for(i=1; i<k-1; i++)//O(n)
        next1A[i]=sumB[onePtrA[i+1]-1]-sumB[onePtrA[i]];
    for(i=1; i<j-1; i++)//O(n)
        next1B[i]=sumA[onePtrB[i+1]-1]-sumA[onePtrB[i]];
  
    for(i=1; i<n; i++)
    {
        diffA=sumA[end]-sumA[start-1];
        diffB=sumB[end]-sumB[start-1];
        if(diffA == diffB)
            break;
        if (diffB > diffA)
            changeStartEnd(a, b, &start, &end, sumA, next1A);//O(1)
        else
            changeStartEnd(b, a, &start, &end, sumB, next1B);//O(1)
    }//O(n)
    printf("%d, %d\n", start, end);
    printArray(a, start, end);
    printArray(b, start, end);
}
void main()
{
    int b[14]={0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1}; // One based indexing
    int a[14]={0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0}; // One based indexing
    largestSpan(a, b, 14);
}

Hence it takes ϴ(n) time and space