Programming Challenges

Links from class:

• Today’s contest
• Solutions to today’s contest
• Today’s slides

Recommended Java API pages

There are a number of important features in Java that can help you write smaller, faster, bug-free code. Here are some of my favorites:

• String
• Collections
• Arrays
• Math
• StringBuilder – instead of string buffer, use these to build your incomplete strings
• Scanner
• BufferedReader – for some problems, it can be easier to use BufferedReader than Scanner

Union-Find Disjoint Sets

Section 2.3.2 in Competitive Programming gives a nice description of Union-Find Disjoint Sets. Below is Java code that could be used to solve problem C or any union-find problem in general. This data structure comes up again and again in programming contests.

public class UnionFind {
    
    int sets[] = new int[100];
    int nextId = 0;
    
    public void init() {
        for (int i = 0; i < sets.length; i++) {
            sets[i] = i;
        }
    }

    public void union(int s1, int s2) {
        sets[s2] = s1;
    }
    
    public int find(int index) {
        if (sets[index] == index) {
            return index;
        }
        
        return sets[index] = find(sets[index]);
    }

    public void run() throws Exception {
        init();
        
        /* Do stuff */
    }
    
    public static void main(String[] args) throws Exception {
        new UnionFind().run();
    }

}

For next class

Assigned readings:

• Programming Challenges: Chapter 2 – skip over Binary Indexed (Fenwick) Trees and Segment Trees

Assigned problems:

• Automatic Answer
• List of Conquests – Hint: Do a frequency count and sort the output (Is there a data structure that does this for you?) SOLUTION
• Event Planning
• Minesweeper (Optional)
• Magic Square Palindromes (Optional)

Assigned exercise:

• Look over the solutions to this class’ problems