USACO: Stringsobits

Problem Links:

USACO: kimbits

Problem:

Stringsobits
Kim Schrijvers Consider an ordered set S of strings of N (1 <= N <= 31) bits. Bits, of course, are either 0 or 1.
This set of strings is interesting because it is ordered and contains all possible strings of length N that have L (1 <= L <= N) or fewer bits that are `1'.
Your task is to read a number I (1 <= I <= sizeof(S)) from the input and print the Ith element of the ordered set for N bits with no more than L bits that are `1'.

PROGRAM NAME: kimbits

INPUT FORMAT

A single line with three space separated integers: N, L, and I.

SAMPLE INPUT (file kimbits.in)

5 3 19

OUTPUT FORMAT

A single line containing the integer that represents the Ith element from the order set, as described.

SAMPLE OUTPUT (file kimbits.out)

10011

Solution:

First, I tried to solve this problem recursively, while data set #7 always make my code exceed time limit(ETL),

Source Code:

Code Got Passed.

/*
 ID: ***
 TASK: kimbits
 LANG: JAVA 
 */
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;

/**
 * @author antonio081014
 * @time Feb 21, 2013, 7:37:09 PM
 */
public class kimbits {

 private int N;
 private int L;
 private long I;
 private long[][] mark;
 private PrintWriter out;

 public static void main(String[] args) throws Exception {
  kimbits main = new kimbits();
  main.run();
  System.exit(0);
 }

 private void run() throws Exception {
  BufferedReader br = new BufferedReader(new FileReader("kimbits.in"));
  out = new PrintWriter(new FileWriter("kimbits.out"));

  String[] strs = br.readLine().split("\\s");
  N = Integer.parseInt(strs[0]);
  L = Integer.parseInt(strs[1]);
  I = Long.parseLong(strs[2]);
  br.close();

  mark = new long[N + 1][L + 1];
  for (int i = 0; i <= N; i++)
   mark[i][0] = 1L;
  for (int i = 0; i <= L; i++) {
   mark[0][i] = 1L;
  }

  for (int i = 1; i <= N; i++) {
   for (int j = 1; j <= L; j++)
    if (i >= j)
     mark[i][j] = mark[i - 1][j - 1] + mark[i - 1][j];
    else
     mark[i][j] = mark[i][i];
  }
  // print(N, L, I);
  printbit(N, L, I);
  out.write('\n');
  out.close();
 }

 private void print(int n, int l, int i) {
  if (l > n)
   l = n;
  if (mark[n][l] == i) {
   for (int j = 0; j < i; j++)
    out.write('1');
   for (int j = i; j < n; j++)
    out.write('0');
  } else {
   if (i > mark[n - 1][l]) {
    out.write('1');
    print(n - 1, l - 1, (int) ((long) i - mark[n - 1][l]));
   } else {
    out.write('0');
   }
  }
 }

 void printbit(int i, int j, long K) {
  if (j > i)
   j = i;

  if (K == mark[i][j]) {
   for (int t = 1; t <= j; t++)
    out.write('1');
   for (int t = 1; t <= i - j; t++)
    out.write('0');
  } else {

   if (K <= mark[i - 1][j]) {
    out.write('0');
    printbit(i - 1, j, K);
   } else {
    out.write('1');
    printbit(i - 1, j - 1, K - mark[i - 1][j]);
   }
  }
 }
}

/*
 ID: ***
 TASK: kimbits
 LANG: JAVA
 */
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;

public class kimbits {

        private int L;
        private int N;
        private int I;
        private String[] list;
        private PrintWriter out;
        private boolean flag;
        private int top;

        public static void main(String[] args) throws Exception {
                kimbits main = new kimbits();
                main.run();
                System.exit(0);
        }

        private void run() throws Exception {
                BufferedReader br = new BufferedReader(new FileReader("kimbits.in"));
                out = new PrintWriter(new BufferedWriter(new FileWriter("kimbits.out")));
                String[] strs = br.readLine().split("\\s");
                br.close();
                flag = true;
                N = Integer.parseInt(strs[0]);
                L = Integer.parseInt(strs[1]);
                I = Integer.parseInt(strs[2]);
                // System.out.println(String.format("N %d, L %d, I %d", N, L, I));
                list = new String[I];
                top = 0;
                rec("", 0);
                out.close();
        }

        private void rec(String s, int ones) {
                if (s.length() == N) {
                        if (ones <= L && flag)
                                list[top++] = s;
                        if (top == I && flag) {
                                out.write(s + "\n");
                                flag = false;
                        }
                        return;
                }
                if (flag == false)
                        return;
                rec(s + "0", ones);
                rec(s + "1", ones + 1);
        }
}