INC 2010

Soal F Searching In Tree

Gua dah pernah buat nih soal di SPOJ dengan kode soal PT07J, cuma beda format input output sedikit. Di SPOJ kena TLE mulu karena time limit yang terlalu ketat. Gua solve ini soal pake binary search + segment tree + fractional cascading, buat 1x query bakal jadi log^2 x, dimana x adalah ukuran subtree yang di query. Cukup rumit buat dijelasin, gua bagi jadi 3 bagian, pertama – tama mungkin ga nyambung, baca aja dulu 🙂

A. segment tree yang gua pake, mirip ma tree proses nya merge sort, gambarnya kira – kira gini

Gambar diatas kebalik sama segment tree yang gua buat,  jadi rootnya adalah yang paling bawah, berisi 7 elemen. Nah kalo udah punya tree kayak gini, kita bisa jawab pertanyaan “untuk angka dari L..R ada berapa angka yang <= x” dalam waktu log^2 N kalo melakukan binary search ketika traverse tree, atau log N kalo pake fractional cascading . Silahkan pikir sendiri 🙂

B.   Misal dikasih sequence angka, dan ditanya berapakah elemen ke – k jika angka dari indeks a sampai b diurutkan

contoh : 4 5 76 8 9 2 1    berapakah angka ke 3 terbesar jika dari indeks 2 sampai 6 diurutkan ? kalo diurutin 2 5 8 9 76  angka ke – 3 adalah 8. Soal ini bisa dijawab dengan kompleksitas log N * kompleksitas pada point A. Caranya adalah kita tebak – tebak jawabannya pake binary search 🙂

4 [1 2 3 5] 7 4 diurutin jadi 1 2 3 4 4 5 7, misalkan kita mau cari angka ke – 3 dari indeks 2..5, jawabannya yaitu 3, proses binary search nya kira – kira gini

Note :

– angka yang dalam [] adalah angka yang ditebak

– angka yang didepannya dikasih bintang adalah batas kiri dan kanan binary search

– underscore itu dummy, jadi posisi awal left untuk binary search nya, 1 posisi lebih kiri dari data pertama

*_ 1 2 3 [4] 4 5 *7    => ada 3 angka dari indeks 2..5 pada urutan awal yang <= 4, karena rank yang didapatkan >= target, gerak ke kiri (kenapa kalo = gerak ke kiri? penjelasannya tar belakangan)

*_ 1 [2] 3 *4 4 5 7    => ada 2 angka dari indeks 2..5 pada urutan awal yang <= 2, karena rank yang didapat < target, gerak ke kanan

_ 1 *2 [3] *4 4 5 7    => ada 3 angka dari indeks 2..5 pada urutan awal yang <= 3, karena rank yang didapat >= target, gerak ke kiri

_ 1 *2 *3 4 4 5 7    => kalo batasnya udah sebelahan, berhenti, jawabannya ada di batas kanan yaitu 3

oke, selanjutnya penjelasan kenapa kalo dapet rank yang = target kita gerak ke kiri

misal punya barisan angka A = 1, 2,3,5 dan kita punya tabel x spt di bawah ini, dimana x[i] isinya adalah banyaknya elemen yang <= i pada barisan angka A

cth : x[1] = banyaknya angka yang bernilai <= 1 dst

x[1] = 1

x[2] = 2

x[3] = 3

x[4] = 3

x[5] = 4

Dari tabel diatas bisa diliat kalo nilai x[i] dan x[i-1] adalah sama, maka sebenarnya angka i ga ada di set A,  karena itu binary search diatas, bergerak ke kiri kalo ketemu yang ranknya = target.

C. Kembali ke soal awal, dikasih tree, ditanya angka ke – k dari suatu subtree, nah lakukan preorder dulu pada treenya, dan simpan jumlah node di tiap subtree, dari preorder akan didapat sequence angka selanjutnya untuk tiap query, cari angka ke k dari pos[node] .. pos[node] + subtreesize[node] – 1, soal ini jadi sama dengan soal diatas 🙂  Codenya cukup panjang, code yang di bawah ini udah pake fractional cascading, jadi tiap query hanya log^2 |x| dimana |x| adalah ukuran subtree. Kompleksitas total O(N log N) + O(Q log^2 N), cukup kenceng , di komputer gua, butuh waktu 0.969 detik untuk menyelesaikan testcase yang dipakai saat lomba. kode ini termasuk pendek kalo dibandingin sama kode Felix Halim ataupun tim Dongskar.

#include <cstdio>
#include <vector>
#include <map>
#define left(idx) (idx<<1)
#define right(idx) (left(idx)+1)
using namespace std;

typedef struct Tnode
{
	int L, R;
}node;
int number,idx;
map vv;
node Tree[(1<<18) + 1];
int sorted[100001][18];
int data[100001],n;
int subtree[100001];
int label[100001];
int first[100001];
int lf[100001][18],rf[100001][18];
vector tree[100001];
void Build(int L,int R,int idx,int depth)
{
	Tree[idx].L = L;
	Tree[idx].R = R;
	if (L==R)
	{
		sorted[L][depth] = data[L];
		return;
	}

	int mid = (L+R)>>1;
	Build(L,mid,left(idx),depth+1);
	Build(mid+1,R,right(idx),depth+1);

	int i = L;
	int j = mid+1;
	int k = L,pos=0,posR=0;
	while (i<=mid && j<=R)
	{
		if (sorted[i][depth+1] < sorted[j][depth+1])
			sorted[k][depth] = sorted[i++][depth+1],pos++;
		else
			sorted[k][depth] = sorted[j++][depth+1];
		lf[k++][depth] = pos;
	}
	while (i<=mid) lf[k][depth]=++pos,sorted[k++][depth] = sorted[i++][depth+1];
	while (j<=R) lf[k][depth]=mid-L+1,sorted[k++][depth] = sorted[j++][depth+1];
}

int GetRank(int L,int R,int idx,int depth,int pos) //getrank number in range L..R
{
 	if (pos==0) return 0;
 	if (Tree[idx].L == L && Tree[idx].R == R) return pos;
 	else
 	{
 		int ret = 0;
 		int count = lf[pos+Tree[idx].L-1][depth];
 		int mid = (Tree[idx].L + Tree[idx].R) >> 1;
		if (L <= mid)  ret += GetRank(L,min(R,mid) ,left(idx),depth+1,count);
 		if (R > mid) ret += GetRank(  max(L,mid+1),R,right(idx),depth+1,pos-count);
		return ret;
	}
}

void dfs(int node,int parent)
{
	data[++idx] = label[node];
	first[node] = idx;
	subtree[node]=1;
	for(int i=0,_n=tree[node].size();i<_n;i++)
		if (tree[node][i]!=parent)
		{
			dfs(tree[node][i],node);
			subtree[node]+=subtree[tree[node][i]];
		}
}

int main()
{
  int q,node,rank,a,b,low,high,mid,k,L,R,i,t;
  scanf("%d",&t);
  for(int T = 1 ;T<=t;T++)
  {
    printf("Case #%d:\n",T);
  	scanf("%d %d",&n,&q);
  	idx = 0;
  	for( i=1;i<=n;i++)  scanf("%d",label+i),vv[label[i]] = i;
  	for( i=1;i<=n;i++) tree[i].clear();
  	for( i=1;i<=n;i++)
  	{
  		scanf("%d",&a);
  		if (a+1 !=i)tree[a+1].push_back(i);
  	}
  	dfs(1,-1);
  	Build(1,n,1,0);

  	for( i=1;i<=q;i++)
  	{
  		scanf("%d %d",&rank,&node);
  		node++;
  		L = first[node];
  		R = L + subtree[node]-1;
  		low=0,high=n;
  		while (low+1 < high)
   		{
   			mid = (low + high)>>1;
  			number = sorted[mid][0];
  			k = GetRank(L,R,1,0,mid);
  				if (k >= rank)
  					high = mid;
  				else low = mid;
  		}
  		printf("%d\n",sorted[high][0]);
  	}
  }
	return 0;
}

8 comments on “INC 2010

  1. @su : punya gua pre-order kok buat traverse node nya, misal A punya anak B,C trus B punya anak D, E tar punya gua jadiin sequence A,B,D,E,C

    @felix : eh iya nih, yang C juga pada ilang2, padahal cara post code nya pake tag yang sama, btr gua benerin

    Suka

  2. Ping-balik: 2010 in review | Marcadian's Blog

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s