USACO 1.3.3 Calf Flac

Calf Flac

It is said that if you give an infinite number of cows an infinite number of heavy-duty laptops (with very large keys), that they will ultimately produce all the world’s great palindromes. Your job will be to detect these bovine beauties.

Ignore punctuation, whitespace, numbers, and case when testing for palindromes, but keep these extra characters around so that you can print them out as the answer; just consider the letters `A-Z’ and `a-z’.

Find the largest palindrome in a string no more than 20,000 characters long. The largest palindrome is guaranteed to be at most 2,000 characters long before whitespace and punctuation are removed.

PROGRAM NAME: calfflac

INPUT FORMAT

A file with no more than 20,000 characters. The file has one or more lines. No line is longer than 80 characters (not counting the newline at the end).

SAMPLE INPUT (file calfflac.in)

Confucius say: Madam, I'm Adam.

OUTPUT FORMAT

The first line of the output should be the length of the longest palindrome found. The next line or lines should be the actual text of the palindrome (without any surrounding white space or punctuation but with all other characters) printed on a line (or more than one line if newlines are included in the palindromic text). If there are multiple palindromes of longest length, output the one that appears first.

SAMPLE OUTPUT (file calfflac.out)

11
Madam, I'm Adam

SOLUTION

This problem was a real pain and very difficult for me… First of all, I thought the palindromes were to be found on each line but they were actually supposed to be found throughout the entire input.  After I resolved that, I found that the algorithm I was using was too slow.  After getting frustrated and trashing my initial program, I searched online for a better algorithm…

You create two strings of the input, one is the raw input and one has only the letters.  You walk through each character of the string with letters treating each letter as the centre of a palindrome.  You expand from the centre checking if the left side is equal to the right side.  The longest match between right and left side is the longest palindrome with a center at that point.

There are two kinds of palindromes:  even length and odd length.  We have to check both types.

I decided to write this in c++, even though I’m not very familiar with the language, because it runs faster than Java.

Here is the code in c++

/*
ID: frigid.1
PROG: calfflac
LANG: C++
*/

#include <iostream>
#include <fstream>
#include <string>

   using namespace std;

   char s[20000], ss[20000];
	int slen, sslen;
	int maxp, maxq, maxl = 0;
	
	int findpal (int p, int q) {
		int i, j;
		while (ss[p] == ss[q] && p >= 0 && q < sslen) {
			i = p;
			j = q;
			p--;
			q++;
		}
		if (j - i + 1 > maxl)
		{
			maxp = i;
			maxq = j;
			maxl = j - i + 1;
		}
	}
	
   int main() {
   
      ofstream fout ("calfflac.out");
      ifstream fin ("calfflac.in");
	 	char c;
      slen = 0;
		sslen = 0;
    	
      while (fin.get(c)) {
			s[slen] = c;
			slen++;
			if (isalpha(c)) {
				ss[sslen] = tolower(c);
				sslen++;
			}
		}
		
		for (int i = 1; i < sslen; i++) {
			//odd palindrome
			findpal (i - 1, i + 1);
			//even palindrome
			findpal (i - 1, i);
		}
		
		string output = "";
		int alpha = -1;
		
		for (int i = 0; i < slen && maxq >= alpha + 1; i++) {
			if (isalpha (s[i]))
				alpha++;
			if (maxp <= alpha && maxq >= alpha)
				output += s[i];
		}
		
		fout << maxl << endl;
		fout << output << endl;
   
      return 0;
   
   }

USACO 1.3.2 Barn Repair

It was a dark and stormy night that ripped the roof and gates off the stalls that hold Farmer John’s cows. Happily, many of the cows were on vacation, so the barn was not completely full.

The cows spend the night in stalls that are arranged adjacent to each other in a long line. Some stalls have cows in them; some do not. All stalls are the same width.

Farmer John must quickly erect new boards in front of the stalls, since the doors were lost. His new lumber supplier will supply him boards of any length he wishes, but the supplier can only deliver a small number of total boards. Farmer John wishes to minimize the total length of the boards he must purchase.

Given M (1 <= M <= 50), the maximum number of boards that can be purchased; S (1 <= S <= 200), the total number of stalls; C (1 <= C <= S) the number of cows in the stalls, and the C occupied stall numbers (1 <= stall_number <= S), calculate the minimum number of stalls that must be blocked in order to block all the stalls that have cows in them.

Print your answer as the total number of stalls blocked.

PROGRAM NAME: barn1

INPUT FORMAT

Line 1: M, S, and C (space separated)
Lines 2-C+1: Each line contains one integer, the number of an occupied stall.

SAMPLE INPUT (file barn1.in)

4 50 18
3
4
6
8
14
15
16
17
21
25
26
27
30
31
40
41
42
43

OUTPUT FORMAT

A single line with one integer that represents the total number of stalls blocked.

SAMPLE OUTPUT (file barn1.out)

25

SOLUTION

This is my algorithm for this problem…

  1. Sort stall numbers
  2. Find gaps between stalls
  3. Sort gaps
  4. Assume that each consecutive stall with cows is covered by a board
  5. Cover the gaps one by one (starting from the smallest) by merging boards
  6. Do this until the number of boards is equal to the maximum number of boards that can be purchased

Explanation

We first imagine that each consecutive stall with cows is covered by a board.  This means that every stall is covered, and since no stalls without cows are covered, this is the minimum number of covered stalls that must be blocked.  This may be the minimum number but it uses too many boards.  In order to reduce the number of boards used, we merge the boards between the smallest gaps.  If we do it between the smallest gaps, it means that the least number of stalls are covered in merging the boards.  Each time two boards are merged, our number of boards used reduces by one.  We continuously do this until the number of boards we are using is equal to M (the maximum boards we can purchase).

This algorithm is greedy because we are using the minimum number of covered stalls for N boards to find the minimum number of covered stalls for N – 1 boards.

Here is my implementation in Java (I’m sorry it’s not very transferrable into other languages because of the use of ArrayList but it’s all I could come up with)…

/*
ID: frigid.1
LANG: JAVA
TASK: barn1
*/

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

   class Gap implements Comparable<Gap> {
      int start, end;

      Gap (int s, int e) {
         start = s;
         end = e;
      }

      public int compareTo (Gap o) {
         return getSize() - o.getSize();
      }

      public int getSize () {
         return end - start - 1;
      }

   } //Gap class

   public class barn1 {

      public static void main (String [] args) throws IOException {

         BufferedReader f = new BufferedReader(new FileReader("barn1.in"));
         PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("barn1.out")));

         StringTokenizer st = new StringTokenizer (f.readLine());
         Gap g;

         int m = Integer.parseInt (st.nextToken());
         int s = Integer.parseInt (st.nextToken());
         int c = Integer.parseInt (st.nextToken());
         int boards, stallsCovered = c;

         int [] stalls = new int [c];
         ArrayList<Gap> gaps = new ArrayList<Gap>();

         for (int i = 0; i < c; i++)
            stalls[i] = Integer.parseInt (f.readLine());

			//sort stalls

         Arrays.sort (stalls);

			//determine gaps

         for (int i = 1; i < c; i++) {
            if (stalls[i] - stalls[i - 1] > 1) {
               gaps.add (new Gap (stalls[i - 1], stalls[i]));
            }
         }

			//sort gaps

         Collections.sort (gaps);

			//number of boards needed is # of gaps + 1

         boards = gaps.size() + 1;

         while (boards > m) {
				//remove smallest gap
            g = gaps.remove(0);
				//add its size to stallsCovered
            stallsCovered += g.getSize();
				//remove a board
            boards--;
         }

         out.println (stallsCovered);

         out.close();
         System.exit(0);
      } //main method
   } //barn1 class

USACO 1.3.1 Mixing Milk

I’ve been doing the USACO Training Program (a programming contest training program) lately so I have decided to share some solutions on this blog for anyone having trouble (I know I had a lot of trouble solving these problems…).  This problem is called Mixing Milk, it’s the first question from section 3.

——

Since milk packaging is such a low margin business, it is important to keep the price of the raw product (milk) as low as possible. Help Merry Milk Makers get the milk they need in the cheapest possible manner.

The Merry Milk Makers company has several farmers from which they may buy milk, and each one has a (potentially) different price at which they sell to the milk packing plant. Moreover, as a cow can only produce so much milk a day, the farmers only have so much milk to sell per day. Each day, Merry Milk Makers can purchase an integral amount of milk from each farmer, less than or equal to the farmer’s limit.

Given the Merry Milk Makers’ daily requirement of milk, along with the cost per gallon and amount of available milk for each farmer, calculate the minimum amount of money that it takes to fulfill the Merry Milk Makers’ requirements.

Note: The total milk produced per day by the farmers will be sufficient to meet the demands of the Merry Milk Makers.

PROGRAM NAME: milk

INPUT FORMAT

Line 1: Two integers, N and M.
The first value, N, (0 <= N <= 2,000,000) is the amount of milk that Merry Milk Makers’ want per day. The second, M, (0 <= M <= 5,000) is the number of farmers that they may buy from.
Lines 2 through M+1: The next M lines each contain two integers, Pi and Ai.
Pi (0 <= Pi <= 1,000) is price in cents that farmer i charges.
Ai (0 <= Ai <= 2,000,000) is the amount of milk that farmer i can sell to Merry Milk Makers per day.

SAMPLE INPUT (file milk.in)

100 5
5 20
9 40
3 10
8 80
6 30

OUTPUT FORMAT

A single line with a single integer that is the minimum price that Merry Milk Makers can get their milk at for one day.

SAMPLE OUTPUT (file milk.out)

630

SOLUTION

This is one algorithm to solve this problem:

  1. Sort the farmers by cost
  2. Buy from the farmers (starting from the lowest cost) until the amount of milk wanted is reached.

This algorithm works because when you buy from the lowest cost available, the milk you’re buying is of the best value.  As long as you’re always buying milk of the best value, the amount of money you spend is minimal.

/*
ID: frigid.1
LANG: JAVA
TASK: milk
*/

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

   class Farmer implements Comparable {

      int cost, milk;

      public Farmer (int c, int m) {
         cost = c;
         milk = m;
      }

      public int compareTo (Farmer o) {
         return cost - o.cost;
      }

   } //Farmer class

   public class milk {

      public static void main (String[] args) throws IOException {
         BufferedReader f = new BufferedReader (new FileReader ("milk.in"));
         PrintWriter out = new PrintWriter (new BufferedWriter (new FileWriter ("milk.out")));

         int minPrice = 0;

         StringTokenizer st = new StringTokenizer (f.readLine());

         int milkWanted = Integer.parseInt (st.nextToken());
         int n = Integer.parseInt (st.nextToken());
         Farmer[] farmers = new Farmer[n];

         for (int i = 0; i < n; i++) {
            st = new StringTokenizer (f.readLine());
            farmers[i] = new Farmer (Integer.parseInt (st.nextToken()), Integer.parseInt (st.nextToken()));
         }

      //sort farmers

         Arrays.sort(farmers);

      //buy from farmers (starting from lowest cost) until goal is reached

         for (int i = 0; i < n && milkWanted > 0; i++) {
            if (milkWanted >= farmers[i].milk) {
               minPrice += farmers[i].cost * farmers[i].milk;
               milkWanted -= farmers[i].milk;
            }
            else {
               minPrice += farmers[i].cost * milkWanted;
               milkWanted = 0;
            }
         }

         out.println(minPrice);

         out.close();

      } //main method

   } //milk class

This problem can also be done without using a Farmer object. Instead of having a list of Farmer objects, you can make an integer array of size 1001 where each index is a price and add the amount of milk to each index. The sorting algorithm used here is called Counting Sort. Here is the above program modified in this way…

/*
ID: frigid.1
LANG: JAVA
TASK: milk
*/

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

   public class milk {

      public static void main (String[] args) throws IOException {
         BufferedReader f = new BufferedReader (new FileReader ("milk.in"));
         PrintWriter out = new PrintWriter (new BufferedWriter (new FileWriter ("milk.out")));

         int minPrice = 0;

         StringTokenizer st = new StringTokenizer (f.readLine());

         int milkWanted = Integer.parseInt (st.nextToken());
         int n = Integer.parseInt (st.nextToken());
         int[] farmers = new int [1001];

         for (int i = 0; i < n; i++) {
            st = new StringTokenizer (f.readLine());
            farmers[Integer.parseInt (st.nextToken())] += Integer.parseInt (st.nextToken());
         }

      //buy from farmers (starting from lowest cost) until goal is reached

         for (int i = 0; i < 1001 && milkWanted > 0; i++) {
            if (milkWanted >= farmers[i]) {
               minPrice += i * farmers[i];
               milkWanted -= farmers[i];
            }
            else {
               minPrice += i * milkWanted;
               milkWanted = 0;
            }
         }

         out.println(minPrice);

         out.close();

      } //main method

   } //milk class