Google Code Jam 2008 EMEA: Разбор задачи Painting a Fence

Здравствуйте, уважаемые.

Зашел сегодня посмотреть, как там соревнования Гугла проходят, заодно попрактиковаться на прошедших соревнованиях. Условия задачи Scaled Triangle я так и не понял, поэтому взялся за вторую задачу Painting a Fence. Порадовало то, что мозг шевелится, есть идеи. Решение сразу встало перед глазами -
первое) надо построить ориентированный нецикличный граф ^_^ + зачем-то мне взбрело в голову, добавить в граф вершину начала и вершину конца (это поможет мне совсем забыть о диапазонах, буду работать только с графом), переформулировав задачу, найти минимальное число вершин чтобы дойти от вершины начала до вершины конца.
второе) поиск в глубину должен учитывать количество цветов на каждой ветке: при переходе на следующий уровень - добавлять цвет, при возврате - убавлять.

2 несложных пункта средствами Java реализовать крайне легко:

import java.io.FileNotFoundException;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class PaintingFence {

 private String[] colors;

 private boolean[][] g;

 private int N;
 // Удобная штука Map в ней ключ - имя цвета, значение - количество художников, использующих этот цвет
 private Map<String, Integer> colorMap = new HashMap<String, Integer>();

 public int getMinimumPainters(String[] colors, int[] start, int[] finish) {
  this.colors = colors;
  N = colors.length;
  // мы создаем матрицу достижимости (ориентированный граф) и добавляем в нее 2 узла - начало и конец
  g = new boolean[N + 2][N + 2];
  /*
   * попарно проверяем возможность перехода
   * критерий один - если из отрезка i можно увеличить сплошной отрезок с помощью отрезка j,
   * то считаем, что из узла i можно перейти в узел j
   */
  for (int i = 0; i < N; i++) {
   for (int j = 0; j < N; j++)
    g[i][j] = finish[j] > finish[i] && start[j] <= finish[i] + 1;
   // проверяем, можно ли войти в этот узел, другими словами, предлагает ли художник рисовать с начала полотна
   g[N][i] = start[i] == 1;
   // проверяем, может ли художник закончить полотно
   // далее точка N + 1 будет означать, что мы смогли полностью закрасить полотно
   g[i][N + 1] = finish[i] == 10000;
  }
  int res = Integer.MAX_VALUE;
  for (int i = 0; i < N; i++)
   // начинаем с точек входа, которые мы определили на прошлом шаге
   if (g[N][i]) {
    // резервируем цвет
    colorMap.put(colors[i], 1);
    res = Math.min(doIt(i), res);
    colorMap.clear();
   }
  return res == Integer.MAX_VALUE ? -1 : res;
 }

 private int doIt(int c) {
  // если художник может завершить полотно, то нам достаточно его одного
  if (g[c][N + 1]) return 1;
  int res = Integer.MAX_VALUE;
  for (int i = 0; i < N; i++) {
   if (g[c][i]) {
    String currentColor = colors[i];
    // если количество цветов, задействованных не превышает 3, или цвет рассматриваемого художника уже используется
    if (colorMap.size() < 3 || colorMap.containsKey(currentColor)) {
     // учитываем цвет, которым рисует художник
     if (colorMap.containsKey(currentColor))
      colorMap.put(currentColor, colorMap.get(currentColor) + 1);
     else
      colorMap.put(currentColor, 1);
     // продвигаемся вглубь
     int cur = doIt(i);
     // если решение найдено
     if (cur != Integer.MAX_VALUE)
      res = Math.min(res, cur + 1);
     // цвет, которым рисует художник учесть учли, теперь еще раз учитываем, только в обратную сторону
     colorMap.put(colors[i], colorMap.get(currentColor) - 1);
     // если цвет больше никем не используется, то удаляем его из списка
     if (colorMap.get(currentColor) == 0)
      colorMap.remove(currentColor);
    }
   }
  }
  // возвращаем минимальное число художников, которые могут нарисовать полотно
  return res;
 }

 public static void main(String[] args) throws FileNotFoundException {
  Scanner sc = new Scanner(System.in);
  int N = sc.nextInt();
  for (int i = 1; i <= N; i++) {
   int n = sc.nextInt();
   String[] colors = new String[n];
   int[] start = new int[n];
   int[] finish = new int[n];
   sc.nextLine();
   for (int j = 0; j < n; j++) {
    String[]t = sc.nextLine().split(" ");
    colors[j] = t[0];
    start[j] = Integer.valueOf(t[1]);
    finish[j] = Integer.valueOf(t[2]);
   }
   int res = new PaintingFence().getMinimumPainters(colors, start, finish);
   System.out.println("Case #" + i + ": " + (res == -1? "IMPOSSIBLE" : String.valueOf(res)));
  }
 }
}