6 May 2011 Comments Off

Tips and Tricks

- Chua Hock-Chuan (ehchua@ntu.edu.sg)

(C/C++) Avoiding “if (i=0) {…}” error – This is probably C++ Tips Number 1

If you are comparing with a constant, you could place the constant on the LHS (instead of the usual RHS). That is, instead of writing "if (i == 0) {...}“, write “if (0 == i) {...}“. The compiler will flag out a syntax error if you inadvertently write "if (0 = i) {...}". [Java introduces a new data type called boolean, which kills this problem.]

[Contributed by Nguyen Trung Nghia]

(C/C++/Java) switch is better than nested-if

Instead of writing:

if (0 == i)
   //do something
else if (1 == i)
   //do something
else if (2 == i)
   //do something
else if (3 == i)
   //do something
else
   //do something

It is better to write:

switch(i) {  // for int and char only
   case 0:
      //do something
      break;
   case 1:
      //do something
      break;
   case 2:
      //do something
      break;
   case 3:
      //do something
      break;
   default:
      //do something
}

[Contributed by Nguyen Trung Nghia]

(C/C++) The dreaded #define

Nghia recommends the following #define to speed up your programming in the contest:

#define REP(i,a) for(i=0;i<a;i++)
#define FOR(i,a,b) for(i=a;i<b;i++)
#define VE vector<int>
#define SZ size()
#define PB push_back

My Note: Beware of #define in normal programming. You could use #define to change the C++ language into C--, a useless language that only you can understand (in other words, this is not a good software engineering practice).

(C/C++/Java) Bit Manipulation

From http://en.wikipedia.org/wiki/Bit_manipulation:

To “set” a bit (where n is the bit number, and bit 0 is the least significant bit):

unsigned char a |= (1 << n);   // '|' is bitwise OR, '<<' is bit left-shift

To “clear” a bit:

unsigned char b &= ~(1 << n);  // '&' is bitwise AND

To “toggle” a bit:

unsigned char c ^= (1 << n);   // '^' is bitwise XOR

To “test” a bit:

unsigned char e = d & (1 << n); //d has the byte value.

(Training Problem) Prime Numbers

The simplest, most elegant algorithm is perhaps the sieve of Eratosthenes. This pseudo-code is given in http://en.wikipedia.org/wiki/Prime_number:

// arbitrary search limit
limit ← 1000000                   

// assume all numbers are prime at first
is_prime(i) ← true, i ∈ [2, limit] 

for n in [2, √limit]:
   if is_prime(n):
      // eliminate multiples of each prime,
      // starting with its square
      // 2n, 3n, ..., (n-1)n already eliminated
      // nn, (n+1)n, (n+2)n, ... to be eliminated
      is_prime(i) ← false, i ∈ {n^2, n^2+n, n^2+2n, ..., limit}

for n in [2, limit]:
   if is_prime(n): print n

Nghia wrote: with this simple algorithm, you can solve quite a number of problems in acm.uva.es. You should use bit operations to reduce the size of memory used.

  • http://acm.uva.es/p/v1/136.html (warming up)
  • http://acm.uva.es/p/v1/160.html
  • http://acm.uva.es/p/v4/406.html
  • http://acm.uva.es/p/v5/583.html
  • http://acm.uva.es/p/v103/10394.html
  • http://acm.uva.es/p/v105/10539.html
  • http://acm.uva.es/p/v108/10858.html
  • http://acm.uva.es/p/v108/10856.html (this problem needs prime generator + very simple DP + very useful and basic search technique)

(Training Problem) To find B^P mod M

B^P means B raise to the power of P. B and P are integers in the range 0 to 2147483647 inclusive. M is an integer in the range 1 to 46340 inclusive.

Hint:

  • P = a0 x 2^0 + a1 x 2^1 + a2 x 2^2 + a3 x 2^3 + … + an x 2^n (n<32)
  • Find B^a0 mod m, B^a1 mod m, B^a2 mod m, B^a3 mod m, …, B^an mod m (32 term only)
  • B^ai mod m can be found by using the result from B^aj mod m, j = i – 1 (this is called Dynamic Programming)
  • Please remember (axb) mod m = ((a mod m) x (b mod m)) mod m (to avoid overflow errors)
  • The complexity of this algorithm is log(P)
  • try to make your source code as short as possible. In order to do that, you may need to use bit operation and only one for/while loop.

Try these problems:

  • http://acm.uva.es/p/v3/374.html
  • http://online-judge.uva.es/p/v102/10229.html ( try to represent f[n] as = [ a b ; c d ]^n )
Tags: , ,
6 May 2011 Comments Off

Step by Step..ACM ICPC

Step by Step..ACM ICPC

- Chua Hock-Chuan (ehchua@ntu.edu.sg)
Step 1 – Try PKU Online Judge

  1. Register with PKU online judge @ http://acm.pku.edu.cn/JudgeOnline/.
  2. Read the FAQ to understand to submission rules – IMPORTANT!
  3. Read the FAQ AGAIN.
  4. The programming rules for ICPC are:Java Language
    • Input comes form System.in and output goes to System.out (no File IO allowed).
    • The source file must contain a class called Main with the entry-method main:
      public static void main(String[] args) { ... }.

    C++ Language

    • Input comes form std:cin and output goes to std:cout (no File IO allowed).
    • The source file must contain the entry-function int main() { ... }.
  5. Try the first problem “1000 (A+B)” with the solution provided in FAQ. The purpose of this problem is to let you understand the above programming rules. In your submission, make sure you specify the language used (“Java”, “G++” for GNU C++ compiler, or “C++” for VC6 compiler).For Java programmers
    You should program at JDK 1.5 or above. Use Scanner, in.nextInt(), in.nextDouble(), in.next() for inputting int, double, and String, and C-like System.out.printf("formatString", args...) for output.
    JDK 1.5 Program Template for ICPC Online Judge

    import java.util.Scanner;
    
    public class Main {   // save as Main.java
       public static void main(String[] args) {
          Scanner in = new Scanner(System.in);
    
          int    i = in.nextInt();    // read int
          double d = in.nextDouble(); // read double
          String s = in.next();       // read String
          // There is no nextChar(), use next() and charAt()
          char c = s.charAt(2);
          // Read whole line (or rest of the line past '\n')
          String line = in.nextLine();
    
          System.out.printf("%4d, %6.2f, %s, %c\n", i, d, s, c);
          // Use %f for double (not %lf)
          // Don't forget to print the '\n'
       }
    }
    
  6. Try another few (extremely) simple problems (you can look at the percentages to estimate the difficulty of the problems)
    • Read the programming rules AGAIN before trying these problems.
    • You input and output must strictly follow the description given. You need not and CANNOT print input prompting message such as “Please enter a number” (because nobody is sitting at the online judging system to read these prompts).
    • Do “1004 (Financial Management)” – Simply averaging 12 numbers
      Hints: To test this program, you have two options: (a) key in the 12 numbers slowly, or (b) save the 12 numbers in a file, says “in.txt“, start a Command shell (“cmd“), and use the “pipe” operator “<” to re-direct the input from the file “in.txt” to the stdin as follows:
      For Java Programmers
      Assume that the source file is called Main.java

      > javac Main.java
      > java Main < in.txt
      

      For C++ programmers
      Assume that the source file is called test.cpp

      > g++ -o test.exe test.cpp
      > test < in.txt
      
    • “1003 (Hangover)” – Compute the sum of a harmonic series and compare…
    • “1005 (I think I need a house boat)” – Compute the area of a semi-circle and compare…

Step 2 – Try UVA Online Judge: This site is meant for C/C++ programmers. Java programmers can forget about this site (as there is no support for JDK 1.5). For C programs, you cannot use // comments.

  1. Register with UVA online judge @ http://online-judge.uva.es/problemset/.
  2. Read the HOWTOs, especially on how to submit solution.
  3. Try the first problem Volume 1 Problem 100 (3n+1) with the solution provided in HOWTOs.

The above steps are meant for you to familiarize with the contest process. Here come the “serious” training…

Step 3 – Try USACO Training Problem

  1. Register with USACO Training Program @ http://train.usaco.org/usacogate/.
  2. Read “Section 1.0 Text Introduction” and “Section 1.1 Submitting Solutions”.
    As mentioned, this site is meant for IOI instead of ICPC, the submission requirements are different from the online judges.
    You are required to read from an input file named “xxxx.in” and write to an output file named “xxxx.out” where “xxxx” is the name of the problem.
    Try the “First Challenge” (or “test” problem). If you encounter problem in File IO under VC++ or Eclipse, read “VC++ File Input/Output” or “Eclipse File Input/Output“, respectively.
    For Java programmers
    The sampled Java solution given is based on JDK 1.2, which is rather clumsy in IO processing. I provide the sample solution in JDK 1.5 is as follows:JDK 1.5 Program Template for USACO

    /*
    ID: yourID
    LANG: JAVA
    TASK: test
    */
    
    import java.util.Scanner;
    import java.util.Formatter;
    import java.io.File;
    import java.io.IOException;
    
    public class test {  // saved as test.java
       public static void main (String [] args) throws IOException {
          Scanner in = new Scanner(new File("test.in"));        // file input
          Formatter out = new Formatter(new File("test.out"));  // file output
    
          int a = in.nextInt();
          int b = in.nextInt();
          out.format("%d\n",a+b);  // format() has the same syntax as printf()
    
          out.close();    // flush the output and close the output file
          System.exit(0); // likely needed in USACO
       }
    }
    
  3. Continue and try to complete the training problem. As mentioned, this site provides systematic training for the frequently used algorithms encountered in contests (IOI as well as ICPC).

Read More: http://www.ntu.edu.sg/home/ehchua/programming/icpc/icpc_getting_started.html

Resources:

Training ICPC Teams: A Technical Guide
ACM International Collegiate Programming Contest
International Collegiate Programming Contest: Getting Started
Policies and Procedures for the ACM International Collegiate Programming Contest

Tags:
15 March 2011 Comments Off

Top Coder – Algorithm Tutorials

Q. How to do better in Contests?

A. Very nice place to start is the TopCoder Algorithm Tutorials. They have some very good articles. But at the end of the day, you will need to study a good book on algorithms. The most popular one is CLRS (“Introduction to Algorithms” by Cormen et. al.). I would also recommend “Algorithm Design” by Kleinberg and Tardos.

Also, sites like TopCoder, Google Code Jam and CodeForces have problem analyses and the code submitted during the contest available. Reading those is a great way learning new techniques and approaches.….

Writer                                         Tutorials

lbackstrom The Importance of Algorithms
antimatter How To Dissect a TopCoder Problem Statement
Dumitru How to Find a Solution
leadhyena_inran Planning an Approach to a TopCoder Problem:
Section 1
Section 2
dimkadimon Mathematics for TopCoders
lbackstrom Geometry Concepts:
Section 1: Basic Concepts
Section 2: Line Intersection and its Applications
Section 3: Using Geometry in TopCoder Problems
gladius Introduction to Graphs and Their Data Structures:
Section 1: Recognizing and Representing a Graph
Section 2: Searching a Graph
Section 3: Finding the Best Path through a Graph
supernova Greedy is Good
Dumitru Dynamic Programming: From novice to advanced
misof Computational Complexity
Section 1
Section 2
Dan[Popovici] & mariusmuja Using Regular Expressions
supernova Understanding Probabilities
timmac Data Structures
cucu New Features of Java 1.5
timmac Sorting
_efer_ Maximum Flow
Section 1
Section 2
misof Representation of Integers and Reals
Section 1
Section 2
lovro Binary Search
bmerry A bit of fun: fun with bits
danielp Range Minimum Query and Lowest Common Ancestor
DmitryKorolev Power up C++ with the Standard Template Library: Part I
DmitryKorolev Power up C++ with the Standard Template Library: Part II: Advanced Uses
medv Prime Numbers, Factorization and Euler Function
jmzero An Introduction to Recursion, Part 1
jmzero An Introduction to Recursion, Part 2
cpphamza An Introduction to Binary Search and Red-Black Trees
bmerry Line Sweep Algorithms
Zealint Minimum Cost Flow
Part 1 – Key Concepts
Part 2 – Algorithms
Part 3 – Applications
rasto6sk Algorithm Games
boba5551 Binary Indexed Trees
TheLlama Introduction to String Searching Algorithms
Zealint Maximum Flow: Augmenting Path Algorithms Comparison
x-ray Basics of combinatorics
NilayVaish A New Approach to the Maximum Flow Problem
vlad_D Disjoint-set Data Structures
luison9999 Using Tries
dcp An Introduction to Multidimensional Databases
zmij The Best Questions for Would-be C++ Programmers
Part 1
Part 2
innocentboy Primality Testing : Non-deterministic Algorithms
x-ray Assignment Problem and Hungarian Algorithm
16 February 2011 Comments Off

Useful Algorithm Concepts

Useful Algorithm Concepts

Recently, I found a nice article written by Kaiser Md. Nahiduzzaman, PhD student at UC.  The original article is available here: http://www.kaisernahid.com/files/Various.pdf. Here I quote part of it:

“A. Greedy algorithm
Some local optimum is chosen; when the algorithm terminates, we hope that the local optimum is equal to the global optimum.
Examples of Popular Greedy Algorithms: Dijkstra, Prim, Kruskal algorithm.
ACM Uva Examples: 10020, 10340, 10440
Real life example:
To make change in currency, repeatedly dispense the largest denomination. To give out sixty nine dollars we give out a fiftydollar bill, a tendollar bill, a fivedollar bill, two twodollar bills. In this way, we are guranteed to minimize the number of bills. That is, first consider the largest denominator in 69 which is 50 and the rest is 19. Now consider the largest denominator in 19 which is 10 and the rest is 9. Do it repeatedly.

B. Divide and Conquer
Divide: Smaller problems are solved recursively (except the base cases).
Conquer: Solution to the original problem is formed from the solutions to the subproblems.
The subproblems should be disjoint (nonoverlapping).
Examples: maximum subsequence sum problem, lineartime tree traversal strategies, mergesort, quicksort.

Running Time: T(N) = 2T(N/2) + O(N)
i.e O(N log N)

C. Dynamic Programming
A problem that can be mathematically expressed recursively can also be expressed as a recursive algorithm, yielding a significant performance improvement over a naive search. Any recursive mathematical formula could be directly translated to a recursive algorithm, but the underlying reality is
that often the compiler will not do justice to the recursive algorithm, and an inefficient program results. When we suspect that this is likely to be the case, we must provide a little more help to the compiler, by rewriting the recursive algorithm as a nonrecursive algorithm that systematically records the answers to the subproblems in a table. One technique that makes use of this approach is known as dynamic programming.
Examples: Matrix multiplication, allpairs
shortest path, optimal binary search tree, longest common subsequence
ACM Uva Examples: 10131, 10069, 10154, 116, 10003, 10261, 10271, 10201
D. Backtracking Algorithms
It’s a clever implementation of exhaustive search. In this algorithm, a large group of possiblities are eliminated in one step which is known as pruning.
Example:
Suppose we are given N points, located on the x-axis. Let us assume that the first point’s xcoordinate
is 0 and the points are given from left to right. If we are given a set of points, it is easy to construct the set of distances between every pair of points. But the turnpike reconstruction problem is to reconstruct a point set from the distances. Suppose we are given the distance set

D = {1,2,2,2,3,3,3,4,5,5,5,6,7,8,10}.

We know that N = 6. The first number is 0 and the last(6th) number is 10.
We remove 10 from D. Next the largest remaining distance is 8, which means that either the second element is 2 or the 5th element is 8. We construct a tree for the solutions and after propagating a certain path, we will conclude that one path is not the correct path and we will backtrack to last correct position. We need to do these prunings all over the tree to get the correct result.
ACM Uva Examples: 861, 10181, 10128, 10160, 10032, 10001, 704, 10270
E. Appendix:
IMPORTANT WEBSITES/ FOR ACM/ICPC PROGRAMMERS:
ACM online site: http://onlinejudge.uva.es/

and
http://ciijudge. baylor.edu/

Helping site: http://www.comp.nus.edu.sg/~stevenha/programming/acmoj.html
Online book: http://acm.uva.es/p/Art_of_Programming_Contest_SE_for_uva.pdf
References
1. Data Structures and Algorithm Analysis Mark Allen Weiss
2. Programming Challenges Steven
S. Skiena, Miguel A. Revilla
3. Art of Programming Contest – Ahmed Shamsul Arefin”

Tags: , ,
24 October 2010 Comments Off

Eclipse Debugging Tutorial by Lars Vogel

Most people know Eclipse as an integrated development environment (IDE) for Java. Eclipse is created by an open source community and is used in several different areas, e.g. as IDE for Java or for Android or as a platform to develop Eclipse RCP applications, etc.. The usage of Eclipse as a Java development environment will be described in this tutorial.

Create a Java project “de.vogella.debug.first” with the package “de.vogella.debug.first” and the following classes.

<pre>package de.vogella.debug.first;

public class Counter {
	private int result=0;
	public int getResult() {
		return result;
	}

	public void count() {
		for (int i = 0; i &lt; 100; i++) {
			result += i +1;
		}
	}
}</pre>
<pre>package de.vogella.debug.first;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Counter counter = new Counter();
		counter.count();
		System.out.println("We have counted " + counter.getResult());
	}

}

Debug

Setting Breakpoints

To set breakpoints right click in the small left column in your source code editor and select toggle breakpoint. Or you can double click on this place.

24 October 2010 Comments Off

Very impotant notes by Igor and Frank for newcomers

Notes by Igor Naverniouk (Abednego) and Frank Chu (fpmc) for newcomers :

  • C++ I/O. Note: Be very careful when you use getline after using cin! The first getline may return an empty line (why?)
  • Another I/O tutorial by Yury Kholondyrev (warmingup).
  • C++ STL (vectors, lists, sets, maps, pairs) and algorithms.
    Part 1, Part 2, and Part 3.
  • Graph algorithms (BFS, colored DFS, shotest paths, union/find, spanning trees, Euler paths, flow and matching).
    Part 1, Part 2, Part 3, Part 4, and Part 5.
  • Classroom DP and memoization (including bitset DP).
    Part 1, Part 2, and Part 3.
  • Brute force tricks (Backtracking, branch and bound, iterative deepening, bidirectional search).
    Part 1, Part 2, and Part 3.

Source: http://www.cs.cornell.edu/~wdtseng/icpc/index.html