Longest path in a tree - หาเส้นทางที่ยาวที่สุดในต้นไม้

โจทย์จาก
http://www.spoj.com/problems/PT07Z/
อธิบายโจทย์
ถ้ามี Tree ที่ unweighted, undirected มี N nodes จงหาเส้นทางที่มีความยาวที่สุด

ลองสังเกต
unweighted คือไม่มีการถ่วงน้ำหนักทุกเส้นมีระยะทางเท่ากันหมด undirected คือเส้นแต่ละเส้นไม่มีลูกศร หมายความว่า ถ้า A เชื่อม B เราสามารถเดินจาก A->B หรือกลับ B->A ได้

รูป 1.1

tree ในรูป 1.1 เป็น directed tree เส้นทางสีแดงและสีน้ำเงินคือเส้นทางที่ยาวที่สุด ถ้าเปลี่ยนเป็น undircted

รูป 1.2

ถ้าเรามองรูป 1.2 เราอาจจะอยากตอบว่าเส้นทางที่ยาวที่สุดคือเส้นสีแดงหรือสีน้ำเงิน แต่จริงๆแล้วถือว่าผิด เพราะกราฟนี้เป็น undirected ถ้าวาดกราฟนี้ใหม่ให้เป็นแบบนี้

รูป 1.3

กราฟของเราก็จะมีความยาวเพิ่มจาก 2 เป็น 3 

เราจะแก้ปัญนี้อย่างไร
ถ้าเราเริ่มต้นที่ 1 แล้วทุกครั้งที่เราขยับไป node อื่นถือว่าเราเดิน 1 ก้าว เราจะได้เป็นรูปนี้

รูป 1.4

ถ้าเราเลือกไป 0 เราจะได้ 2 ต่อมาเรายังเลือกได้อีกเส้น เราจะเลือกเส้นที่ไป 3 หรือ 4 ก็ได้ เพราะมีค่าเท่ากันคือ 1 เราเอา 2 + 1 จะได้ 3 คำตอบทางที่ยาวที่สุดคือ 3 เราไม่ต้องรวม 1 เพราะว่าตัวที่เป็น leaf จะไม่ถูกนับ ถ้าเรารวม 1 เราต้องลบออก 1 เพราะว่าเราได้นับ leaf ไปแล้ว เช่น ถ้าเราเลือกไป 0 กับ 4
เราจะได้รูปนี้

รูป 1.5

เราได้นับ 0 4 2 แต่เราไม่ได้นับ 1 ซึ่งเท่ากับ 3 หากเรานับ 1 จะเป็น 1 4 0 2 ซึ่งเท่ากับ 4 แล้วเราต้องลบ leaf ออก 4 - 1 = 3 ซึ่งทำให้เราไม่จำเป็นที่จะต้อง 1 รวมไปก็ได้

เราจะทำแบบที่เราคิดได้อย่างไร 

ถ้าเรา dfs(1) เราจะสามารถขยับเข้าไปปลาย tree นี้ได้ทีละเส้นๆ ตาม algorithm ของ dfs แต่ละครั้งที่เราขยับ เราจะ +1 เมื่อเราถึงทุกปลายแล้ว เราจะ backtrack กับมาที่ 1 แล้วเลือกเส้นที่มากที่สุดมาสองเส้น

การที่เราเลือกมากที่สุดมาสองเส้นหมายความว่าเรากำลังจะเลือก ตัวมากสุดตัวแรก กับตัวมากสุดตัวสอง ซึ่งตัวมากสุดตัวแรกสามารถมีค่าเดียวกับตัวสองได้

เขียนเป็น code ได้แบบนี้

	#include <iostream>
	#include <iomanip>
	#include <cstring>
	#include <cmath>
	#include <cstdio>
	#include <algorithm>
	#include <vector>
	#include <climits>
	using namespace std;
	#define MAX 100009
	bool visited[MAX];
	int test = -1;
	int dfs(vector<int> v[],int node,int check)
	{
	int max1,max2;
	visited[node] = true;
	max1 = max2 = 0;
	int vsize = v[node].size();
	for(int i = 0; i < vsize; ++i)
	{
	if(!visited[v[node][i]])
	{
	int m = 1 + dfs(v,v[node][i],check);
	if(m >= max1)
	{
	max2 = max1;
	max1 = m;
	}
	else if(m > max2)
	{
	max2 = m;
	}
	}
	}
	if(node == check)
	return max1+max2;
	else
	return max1;
	}
	int main()
	{
	int n,a,b;
	cin>>n;
	vector<int> v[n+9];
	for(int i=0;i<n-1;i++){
	scanf("%d%d",&a,&b);
	v[a].push_back(b);
	v[b].push_back(a);
	}
	printf("%d\n",dfs(v,1,1));
	}

view raw LONGETSPATH.cpp hosted with ❤ by GitHub

ซึ่งก็คือ dfs ธรรมดาๆ แค่มีการดูว่าตัวไหน max1 max2 และเวลา return ถ้าไม่ใช่ node ที่เราใส่ไปตอนแรกก็จะ return ค่า max1 ออกไป เรา return max1 เพราะจะได้ทางที่ยาวสุด ถ้า return max2 จะได้ทางที่ยาวรองลงมา

[Dynamic Programming] Edit Distance

โจทย์จาก : Edit Distance เป็นปัญหาที่ถามเราว่าถ้ามี String 2 ตัว A,B จะมี operation ทำให้เหมือนกันโดยน้อยที่สุด โดยมี 3 operation

1. insert แทรกตัวอักษรเข้าไป 
2. delete ลบตัวอักษรออกจาก String
3.  replace เปลี่ยน A[i] เป็น B[j] 

 เช่น ถ้า A = ABC B = DEF
   operation ที่น้อยที่สุดคือ เปลี่ยน A -> D และเปลี่ยน B -> E และสุดท้าย C -> F ถ้า A = ABC B = ADE
   จะใช้เพียงแค่ 2 operation เพราะ A[0] กับ B[0] เท่ากันแล้ว  

วิธีตรงไปตรงมา(recursion)
เนื่องจากเราไม่รู้ว่าทำแบบไหนจะได้น้อยสุด เราจะทำทั้งหมดแล้วดูว่าวิธีไหนน้อยสุด
A = "X" B = "PQ" วิธีที่เราจะทำได้คือ

insert    : A -> "PX" B = "PQ" insert P เข้าไปใน A ทำให้ A กับ B มี P เหมือนกันแล้ว
delete   : A ->   _     B = "PQ" ลบ X ออก 
replace : A -> "P"    B = "PQ" เปลี่ยน X เป็น P

ตัวสีแดงคือตัวอักษรที่เราไม่สนใจแล้ว (ถูกดำเนินการแล้ว) ตัวอักษรที่ขีดเส้นใต้คือตัวอักษรที่เราต้องเปลี่ยน เช่น insert X กับ Q ถูกขีดเส้นตาย เพราะเราสามารถ
1.ลบ X ออก แล้วเพิ่ม Q 
2.ลบ Q ออกแล้วเพิ่ม X 
3.เปลี่ยน X ->Q หรือ Q -> X ก็จะทำให้เท่ากัน 
ส่วน P เราไม่ยุ่งเพราะเราทำให้เหมือนกันแล้ว


จากตัวอย่างข้างบนถ้าเราดำเนินการต่อแต่ละเคส ด้วย 3 เคสนี้ไปเรื่อยๆ เราก็จะรู้ว่าแต่ละแบบใช้กี่ครั้งจะเหมือนกัน

คำถามคือเราจะหยุดเมื่อไหร่ เพราะเราสามารถเพิ่มเข้าไปได้เรื่อยๆ หรือเปลี่ยนไปเรื่อยๆ ถ้าตัวขีดเส้นใต้ของเราคือตัวที่เราจะเปลี่ยนแล้วตัวขีดเส้นใต้ของเราไม่มีใน A หรือใน B แล้ว แปลว่าเราไม่ต้องทำต่อแล้ว แต่อาจจะเกิดกรณี A = "PQX" B = "PQ" ตัวขวาเราไม่มีตัวไหนที่ต้องดูแล้ว แต่ตัว X ยังมีในกรณีนี้ ถ้าตัวขวาเป็น 0 เราจะตอบว่าต้องลบตัวใน A เป็นจำนวนตัวที่ต้องเปลี่ยนขีดเส้นใต้ของ X และในทางกลับกันถ้าตัวซ้ายตัวที่เราต้องเปลี่ยนหมดแล้ว เราก็จะตอบจำนวนตัวที่ต้องเปลี่ยนใน X แทน

เพระฉะนั้น base case ของเราเป็น if(i == 0) return j;
                                               if(j == 0) return i;
ถ้ามอง recursion tree ด้านล่างเราจะจบทุกครั้งที่เป็น 0

recursion tree ที่เราจะเขียนจะทำทุกวิธีที่เป็นไปได้จนกว่าตัวที่เราสนใจจะเปลี่ยนเป็น 0
เราจะสร้าง f(i,j) ฟังค์ชั่นตัวนึงขึ้นมา f(i,j) จะให้ค่าน้อยที่สุดของ f(i,j)

f(i,j-1) คือ การ insert
f(i-1,j) คือ การ delete
f(i-1,j-1) คือการ replace
และเราก็ทำการเลือก min ของ 3 ฟังชั่นข้างบน ส่วน 1 คือไม่ว่าเราจะเลือกอะไรจาก 3 operation ก็ถือว่า 1 ครั้ง Tree ของเรายิ่งสูงขึ้นจำนวน + 1 ที่นี้จะบอกว่าเราสูงเท่าไหร่

ถ้าอธิบาย f(i,j) ให้เป็นภาษาทั่วไปคือ มี 3 วิธีไปเลือกวิธีที่น้อยที่สุดมาจาก 3 วิธีนี้ ส่วน + 1 ก็คือเราเลือกตัวน้อยสุด 1 ตัว และแต่ละครั้งก็จะถามแบบนี้จนกว่าจะไปเจอ i == 0 หรือ j == 0

	#include <iostream>
	#include <iomanip>
	#include <cstring>
	#include <cmath>
	#include <cstdio>
	#include <algorithm>
	#include <vector>
	#include <climits>
	using namespace std;
	int editDistance(char a[],char b[],int i,int j)
	{
	if(i == 0)
	return j;
	if(j == 0)
	return i;
	else if(a[i-1] == b[j-1])
	return editDistance(a,b,i-1,j-1);
	else
	return 1 + min(editDistance(a,b,i,j-1),min(editDistance(a,b,i-1,j),editDistance(a,b,i-1,j-1)));
	}
	int main()
	{
	char a[1000];
	char b[1000];
	scanf("%s %s",a,b);
	printf("minimum distance = %d\n",editDistance(a,b,strlen(a),strlen(b)));
	}

view raw EDITDIST.cpp hosted with ❤ by GitHub

จาก code จะเห็นเคส else if(a[i-1] == b[j-1]) คือกรณีที่เหมือนกัน ถ้าตัวอักษรเหมือนกัน ก็เหมือนเรา replace เช่น "AC" "PX" ถ้า replace ก็เป็น "PC" "PX" ถือว่านับ 1 แต่ถ้า
"AC" "AX" เราก็ไม่ต้องเช็คตัวแรกของแต่ละตัวแล้วเพราะว่ามันเหมือนกันแล้ว จะกลายเป็น
"AC" "PX" แต่เราจะไม่ + 1 เพราะว่าเราไม่จำเป็นต้องทำอะไร เพราะเท่ากันแล้ว

วิเคราะห์ Algorithm นี้  ถ้าเราลองนับดูว่า A = "ABC" B = "DEF" ซึ่งแค่ 3 ตัวอักษรแต่จะพบว่า recursion นี้ทำหลายรอบมากๆ
จะทำให้ดีขึ้นได้อย่างไร ถ้ามองรูป tree ด้านบน เราจะเห็นว่ามีบาง f(i,j) ที่เราได้หาเจอแล้ว ถูกเรียกใหม่อีกรอบ ในรูป f(1,1) ได้ถูกหาไปแล้วจากซ้ายสุด และถูกหาอีกครั้งตรงกลาง
เราจะใช้ dynamic programming เข้ามาช่วย
เขียน f(i,j) เต็มๆจะได้ 

ถ้าเราจะทำแบบ top down เราก็ต้องจำค่าแต่ละ f(i,j) และเมื่อ f(i,j) ถูกคำนวณไปแล้วเราจะตอบทันทีไม่ไปเสียเวลาเพิ่ม
ถ้าเราจะเขียนแบบ bottom up ก็ใช้ตรรกะเดียวกับข้างบนแต่เราจะทำตั้งแต่
 i = 0 -> len(A) j = 0 -> len(B)

	#include <iostream>
	#include <iomanip>
	#include <cstring>
	#include <cmath>
	#include <cstdio>
	#include <algorithm>
	#include <vector>
	#include <climits>
	using namespace std;
	int editDistance(char a[],char b[],int m,int n)
	{
	int dp[m+1][n+1];
	for(int i = 0; i <= m; ++i)
	for(int j = 0; j <= n; ++j)
	{
	if(i == 0)
	dp[i][j] = j;
	else if(j == 0)
	dp[i][j] = i;
	else if(a[i-1] == b[j-1])
	dp[i][j] = dp[i-1][j-1];
	else
	dp[i][j] = 1 + min(min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1]);
	}
	return dp[m][n];
	}
	int main()
	{
	char a[1000];
	char b[1000];
	scanf("%s %s",a,b);
	printf("minimum = %d\n",editDistance(a,b,strlen(a),strlen(b)));
	}

view raw EDITDIST(DP).cpp hosted with ❤ by GitHub

Inversion Count

โจทย์จาก: http://www.spoj.com/problems/INVCNT/
แปล : ให้ A เป็น array ขนาด n โดยที่สมาชิกไม่ซ้ำ ถ้ามี i < j แล้ว A[i] > A[j] ถือว่าคู่ (A[i],A[j]) เกิดการ inversion จงหาว่า A เกิดการ inversion กี่ครั้ง

กำหนดให้
 0 <= i,j <= n-1

ตัวอย่าง:
8 4 2 1
 คำตอบคือ (8,4),(8,2),(8,1),(4,2),(4,1) = 5 ตัว
1 2 3
คำตอบคือ 0 เพราะทุก A[i] > A[j]

วิธีทำแบบตรงไปตรงมา
ถ้าแปลโจทย์ให้เข้าใจง่ายขึ้นจะแปลได้ว่า ทุกตำแหน่ง(A[i]) ถ้ามีตัวฝั่งขวา(A[j])ที่มือที่น้อยกว่า ถือว่าเป็น inversion จากแนวคิดนี้ ผมจะสามารถเช็คได้เพราะในแต่ละตำแหน่ง A[i] ผมจะมองหาตัวขวา A[j] ที่น้อยกว่า

	#include <iostream>
	#include <iomanip>
	#include <cstring>
	#include <cmath>
	#include <cstdio>
	#include <algorithm>
	#include <vector>
	#include <climits>
	#include <stack>
	#include <queue>
	#include <sstream>
	#include <map>
	using namespace std;
	int main()
	{
	int tc;
	scanf("%d",&tc);
	while(tc--)
	{
	int n;
	scanf("%d",&n);
	int arr[n];
	int cnt = 0;
	for(int i = 0; i < n; ++i)
	{
	scanf("%d",&arr[i]);
	}
	for(int i = 0; i < n; ++i)
	{
	for(int j = i + 1; j < n; ++j)
	{
	if(arr[i] > arr[j])
	cnt++;
	}
	}
	printf("%d\n",cnt);
	}
	}

view raw INVCNT(Naive).cpp hosted with ❤ by GitHub

จากแนวคิดข้างบน เมื่อ n มีค่ามากขึ้น algorithm เราจะช้ามาก big o ของ algorithm นี้ คือ O(n^2)

เราจะทำให้ดีขึ้นกว่านี้ได้อย่างไร 

ถ้าเรามอง Algorithm ข้างบนดีๆ เราจะเห็นว่ามันคือ การ sort ตัวเลขใน array  เราสามารถ sort ให้ไวขึ้นโดยใช้ Algorithm ที่ชื่อ ว่า merge sort และเมื่อ n มากๆ big o ของ algorithm นี้คือ O(nlog n) ซึ่งถือว่าไวกว่า O(n^2) พอสมควร
ทำไม merge sort ถึงเวิค
ถ้าเรามี A = {2,3,8,6,1}
merge sort จะแยก 2 3 8 6 1 ออกจากกัน แล้วเปรียบเทียบทีละคู่ 2 กับ 3 เรียงแล้ว 8 กับ 6 ยังไม่เรียงเราก็เรียงเป็น 6,8 ตอนนี้ A จะเป็น 2,3  8,6  1 เราเปรียบเทียบ 8,6 กับ 1 จะได้ใหม่เป็น 1,6,8
A จะกลายเป็น 2,3  1,6,8 เปรียบเทียบ 2,3  กับ  1,6,8  เราจะได้เป็น 1,2,3,6,8

แต่ละครั้งที่เราเปรียบเทียบ เราจะรู้ว่ามีฝั่งขวาที่มากกว่าฝั่งซ้ายกี่ตัว

	#include <iostream>
	#include <iomanip>
	#include <cstring>
	#include <cmath>
	#include <cstdio>
	#include <algorithm>
	#include <vector>
	#include <climits>
	#include <stack>
	#include <queue>
	#include <sstream>
	#include <map>
	using namespace std;
	static long long cnt = 0;
	int MAX = 200000;
	void merge_sort(int arr[],int low,int mid,int high)
	{
	int l = low;
	int h = mid + 1;
	int k = low;
	int temp[MAX];
	while(l <= mid && h <= high)
	{
	if(arr[l] > arr[h])
	{
	temp[k] = arr[h];
	cnt += (mid - l) + 1;
	h++;
	}
	else
	{
	temp[k] = arr[l];
	l++;
	}
	k++;
	}
	if(l > mid)
	for(int i = h; i <= high; ++i)
	temp[k++] = arr[i];
	else
	for(int i = l; i <= mid; ++i)
	temp[k++] = arr[i];
	for(int i = low; i <= high; ++i)
	arr[i] = temp[i];
	}
	void partition(int arr[],int low,int high)
	{
	int mid = (low + high) / 2;
	if(low < high)
	{
	partition(arr,low,mid);
	partition(arr,mid + 1,high);
	merge_sort(arr,low,mid,high);
	}
	}
	void printArr(int *p,int n)
	{
	for(int i = 0; i < n; ++i)
	{
	printf("%d ",*(p+i));
	}
	printf("\n");
	}
	int main()
	{
	int tc;
	scanf("%d",&tc);
	while(tc--)
	{
	int n;
	cnt = 0;
	scanf("%d",&n);
	int arr[n];
	for(int i = 0; i < n; ++i)
	{
	scanf("%d",&arr[i]);
	}
	partition(arr,0,n - 1);
	printf("%lld\n",cnt);
	}
	}
	//g++ main.cpp -o main && timeout 2s ./main < inputf.in > outputf.out

view raw INVCNT(mergesort).cpp hosted with ❤ by GitHub

บรรทัดที่ 27 จะหาจำนวนตัวฝั่งซ้ายที่มากกว่าฝั่งขวา