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
}

A – Ants Colony – ACM ICPC Latin America 2010

This is a typical case of LCA. Example (Sample input 1):

6                Tree:   0
0 8                     / 
1 7                    1   4
1 9                   /    
0 3                  2   3   5
4 2
4
2 3
5 2
1 4
0 3

(2 3):

 sum = 0      sum = 0    sum = p[a] + p[b] = 7 + 9 = 16
    x           x           x       
   /          /          /       
  1   x   =   1   x   = ab1   x  
 /         /         /        
2   3   x   a2 b3   x   x   x   x

(5 2):

 sum = 0      sum = 0  sum=p[a]+p[b]= 9 + 11 = 20
                              2+7         8+3

    0           0           0           0ab       
   /          /          /          /       
  1   4   =   1   4   =   1a  4b  =   x   x   
 /         /         /         /        
2a  3  b5   2a  x  b5   x   x   x   x   x   x

This is my implementation:

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

#define FOR(i,a,b)  for(int i=(a),_##i=(b);i<_##i;++i)
#define F(i,a)      FOR(i,0,a)
#define PB          push_back
#define MP          make_pair
#define S           size()
typedef long long   LL;

int TreeDad[100000], TreeDadH[100000];
int TreeLevel[100000];
LL TreeLen[100000];
vector<vector<int> > TreeSons(100000);

int N, sqrtL;

void build_tree(int node){
  if(!(TreeLevel[node] % sqrtL))
    TreeDadH[node] = TreeDad[node];
  else
    TreeDadH[node] = TreeDadH[ TreeDad[node] ];
  F(i, TreeSons[node].S)
    build_tree(TreeSons[node][i]);
}

int LCA(int x, int y) {
  while (TreeDadH[x] != TreeDadH[y]){
    if(TreeLevel[x] > TreeLevel[y]) x = TreeDadH[x];
    else y = TreeDadH[y];
  }
  while (x != y){
    if (TreeLevel[x] > TreeLevel[y]) x = TreeDad[x];
    else y = TreeDad[y];
  }
  return x;
}

int main(){
  int l, a, Q, s, t;
  while(scanf("%d", &N) && N){
    F(i, N) TreeSons[i].clear();
    int MaxLevel = 0;
    FOR(i, 1, N){
      scanf("%d %d", &a, &l);
      TreeDad[i] = a;
      TreeLen[i] = TreeLen[a] + LL(l);
      TreeLevel[i] = TreeLevel[a] + 1;
      TreeSons[a].PB(i);
      MaxLevel = max(MaxLevel, TreeLevel[i]);
    }
    sqrtL = sqrt(MaxLevel);
    build_tree(0);

    scanf("%d", &Q);
    F(i, Q){
      if(i) printf(" ");
      scanf("%d %d", &s, &t);
      printf("%lld", TreeLen[s] + TreeLen[t] - (TreeLen[LCA(s, t)]*2LL) );
    }
    printf("n");
  }
}