IOI

IOI 2012 – Crayfish Scrivener

Problem description: Crayfish Scrivener

The first thing that we need is save the TEXT and know how it can be undo. This is easy we need a tree when it do undo only jump for the actions saved, for do TypeLetter add the new letter in the tree (see image).

IMG_0053

With this tree we can obtain the i-th character in the text, we always point to the last character and climb in the tree.

IMG_0054
IMG_0055

Ok it can solve task-4 but we need solve task-5 (The total number of commands and queries is between 1 and 1.000.000), our problem is ‘GetLetter’ function, it is O(P) for now. In the worst case the P can be 500.000 and it can be called 500.000 times.

IMG_0056

A good improvement is for do ‘GetLetter’ in O( sqrt(height of the tree) ). It need save the dad of the node and the ‘sqrt(height of the tree)’-th dad of each node. When the search is for a ‘P’ upper to ‘sqrt(height of the tree)’ we can jump ‘sqrt(height of the tree)’ nodes. Now ‘GetLetter’ function is O(sqrt(height of the tree) )

IMG_0057

This is my implementation

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;

char T[1000001];
int dad[1000001], dadH[1000001], H[1000001];
vector<int> v;
int act, it;

void Init() {
  it = 1;
  act = 0;
  H[0] = -1;
  dad[0] = dadH[0] = 0;
  v.clear();
}

void TypeLetter(char L) {
  T[it] = L;
  H[it] = H[act]+1;
  dad[it] = act;
  if(H[it] % 1000 == 0) //sqrt(1000000) => 1000
    dadH[it] = it;
  else
    dadH[it] = dadH[act];
  v.push_back(it);
  act = it++;
}

void UndoCommands(int U) {
  act = v[v.size() - U - 1];
  v.push_back(act);
}

char GetLetter(int P) { // O(sqrt(height))
  int i = act;
  while(H[ dadH[i] ] > P) i = dadH[i];// O(sqrt(height))
  while(H[ dad[i] ] >= P) i = dad[i]; // O(sqrt(height))
  return T[i];
}

int main(){
  Init();
  TypeLetter('a');			//  a
  TypeLetter('b');			//  ab
  cout<<GetLetter(1)<<endl;	//b ab
  TypeLetter('d');			//  abd
  UndoCommands(2);			//  a
  UndoCommands(1);			//  abd
  cout<<GetLetter(2)<<endl;	//d abd
  TypeLetter('e');			//  abde
  UndoCommands(1);			//  abd
  UndoCommands(5);			//  ab
  TypeLetter('c');			//  abc
  cout<<GetLetter(2)<<endl;	//c abc
  UndoCommands(2);			//  abd
  cout<<GetLetter(2)<<endl;	//d abd
}