ผู้ใช้:Pattara.S

Freivalds' Algorithm (กระดาษทด)

Freivalds' Algorithm เป็นขั้นตอนวิธีแบบสุ่ม (Randomized algorithm) ที่ใช้สำหรับตรวจสอบความเท่ากันของ ผลคูณของเมทริกซ์ กับเมทริกซ์ต้นแบบซึ่งขั้นตอนวิธี (Algorithm) นี้ถูกนำเสนอโดย Rusins Martins Freivalds นักวิทยาศาสตร์ชาวลัตเวีย

ขั้นตอนวิธี

ข้อมูลนำเข้า (Input)

เมทริกซ์จตุรัส 3 เมทริกซ์ มีขนาด $n\times n$ ได้แก่ $A,B,C.$

ข้อมูลส่งออก (Output)

ตอบ ใช่ ถ้า $A\times B=C$

ตอบ ไม่ใช่ ถ้า $A\times B\neq C$

วิธีการ (Procedure)

1. สุ่ม เวกเตอร์ ${\vec {r}}$ ขนาด $n\times 1$.
2. คำนวณ ${\vec {P}}=A\times (B{\vec {r}})-C{\vec {r}}$.
3. ตรวจสอบว่า${\vec {P}}$ เป็นเวกเตอร์ศูนย์หรือไม่ คืนค่า ใช่ ถ้า${\vec {P}}$ เป็นเวกเตอร์ศูนย์ คืนค่า ไม่ใช่ถ้า${\vec {P}}$ ไม่ได้เป็นเวกเตอร์ศูนย์

รหัสเทียม (pseudo code)

bool Freivalds(int a[][],int b[][],int c[][], int n){
	// return true if axb=c
	// false otherwise
	int *r=(int *)malloc(sizeof(int)*n);
	for(int i=0;i<n;i++){
		r[i]=rand()&1;
	}
	int *br=(int *)malloc(sizeof(int)*n);
	int *cr=(int *)malloc(sizeof(int)*n);
	// br denote bxr and cr denote cxr
	for(int i=0;i<n;i++){
		br[i]=cr[i]=0;
		for(int j=0;j<n;j++){
			br[i]+=b[i][j]*r[j];
			cr[i]+=c[i][j]*r[j];
		}
	}
	int *abr=(int *)malloc(sizeof(int)*n);
	// abr denote ax(bxr)
	for(int i=0;i<n;i++){
		abr[i]=0;
		for(int j=0;j<n;j++){
			abr[i]+=a[i][j]*br[j];
		}
	}
	for(int i=0;i<n;i++){
		if(abr[i]!=cr[i])return false;
	}
	return true;
}

ความซับซ้อนเชิงเวลา ([Time complexity])

ทำงานใน O(n²) ซึ่งเร็วกว่าการคูณเมทริกซ์แล้วเปรียบเทียบทีละตัว (ทำงานใน O(n³) ) รวมถึงเร็วกว่า [ขั้นตอนวิธีของ Coppersmith-Winograd] ซึ่งเป็นขั้นตอนวิธีในการหาผลคูณของเมทริกซ์ที่เร็วที่สุดในปัจจุบัน (ทำงานใน O(n^2.376)) มาก

วิเคราะห์ความผิดพลาด

ขั้นตอนวิธีนี้รับประกันว่า ถ้า $A\times B=C$ แล้วความน่าจะเป็นในการตอบผิดจะเป็น 0, ถ้า $A\times B\neq C$ แล้วความน่าจะเป็นในการตอบผิดมีค่าไม่เกิน ${\frac {1}{2}}$

• พิจารณากรณีที่ $A\times B=C$

${\vec {P}}=A\times (B{\vec {r}})-C{\vec {r}}={\vec {0}}$ สำหรับทุก ${\vec {r}}$ ที่เป็นไปได้ดังนั้นความน่าจะเป็นในการตอบผิดเป็น 0

• พิจารณากรณีที่ $A\times B\neq C$

กำหนดให้ ${\vec {D}}=A\times B-C$ เนื่องจาก $A\times B\neq C$ แสดงว่าจะมีค่า i,j บางค่าที่ $d_{ij}\neq 0$

${\vec {P}}=A\times (B{\vec {r}})-C{\vec {r}}=D{\vec {r}}={\begin{bmatrix}p_{1}&p_{2}&p_{3}&\cdots &p_{n}\end{bmatrix}}$

$p_{i}=\Sigma d_{ij}\cdot r_{j}=d_{ij}+K$

โดย กฎของเบย์ (Bayes' theorem)

$Pr[p_{i}=0]=Pr[p_{i}=0|K=0]\cdot Pr[K=0]+Pr[p_{i}=0|K\neq 0]\cdot Pr[K\neq 0]$

$Pr[p_{i}=0|K=0]=Pr[r_{j}=0]={\frac {1}{2}}$

$Pr[p_{i}=0|K\neq 0]<=Pr[r_{j}=1]={\frac {1}{2}}$

$Pr[p_{i}=0]<={\frac {1}{2}}\cdot Pr[K=0]+{\frac {1}{2}}\cdot Pr[K\neq 0]$

$Pr[p_{i}=0]<={\frac {1}{2}}\cdot Pr[K=0]+{\frac {1}{2}}\cdot (1-Pr[K=0])$

$Pr[p_{i}=0]<={\frac {1}{2}}$

เพราะฉะนั้น $Pr[{\vec {P}}={\vec {0}}]<=Pr[p_{i}=0]<={\frac {1}{2}}$

โจทย์ปัญหา

You and your friend are playing a game in which you and your friend take turns removing stones from piles. Initially there are N piles with a1, a2, a3,..., aN number of stones. On each turn, a player must remove at least one stone from one pile but no more than half of the number of stones in that pile. The player who cannot make any moves is considered lost. For example, if there are three piles with 5, 1 and 2 stones, then the player can take 1 or 2 stones from first pile, no stone from second pile, and only 1 stone from third pile. Note that the player cannot take any stones from the second pile as 1 is more than half of 1 (the size of that pile). Assume that you and your friend play optimally and you play first, determine whether you have a winning move. You are said to have a winning move if after making that move, you can eventually win no matter what your friend does.

ข้อจำกัดเชิงเวลา

โปรแกรมต้องสามารถทำงานจบภายในเวลา 3 วินาที

ข้อมูลนำเข้า

The first line of input contains an integer T (T100) denoting the number of testcases. Each testcase begins with an integer N (1N100) the number of piles. The next line contains N integers a1, a2, a3,..., aN (1ai2 * 1018) the number of stones in each pile.

ข้อมูลส่งออก

For each testcase, print ``YES" (without quote) if you have a winning move, or ``NO" (without quote) if you don‟t have a winning move.

ตัวอย่าง ข้อมูลนำเข้า/ข้อมูลส่งออก

ข้อมูลนำเข้า	ข้อมูลส่งออก
4 2 4 4 3 1 2 3 3 2 4 6 3 1 2 1	NO YES NO YES

แนวคิด

โจทย์ปัญหาข้อนี้ เป็นโจทย์เกี่่ยวกับทฤษฎีเกม ซึ่งคล้ายคลึงกับ เกมนิม เพียงแต่ว่ามีการกำหนดในการหยิบหินแต่ละกองนั่นคือ สามารถหยิบหินออกจากกองได้ไม่เกินครึ่งหนึ่ง ของจำนวนหินในกองนั้น (ถ้ากองหินกองใด เหลือหินเพียงก้อนเดียวก็จะไม่สามารถหยิบหินจากกองนั้นได้) ดังนั้นปัญหาของโจทย์ข้อนี้คือ จะหาเลขกรันดี้ อย่างไรให้ดีพอที่จะตอบคำถามได้ในเวลาที่กำหนด

เลขกรันดี้ ของกองหินขนาดต่างๆ

ขนาดของกองหิน	1	2	3	4	5	6	7	8	9	10
เลขกรันดี้	0	1	0	2	1	3	0	4	2	5

• ข้อสังเกตแรก $Grundy(x)=x/2;xiseven$
• ข้อสังเกตที่สอง $Grundy(x)=Grundy(x/2);xisodd$
• จากข้อสังเกตสองข้อนี้ เราสามารถหาเลขกรันดี้ของกองหินขนาด n ได้ในเวลา O(lg(n))