July 23, 2021 Rookie SRM 6 Editorial

BiggestDuplicate

Probably the easiest way to handle this problem is to first sort the list of integers. Then, starting with the largest ones, we look to see if any are duplicated. Since the list is sorted, duplicates will always be adjacent.

public int findLargest(int[] x) {
  Arrays.sort(x);
  for (int i = x.length - 2; i >= 0; i--)
    if (x[i] == x[i + 1])
      return x[i];
      
  return -1;
}

LinearSignals

The size of the problem is small enough that we could simply check, for each cell, how many towers are in range. And this works just fine.

Alternatively, we can do something a little more fancy that would work for much larger test cases and still be efficient. We can imagine that a range of 2 * maxDist + 1 cells is the full collection of potential towers that can be seen from a single cell. So, let’s start at the left and figure out how many towers are available. Then, we can sweep our range to the right, one cell at a time, subtracting a tower whenever one goes out of range on the left, or adding a tower whenever one comes into range on the right. This gives us a linear time solution.

public int maxSignals(String towers, int maxDist) {
  int cur = 0;
  int start = 0;
  int end = 0;
  for (end = 0; end <= start + 2 * maxDist && end < towers.length(); end++)
    if (towers.charAt(end) == 'X')
      cur++;  
  int best = cur;
  end = start + 2 * maxDist;
  while (end < towers.length() - 1) {
    if (towers.charAt(start) == 'X')
      cur--;
    start++; end++;
    if (towers.charAt(end) == 'X')
      cur++;  
    best = Math.max(best, cur);
  }  
  return best;
}

SlowTerrain

This is a classic kind of “find your way through the maze” problem, although the weights assigned to each cell give us a new twist to think about. We can’t simply do a breadth-first search, as it may be possible to get to the destination in more steps, but at a lower cost, and we need to be able to find such a path.

So, for each cell, we need to keep track of “what is the least expensive path we have found so far to get to this cell?” If we proceed with our search that way, and continue searching whenever we find a cheaper path to a cell, we will be guaranteed to have found the best overall.

The reference solution uses a simple queue to keep track of “which cells do we need to recheck again?”

public int fastestPath(String[] map) {
    int startX = 0;
    int startY = 0;
    int endX = 0;
    int endY = 0;
    int[][] m = new int[map.length][map[0].length()];
    int best = 99999;
    for (int y = 0; y < map.length; y++)
      for (int x = 0; x < map[y].length(); x++) {
        m[y][x] = 99999;
        if (map[y].charAt(x) == 'S') {
          startX = x;
          startY = y;
        }
        if (map[y].charAt(x) == 'D') {
          endX = x;
          endY = y;
        }
      }
    int[] q = new int[100000];
    q[0] = startY * 52 + startX;
    m[startY][startX] = 0;
    int cur = 0;
    int end = 1;
    while (cur < end) {
      int y = q[cur] / 52;
      int x = q[cur] % 52;
      int total = m[y][x];
      //System.out.println(y + "," + x + ": " + total);
      char c = map[y].charAt(x);
      if (y == endY && x == endX)
        best = Math.min(best, total);        
      int val = (c == 'S' || c == 'D') ? 0 : (c - '0');
      int test = total + val;
      if (x > 0) {
        if (test < m[y][x - 1]) {
          m[y][x - 1] = test;
          q[end] = y * 52 + x - 1;
          end++;
        }
      }
      if (x < map[0].length() - 1) {
        if (test < m[y][x + 1]) {
          m[y][x + 1] = test;
          q[end] = y * 52 + x + 1;
          end++;
        }
      }
      if (y > 0) {
        if (test < m[y - 1][x]) {
          m[y - 1][x] = test;
          q[end] = (y - 1) * 52 + x;
          end++;
        }
      }
      if (y < map.length - 1) {
        if (test < m[y + 1][x]) {
          m[y + 1][x] = test;
          q[end] = (y + 1) * 52 + x;
          end++;
        }
      }
      cur++;
    }
    return best;
  }


KassanErinn

Guest Blogger


categories & Tags


Close

Sign up for the Topcoder Monthly Customer Newsletter

Thank you

Your information has been successfully received

You will be redirected in 10 seconds