import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Vector;


public class VerifyLowerBound {
   // Maximum number of jobs that should be considered
   private static int howFar=100;

   /* The idea is to keep the leaves in the tree (the partial candidates) which 
      must be considered (have not been pruned yet) in a linked list called candidates.
    */

   public static void main(String[] args) {
      int count = 0; 
      int[] opt = calculateOpt(); 
      int[] suggested = {0,2,5,9,13,18,23,29,35,41,48,54,61,68,76,84,91,100,108,117,
                         126,135,145,156,167,179,192,206,221,238,257,278,302,329,361,
                         397,439,488,545,612,690,781,888,1013,1159,1329,1528,1760,2000};
      LinkedList<PartialCandidate> candidates = new LinkedList<PartialCandidate>();
      PartialCandidate pC;

      // Start with the tree that results after considering just 1 job
      candidates.add(new PartialCandidate());

      /* While there are candidates remaining, remove the first. If it has reached the
         maximum number of jobs that should be considered, print out the solution and 
         add one to the count. If the candidate  has not reached the maximum number of 
         jobs, check whether 
         1) has a cost ratio strictly smaller than 619/583    AND
         2) it does not have a just as good candidate already in the list.
         If both are true, then add both of its children to the list of candidates.
       */

      while (candidates.size() !=0) {
         pC = candidates.remove();
         if (pC.getHowFar() > howFar) {
            count++;
            System.out.println(pC);
         }
         else if (583*pC.evalCost() < 619*opt[pC.getHowFar()]) {
            if(!existJustAsGood(pC,candidates)) {
               candidates.add(new PartialCandidate(pC,false));
               candidates.add(new PartialCandidate(pC,true));
            }
         }
      }
      System.out.print(count + " candidates achieve a cost ratio strictly smaller");
      System.out.println("than 619/583 on all sequences no longer than " + howFar);

      // Verify that the suggested candidate succeeds up to 2000 jobs
      boolean success = true;
      int value = 0, j=0;
      for (int i=1; i<2000; i++) {
         value += (i-suggested[j]-1)+i+j+1;
         if (i==suggested[j+1])
            j++;
         if (583*value > 638*opt[i])
            success = false;
      }
      System.out.println("The suggested candidate is a success up to 2000 jobs? " + success);
   }

   // Uses Lemma 1 / Theorem 4 to calculate the offline optimum costs
   private static int[] calculateOpt() {
      int n, m=0, howMany=2001;
      int[] answer = new int[howMany];
      answer[0] = 0;
      for (n=0;n<howMany-1;n++) {
         if (2*n<(m+2)*(m+1))
            answer[n+1]=answer[n]+n+m+2;
         else {
            m++;
            answer[n+1]=answer[n]+n+m+2;
         }
      }
      return answer;
   }

   /* Checks to see if the list already has a candidate which has gotten as far,
      has no greater cost, uses no more set ups, and has the most recent set up 
      at the same location, 
    */
   private static boolean existJustAsGood(PartialCandidate pC, LinkedList<PartialCandidate> ll) {
      PartialCandidate jAGC;
      ListIterator<PartialCandidate> i = ll.listIterator(0);
      while (i.hasNext()) {
         jAGC = i.next();
         if (
             jAGC.getHowFar() == pC.getHowFar() &&
             jAGC.evalCost() <= pC.evalCost() &&
             jAGC.getSetUps().size() <= pC.getSetUps().size() &&
             jAGC.getSetUps().lastElement().equals(pC.getSetUps().lastElement())
            )
            return true;
      }
      return false;
   }
}


/* An algorithm for the unit job batching problem can be specified by
   where the set up times occur (or equivalently where it batches). A 
   partial candidate is an incompletely specified algorithm. A partial 
   candidate has a list (stored in setUps) which specifies where the 
   set up times occur only for sequences of up to a certain length (ie
   the depth in the tree - stored in howFar).  
 */


class PartialCandidate {

   private Vector<Integer> setUps;
   private int howFar;

   // Create the only reasonable candidate for the sequence of 1 job.
   public PartialCandidate() {
      setUps = new Vector<Integer>();
      setUps.add(0);
      howFar = 1;
   }

   /* Given a partial candidate create a new partial candidate which
      is defined for sequences one job longer. Determine whether to
      add an additional set up at this point based upon the value of
      batch.
    */
   public PartialCandidate(PartialCandidate pC, boolean batch) {
      Vector<Integer> prevSetUps = pC.getSetUps();
      int prevHowFar = pC.getHowFar();

      setUps = new Vector<Integer>();
      for (int i=0; i<prevSetUps.size(); i++) {
         setUps.add(prevSetUps.get(i));
      }
      if (batch)
         setUps.add(prevHowFar);

      howFar = prevHowFar+1;
   }

   // Calculate cost of the partial candidate on a sequence of howFar jobs.
   public int evalCost() {
      int value=0;
      for (int i=1; i<setUps.size(); i++) 
         value += (i+setUps.get(i))*(setUps.get(i)-setUps.get(i-1));
      value += (setUps.size()+howFar)*(howFar-setUps.get(setUps.size()-1));
      return value;
   }

   // Used to print out the partial candidate
   public String toString() {
      String str="";
      for (int i=0; i<setUps.size(); i++)
         str += setUps.get(i)+" ";
      str += "Cost "+evalCost();
      return str;
   }

   // Accessors
   public Vector<Integer> getSetUps() {
      return setUps;
   }

   public int getHowFar() {
      return howFar;
   }

}