[Timus] 1613 For Fans of Statistics

Problem statement is here: http://acm.timus.ru/problem.aspx?space=1&num=1613

Not a very difficult problem but requires some thought on how to optimize for searching in interval. Some point to note that:

1. This is a searching problem.

2. The indices of the traffic in the input array are by definition sorted.

Searching in a sorted list means we can use binary search to optimize.

The second point above needs a bit of expansion. If we keep a map which uses the traffic data as key with collision resolved through chaining, we can easily search the indices. To resolve collision, a list can be used which stores the index in the input array (corresponding to a city) where the traffic was noted. We build the list as we parse the input so the list would always be sorted, we need not sort it later. This should provide enough hint to solve this problem. Here is the code:

public class Task1613 {

  public void solve(int testNumber, InputReader in,
      OutputWriter out) {
    Map<Integer, List<Integer>> populationTable = new HashMap<>();
    int n = in.nextInt();

    for (int i = 0; i < n; i++) {
      int population = in.nextInt();
      List<Integer> indices = populationTable
          .getOrDefault(population, new ArrayList<>());
      indices.add(i + 1);
      populationTable.put(population, indices);
    }

    int q = in.nextInt();
    while (q-- > 0) {
      int l = in.nextInt();
      int r = in.nextInt();
      int x = in.nextInt();

      if (populationTable.containsKey(x)) {
        if (binarySearch(populationTable.get(x), l, r, 0,
            populationTable.get(x).size())) {
          out.print('1');
        } else {
          out.print('0');
        }
      } else {
        out.print('0');
      }
    }
  }

  private boolean binarySearch(List<Integer> indices, int l,
      int r, int lo, int hi) {
    if (lo >= hi) {
      return false;
    }
    int mid = lo + (hi - lo) / 2;

    if (indices.get(mid) >= l && indices.get(mid) <= r) {
      return true;
    }

    if (indices.get(mid) < l) {
      return binarySearch(indices, l, r, mid + 1, hi);
    }

    return binarySearch(indices, l, r, lo, mid);
  }
}

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *

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