Category Archives: Competitive Programming 3

UVA 11687 – Digits

This question is terribly worded I think. Basically it wants you to find the length of the input string and let this length become the new string. Keep following this process until the length of the string and string are the same.

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

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

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

    while (sc.hasNext()) {
      String input = sc.next();
      if (input.equals("END"))
        break;
      out.println(solve(input));
    }

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

  private static int solve(String input) {
    int count = 1;
    int len = input.length();
    if ((len + "").equals(input))
      return count;
    else
      return count + solve(len + "");
  }
}

UVA 11683 – Laser Sculpture

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();
  }
}

UVA 11661 – Burger Time?

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();
  }

}

UVA 11586 – Train Tracks

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();
  }
}

UVA 11507 – Bender B. Rodríguez Problem

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();
  }
}

UVA 10919 – Prerequisites?

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();
  }

}

UVA 10424 – Love Calculator

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

}

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

}

UVA 1112 – Mice and Maze

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 &lt; 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 &lt; N; j++) {
        graph[j] = new Node(j);
      }
      for (int j = 0; j &lt; 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 &lt; N; j++) {
        if (shortest[j] == 0) {
          Object[] output = dfs(graph, j, E);
          if (output != null) {
            @SuppressWarnings(&quot;unchecked&quot;)
            ArrayList&lt;Integer&gt; tmp = (ArrayList&lt;Integer&gt;) output[0];
            int cost = (int) output[1];
            int size = tmp.size();
            int thing = 0;
            shortest[tmp.get(0)] = cost;
            for (int k = 1; k &lt; 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 &lt; N; k++) {
            graph[k].visited = false;
          }
        }
      }
      int ans = 0;
      for (int j = 0; j &lt; N; j++) {
        if (shortest[j] &lt;= T &amp;&amp; shortest[j] != -1) {
          ans++;
        }
      }
      out.println(ans);
    }
    out.close();
    sc.close();
  }

  @SuppressWarnings(&quot;unchecked&quot;)
  private static Object[] dfs(Node[] graph, int j, int e) {
    PriorityQueue&lt;Object[]&gt; queue = new PriorityQueue&lt;Object[]&gt;(1, new Comparator&lt;Object[]&gt;() {
      @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&lt;Integer&gt;(), 0 });
    while (!queue.isEmpty()) {
      Object[] next = queue.poll();
      Node n = ((Node) next[0]);
      ((ArrayList&lt;Integer&gt;) 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&lt;Integer&gt; tmp = new ArrayList&lt;Integer&gt;();
            tmp.addAll((ArrayList&lt;Integer&gt;) 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&lt;Integer, Integer&gt; cost;

    public Node(int idx) {
      this.idx = idx;
      cost = new HashMap&lt;Integer, Integer&gt;();
    }

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

}

UVA 10141 – Request for Proposal

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

}