Wstęp

Niektóre osoby mogą nie znać pewnych elementów języka C++, odpowiednia notka co do bardziej zaawansowanych fragmentów znajduje się pod koniec artykułu.

Problem RMQ

Niech będzie dana tablica n-elementowa T[n], tablica jest wypełniona liczbami całkowitymi. Interesują nas zapytania o najmniejszą wartość z danego przedziału. Takie zapytania będziemy oznaczać przez RMQ(a,b), gdzie a to lewy indeks przedziału o który pytamy, a b to prawy indeks przedziału o który pytamy. Innymi słowy RMQ(a,b) = min(T[a],T[a+1],…T[b]). Na rys. 1 przedstawiona jest tablica 10 elementowa i zapytanie o minimum z przedziału 2-6.

Rys. 1 Zapytanie o najmniejszą wartość w tablicy T z przedziału od 2 do 6 włącznie.

Interesować nas będzie oczywiście udzielanie szybkich odpowiedzi na zapytania tego typu. Pod spodem znajduje się przykładowy program wczytujący tablicę o określonej liczbie elementów i udzielający odpowiedzi na określoną ilość pytań.

 1  #include <iostream>

 2  #include <algorithm>

 3 

 4  using namespace std;

 5 

 6  const int N = 1000000;/// maksymalny rozmiar tablicy

 7  const int INF = 1000000001;///swoisty odpowiednik nieskonczonosci

 8 

 9  int T[N];

10 

11  ///T - tablica z liczbami

12  ///a - lewy(ten mniejszy) indeks przedzialu w tablicy T

13  ///b - prawy indeks przedzialu w tablicy T

14  int Query(int a,int b){

15      int minimum=INF;

16      for(int i=a;i<=b;++i)

17          minimum=min(minimum,T[i]);

18      return minimum;

19  }

20 

21  int main(){

22      cout<<"Podaj rozmiar tablicy."<<endl;

23      int n; cin>>n;

24      for(int i=0;i<n;++i){

25          cout<<"Podaj T["<<i<<"]."<<endl;

26          cin>>T[i];

27      }

28      cout<<"Podaj liczbe zapytan."<<endl;

29      int m;cin>>m;

30      for(int i=0;i<m;++i){

31          cout<<"Podaj lewy indeks przedzialu."<<endl;

32          int a; cin>>a;

33          cout<<"Podaj prawy indeks przedzialu."<<endl;

34          int b; cin>>b;

35          cout<<"Minimum z tego przedzialu to -> "<<Query(a,b)<<endl;

36      }

37      return 0;

38  }

 

Spróbujmy określić złożoność takiej metody radzenia sobie z problemem RMQ. Spójrzmy na samą funkcję Query(int a, int b), w najgorszym przypadku funkcja będzie musiała przeszukać przedział o długości O(n)(n – wielkość tablicy). Wobec tego złożoność tej funkcji szacujemy jako O(n). Dalej widzimy, że złożoność programu jest uzależniona od liczby zapytań – m. Wobec tego złożoność całego programu to O(n)*O(m) = O(n*m). Jednak gdy mamy odpowiednio duże parametry m i n robi się nieciekawie.

W takim razie spróbujemy poprawić złożoność naszego algorytmu. Dla każdej pary indeksów (a,b) w nowej tablicy S[n][n] będziemy przechowywać wartość minimum z przedziału <a,b>. Czyli podsumowując RMQ(a,b) = S[a][b]. Jednakże jak poprawnie obliczyć taką tablicę S? W tym celu przeanalizujmy poniższy fragment kodu.

1 for(int i=0;i<n;++i)
2      for(int j=i;j<n;++j)
3          S[i][j]=Query(i,j);

 

Już wiemy, że Query ma złożoność O(n), liczbę obrotów pierwszej pętli for szacujemy na O(n) obrotów, tak samo jak drugiej. Podsumowując daje to nam złożoność powyższego kodu rzędu O(n)*O(n)*O(n) = O(n3). Co prawda jest to dużo, jednak mając już tablicę S na pytania odpowiadamy w czasie O(1), ponieważ RMQ(a,b) = S[a][b]. O ile liczba m jest większa od n2, opłaci nam się takie rozwiązanie. Co nie zmienia faktu, że jest to mało przydatne. Na dobrą sprawę można by zapisywać na bieżąco wartości tablicy S, by nie obliczać 2 razy tego przedziału. Jednak tablicę S można obliczyć sprytniej.

Co należy zauważyć? RMQ(a,a) = T[a], ponieważ jest to przedział jedno elementowy, co siłą rzeczy oznacza, że T[a] jest najmniejszym elementem z tego przedziału. Zaś dla pewnego b>a, RMQ(a,b) = min(T[b],RMQ(a,b-1)). Gdyż RMQ(a,b-1) to najmniejsza wartość z przedziału <a,b-1>, jednak może się okazać, że T[b] jest jeszcze mniejsze i wtedy wynik należy poprawić, stąd min(T[b],RMQ(a,b-1)). Poniższy program wykorzystuje ten fakt.

1 #include <iostream>
 2  #include <algorithm>
 3  
 4  using namespace std;
 5  
 6  const int N = 1000;/// maksymalny rozmiar tablicy
 7  const int INF = 1000000001;///swoisty odpowiednik nieskonczonosci
 8  
 9  int T[N],A[N][N];
10  ///T - tablica z liczbami
11  /// A[N][N] - tablica przechowujaca minima
12  
13  ///a - lewy(ten mniejszy) indeks przedzialu w tablicy T
14  ///b - prawy indeks przedzialu w tablicy T
15  int Query(int a,int b){///uproszczona wersja funkcji Query korzystajaca z tablicy A
16      return A[a][b];
17  }
18  
19  void Init(int n){///funkcja wyliczajaca tablice A, przyjmuje parametr n, ktorym jest rozmiar(wykorzystywany) tablicy T
20      for(int i=0;i<n;++i)
21          A[i][i]=T[i]; /// korzystamy z tozsamosci, ze RMQ(a,a) = T[a]
22      for(int i=0;i<n;++i)
23          for(int j=i+1;j<n;++j)
24              A[i][j]=min(A[i][j-1],T[j]);///korzystamy z tozsamosci, ze RMQ(a,b) = min(RMQ(a,b-1),T[b]), dla b>a
25  }
26  
27  int main(){
28      cout<<"Podaj rozmiar tablicy."<<endl;
29      int n; cin>>n;
30      for(int i=0;i<n;++i){
31          cout<<"Podaj T["<<i<<"]."<<endl;
32          cin>>T[i];
33      }
34      Init(n);
35      cout<<"Podaj liczbe zapytan."<<endl;
36      int m;cin>>m;
37      for(int i=0;i<m;++i){
38          cout<<"Podaj lewy indeks przedzialu."<<endl;
39          int a; cin>>a;
40          cout<<"Podaj prawy indeks przedzialu."<<endl;
41          int b; cin>>b;
42          cout<<"Minimum z tego przedzialu to -> "<<Query(a,b)<<endl;
43      }
44      return 0;
45  }

 

Jak widać teraz złożoność zapytania – Query wynosi O(1). Jednak pojawiła się funkcja(czy raczej powinienem powiedzieć procedura, choć w C++ nie występuje podział na procedury i funkcje) o nazwie Init, odpowiada ona za poprawne wyliczenie tablicy A korzystając z poprzednich obserwacji. Widzimy, że w funkcji Init występuje pętla wykonująca O(n) obrotów, następnie występują 2 zagnieżdżone pętle wykonujące po O(n) obrotów, stąd O(n)+O(n)*O(n) = O(n)+O(n2) = O(n+n2)=O(n2). Istotnie udało nam się przyśpieszyć proces wyliczania tablicy A. Teraz o ile nasze m>n mamy optymalniejszy algorytm od tego o złożoności O(n*m). Jednakże zadajmy sobie pytanie, czy można jeszcze szybciej obliczyć tablicę A? Otóż okazuje się że nie, dlaczego? A no dlatego, że jak widzimy tablica A jest dwuwymiarowa,  co to oznacza? Posiada dokładnie n2 elementów, nie jest możliwym więc szybsze jej obliczenie.

Na tym jednak nie koniec. Może i szybciej nie damy rady policzyć tablicy A, lecz możemy z niej zrezygnować i poszukać innego rozwiązania. Podzielmy tablicę n-elementową na  części. Przyjrzyjmy się temu na przykładzie rys. 2.

Rys. 2 Dzielimy tablicę na fragmenty po elementów. Zauważamy, że RMQ(3,14) składa się z minimum z dwóch fragmentów f1 i f2 oraz przedziałów <3,3> i <12,14>.

Załóżmy, że mamy policzone minima dla wszystkich fragmentów po . Zastanówmy się z ilu całkowitych fragmentów może się składać nasz przedział o który pytamy. Nie jest tajemnicą, że tablica T dzieli się na fragmentów po elementów . Widzimy, że przedział o jaki pytamy może zawierać pewną ilość takich fragmentów w sobie, wobec tego wyciągniemy z nich minimum w czasie (ponieważ co najwyżej tyle jest tych fragmentów, a z każdego fragmentu pozyskujemy minimum w czasie O(1)).  Jednak przedział o jaki pytamy, oprócz fragmentów o długości , może w sobie zawierać przedziały, które nie mają długości .  Na rys. 2 są to przedziały <3,3> i <12,14> dla RMQ(3,14). Zauważmy także, że takich przedziałów jest co najwyżej 2. Rozmiar każdego z nich można oszacować przez , więc można po prostu przejrzeć ich elementy jeden po drugim i uzyskać z nich minimum. Tym sposobem możemy zrealizować zapytanie o dowolny przedział w zakresie naszej tablicy w czasie . Zanim przejdziemy do kodu zapytania, skupimy się na kodzie uzyskania minimum z fragmentów długości .

1 void Init(int n){///funkcja wyliczajaca tablice f
2      int c=ceil(sqrt(n));
3      int d=n/c+(n%c>0);///ilosc fragmentow ktore pokrywaja tablice T
4      for(int i=0;i<d;++i){
5          f[i]=INF;
6          for(int j=0;j<c;++j)///przechodzenie kolejno po elementach fragmentu
7              f[i]=min(f[i],T[i*c+j]);
8      }
9  }
 

Jak widzimy, wyznaczenie minim z tych fragmentów zajmuje czas rzędu O(n). Co jest do przyjęcia. Ustalmy funkcję, które będzie dla nas liczyła minimum z danego przedziału w sposób bezpośredni.

1 int Brute_force(int a,int b){///po prostu liczymy minimum z zadanego przedzialu
2      int minimum=INF;
3      for(int i=a;i<=b;++i)
4          minimum=min(minimum,T[i]);
5      return minimum;
6  }

Jest to oczywiście kod funkcji Query z pierwszego algorytmu. I będzie działał w czasie , ponieważ tylko przedziały o co najwyżej takiej długości będą do tej funkcji podawane. Teraz można już napisać kod funkcji Query.

1 int Query(int a,int b){
 2      int c=ceil(sqrt(n));
 3      if(b-a+1<=2*c){///jezeli przedzial ma dlugosc mniejsza badz rowna 2*c, to mozemy to policzyc brutalnie
 4          return Brute_force(a,b);
 5      }else{
 6          int minimum=INF;
 7          if(a%c!=0){///jezeli a nie jest poczatkiem jakiegos fragmentu
 8              ///uaktualniamy minimum o przedzial ktory nie jest fragmentem,a zaczyna sie w a
 9              minimum=min(minimum,Brute_force(a,c*(a/c+1)-1));
10              a=c*(a/c+1);///nowe a, bedace poczatkie fragmentu sasiadujacego z a od prawej
11          }
12          if((b+1)%c!=0){///b+1 powinno byc poczatkiem nowego fragmentu
13              minimum=min(minimum,Brute_force(c*(b/c),b));
14              b=c*(b/c)-1;///koniec najbliszego fragmentu
15          }
16          for(int i=a/c;i<=(b+1)/c;++i)
17              minimum=min(minimum,f[i]);
18          return minimum;
19      }
20  }

W wierszu 3 sprawdzamy, czy długość przedziału o jaki pytamy jest mniejsza bądź równa 2*, jeżeli tak to liczymy minimum bezpośrednio, co siłą rzeczy ma złożoność . Jednak dlaczego 2*? Ponieważ wiemy, że każdy dłuższy przedział na pewno ma w sobie jakiś fragment długości . Następnie w wierszach 6-15 obliczamy bezpośrednio minima z przedziałów, które nie są fragmentami długości . Wiersze 16-17 to wyciągnięcie minimum z tych fragmentów. Złożoność funkcji Query szacujemy na . Podsumowując po przetworzeniu danych w czasie O(n), możemy odpowiadać na pytania o minimum z przedziału w czasie . Poniżej znajduje się kod przykładowego programu.

 1  #include <iostream>
 2  #include <algorithm>
 3  #include <cmath>
 4  
 5  using namespace std;
 6  
 7  const int N = 10000;/// maksymalny rozmiar tablicy
 8  const int MAX_SQRT = 100;
 9  const int INF = 1000000001;///swoisty odpowiednik nieskonczonosci
10  
11  int T[N],f[MAX_SQRT];
12  int n;
13  ///T - tablica z liczbami
14  ///f – tablica z minimami z fragmentow
15  
16  int Brute_force(int a,int b){///po prostu liczymy minimum z zadanego przedzialu
17      int minimum=INF;
18      for(int i=a;i<=b;++i)
19          minimum=min(minimum,T[i]);
20      return minimum;
21  }
22  
23  ///a - lewy(ten mniejszy) indeks przedzialu w tablicy T
24  ///b - prawy indeks przedzialu w tablicy T
25  int Query(int a,int b){
26      int c=ceil(sqrt(n));
27      if(b-a+1<=2*c){///jezeli przedzial ma dlugosc mniejsza badz rowna 2*c, to mozemy to policzyc brutalnie
28          return Brute_force(a,b);
29      }else{
30          int minimum=INF;
31          if(a%c!=0){///jezeli a nie jest poczatkiem jakiegos fragmentu
32              ///uaktualniamy minimum o przedzial ktory nie jest fragmentem,a zaczyna sie w a
33              minimum=min(minimum,Brute_force(a,c*(a/c+1)-1));
34              a=c*(a/c+1);///nowe a, bedace poczatkie fragmentu sasiadujacego z a od prawej
35          }
36          if((b+1)%c!=0){///b+1 powinno byc poczatkiem nowego fragmentu
37              minimum=min(minimum,Brute_force(c*(b/c),b));
38              b=c*(b/c)-1;///koniec najbliszego fragmentu
39          }
40          for(int i=a/c;i<=(b+1)/c;++i)
41              minimum=min(minimum,f[i]);
42          return minimum;
43      }
44  }
45  
46  void Init(int n){///funkcja wyliczajaca tablice f
47      int c=ceil(sqrt(n));
48      int d=n/c+(n%c>0);///ilosc fragmentow ktore pokrywaja tablice T
49      for(int i=0;i<d;++i){
50          f[i]=INF;
51          for(int j=0;j<c;++j)///przechodzenie kolejno po elementach fragmentu
52              f[i]=min(f[i],T[i*c+j]);
53      }
54  }
55  
56  int main(){
57      cout<<"Podaj rozmiar tablicy."<<endl;
58      cin>>n;
59      for(int i=0;i<n;++i){
60          cout<<"Podaj T["<<i<<"]."<<endl;
61          cin>>T[i];
62      }
63      Init(n);
64      cout<<"Podaj liczbe zapytan."<<endl;
65      int m;cin>>m;
66      for(int i=0;i<m;++i){
67          cout<<"Podaj lewy indeks przedzialu."<<endl;
68          int a; cin>>a;
69          cout<<"Podaj prawy indeks przedzialu."<<endl;
70          int b; cin>>b;
71          cout<<"Minimum z tego przedzialu to -> "<<Query(a,b)<<endl;
72      }
73      return 0;
74  }

Optymalny Algorytm

Wciąż jeszcze można usprawnić wyliczanie RMQ z danego przedziału. W tym celu utworzymy nową tablicę M[n][ ] postaci M[i][j]=RMQ(i,2j-1). Czyli będziemy przechowywać w niej wartości minim zaczynających się od pewnego i i mających długość 2j .

Rys. 3 Kilka przykładów z tablicą M.

Mając daną taką tablicę M, możemy odpowiedzieć w czasie stałym na pytanie o minimum z każdego przedziału. Wystarczy zauważyć jedną rzecz:

RMQ(i,j)=min(M[i][k], M[j-2k+1][k]), gdzie k= 

No dobra, ale na pierwszy rzut oka nie koniecznie widać o co chodzi. No to po kolei, k to jest wykładnik największej potęgi dwójki mieszczącej się w długości przedziału(j-i+1). Mamy dane minimum przedziału <i , i+2k-1>. Jednak nie zawsze jest to te minimum, którego szukamy. Nie szkodzi, widzimy, że ten przedział pokrywa przynajmniej połowę naszego przedziału docelowego(gdyby tak nie było to moglibyśmy go powiększyć dwukrotnie, jednak wiemy, że 2k jest największą potęgą 2, która się mieści w naszym przedziale). I teraz możemy znaleźć taki indeks, że przedział zaczynający się w nim i mający długość 2k skończy się na indeksie j. Jak możecie się przekonać ten przedział to <j-2k+1,j>.  Tak jak poprzednio ten przedział pokrywa więcej niż połowę naszego przedziału docelowego, skoro tak to szukaną wartością jest minimum z tych 2 przedziałów pokrywających nasz przedział docelowy - RMQ(i,j)=min(M[i][k], M[j-2k+1][k]). Trochę zawiłe, jednak rysunek 3a, powinien rzucić na to trochę więcej światła.

Rys. 3a

Widzimy, że RMQ(1,4)=M[1][2] to zwykłe podstawienie do wzoru M[i][k] przy k równym 2. K jest równe 2 ponieważ, jak już wcześniej powiedziałem k jest wykładnikiem największej potęgi dwójki która mieści się w długości przedziału. W tym wypadku przedziałem jest <1,7>, czyli ten przedział ma długość 7. A 23 jest równe 8, czyli istotnie więcej niż długość naszego przedziału rozważanego na rysunku 3a, czyli k musi być równe 2 bo 22  mieści się w długości przedziału a 23 już nie. M[1][2] pokrywa pierwszą połowę przedziału. Następnie spójrzmy na RMQ(4,7)=M[4][2] to jest oczywiście podstawienie do wzoru M[j-2k+1][k], w tym wypadku ten przedział pokrywa drugą połowę przedziału <1,7>. Wniosek? Z obu połów przedziału docelowego posiadamy minima, teraz wystarczy je rozpatrzyć i zwrócić mniejszą, co daje nam  min(M[i][k], M[j-2k+1][k]).

A jak wyliczyć tablicę M? Ponownie wystarczy zauważyć pewną rzecz:

M[i][0]=T[i]

M[i][j]=min(M[i][j-1],M[i+2j-1][j-1])

To może się wydawać niejasne, jednak znów rysunek powinien pomóc zrozumieć o co w tym chodzi. W takim razie spójrzmy na rysunek 3b.

Rys. 3b

Patrząc na rysunek powinniśmy zauważyć pewną prawidłowość, M[2][1] to tak naprawdę min(M[2][0],M[3][0]). Dalej M[2][2] to min(M[2][1],M[4][1]). Teraz wystarczy podstawić liczby z rysunku do wzoru M[i][j]=min(M[i][j-1],M[i+2j-1][j-1]) by przekonać się o jego prawdziwości. Podobnie jak w jednym z wcześniejszych algorytmów korzystamy tutaj z wartości już policzonych.

Poniżej znajduje się kod obliczający tablicę M. Warto wspomnieć, że będziemy potrzebowali tablicy k[N+1] przechowującą w k[i] wykładnik największej potęgi 2 mieszczącej się w i.

 1 void Init(int n){///funkcja wyliczajaca tablice M i k, przyjmuje parametr n, ktorym jest rozmiar tablicy T
 2      for (int i = 0; i < n; ++i)///obliczanie wartosci M[i][0]
 3            M[i][0] = T[i];
 4      for (int j = 1; 1 << j <= n; ++j)///dla kazdej potegi 2 od 1 do takiej ktora jest mniejsza badz rowna n
 5          for (int i = 0; i + (1 << j) - 1 < n; ++i)///kolejno dla kazdej pozycji dla ktorej odpowiednia potega 2 miesci sie w tablicy
 6              M[i][j]=min(M[i][j-1],M[i + (1 << (j - 1))][j - 1]);
 7      int val=0;///wykładnik zerowej potegi dwojki
 8      for(int i=1;i<=n;++i){
 9          if((1<<val+1) <=i) val+=1;///zwiekszamy val o 1
10          k[i]=val;
11      }
12  }

 

Pętle w linijkach 2 i 8 są wykonywane w czasie O(n). Skupmy się jednak na analizie wierszy od 4 do 6. Złożoność pierwszej pętli można oszacować jako O(log n), zaś drugiej jako O(n), stąd O(log n)*O(n)=O(n log n). Teraz można już napisać funkcję Query.

1 int Query(int a,int b){
 2      int c=k[(b-a+1)];///najwieksza potega 2 mieszczaca sie w przedziale
 3      return min(M[a][c], M[b-(1<<c)+1][c]);
 4  }

 

Oczywiście nie trudno zauważyć, że funkcja ta działa w czasie O(1).Podsumowując, otrzymaliśmy rozwiązanie, które wymaga wstępnego przetworzenia danych w czasie O(n log n), ale pozwala odpowiadać na zapytania o minimum z przedziału w czasie O(1). Poniżej znajduje się kod przykładowego programu, korzystającego z tego algorytmu.

1   #include <iostream>
2   #include <algorithm>
3  
4   using namespace std;
5  
6   const int N = 1000;/// maksymalny rozmiar tablicy
7   const int INF = 1000000001;///swoisty odpowiednik nieskonczonosci
8   const int MAXLOGN = 10;///maksymalna potega 2
9  
10  int T[N],M[N][MAXLOGN],k[N+1];
11  ///T[N] - tablica z liczbami
12  /// M[N][MAXLOGN] - tablica pomocnicza
13  ///k[N+1} - k[i] przechowuje najwieksza potege 2 mniejsza lub rowna i
14  
15  ///a - lewy(ten mniejszy) indeks przedzialu w tablicy T
16  ///b - prawy indeks przedzialu w tablicy T
17  int Query(int a,int b){
18      int c=k[(b-a+1)];///najwieksza potega 2 mieszczaca sie w przedziale
19      return min(M[a][c], M[b-(1<<c)+1][c]);
20  }
21  
22  void Init(int n){///funkcja wyliczajaca tablice A, przyjmuje parametr n, ktorym jest rozmiar(wykorzystywany) tablicy T
23      for (int i = 0; i < n; ++i)///obliczanie wartosci M[i][0]
24            M[i][0] = T[i];
25      for (int j = 1; 1 << j <= n; ++j)///dla kazdej potegi 2 od 1 do takiej ktora jest mniejsza badz rowna n
26          for (int i = 0; i + (1 << j) - 1 < n; ++i)///kolejno dla kazdej pozycji dla ktorej odpowiednia potega 2 miesci sie w tablicy
27              M[i][j]=min(M[i][j-1],M[i + (1 << (j - 1))][j - 1]);
28      int val=0;///wykładnik zerowej potegi dwojki 
29      for(int i=1;i<=n;++i){
30          if((1<<val+1) <=i) val+=1;///zwiekszamy val o 1
31          k[i]=val;
32      }
33  }
34  
35  int main(){
36      cout<<"Podaj rozmiar tablicy."<<endl;
37      int n; cin>>n;
38      for(int i=0;i<n;++i){
39          cout<<"Podaj T["<<i<<"]."<<endl;
40          cin>>T[i];
41      }
42      Init(n);
43      cout<<"Podaj liczbe zapytan."<<endl;
44      int m;cin>>m;
45      for(int i=0;i<m;++i){
46          cout<<"Podaj lewy indeks przedzialu."<<endl;
47          int a; cin>>a;
48          cout<<"Podaj prawy indeks przedzialu."<<endl;
49          int b; cin>>b;
50          cout<<"Minimum z tego przedzialu to -> "<<Query(a,b)<<endl;
51      }
52      return 0;
53  }

 

Ustalenie techniczne

Funkcja min, której często używamy w kodzie pochodzi z biblioteki algorithm. Przyjmuje ona dwie zmienne takiego samego typu i zwraca mniejszą z nich. Jeżeli zaś chodzi o fragmenty kodu postaci 1<<j , są to przesunięcia bitowe w lewo o j pozycji. Można o nich poczytać chociażby tutaj http://guidecpp.cal.pl/cplus,operators-bits. Jednak do zrozumienia tego kodu, wystarczy wiedzieć, że 1 <<j to tak naprawdę 2j .

Bibliografia

-http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

-http://oi.edu.pl/static/attachment/20120215/oi18.pdf