UVA 10324 – Zeros and Ones

I finally solved this problem. Everytime I see the word queries or MOD 1000000007 I instantly panic because I know I haven’t quite yet gotten to making a Segment Tree or solving DP problems yet. I did end up making a Segment Tree that does successfully solve this problem however since our input is so huge it will most definitely TLE. Here is my solution, I can just keep summing the values and put them in an ArrayList and then just compare the sums at the query endpoints. I did however miss out the edge case of [1,0,0,0,0] as the sum would be same at both ends however the actual numbers are different. I just added that case in and AC!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

/**
 * 
 * @author Sanchit M. Bhatnagar
 * @see http://uhunt.felix-halim.net/id/74004
 * 
 */
public class P10324 {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter out = new PrintWriter(System.out);
    StringTokenizer st = null;

    long test = 1;
    String line = null;
    while ((line = br.readLine()) != null) {
      char[] input = line.trim().toCharArray();
      if (input.length == 0)
        break;
      ArrayList<Integer> sumArray = new ArrayList<Integer>();
      int sum = 0;
      for (int i = 0; i < input.length; i++) {
        sum += Integer.parseInt(input[i] + "");
        sumArray.add(sum);
      }
      int N = Integer.parseInt(br.readLine().trim());
      out.println("Case " + test + ":");
      for (int i = 0; i < N; i++) {
        st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        out.println(solve(Math.min(a, b), Math.max(a, b), sumArray, input));
      }
      test++;
    }
    out.close();
    br.close();
  }

  private static String solve(int min, int max, ArrayList<Integer> sumArray, char[] input) {
    int a = sumArray.get(min);
    int b = sumArray.get(max);
    if ((a == b || b - a + 1 == max - min + 1) && input[min] == input[max]) {
      return "Yes";
    } else {
      return "No";
    }
  }

}

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.