Tuesday, January 22, 2013

Codeforces


Problem Example 1: Palindrome Pairs



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 = s1s2... s|s| is a string sisi + 1... sj. 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



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 ci and size si. 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 ≤ 105) — 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 ci and si (1 ≤ ci, si ≤ 109) — 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;
 }
}