One pass is indeed enough!

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

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

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

    while ((line = br.readLine()) != null) {
      st = new StringTokenizer(line.trim());
      int A = Integer.parseInt(st.nextToken());
      if (A == 0)
        break;

      int B = Integer.parseInt(st.nextToken());
      int[] sculpt = new int[B];
      st = new StringTokenizer(br.readLine().trim());
      int ans = 0;
      int last = -1;
      for (int i = 0; i < B; i++) {
        sculpt[i] = Integer.parseInt(st.nextToken());
        if (last == -1) {
          last = sculpt[i];
          if (sculpt[i] != A)
            ans += (A - sculpt[i]);
        }
        if (sculpt[i] >= last) {
          last = sculpt[i];
        } else {
          ans += (last - sculpt[i]);
          last = sculpt[i];
        }
      }
      out.println(ans);
    }

    out.close();
    br.close();
  }
}

Just keep track of the last burger joint you saw and the last restaurant you saw. You can solve this greedily. If you ever find a ‘Z’ then the answer is immediately always 0.

import java.io.PrintWriter;
import java.util.Scanner;

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

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);

    while (sc.hasNextLine()) {
      int L = Integer.parseInt(sc.nextLine());
      if (L == 0)
        break;
      char[] road = sc.nextLine().toCharArray();
      int lastDrugStore = -1;
      int lastRestaurant = -1;
      int min = Integer.MAX_VALUE;
      for (int i = 0; i < road.length; i++) {
        if (road[i] == 'R') {
          lastRestaurant = i;
        } else if (road[i] == 'D') {
          lastDrugStore = i;
        } else if (road[i] == 'Z') {
          min = 0;
          break;
        }
        if (lastDrugStore != -1 && lastRestaurant != -1) {
          min = Math.min(Math.abs(lastDrugStore - lastRestaurant), min);
        }
      }
      out.println(min);
    }

    out.close();
    sc.close();
  }

}

Pretty easy. Loops are formed if you have an even number of MF/FM tracks and an equal number of MM and FF tracks. Just check for both conditions to be true.

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

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

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

    int[] count;
    int N = Integer.parseInt(br.readLine().trim());
    for (int zz = 0; zz < N; zz++) {
      count = new int[] { 0, 0 };
      StringTokenizer st = new StringTokenizer(br.readLine().trim());
      while (st.hasMoreTokens()) {
        String input = st.nextToken();
        if (input.equals("MF") || input.equals("FM")) {
          if (count[0] == 0)
            count[0]++;
          else
            count[0]--;
        } else {
          if (input.equals("MM")) {
            count[1]++;
          } else {
            count[1]--;
          }
        }
      }
      if (count[0] == 0 && count[1] == 0) {
        out.println("LOOP");
      } else {
        out.println("NO LOOP");
      }
    }

    out.close();
    br.close();
  }
}

There’s really no need to attempt to code super simple programs more efficiently. Don’t be afraid to write a bunch of if-elses!

import java.io.PrintWriter;
import java.util.Scanner;

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

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);

    while (sc.hasNextInt()) {
      int L = sc.nextInt();
      if (L == 0)
        break;
      L--;

      String ans = "+x";
      for (int i = 0; i < L; i++) {
        String input = sc.next();
        if (!input.equals("No"))
          if (ans.equals("+x")) {
            ans = input.toString();
          } else if (ans.equals("-x")) {
            if (input.charAt(0) == '-') {
              ans = "+" + input.charAt(1);
            } else {
              ans = "-" + input.charAt(1);
            }
          } else if (ans.equals("+y")) {
            if (input.equals("+y")) {
              ans = "-x";
            } else if (input.equals("-y")) {
              ans = "+x";
            } else {
              ans = "+y";
            }
          } else if (ans.equals("-y")) {
            if (input.equals("+y")) {
              ans = "+x";
            } else if (input.equals("-y")) {
              ans = "-x";
            } else {
              ans = "-y";
            }
          } else if (ans.equals("+z")) {
            if (input.equals("+z")) {
              ans = "-x";
            } else if (input.equals("-z")) {
              ans = "+x";
            } else {
              ans = "+z";
            }
          } else if (ans.equals("-z")) {
            if (input.equals("+z")) {
              ans = "+x";
            } else if (input.equals("-z")) {
              ans = "-x";
            } else {
              ans = "-z";
            }
          }
      }
      out.println(ans);
    }

    out.close();
    sc.close();
  }
}

Super easy. HashSet would have provided better performance than an ArrayList though.

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Scanner;

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

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);

    while (sc.hasNextInt()) {
      int K = sc.nextInt();
      if (K == 0)
        break;
      int M = sc.nextInt();

      ArrayList<String> courses = new ArrayList<>();
      for (int i = 0; i < K; i++) {
        courses.add(sc.next());
      }

      boolean good = true;
      for (int i = 0; i < M; i++) {
        int num = sc.nextInt();
        int min = sc.nextInt();
        int count = 0;
        for (int j = 0; j < num; j++) {
          String course = sc.next();
          if (courses.contains(course))
            count++;
        }
        if (count < min)
          good = false;
      }

      if (good) {
        out.println("yes");
      } else {
        out.println("no");
      }
    }

    out.close();
    sc.close();
  }

}

Pretty easy. Just make appropriate functions and call them recursively.

import java.io.PrintWriter;
import java.text.DecimalFormat;
import java.util.Scanner;

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

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);

    DecimalFormat df = new DecimalFormat();
    df.setMinimumFractionDigits(2);
    df.setMaximumFractionDigits(2);

    while (sc.hasNextLine()) {
      String first = sc.nextLine().toLowerCase();
      String second = sc.nextLine().toLowerCase();
      double numFirst = toNum(convert(first));
      double numSecond = toNum(convert(second));
      double ans;
      if (numFirst < numSecond) {
        ans = numFirst * 100 / numSecond;
      } else {
        ans = numSecond * 100 / numFirst;
      }
      out.println(df.format(ans) + " %");
    }

    out.close();
    sc.close();
  }

  private static String convert(String first) {
    int x = 0;
    for (int i = 0; i < first.length(); i++) {
      char c = first.charAt(i);
      if (c >= 'a' && c <= 'z')
        x += (c - 'a') + 1;
    }
    return x + "";
  }

  private static double toNum(String first) {
    if (first.length() != 1) {
      int x = 0;
      for (int i = 0; i < first.length(); i++) {
        x += Integer.parseInt(first.charAt(i) + "");
      }
      return toNum(x + "");
    } else {
      return Double.parseDouble(first);
    }
  }

}

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";
    }
  }

}

This question is part of the Competitive Programming 3 book however I haven’t quite reached that chapter yet. Let me see how my approach to solving this problem changes once I get there.

Below is the way I would have done it without having reading the book.

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Scanner;

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

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);

    int zz = sc.nextInt();
    for (int i = 0; i < zz; i++) {
      if (i != 0)
        out.println();
      int N = sc.nextInt();
      int E = sc.nextInt() - 1;
      int T = sc.nextInt();
      int M = sc.nextInt();
      Node[] graph = new Node[N];
      for (int j = 0; j < N; j++) {
        graph[j] = new Node(j);
      }
      for (int j = 0; j < M; j++) {
        int a = sc.nextInt() - 1;
        int b = sc.nextInt() - 1;
        int c = sc.nextInt();
        graph[a].add(graph[b], c);
      }
      int[] shortest = new int[N];
      for (int j = 0; j < N; j++) {
        if (shortest[j] == 0) {
          Object[] output = dfs(graph, j, E);
          if (output != null) {
            @SuppressWarnings("unchecked")
            ArrayList<Integer> tmp = (ArrayList<Integer>) output[0];
            int cost = (int) output[1];
            int size = tmp.size();
            int thing = 0;
            shortest[tmp.get(0)] = cost;
            for (int k = 1; k < size; k++) {
              thing += graph[tmp.get(k - 1)].cost.get(tmp.get(k));
              shortest[tmp.get(k)] = cost - thing;
            }
          } else {
            shortest[j] = -1;
          }
          for (int k = 0; k < N; k++) {
            graph[k].visited = false;
          }
        }
      }
      int ans = 0;
      for (int j = 0; j < N; j++) {
        if (shortest[j] <= T && shortest[j] != -1) {
          ans++;
        }
      }
      out.println(ans);
    }
    out.close();
    sc.close();
  }

  @SuppressWarnings("unchecked")
  private static Object[] dfs(Node[] graph, int j, int e) {
    PriorityQueue<Object[]> queue = new PriorityQueue<Object[]>(1, new Comparator<Object[]>() {
      @Override
      public int compare(Object[] o1, Object[] o2) {
        return Integer.compare((int) o1[2], (int) o2[2]);
      }
    });
    queue.add(new Object[] { graph[j], new ArrayList<Integer>(), 0 });
    while (!queue.isEmpty()) {
      Object[] next = queue.poll();
      Node n = ((Node) next[0]);
      ((ArrayList<Integer>) next[1]).add(n.idx);
      n.visited = true;
      if (n.idx == e) {
        return new Object[] { next[1], next[2] };
      } else {
        for (Integer in : n.cost.keySet()) {
          if (!graph[in].visited) {
            ArrayList<Integer> tmp = new ArrayList<Integer>();
            tmp.addAll((ArrayList<Integer>) next[1]);
            queue.add(new Object[] { graph[in], tmp, (int) next[2] + n.cost.get(in) });
          }
        }
      }
    }
    return null;
  }

  private static class Node {
    boolean visited;
    int idx;
    HashMap<Integer, Integer> cost;

    public Node(int idx) {
      this.idx = idx;
      cost = new HashMap<Integer, Integer>();
    }

    public void add(Node n, int cost) {
      if (this.cost.containsKey(n.idx)) {
        int tmp = this.cost.get(n);
        this.cost.put(n.idx, Math.min(tmp, cost));
      } else {
        this.cost.put(n.idx, cost);
      }
    }
  }

}

Meh, missed edge case of an RFP having NO requirements at all. Other than that pretty easy problem. Could have done it without using a heap and keeping track of some variables but I used one anyways.

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

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

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

    boolean first = true;
    int test = 1;
    String line = null;
    while ((line = br.readLine()) != null) {
      st = new StringTokenizer(line);
      int N = Integer.parseInt(st.nextToken());
      int P = Integer.parseInt(st.nextToken());
      if (N == 0 && P == 0)
        break;
      if (!first)
        out.println();
      ArrayList<String> requirements = new ArrayList<String>();
      for (int i = 0; i < N; i++) {
        requirements.add(br.readLine());
      }

      PriorityQueue<Offer> heap = new PriorityQueue<Offer>(P, new Comparator<Offer>() {
        @Override
        public int compare(Offer arg0, Offer arg1) {
          if (arg0.compliance == arg1.compliance) {
            if (arg0.price == arg1.price) {
              return Integer.compare(arg0.idx, arg1.idx);
            } else {
              return Double.compare(arg0.price, arg1.price);
            }
          } else {
            return Double.compare(arg1.compliance, arg0.compliance);
          }
        }
      });

      for (int i = 0; i < P; i++) {
        String name = br.readLine();
        st = new StringTokenizer(br.readLine());
        double price = Double.parseDouble(st.nextToken());
        int offer = Integer.parseInt(st.nextToken());
        int count = 0;
        for (int j = 0; j < offer; j++) {
          br.readLine();
          count++;
        }
        heap.add(new Offer(name, price, count, i));
      }
      out.println("RFP #" + test);
      out.println(heap.poll().name);
      test++;
      first = false;
    }

    out.close();
    br.close();
  }

  private static class Offer {
    int idx;
    String name;
    double price;
    double compliance;

    public Offer(String name, double price, double compliance, int idx) {
      this.name = name;
      this.price = price;
      this.compliance = compliance;
      this.idx = idx;
    }
  }

}

Blank line after every case. :[

import java.io.PrintWriter;
import java.util.Scanner;

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

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);

    int count = 1;
    while (sc.hasNextInt()) {

      int N = sc.nextInt();
      int M = sc.nextInt();
      int C = sc.nextInt();

      if (N == 0)
        break;

      long[] power = new long[N];
      for (int i = 0; i < N; i++)
        power[i] = sc.nextInt();

      boolean[] on = new boolean[N];
      long current = 0;
      long max = 0;
      for (int i = 0; i < M; i++) {
        int tmp = sc.nextInt() - 1;
        if (on[tmp]) {
          on[tmp] = false;
          current -= power[tmp];
        } else {
          on[tmp] = true;
          current += power[tmp];
          max = Math.max(max, current);
        }
      }

      out.println("Sequence " + count);
      if (max > C) {
        out.println("Fuse was blown.");
      } else {
        out.println("Fuse was not blown.");
        out.println("Maximal power consumption was " + max + " amperes.");
      }
      out.println();
      count++;
    }

    out.close();
    sc.close();
  }

}