Summary of Class - 03

[svm11]

Here is a summary of the class that took place on 17th June, 2013 and the references you will needing.

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Problem Fibsieve`s Fantabulous Birthday. Here is a sample C solution.

#include <stdio.h>
#include <math.h>
#define LL long long int

int main() {
	int t, T;
	LL S, A, B, x, y; 
	scanf("%d", &T);
	for (t = 1; t <= T; ++t) {
		scanf("%lld", &S);
		A = ceil(sqrt(S));
		B = 1 + A * (A - 1);
		if (A % 2 == 0) {
			if (S <= B) x = A - (B - S), y = A;
			else x = A, y = A - (S - B);
		}
		else {
			if (S <= B) x = A, y = A - (B - S);
			else x = A - (S - B), y = A;
		}
		printf("Case %d: %lld %lld\n", t, x, y);
	}
	return 0;
}

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Problem Eid. Here is a sample JAVA code. Only the crux of the actual solution. The solve() function in Class Eid solves a particular test case.

class Eid {
    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int count = in.readInt();
        int[] primeExponents = new int[10010];
        for (int i = 1; i <= count; ++i) {
            int x = in.readInt();
            for (int divisor = 2, exponent; divisor * divisor <= x; ++divisor) {
                for (exponent = 0; x % divisor == 0; ++exponent, x /= divisor);
                primeExponents[divisor] = Math.max(primeExponents[divisor], exponent);
            }
            if (x > 1) primeExponents[x] = Math.max(primeExponents[x], 1);
        }
        StringBuilder res = new StringBuilder("1");
        for (int i = 2; i < primeExponents.length; ++i) {
            for (int j = 0; j < primeExponents[i]; ++j) {
                int carry = 0;
                for (int k = 0; k < res.length(); ++k) {
                    carry += (res.charAt(k) - '0') * i;
                    res.setCharAt(k, (char) (carry % 10 + '0'));
                    carry /= 10;
                }
                while (carry > 0) {
                    res.append((char) (carry % 10 + '0'));
                    carry /= 10;
                }
            }
        }
        out.println("Case " + testNumber + ": " + res.reverse().toString());
    }
}
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Problem LCMSUM.
Problem LCMEXTREME. (You can see the problem statement in the PDF here.)
Solutions to these will be discussed only on demand.
Some more problems form the contest.
Use the below mentioned links to find more problems.
http://uvatoolkit.com/problemssolve.php
http://problemclassifier.appspot.com/
There are problems at the end of Topcoder tutorials too posted next.

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Resources:
Topcoder Tutorial 1
Topcoder Tutorial 2
Chapter 31 from Introduction to Algorithms
Googling Wiki should be easy now for all the terms mentioned in the class, i.e, 
GCD
Euclid's Algorithm
Extended Euclid's Algorithm
LCM
Prime/Composite
Co-Prime
Prime Factorization
Sieve of Eratosthenes
Euler Totient Function
Euler's Theorem
Fermat's Theorem
Chinese Remainder Theorem
Modular Theory
Exponentiation by Squaring
Inverse Modulo
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
USACO is back online. Do chapter 1 from it. 
Do tasks mentioned in summary 01 and summary 02. 
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Post as many problems as you can find based on number theory collectively from various places so that others can practice too. If you get stuck post on the group the problem statement, your approach clearly, and possibly code formatted in html with an ideone link to the same. Even if you are feeling too lazy to post so many things, just post the link to the problem statement. I need to practice more on number theory.
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
For the next class I will take up dynamic programming. Read up the theory from Introduction to Algorithms and Topcoder Algorithm Tutorials.
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

I wrote the summary in a hurry. If I missed a topic post it up here.  

[svm11]

Hah! I messed up the date. 

It took place on 25th June, 2013.