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 ได้แบบนี้

ซึ่งก็คือ 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

จาก 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)

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] ที่น้อยกว่า

จากแนวคิดข้างบน เมื่อ 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

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


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

Project Euler 016: Power digit sum

โจทย์จาก : www.hackerrank.com
2^9 =  512  sum of its digits is 5 + 1 + 2 = 7 what is the sum of digits of  number 2^N
Input Format 
The first line contains an integer  , i.e., number of test cases. 
Next  lines will contain an integer .
Output Format 
Print the values corresponding to each test case.

Constraints
1<=T<=100
1<=N<=10000

แนวคิด
เนื่องจาก 2^N N สามารถมีค่ามากถึง 10000 ซึ่งไม่สามารถเก็บไว้ใน int หรือ long ได้ วิธีทำข้อนี้เราอาจจะใช้ Big Int เข้ามาช่วยหรือใช้ภาษาที่มี Big int ให้เรียกใช้ หรือไม่ก็ใช้แนวคิดการคูณเลขสมัยประถมเข้ามาแก้ก็ได้เหมือนกัน ในที่นี้ผมจะใช้วิธีการคูณเลขเข้ามาช่วย ผมสร้าง array ขนาดประมาณ5000 ช่องตัวนึงขึ้นมา array ตัวนี้จะเก็บผลคูณแต่ละหลัก โดนที่ array นี้จะเก็บจากหน้าไปหลัง เช่นถ้าเรามีเลข 128 array ของเราจะเก็บ [8,2,1,0,0,0,0,...] ทุกครั้งที่เราเอาเลข 2 ไปคูณแต่ละหลักค่าที่ได้อาจจะมากกว่า 10 หรือ น้อยกว่า 10 ก็ได้ แต่ในการคูณแต่ละหลักค่ามากสุดที่จะได้คือ 2*9 = 18 นั่นแสดงให้เห็นว่าเราจะได้ตัวเลข 2 ตัวคือตัว ทด กับ ตัวที่เป็นคำตอบของหลักนั้นๆ ถ้าคูณการในหลักแล้วได้ไม่ถึง 10 ตัวทดของเราก็จะเป็น 0 นั่นหมายความว่า ตัวทด = ผลคูณ/10 ส่วนคำตอบของหลัก = ผลคูณ % 10 นี่คือแนวคิด algorithm การคูณ แต่ว่าในการคูณแต่ละครั้งเราต้องคูณถึง 5000 รอบซึ่งถือว่าเสียเวลามาก ผมเลยหาว่าแต่ละรอบที่ 2 ยกกำลังมากขึ้นเรื่อยๆ จะมีกี่หลัก เพื่อที่จะทำให้ไวขึ้น โดยเราสามารถหาได้จาก จำนวนหลัก = (N*ln(2))/ln(10) และเพื่อทำให้โปรแกรมเราไวขึ้นเราสามารถเรียก N เป็น 10000 เพราะว่าเมื่อ N เป็น 10000 N ตั้งแต่ 1 ถึง 9999 ก็จะต้องถูกหาออกมาด้วย ในแต่ละรอบที่หา N มาได้ผมก็จะเก็บผลบวกไว้ลงไปใน array sum เหมือนเป็นการคิดคำตอบล่วงหน้าเอาไว้

สามารถเอาแนวคิดเขียนเป็นโค้ดได้แบบนี้ 

Lattice Path

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a  grid? As number of ways can be very large, print it modulo (10^9 +7)

Constraints 

1 ≤ T ≤ 1000
1 ≤ N ≤ 500
1 ≤ M ≤ 500

โจทย์ข้อนี้ต้องการให้เราหาว่า ถ้าเราเริ่มจากจุดบนสุดฝั่งซ้ายลงจุดล่างสุดฝั่งขวา จะทำได้กี่วิธี ซึ่งถ้าดูแล้วเป็นโจทย์ที่ดูค่อนข้างจะง่าย เพราะสามารถใช้เรื่อง combinatorics เข้ามาแก้ได้ (N+M)!/(N!M!)
แต่ว่า  N กับ M อาจจะเป็นได้ถึง 500 ซึ่งค่าเยอะมาก ผมเลยไม่ได้ใช้สูตรนี้เข้ามาแก้ เมื่อผมลองมองหาวิธีอื่น ผมก็นึกถึง dynamic programming ผมเลยลองคิดว่าถ้าสี่เหลี่ยมขนาด 1*1 จะมีได้กี่วิธี และถ้า 2*1 จะมีได้กี่วิธี ผมลองเพิ่มหลักไปเรื่อยๆจนเป็น 1*6 แล้วลองเพิ่มแถวเป็น 2*1 3*1 ... 6*1 จนผมได้ตารางออกมา

ตอนแรกตารางนี้ไม่ได้มีแถวหรือหลักที่มี 1 แต่เมื่อผมเขียนตาราง 6*6 ออกมาแล้ว วิธีที่ M*N จะทำได้มีค่าเท่ากับ 
DP[i][j] = DP[i-1][j] + DP[i][j-1]  เช่นถ้าผมอยากรู้ว่า 1*1 ทำได้กี่วิธี

ผมสามารถหาได้จาก DP[1][1] = DP[0][1] + DP[1][0] , DP[0][1] = 1 DP[1][0] = 1 DP[1][1] จึงเท่ากับ 2 แต่ว่าโจทย์ข้อนี้เราต้องระวังเพราะเขาต้องการให้เรา mod(10^9+7) เพราะฉะนั้นในการสร้างตารางเราจะต้องทำการ mod ไม่ให้ค่าเกิน 10^9 +7 

( (a+b)%m = (a%m + b%m)%m) 

เราสามารถเอาไอเดียนี้เขียนเป็นโค้ดได้ 

สามารถไปลองทำกันได้ที่ www.hackerrank.com

Project Euler 014 - Longest Collatz sequence

โจทย์จาก : https://www.hackerrank.com/contests/projecteuler/challenges/euler014

ลำดับ Collatz สามารถสร้างได้โดย 3 เงื่อนใข 1.ถ้า n = 1 ให้ หยุด

                                   2.ถ้า n เป็นเลขคู่ ให้ n/2
                                   3.ถ้า n เป็นเลขคี่ ให้ 3n+1
เช่น n = 13 ลำดับก็จะเป็น 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 เมื่อ n = 13 ลำดับนี้จะมีความยาว = 10  โจทย์ข้อนี้ต้องการให้เราหาความยาวของลำดับที่มากที่สุด ที่ถูกสร้างโดยเลขที่ <= n
นั่นหมายความว่า ถ้า n เป็น 13 เราจะต้องไล่หาลำดับของ 13 , 12 , 11 ,10 ,...,1 แล้วดูว่าลำดับไหนมีความยาวมากที่สุด

แนวคิด ถ้ามองโจทย์ดีๆแล้วเมื่อเราสร้าง Collatz ของ 13 เราจะสร้างของ 40,20,10,5,16,8,2,1 เช่นเดียวกัน เพราะฉะนั้นเราสามารถใช้เทคนิคการ Memoization เข้ามาช่วยได้ จะทำให้เราสามารถหาลำดับ Collatz ได้ไวขึ้นมาก เมื่อเราหาได้แล้วเราจะต้องไล่ตั้ง 1 จนถึง n เพื่อหาว่าตัวไหนมากสุด แต่ถ้าหากคิดดีๆแล้ว
ถ้าเราจำค่าความยาวที่มากสุดแล้วนำไปเปรียบเทียบกับตัวถัดไปเรื่อยๆ เราก็สามารถทำการ precompute ทุกคำตอบได้เหมือนกัน

Project Euler 003 - Largest Prime factor - การหา prime factor ที่ใหญ่ที่สุด

โจทย์จาก : https://www.hackerrank.com/contests/projecteuler/challenges/euler003

โจทย์ข้อนี้ต้องการให้เราหาจำนวนเฉพาะที่ใหญ่ที่สุด และเป็นตัวประกอบของ N โดย
ที่ 10 <=N<= 10^12 
แนวคิด เมื่อผมเห็นข้อนี้ สิ่งที่ผมคิดไว้ตอนแรกคือการรันลูปไล่ตั้งแต่ 2 จนถึง N/2 เพื่อหาตัวที่หารลงตัว เมื่อได้ตัวที่หารลงตัว ก็นำไปเช็คต่อว่าเป็นจำนวนเฉพาะไหม แต่ถ้าลองคิดดีๆแล้วการที่ N มีค่าเยอะๆ แล้ว factor ของ N มีจำนวนเฉพาะที่ค่าเยอะ ก็จะเสียเวลาในการเช็คอย่างมาก ผมก็เลยนึกถึงการหา factor สมัยตอนมัธยมต้น เพราะเนื่องจากจำนวนเต็มบวกสามารถเขียนอยู่ในรูปผลคูณ
ของจำนวนเฉพาะได้

จากรูปด้านบน คือการหา factor ของ 160 เราเริ่มจากเอา 2 ซึ่งเป็นจำนวนเฉพาะที่เล็กที่สุด ที่สามารถหาร 160 ได้ไปหารจนกว่าจะหารไม่ได้ หากเราทำการหารด้วยจำนวนเฉพาะจนกว่าจะหารไม่ได้ไปเรื่อยๆแล้วๆ สุดท้ายแล้วเราก็จะได้จำนวนเฉพาะที่ใหญ่ที่สุดออกมา (จำนวนเฉพาะที่เล็กที่สุด ของจำนวนประกอบ N ใดๆ จะมีค่าน้อยกว่าหรือเท่ากับ sqrt(N))

เราสามารถนำแนวคิดนี้ไปเขียนเป็นโค้ดในภาษาซีได้แบบนี้