Friday, 22 June 2018

Dynamic programming applied on the Ant Stack problem from Google Jam Code 2018

You are probably overviewing a problem that are is polynomial non-deterministic and you heard that it is possible to solve a subset of its instances by using pseudo-polynomial technique. Yes, this technique is dynamic programming and how you get to master this technique is a matter of pure intuition.

I will try exemplify what I mean by providing a sample problem from the Google Code Jam 2018, Round 1C 2018, Written by Pablo Heiber and pprepared by Kevin Tran.


The problem description:

Scott has an ant farm containing N ants. Each ant has a certain length and weight.
Today, as a challenge for the ants, Scott has placed some food at the top of the ant farm. The ants will try to reach it by arranging themselves into a vertical stack, with each ant in the stack directly holding the next on its back. In this way, each ant bears the weight of all ants above it. Scott's ants are very strong for their size and are able to carry up to 6 times their own weight. For example, an ant that weights 8 milligrams can carry two other ants weighing 24 milligrams each! Each ant also has a body length; the exact lengths are not important, except that they are all different.
  • The stack must be linear. Each ant except for the top ant must be directly below exactly one ant, and each ant except for the bottom ant must be directly above exactly one ant.
  • The lengths of the ants in the stack must be strictly decreasing from the bottom to the top of the stack; this ensures that each new ant that joins the stack will be able to climb up to the top.
  • For each ant, the sum of the weights of all the ants above it in the stack must be no more than 6 times the weight of that ant.

What is the maximum number of these ants that can form such a stack?

Input

The first line of the input gives the number of test cases, TT test cases follow. Each begins with one line with an integer N: the number of ants in the colony. Then, a second line follows containing N integers W1,W2, ..., WN, where Wi is the weight in milligrams of the i-th ant. The ants are listed in strictly increasing order of length. Notice that no actual length values are given; only the order is important.

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 maximum number of the given ants that can form a stack that obeys the rules above.

Limits

7 ≤ T ≤ 100.
Time limit: 15 seconds per test set.
Memory limit: 1GB.

Test set 1 (Visible)

For exactly 6 cases, N = 100; for the other T - 6 cases, 2 ≤ N ≤ 50.
1 ≤ Wi ≤ 1000, for all i.

Test set 2 (Hidden)

For exactly 6 cases, N = 105; for the other T - 6 cases, 2 ≤ N ≤ 500.
1 ≤ Wi ≤ 109, for all i.

So how did I solve it?

First, let's recall the pipe of steps involved in building a dynamic programming solution, namely:

  1. Recursion
  2. Memoization
  3. Bottom-up


Recursion

This problem reminds us of the knapsack 0-1 problem whose dynamic programming solution is laid out as a decision tree. Similarily we try to establish a decision tree for this problem. At each node encoded as state [n,w] , we need to establish the appropiate weight and the value of the node which will represent the maximum number of ants up to this node.

We start with the maximal supported weight among all ants. For each child node, we apply the following logic :

pseudocode:       

we compare the current ant weight to the current supported weight 

If we cannot support the current ant

        then we go one ant downwards

else

        we calculate a potential new weight as  min(6 * ants[i - 1], supported weight - ants[i - 1]);

        node [i][w] = max(1 + node[i - 1][new weight], node[i - 1][supported weight]);

end else



We have n levels in our decision tree with 3 nodes children on each node. The complexity of this algorithm goes to 3n  time units. Under a large n this algorithm will not finish, hence we need to find another way to span our state space.











Here is the solution:

import java.io.*;
import java.util.*;

/** 
 Copyright belongs to Dub Andrei-Manuel. 
 Please refer this author to any reference 

**/

public class Solution {

    static boolean logTime = false;

    public static Map getLadder() {
        Map map = new HashMap();
        long top = (long) Math.pow(10, 9);
        long load = 0;
        long weight = 1;
        int ants = 1;
        while (weight < top) {
            if (load <= (6 * weight)) {
                load += weight;
                map.put(ants, weight);
                    System.out.println(ants+" : "+
                            weight);
                ants++;
            } else {
                weight++;
            }
        }
        return map;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int t = in.nextInt();
        for (int i = 1; i <= t; ++i) {

            int antsNr = in.nextInt();
            long[] ants = new long[antsNr];

            for (int j = 0; j < antsNr; j++) {
                int weight = in.nextInt();
                ants[j] = weight;
            }


            long start = System.currentTimeMillis();

            int maxAnts2 = solutionDP2(ants);

            long end = System.currentTimeMillis();

            System.out.println("Case #" + i + ": " + maxAnts2);

            if (logTime)
                System.out.println(end - start);

        }
    }


    public static long getMaxWeight(long[] ants) {
        long max = 0l;
        for (long weight : ants) {
            if (weight > max)
                max = weight;
        }
        return max;
    }


    public static int solutionDP2(long[] ants) {
        int max = searchDP2(ants, ants.length);
        return max;
    }

    public static int solutionDP(long[] ants) {
        long capacity = getMaxWeight(ants) * 7;
        int max = searchDP(ants, ants.length, capacity);
        return max;
    }




    public static int searchDP2(long[] ants, int n) {
        int max = 0;

        int k = 139;
        long[][] g = new long[n + 1][k + 1];

        for (int x = 0; x <= n; x++) {
            for (int y = 0; y <= k; y++) {
                if (y > x) {
                    g[x][y] = Long.MAX_VALUE;
                } else if (x == 0 || y == 0) {
                    g[x][y] = 0;
                } else if (x == 1 && y == 1) {
                    g[x][y] = ants[x - 1];
                } else {

                    if (g[x - 1][y - 1] > 6 * ants[x - 1]) {
                        g[x][y] = g[x - 1][y];
                    } else {
                        g[x][y] = Math.min(g[x - 1][y - 1] + ants[x - 1], g[x - 1][y]);
                    }

                }

            }


        }



        for (int y = 0; y <= k; y++) {
            if (y > max && g[n][y] < Long.MAX_VALUE) {
                max = y;
            }
        }

        return max;
    }


    public static int searchDP(long[] ants, int n, long availableCapacity) {

        int[][] K = new int[n + 1][((int) availableCapacity) + 1];

        for (int i = 0; i <= n; i++) {
            for (int w = 0; w <= availableCapacity; w++) {
                if (i == 0 || w == 0) {
                    K[i][w] = 0;
                } else {

                    long potentialCapacity = Math.min(6 * ants[i - 1], w - ants[i - 1]);

                    if (ants[i - 1] > w)
                        K[i][w] = K[i - 1][w];
                    else                        
                       K[i][w] = Math.max(1 + K[i - 1][(int) potentialCapacity], K[i - 1][w]);

                }

            }


        }

        return K[n][(int) availableCapacity];
    }




}




Monday, 18 June 2018

If you are getting Invalid UTF-8 middle/second byte or other parsing errors within your JVM, just know


that  :

"The default charset is determined during virtual-machine startup and typically depends upon the locale and charset being used by the underlying operating system."

This is an official excerpt from  :



Other sources that just relate to how to determine or set it up:



Now, how do you know what character set is your JVM defaulting to?

In debug, try to execute the following command:

java.nio.charset.Charset.defaultCharset()

You will get one of the charset listed here (most popular being  iso-8859-1):


To make sure you have a broad encoding character set, solve this issue by overriding your system charset by starting the jvm with this option:


-Dfile.encoding=UTF-8


Familiar exceptions :

       


com.fasterxml.jackson.core.JsonParseException:



com.ctc.wstx.exc.WstxIOException: Invalid UTF-8 middle byte 0x... 

About Me

My Photo