SHARE
TWEET

BracketSequenceDiv2

a guest Mar 29th, 2016 150 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2.  
  3. public class BracketSequenceDiv2 {
  4.   static final int N = 100;
  5.   static final int mod = 1_000_000_007;
  6.  
  7.   int add(int x, int y) {
  8.     x += y;
  9.     if (x >= mod)
  10.       x -= mod;
  11.     return x;
  12.   }
  13.  
  14.   int sub(int x, int y) {
  15.     x -= y;
  16.     if (x < 0)
  17.       x += mod;
  18.     return x;
  19.   }
  20.  
  21.   boolean order(int l, int m, int r) {
  22.     return l <= m && m <= r;
  23.   }
  24.  
  25.   public String checkData(String s) {
  26.     int n = s.length();
  27.     if (!order(1, n, N))
  28.       return "s must contain between 1 and 100 characters, inclusive.";
  29.  
  30.     for (int i = 0; i < n; ++i) {
  31.       char c = s.charAt(i);
  32.       if (c != '(' && c != ')')
  33.         return "Each character in s must be '(' or ')'.";
  34.     }
  35.  
  36.     return "";
  37.   }
  38.  
  39.   int naive(String s) {
  40.     int n = s.length();
  41.     Set<String> good = new HashSet<String>();
  42.  
  43.     for (int mask = 1; mask < (1 << n); ++mask) {
  44.       int bal = 0;
  45.       boolean bad = false;
  46.       String cur = "";
  47.  
  48.       for (int i = 0; i < n; ++i)
  49.         if (((mask >> i) & 1) == 1) {  
  50.           bal += s.charAt(i) == '(' ? 1 : -1;
  51.           cur = cur + s.charAt(i);
  52.         if (bal < 0)
  53.          bad = true;
  54.         }
  55.  
  56.       if (bal == 0 && !bad)
  57.         good.add(cur);
  58.     }
  59.    
  60.     return good.size();
  61.   }
  62.  
  63.  
  64.   public int count(String s) {
  65.     int n = s.length();
  66.     int[][] d = new int[N][2];
  67.  
  68.     for (int i = 0; i < n; ++i) {
  69.       if (s.charAt(i) == '(') {
  70.         for (int j = N - 1; j >= 1; --j) {
  71.           d[j][0] = add(d[j - 1][0], d[j - 1][1]);
  72.           if (j == 1)
  73.             d[j][0] = add(d[j][0], 1); //empty string counts
  74.         }
  75.       } else {
  76.         for (int j = 0; j + 1 < N; ++j)
  77.           d[j][1] = add(d[j + 1][0], d[j + 1][1]);
  78.       }
  79.  
  80.       /*
  81.       for (int j = 0; j < 5; ++j) {
  82.         System.out.print(d[j][0]);
  83.         System.out.print(" ");
  84.         System.out.println(d[j][1]);
  85.       }
  86.       System.out.println();
  87.       */
  88.     }
  89.  
  90.     return d[0][1];
  91.   }
  92.  
  93.   public static void main(String[] args) {
  94.     BracketSequenceDiv2 solver = new BracketSequenceDiv2();
  95.     String s = "(((((()))))()))";
  96.     System.out.println(solver.count(s));
  97.     System.out.println(solver.naive(s));
  98.   }
  99. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top