User Tools

Site Tools


contest_2011-09-27

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Next revision
Previous revision
contest_2011-09-27 [2011/09/22 12:50] – created jtkorbcontest_2011-09-27 [2011/09/27 11:00] (current) jtkorb
Line 10: Line 10:
 ===== Problems ===== ===== Problems =====
  
-  * A: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=31&page=show_problem&problem=1023|WERTYU]]+  * A: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=35&page=show_problem&problem=1051|Light, More Light]] 
 +  * B: [[Prelude One to Carmichael Numbers -- Primality Testing]] 
 +  * C: [[Prelude Two to Carmichael Numbers -- Efficient Power Mod]] 
 +  * D: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=35&page=show_problem&problem=947|Carmichael Numbers]] 
 +  * E: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=35&page=show_problem&problem=1045|Euclid Problem]] 
 +  * F: [[Prelude to Factovisors]] 
 +  * G: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=35&page=show_problem&problem=1080|Factovisors]] 
 +  * H: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=35&page=show_problem&problem=1030|Repackaging]]
  
 //Remember:// If you've already solved one or more of these problems, try (1) solving again without referring to your old solution, and/or (2) using a different language (Java or C++).  If you want to work on an additional problem from the book, let [[jtk@purdue.edu|me]] know. //Remember:// If you've already solved one or more of these problems, try (1) solving again without referring to your old solution, and/or (2) using a different language (Java or C++).  If you want to work on an additional problem from the book, let [[jtk@purdue.edu|me]] know.
Line 16: Line 23:
 **Hints:** **Hints:**
  
-  * A: One solution is to create mapping from mistyped characters to the corresponding correct character. +  * A: Find a pattern.  The solution is extremely short and efficient. 
 +  * B: Repeated divisions is fine (be sure to skip even numbers after 2 and only test as large as necessary). 
 +  * C: Observe that, if ''k'' is even, ''n ^ k mod p'' is ''(n ^ (k/2) mod p) ^ 2 mod p'' Generalize and handle the case for ''k'' odd. 
 +  * D: Combine the two preludes. 
 +  * E: The Extended Euclid Algorithm for GCD (given in the text), given in the text, solves this problem directly. 
 +  * F: Brute force factorization is fine.  You'll want to keep table of ''(p,e)'' pairs for each prime, ''p'', that divides ''e'' times. 
 +  * G: Theorem: The highest power of ''p'' that divides ''n!'' is ''n/p + n/p^2 + n/p^3 ...'' So, ''p^e'' divides ''n!'' if this sum is at least ''e'' before ''n/p^k'' reaches 0. 
 +  * H: The text suggests using the Diophantine solution method given there.  Note that you don't actually need to compute the solution, just determine whether or not a solution exists.
contest_2011-09-27.1316721055.txt.gz · Last modified: 2011/09/22 12:50 by jtkorb