Competitive/Collaborative Programming Class

ICPC Computer Programming Contest Prep

Problem Solving in Computer Science

Fall 2012 -- CSC 2700 Section 02

[Isaac's Home Page ]  [Mailing List ]  [Class Page ]  [Printable ]  
 Home
 Outline/Policy
 Summary
 Approach
 References
 
 Homework
   View
   Upload
 
 Problems:
   Archive
   Archive Mirror
   Categories
   Guidelines
 
 Coding
   Tips
 
 Contests:
   Regional
   NA Qualifier
 
 Extra:
   Grades
 
 
 
 Class:
   CSC 2700 Section 02
   Tureaud Hall 101
   Tuesday
   6:30 PM - 8:20 PM
 
 Previous:
   2012 Spring
   2011 Fall
 

Number Theory

To borrow from Programming Challenges, number theory in programming contests includes the following:

  • Prime Numbers
  • Divisibility
  • Modular Arithmetic

References


Primes

In general, I believe 99% of dealing with primes in a problem boils down to loading a list with the first N prime numbers via the Sieve of Erasthones:

    primeCnt = 0;
    for (i=0; i< UPPERLIMIT; i++) a[i] = i;
    for (i=2; i<UPPERLIMIT; i++)
     { /* for */
        if (0 != a[i])
         { /* found a prime */
            p[primeCnt] = i;
            primeCnt++;
            for (j=i*2; j < UPPERLIMIT; j=j+i) a[j] = 0;
         } /* found a prime */
     } /* for */ 

Of course, what do you do with the list? Using it to determine prime factors might be common.


Divisibility

In one sense divisibility is easy -- use mod. Here are some neat rules for divisibility:

  • 2 - even, number is divisible if last digit is
  • 3 - if repeated sum of digits is 3, 6, or 9 then number is divisible by 3
  • 4 - if last 2 digits are divisible by 4
  • 5 - ends in 0 or 5
  • 6 - both rules 2 and 3 are true
  • 7 - don't know
  • 8 - last 3 digits are divisble by 8
  • 9 - sum of digits is 9


Modular Arithmetic

Modular arithmetic is sometimes called clock arithmetic. It is the idea that the set of numbers is finite and that you wrap to the begining when you go past the end (like a clock does). Lots of problems rely on these ideas (such as the "every nth person out" problems).

A typical code snippet might be something like:

n = (n + 1) mod MAX

When you think about it, this is how all arithmetic works. 9 + 1 = 10 When you add one to the largest base 10 digit (9) you get zero for an answer with a carry into the next column. You do the same in modular arithmetic except for forget the carry.





[ Powered by Red Hat Linux ] [ Powered by Apache ] [ Powered by PHP ]

The statements and opinions included in these pages are those of only. Any statements and opinions included in these pages are not those of Louisiana State University or the LSU Board of Supervisors.
© 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012 Isaac Traxler