Algorithmist - Recent changes [en]

Programming Contest Calendar

217.66.146.81 — Sun, 05 Sep 2010 09:29:49 GMT

← Older revision		Revision as of 09:29, 5 September 2010
Line 2:		Line 2:
	== Short-term Contests ==		== Short-term Contests ==
	* {{timeanddate\|2010\|09\|04\|09\|00}} [http://uva.onlinejudge.org/index.php?option=com_content&task=view&id=2&Itemid=10 Another National Programming Contest]		* {{timeanddate\|2010\|09\|04\|09\|00}} [http://uva.onlinejudge.org/index.php?option=com_content&task=view&id=2&Itemid=10 Another National Programming Contest]
		+	* {{timeanddate\|2010\|09\|10\|15\|00}} [http://codeforces.com Codeforces Beta Round #27 (Codeforces format, Div. 2)]

	== Long-term Contests ==		== Long-term Contests ==

Larry — Thu, 02 Sep 2010 20:16:38 GMT

minor edits.

← Older revision		Revision as of 20:16, 2 September 2010
Line 5:		Line 5:

	== Summary ==		== Summary ==
-	Get the F(n) Fibonacci's Number then get ~~it's~~ modulo on 2^m.	+	Get the F(n) Fibonacci's Number then get its modulo on <math>2^m</math>.

	== Explanation ==		== Explanation ==

Belbesy — Thu, 02 Sep 2010 17:07:17 GMT

← Older revision		Revision as of 17:07, 2 September 2010
(6 intermediate revisions not shown)
Line 5:		Line 5:

	== Summary ==		== Summary ==
-	Get the F(n) Fibonacci's Number then get it's modulo on 2^m~~. use the [[Q-Fibonacci Matrix]] to avoid TLE~~.	+	Get the F(n) Fibonacci's Number then get it's modulo on 2^m.

	== Explanation ==		== Explanation ==
-	#Solving this problem requires you to calculate Fibonacci in lg(n) time. It's by dividing n into n/2 size at each instance. ~~using the[[Q-Fibonacci Matrix]]~~	+	Solving this problem requires you to calculate Fibonacci in lg(n) time. It's by dividing n into n/2 size problem at each instance.

	== Gotchas ==		== Gotchas ==
	*Use a 64 bit integer representation for the Fibonacci's number as a 32 bit will overflow.		*Use a 64 bit integer representation for the Fibonacci's number as a 32 bit will overflow.
		+	*Use the [[Q-Fibonacci Matrix]] to get the output in O(log n) and avoid TLE.

	== Input ==		== Input ==
Line 23:		Line 24:
	25		25
	</pre>		</pre>
		+
		+	== Code ==
		+
		+	http://snipt.org/kgogl
		+

	[[Category:UVa Online Judge\|10229]]		[[Category:UVa Online Judge\|10229]]
	[[Category:Math]]		[[Category:Math]]

Belbesy — Thu, 02 Sep 2010 15:44:34 GMT

New user account

New page

41.129.5.185 — Thu, 02 Sep 2010 15:43:43 GMT

Explanation:

← Older revision		Revision as of 15:43, 2 September 2010
(4 intermediate revisions not shown)
Line 1:		Line 1:
-	Solving this problem requires you to calculate Fibonacci in lg(n) time. It's by dividing n into n/2 size at each instance. Another tweak which can be used in this problem was to store Fibonacci upto 10^6(mod 2^m) where m is maximum modulus. To find Fn(mod 2^k) where k <m, use this formula that	+	[[Category:Math]]

-	~~((fib(n)%t + (1<<m)%t)%t)%t where t is 2^k~~. ~~It is based on fact that if a number '''n''' is stored some modulus '''k''' and u want to know '''num%m''' where m < k~~. ~~Then, it's given by~~	+	== 10229 - Modular Fibonacci ==
		+	*http://online-judge.uva.es/p/v102/10229.html

-	''' (n~~%m + k%m~~)~~%m''' ''Italic text~~''	+	== Summary ==
		+	Get the F(n) Fibonacci's Number then get it's modulo on 2^m. use the [[Q-Fibonacci Matrix]] to avoid TLE.
		+
		+	== Explanation ==
		+	#Solving this problem requires you to calculate Fibonacci in lg(n) time. It's by dividing n into n/2 size at each instance. using the[[Q-Fibonacci Matrix]]
		+
		+	== Gotchas ==
		+	*Use a 64 bit integer representation for the Fibonacci's number as a 32 bit will overflow.
		+
		+	== Input ==
		+	<pre>
		+	11 7
		+	11 6
		+	</pre>
		+	== Output ==
		+	<pre>
		+	89
		+	25
		+	</pre>
		+
		+	[[Category:UVa Online Judge\|10229]]
		+	[[Category:Math]]

218.28.91.237 — Wed, 01 Sep 2010 14:25:01 GMT

Output:

Priyanka.chatterjee — Wed, 01 Sep 2010 06:42:12 GMT

New user account

New page

70.238.202.216 — Wed, 01 Sep 2010 01:54:29 GMT

Output2:

Saiful islam — Tue, 31 Aug 2010 16:06:32 GMT

New user account

New page