Monday 8 December 2014

Bytelandian gold coins

In Byteland they have a very strange monetary system.

Each Bytelandian gold coin has an integer number written on it. A coin n can be exchanged in a bank into three coins: n/2, n/3 and n/4. But these numbers are all rounded down (the banks have to make a profit).

You can also sell Bytelandian coins for American dollars. The exchange rate is 1:1. But you can not buy Bytelandian coins.

You have one gold coin. What is the maximum amount of American dollars you can get for it?

Input

The input will contain several test cases (not more than 10). Each testcase is a single line with a number n, 0 <= n <= 1 000 000 000. It is the number written on your coin.

Output

For each test case output a single line, containing the maximum amount of American dollars you can make.

Recursion ::

// n < 12 : We may get n or less than n when we do exchange.. so dont exchange when n<12

// 5 : 2+1+1 = 4, 6 : 3+2+1=6

//n >= 12 Similarly : We may get more than n or n when we do exchange.. so do exhange whenever n>=12

//Memoize intermediate results using a map.

package SPOJ;/**
 * Created by seesunda on 12/9/2014.
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
// n < 12 : We may get n or less than n when we do exchange.. so dont exchange when n<12
// 5 : 2+1+1 = 4, 6 : 3+2+1=6

//n >= 12 Similarly : We may get more than n or n when we do exchange.. so do exhange whenever n>=12

//Memoize intermediate results using a map.
class coins {

    static HashMap<Long,Long> map = new HashMap<Long, Long>();

    public static void main(String[] args) throws IOException {
        BufferedReader inp = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        String s = "";
        while((s=inp.readLine())!=null) {
            long n = Long.parseLong(s);
            out.println(getMax(n));
        }
        out.flush();
    }

    public static long getMax(long n) {
        if(n < 12)
            return n;

        if(map.containsKey(n))
            return map.get(n);

        long chg = getMax(n/2) + getMax(n/3) + getMax(n/4);
        map.put(n,chg);

        return chg;
    }
}

Friday 5 December 2014

Disjoint-Set Data Structure UNION-FIND

A disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:

Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.

Union: Join two subsets into a single subset.

Union-Find Algorithm can be used to check whether an undirected graph contains cycle or not. Note that we have discussed an algorithm to detect cycle. This is another method based on Union-Find. This method assumes that graph doesn’t contain any self-loops.

We can keeps track of the subsets in a 1D array, lets call it parent[].

Applications:

Detect Cycle in a an Undirected Graph

Minium Spanning Tree - Kruskals

The implementation of union() and find() is naive and takes O(n) time in worst case.
These methods can be improved to O(Logn) using Union by Rank or Height - Next post.

Union-Find in O(n) :

package g4g.Graph;/**
 * Created by seesunda on 12/6/2014.
 */

import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.InputStream;

class UFinN {

    int V;
    int E;
    Edge[] edges;

    UFinN(int v, int e) {
        this.V = v;
        this.E = e;
        this.edges = new Edge[e];
        for(int i=0;i<e;i++)
            edges[i] = new Edge();
    }


    class Edge {
        int src;
        int dest;
    }

    public static void main(String[] args) {
        UFinN u = new UFinN(3,3);

        // add edge 0-1
        u.edges[0].src = 0;
        u.edges[0].dest = 1;

        // add edge 1-2
        u.edges[1].src = 1;
        u.edges[1].dest = 2;

        // add edge 0-2
        u.edges[2].src = 0;
        u.edges[2].dest = 2;

        if(hasCycle(u))
            System.out.println("Detected Cycle");
        else
            System.out.println("No Cycle");

    }


    public static boolean hasCycle(UFinN u) {
        int[] parent = new int[u.V];
        Arrays.fill(parent, -1);

        for(int i=0;i<u.E;i++) {
            int x = find(parent,u.edges[i].src);
            int y = find(parent,u.edges[i].dest);
            //Belongs to same set

            if(x == y) {
                return true;
            }
            union(parent,x,y);

        }
        return false;
    }

    public static int find(int[] parent,int vertex) {
        while(parent[vertex] != -1)
            vertex = parent[vertex];
        return vertex;
    }

    public static void union(int[] parent,int x,int y) {
        int xset = find(parent,x);
        int yset = find(parent,y);
        parent[xset] = yset;
    }
}