Trzy słowa o zadaniu 1 z I kolokwium z ASD 2009/2010.
=====================================================

Zadanie wymagało użycia programowania dynamicznego, w rozwiązaniach
powtarzały się dwa sposoby w czasie O(n^3):
1. Wypełniam tablicę T[k, i, j]: 3 <= k <= 2*n-1, i < j; T[k, i, j]
  to najtańszy sposób dojścia dwoma nieprzecinającymi się ścieżkami,
  z których obie zaczynają się w polu (1,1), jedna kończy w polu
  (i, k-i), a druga w (j, k-j) (intuicyjnie, idziemy takimi
  "przekątnymi": po k-1 krokach ścieżka jest na polu (a,b) takim, 
  że a+b=k). Tablicę tę wypełniamy w kolejności rosnących k.
2. Wypełniamy tablicę T[k, i, j]: 1 <= k <= n, 1 <= i < j <=k;
  T[k, i, j] To najtańszy sposób dojścia dwoma nieprzecinającymi się
  ścieżkami, z których obie zaczynają się w polu (1,1), jedna kończy
  się w polu (k, i) a druga w polu (k, j). Tablicę tę z grubsza
  wypełniamy w kolejności rosnących k; lecz, by otrzymać złożoność
  O(n^3), trzeba było w dobrej kolejności wypełniać pola T[k,i,j]
  dla ustalonego k, np. w kolejności rosnących i, a następnie
  rosnących j.
W obu rozwiązaniach dało się uzyskać pamięć O(n^2), jeśli potrzebujemy
tylko znać na koniec długość najkrótszej trasy, lub O(n^3), jeśli
chcemy odtworzyć tę trasę.

Było dużo niepoprawnych rozwiązań. Oto najczęstsze z nich:
A. Znajduję programowaniem dynamicznym (lub alg. Dijkstry lub alg.
  na najkrótsze ścieżki w DAGu) najkrótszą drogę z (1,1) do (n,n),
  wyrzucam pola użyte, i robię to samo z powrotem, nie używając
  ponownie użytych pól. To nie jest poprawne, spójrzmy na taką tablicę:

  Przykład 1.
  9999911       Optymalne tutaj jest pójście tam i z powrotem,
  9999111       za każdym razem odwiedzając jedno pole o wartości 2,
  9991111       gdy pójdziemy tam używając samych pól o wartości 1,
  9921119       wracając będziemy musieli użyć pola o wartości 9.
  9111199
  1112999
  1119999
  
B. Robię jak w algorytmie A, ale próbuję wracając,
  jeśli napotkam "konflikt", czyli optymalna ścieżka wracająca
  chce użyć pola już zużytego, rozstrzygnąć ten konflikt przyznając
  pole tej ścieżce, która w jakimś sensie "mniej na tym traci".
  Definicje tutaj się różniły, ale właściwie wszystkie algorytmy
  tego typu nie działają na przykładzie podobnym do poniższego
  
  Przykład 2. (Pole A i B ma wartość 1, lecz oznaczyłem je
  9911111      A i B na potrzeby opisu)
  4119991     Idąc od prawego górnego rogu, konflikt następuje
  19A1111     w polu A. Lokalnie, nie przyznając tego pola ścieżce
  1313999     idącej górą, musi ona przejść przez pole o wartości 4,
  11B1999     a ścieżka dolna przez pole o wartości 3. Jednakże,
  1919999     jeśli tutaj zachłannie przyznamy to pole ścieżce górnej,
  1119999     następny konflikt nastąpi w polu B. Tutaj przyznamy
              pierwszeństwo ścieżce dolnej, bo inaczej wpakuje się na 9,
              więc ścieżka górna przejdzie przez 3. Zaliczymy więc
              dwie trójki, a moglibyśmy jedną czwórkę.

Ogólny schemat oceniania:
0 pkt za niepoprawne rozwiązanie
1 pkt za poprawne rozwiązanie wykładnicze
2 pkt za zdefiniowanie obiecującej tablicy do programowania dynamicznego,
      a następnie zrobienie z nią czegoś bardzo dziwnego
5 pkt za poprawne rozwiązanie wielomianowe
8 pkt za rozwiązanie O(n^3)
Najczęstsze minusy:
-0.5pkt za nienapisanie nic o złożoności pamięciowej algorytmu,
  w przypadku algorytmów wielomianowych
-0.5pkt lub -1pkt za błędy w indeksach lub brak większej precyzji,
  zwłaszcza w rozwiązaniu drugim, gdzie trzeba trochę na to uważać