Practice for programming competition

I am entering a programming competition in few weeks and have been tackling past papers. One question I am stuck on is to call a recursive function开发者_如何学C which computes all possible binary integers with n digits, eg user inputs 2, program prints out 00, 01, 10, 11. What is the best way to tackle this? How is it done?

Also, it's an ACM competition - are there any must study books for these competitions? Anything I should definitely read? It is in one months! I am really nervous and don't want to let my team down.

A solution in Java:

for(int i = 0; i < 1 << n; i++)
  {
  System.out.println(Integer.toBinaryString(i));
  }

here's some code with no real limitations (you can remove the recursion but it seemed like it was a requirement of the answer):

public class Bits {
  public static void f(String prefix, int n) {
    if (n == 0) {
      System.out.println(prefix);
      return;
    }
    f(prefix + "0", n - 1);
    f(prefix + "1", n - 1);
  }
  public static void main(String [] argv) {
    f("", 5);
  }
}

Maybe something like that in C or C++, the recursivity is not really necessary or simpler in this case, but if it is asked... The algorithm is exactly what I would do to solve this by hand. Go from right to left changing 1 to 0 and propagating the carry until you find a 0. That's counting in base 2. As an exercice you could try that in base 3 or 4, it's not much different.

#include <stdio.h>
#include <malloc.h>

void f(char *buffer, int max){
    int i;
    printf("%s, ", buffer);
    for (i = max-1 ; buffer[i] == '1' ; i--){
        buffer[i] = '0';
    }
    if (i < 0) return;
    buffer[i] = '1';
    f(buffer, max);
}

int main(int argc, char ** argv){
    int max = atoi(argv[1]);
    char buffer[32];
    int i;
    for (i = 0; i < max ; i++){
        buffer[i] = '0';
    }
    buffer[max] = 0;
    f(buffer, max);
}

To prepare for competition, reviewing past papers is a good idea. But basically you should write as much code as you can. You should also train to implement classical algorithms (trees, sorts, graph implementation and search for best path, lists, 8 queens, etc.) while you can ask for help. One month is not really a large amount of time, so you should probably focus on understanding really well a few classical problems.

I would also recommand to get used to unit testing, this will avoid to propose incorrect answer which is penalized in such competitio and unit testing and TDD help to focus on problems anyway and avoiding losing your time.

This is not java but it IS recursive.

function getBinaryDigitForPosition(currentLevel, currentNumberAsString) {

  // if this were anything but binary I'd put these into an array and iterate thru
  firstNumber = currentNumberAsString + "0";
  secondNumber = currentNumberAsString + "1";

  if (currentLevel == 1) {
    print firstNumber + ", " + secondNumber;
  } else {
    // same iteration here as I mentioned above
    getBinaryDigitForPosition(currentLevel - 1, firstNumber);
    getBinaryDigitForPosition(currentLevel - 1, secondNumber);
  }

}

// calling the function initially:
// make sure that userInputNumberOfDigits is >= 1

getBinaryDigitForPosition(userInputNumberOfDigits, "");

EDIT I wrote this having read the question incorrectly- this is printing out all strings of length N with k bits. Leaving this for the advice on contests.

There is a better solution than the O(2^n), here's a hint - think about the recurrence relation of number of bit strings of length N with k ones. Let S be a function that counts the number of these items

S(N,k) = S(N-1,k-1) + S(N-1,k)

In words, the recurrence boils down to this - you can add a bit or not add a bit. You can use memoization to make this calculation run quickly. You need to reproduce the strings themselves, though, I leave that as an exercise.

There's a lot you can learn by reading books (Introduction to Algorithms and Algorithm Design manual are good ones) to get the 'big picture' algorithms. The rest is having the experience to find when those algorithms fit the problems, when they don't and how to code an ad-hoc solution when this is the case. I've done quite a few of these, can't say I'm good at them though, have fun and good luck :)

Here is a java recursive solution :)

 public class BinaryIntegers {

    public static void main(String[] args) {
        int numberOfBits = 10; // For instance.
        printBinaryNumbers(numberOfBits);
    }

    private static void printBinaryNumbers(int numberOfBits) {
        recursivePrint("", numberOfBits);
    }

    private static void recursivePrint(String current, int numberOfBitsLeft){
        if(numberOfBitsLeft==0)
            System.out.println(current);
        else{
            recursivePrint(current + "0", numberOfBitsLeft-1);
            recursivePrint(current + "1", numberOfBitsLeft-1);
        }
    }
}

Here is a more general solution, which can create lists not only of binary digits, but of any digits :-)

package de.fencing_game.paul.examples;

import java.util.Arrays;


public class AllNaryNumbers {


    private static void printAll(String prefix, Iterable<String> digits,
                                int length)
    {
        if(length == 0) {
            System.out.println(prefix);
            return;
        }
        for(String digit : digits) {
            printAll(prefix + digit, digits, length-1);
        }
    }

    private static void printNumbers(int length, Iterable<String> digits) {
        printAll("", digits, length);
    }

    private static void printBinary(int length) {
        printNumbers(length, Arrays.asList("0", "1"));
    }

    public static void main(String[] params) {
        if(params.length == 0) {
            printBinary(5);
            return;
        }
        int len = Integer.parseInt(params[0]);
        if(params.length == 1) {
            printBinary(len);
            return;
        }
        Iterable<String> digits =
            Arrays.asList(params).subList(1, params.length);
        printNumbers(len, digits);
    }

}

Edit: When using my ProductIterable, the code gets shorter:

private static void printNumbers(int length, Iterable<String> digits)
{
    for(List<String> number :
            new ProductIterable<String>
            (Collections.nCopies(length, digits))) {
        for(String digit : number) {
            System.out.print(digit);
        }
        System.out.println();
    }
}

(and most of it is converting of the Iterable into a string). If we can live with the comma-separated output, we can use a ProductList and make it even shorter:

private static void printNumbers(int length, List<String> digits)
{
    System.out.println(new ProductList<String>
                       (Collections.nCopies(length, digits)));
}

The output would be something like this: [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]].

Its not recursive, but at least lazy (just-in-time) producing of the elements.

There is a book:

http://www.amazon.com/exec/obidos/ISBN=0387001638/theinternationscA/

A friend of mine received such a book (as price for a junior programming contest), and was quite enthousiastic about it, but I'm not sure whether it is this one (although it does have a good rating on Amazon).

The best way to prepare is to just do old programming problems. Check past problem sets, there's always some problems which are always there: something with a maze, something with dynamic programming, etc. Practice these types of problems, so you can quickly solve them in the real competition.

Also, don't underestimate the amount of planning/organizing which goes into participating in a programming contest. A good interaction between team-members (for instance, in picking which excercises to solve) is really important. Also a good process for how to fix wrong programs.

Another thing thing, you said you're really nervous, and afraid to let your team down. But do remember, you're a team. Practice together!! If you're going there as three individuals, you're sure to loose... (best way to lose: Have one teammember claim a certain problem, which he is not going to solve, but of which he is convinced he is 'almost there'; thereby claiming lots of computer time, and solving nothing...)

Also, think about how you're going to work. My personal favorite is two coders and one non-coder. That way there's always some-one using the computer, while the other coder can discuss problems with the non-coder. (by coder I mean someone who actually types code, instead of just writing algorithms on paper)

Good luck! and more importantly: Have Fun!