Codeforces

Problem Example 1: Palindrome Pairs

http://codeforces.com/problemset/problem/159/D

time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Problem

You are given a non-empty string s consisting of lowercase letters. Find the number of pairs of non-overlapping palindromic substrings of this string.

In a more formal way, you have to find the quantity of tuples (a, b, x, y) such that 1 ≤ a ≤ b < x ≤ y ≤ |s| and substrings s[a... b], s[x...y] are palindromes.

A palindrome is a string that can be read the same way from left to right and from right to left. For example, "abacaba", "z", "abba" are palindromes.

A substring s[i... j] (1 ≤ i ≤ j ≤ |s|) of string s = s₁s₂... s_|s| is a string s_is_i + 1... s_j. For example, substring s[2...4] of string s = "abacaba" equals "bac".

Input

The first line of input contains a non-empty string s which consists of lowercase letters ('a'...'z'), s contains at most 2000 characters.

Output

Output a single number — the quantity of pairs of non-overlapping palindromic substrings of s.

My Solution

import java.util.*;


public class D {
 
 public static void main(String args[]) {
  Scanner in = new Scanner(System.in);
  String s = in.next();
  long[] i = new long[s.length()], j  = new long[s.length()];
  ArrayList<LinkedList<Integer>> I = new ArrayList<LinkedList<Integer>>(s.length());
  for (int a = 0; a < s.length(); a++) {
   I.add(new LinkedList<Integer>());
   //odd case
   for (int x = 0; a - x >= 0 && a + x < s.length() && s.charAt(a+x) == s.charAt(a-x); x++) { 
    i[a - x]++;
    j[a + x]++;
    I.get(a - x).add(a + x);
   }
   //even case
   for (int x = 1; a - x + 1 >= 0 && a + x < s.length() && s.charAt(a+x) == s.charAt(a-x + 1); x++) {
    i[a - x + 1]++;
    j[a + x]++;
    I.get(a - x + 1).add(a + x);
   }
  }
  long sum = 0;
  for (int x = i.length-1; x >=0; x--)
   i[x] = (sum += i[x]);
  
  sum = 0;
  for (int x = 0; x < j.length; x++)
   j[x] = (sum += j[x]);
  
  long total = 0;
  for (LinkedList<Integer> list : I) {
   for (Integer J : list) {
    if (list.getFirst() > 0)
     total += j[list.getFirst() - 1];
    if (J < i.length - 1)
     total += i[J + 1];
   }
  }
  
  total /= 2;
  System.out.println(total);
  
  
 }

}

Problem Example 2: Zebra Tower

http://codeforces.com/problemset/problem/159/E

time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Problem

Little Janet likes playing with cubes. Actually, she likes to play with anything whatsoever, cubes or tesseracts, as long as they are multicolored. Each cube is described by two parameters — color c_i and size s_i. A Zebra Tower is a tower that consists of cubes of exactly two colors. Besides, the colors of the cubes in the tower must alternate (colors of adjacent cubes must differ). The Zebra Tower should have at least two cubes. There are no other limitations. The figure to the left shows an example of a Zebra Tower.

A Zebra Tower's height is the sum of sizes of all cubes that form the tower. Help little Janet build the Zebra Tower of the maximum possible height, using the available cubes.

Input

The first line contains an integer n (2 ≤ n ≤ 10⁵) — the number of cubes. Next n lines contain the descriptions of the cubes, one description per line. A cube description consists of two space-separated integers c_i and s_i (1 ≤ c_i, s_i ≤ 10⁹) — the i-th cube's color and size, correspondingly. It is guaranteed that there are at least two cubes of different colors.

Output

Print the description of the Zebra Tower of the maximum height in the following form. In the first line print the tower's height, in the second line print the number of cubes that form the tower, and in the third line print the space-separated indices of cubes in the order in which they follow in the tower from the bottom to the top. Assume that the cubes are numbered from 1 to n in the order in which they were given in the input.

If there are several existing Zebra Towers with maximum heights, it is allowed to print any of them.

My Solution

import java.util.*;

public class E {
 public static void main(String args[]) {
  Scanner in = new Scanner(System.in);
  int index = 1;
  HashMap<Integer, LinkedList<Cube>> data = new HashMap<Integer, LinkedList<Cube>>(200000);
  int n = in.nextInt();
  
  int inC, inS, numcolors = 0;
  
  for (int i = 0; i < n; i++) {
   inC = in.nextInt();
   inS = in.nextInt();
   if (!data.containsKey(inC)) {
    data.put(inC, new LinkedList<Cube>());
    numcolors++;
   }
   data.get(inC).add(new Cube(inC, inS, index));
   index++;
  }
  
  ArrayList<Cube> best1 = new ArrayList<Cube>();
  ArrayList<Cube> best2 = new ArrayList<Cube>();
  
  for (Integer color : data.keySet()) {
   LinkedList<Cube> list = data.get(color);
   Collections.sort(list);
   Collections.reverse(list);
   long sum = 0;
   int pos = 0;
   for (Cube cube : list) {
    cube.curpos = pos;
    sum += cube.s;
    cube.curheight = sum;
    if (best1.size() <= pos)
     best1.add(new Cube(-1, 0, 0));
    if (best2.size() <= pos)
     best2.add(new Cube(-1, 0, 0));
    if (best1.get(pos).curheight <= sum) {
     best2.set(pos, best1.get(pos));
     best1.set(pos, cube);
    } else if (best2.get(pos).curheight <= sum)
     best2.set(pos, cube);
    
    pos++;
   }
   
  }
  Cube besta = new Cube(-1, 0, 0), bestb = new Cube(-1, 0, 0);
  
  for (int i = 0; i < best1.size(); i++) {
   //odd case
   if (i > 0) {
    if (best1.get(i).curheight + best1.get(i-1).curheight > besta.curheight + bestb.curheight && best1.get(i).c != best1.get(i-1).c) {
     besta = best1.get(i);
     bestb = best1.get(i-1);
    } if (best1.get(i).curheight + best2.get(i-1).curheight > besta.curheight + bestb.curheight && best1.get(i).c != best2.get(i-1).c && best2.get(i-1).c > 0) {
     besta = best1.get(i);
     bestb = best2.get(i-1);
    } if (best2.get(i).curheight + best1.get(i-1).curheight > besta.curheight + bestb.curheight && best2.get(i).c != best1.get(i-1).c && best2.get(i).c > 0) {
     besta = best2.get(i);
     bestb = best1.get(i-1);
    }
   }
   
   //even case
   if (best1.get(i).curheight + best2.get(i).curheight > besta.curheight + bestb.curheight && best2.get(i).c > 0) {
    besta = best1.get(i);
    bestb = best2.get(i);
   }
  }
    
  System.out.println(besta.curheight + bestb.curheight);
  System.out.println(besta.curpos + bestb.curpos + 2);

  LinkedList<Cube> lista = data.get(besta.c);
  LinkedList<Cube> listb = data.get(bestb.c);
  
  while (lista.peekLast() != besta)
   lista.removeLast();
  while (listb.peekLast() != bestb)
   listb.removeLast();
   
  while (!lista.isEmpty() && !listb.isEmpty())
   System.out.print(lista.removeFirst().index + " " + listb.removeFirst().index + " ");
  
  if (!lista.isEmpty() && besta == lista.getFirst())
   System.out.print(lista.removeFirst().index);
  
  System.out.print("\n");
  
 }

}

class Cube implements Comparable<Cube> {
 public int c;
 public long s;
 public int index;
 public long curheight;
 public long curpos;
 
 Cube(int color, int size, int indexer) {
  c = color;
  s = size;
  index = indexer;
  curheight = curpos = 0;
 }
 
 public int compareTo (Cube other) {
  if (s < other.s)
   return -1;
  if (s > other.s)
   return 1;
  return 0;
 }
}

AP Computer Science Final Project

I designed and wrote a multifunction cryptography tool for a final project in AP Computer Science last spring. Even though it wouldn't be suitable for actual encryption, because it uses a homemade algorithm, it was an interesting programming and thinking experiment. It has a stream cipher and a steganography module. Unlike most of the other code on this page, it wasn't for a competition, so it is properly commented.

Since the code is long, I hosted it on an external site: http://pastebin.com/At0vd63q

USA Computing Olympiad

Example Problem 1: Islands

http://www.usaco.org/index.php?page=viewproblem2&cpid=132

Whenever it rains, Farmer John's field always ends up flooding. However, since the field isn't perfectly level, it fills up with water in a non-uniform fashion, leaving a number of "islands" separated by expanses of water. FJ's field is described as a one-dimensional landscape specified by N (1 <= N <= 100,000) consecutive height values H(1)...H(n). Assuming that the landscape is surrounded by tall fences of effectively infinite height, consider what happens during a rainstorm: the lowest regions are covered by water first, giving a number of disjoint "islands", which eventually will all be covered up as the water continues to rise. The instant the water level become equal to the height of a piece of land, that piece of land is considered to be underwater. An example is shown above: on the left, we have added just over 1 unit of water, which leaves 4 islands (the maximum we will ever see). Later on, after adding a total of 7 units of water, we reach the figure on the right with only two islands exposed. Please compute the maximum number of islands we will ever see at a single point in time during the storm, as the water rises all the way to the point where the entire field is underwater. PROBLEM NAME: islands INPUT FORMAT: * Line 1: The integer N. * Lines 2..1+N: Line i+1 contains the height H(i). (1 <= H(i) <= 1,000,000,000) SAMPLE INPUT (file islands.in): 8 3 5 2 3 1 4 2 3 INPUT DETAILS: The sample input matches the figure above. OUTPUT FORMAT: * Line 1: A single integer giving the maximum number of islands that appear at any one point in time over the course of the rainstorm. SAMPLE OUTPUT (file islands.out): 4

My Solution:

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

public class Islands {

 public static void main(String[] args) throws IOException {
  Scanner in = new Scanner(new File("islands.in"));
  //Scanner in = new Scanner(System.in);
  int N = in.nextInt();
  Integer[][] A = new Integer[2*N][2];
  
  int ha = 0, hb;
  for (int i = 0; i < N; i++) {
   hb = in.nextInt();
   A[2 * i][0] = ha;
   A[2*i+1][0] = hb;
   if (hb > ha) {
    A[2 * i][1] = 1;
    A[2*i+1][1] = -1;
   } else {
    A[2 * i][1] = 0;
    A[2*i+1][1] = 0;
   }
   ha = hb;
  }
        Arrays.sort(A, new Comparator<Integer[]>() {
            @Override
            public int compare(final Integer[] entry1, final Integer[] entry2) {
                return entry1[0].compareTo(entry2[0]);
            }
        });

  int current = 0, max = 0;
  for (int i = 0; i < 2 * N; i++) {
   current += A[i][1];
   if (current > max)
    max = current;
  }

  PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(new File("islands.out"))));
  out.println(max);
  out.close();
 }

}




Example Problem 2: Clumsy Cows

http://www.usaco.org/index.php?page=viewproblem2&cpid=190

Bessie the cow is trying to type a balanced string of parentheses into her new laptop, but she is sufficiently clumsy (due to her large hooves) that she keeps mis-typing characters. Please help her by computing the minimum number of characters in the string that one must reverse (e.g., changing a left parenthesis to a right parenthesis, or vice versa) so that the string would become balanced. There are several ways to define what it means for a string of parentheses to be "balanced". Perhaps the simplest definition is that there must be the same total number of ('s and )'s, and for any prefix of the string, there must be at least as many ('s as )'s. For example, the following strings are all balanced: () (()) ()(()()) while these are not: )( ())( ((()))) PROBLEM NAME: clumsy INPUT FORMAT: * Line 1: A string of parentheses of even length at most 100,000 characters. SAMPLE INPUT (file clumsy.in): ())( OUTPUT FORMAT: * Line 1: A single integer giving the minimum number of parentheses that must be toggled to convert the string into a balanced string. SAMPLE OUTPUT (file clumsy.out): 2 OUTPUT DETAILS: The last parenthesis must be toggled, and so must one of the two middle right parentheses.

My Solution:

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

public class Clumsy {

 public static void main(String[] args) throws Exception {
  Scanner in = new Scanner(new File("clumsy.in"));
  //Scanner in = new Scanner(System.in);
  String S = in.next();
  int R = 0, L = 0, C = 0;
  for (int i =0; i < S.length(); i++) {
   if (S.charAt(i) == '(')
    R++;
   else if (R > L)
    L++;
   else {
    R++;
    C++;
   }
  }
  C += (R - L) /2;
  //System.out.print(C);

  PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(new File("clumsy.out"))));
  out.println(C);
  out.close();
 }

}