10067 - Playing with Wheels

[brianfry713]

AC output for your input:

Code: Select all

-1
-1
-1
10
5
6
1
11
11
8

[Monty]

But even the UVA toolkit returns exactly what I have for that input... Check it out

http://uvatoolkit.com/problemssolve.php#10067

Is it wrong then?

Thanks

[brianfry713]

On this case:
1
9 9 9 9
0 0 0 0
1
9 9 9 9

The code I just submitted and got AC with returns -1, if you'd rather believe your WA code and UVAtoolkit's 4 that's up to you, let us know if you can get AC with that logic. Others in this thread that have got AC agreed that it should be -1.

[Monty]

Alright, even after altering my code to produce the same results as yours for the first three cases I still get WA. Is there any other critical input that could be messing it up? I thought it could be the formatting so I removed the new line from the last output (which has never been an issue in other problems), still WA after 1.1 seconds. Thanks

[brianfry713]

No critical input besides what you've posted, I used a straightforward BFS.

[drseergio]

I believe I have written a working solution in Java yet I get rejections because of "runtime error". It seems to be caused by NumberFormatException during input>int conversion. I do not understand what sort of input is being provided to cause it. I have tried all test cases from this thread plus some additional ones and it works just fine on my machine. I've tried several variations of the integer conversion code and I still get the same result.

Does anyone has ideas on what could be causing problems here? I've seen similar threads from other Java folks without any follow-up.

Code: Select all

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.List;
import java.util.LinkedList;
import java.util.Iterator;

class Main {
  public static int COMBINATIONS = 10000;

  static class Graph {
    public EdgeNode[] edges;
    public boolean[] invalid;
    public boolean[] discovered;
    public int[] parent;

    class EdgeNode {
      public Integer y;
      public EdgeNode next;

      public EdgeNode(Integer y) {
        this.y = y;
      }
    }

    public Graph() {
      edges = new EdgeNode[COMBINATIONS];
      parent = new int[COMBINATIONS];
      invalid = new boolean[COMBINATIONS];
      discovered = new boolean[COMBINATIONS];

      for (int i = 0; i < COMBINATIONS; i++) {
        List<Integer> neighbors = getNeighbors(i);
        Iterator<Integer> it = neighbors.iterator();

        while (it.hasNext()) {
          insertEdge(i, it.next(), true);
        }
      }
    }

    public void bfs(int start) {
      int v, y;
      EdgeNode p;

      for (int i = 0; i < COMBINATIONS; i++) {
        parent[i] = -1;
        discovered[i] = false;
      }

      LinkedList<Integer> queue = new LinkedList<Integer>();
      queue.add(start);
      discovered[start] = true;

      while (!queue.isEmpty()) {
        v = queue.pollLast();
        p = this.edges[v];

        while (p != null) {
          y = p.y;
          if (!invalid[y] && !discovered[y]) {
            queue.push(y);
            discovered[y] = true;
            parent[y] = v;
          }
          p = p.next;
        }
      }
    }

    public int findPath(int start, int end) {
      if ((start == end) || (end == -1)) {
        return 0;
      } else {
        return 1 + findPath(start, parent[end]);
      }
    }

    private void insertEdge(int x, int y, boolean directed) {
      EdgeNode node = new EdgeNode(y);
      node.next = this.edges[x];
      this.edges[x] = node;
    }

    private List<Integer> getNeighbors(Integer combination) {
      List<Integer> neighbors = new LinkedList<Integer>();
      int digit, temp = combination;

      for (int i = 0; i < 4; i++) {
        digit = temp % 10;
        temp = temp / 10;

        if (digit == 0) {
          neighbors.add(combination + 9 * (int) Math.pow(10, i));
          neighbors.add(combination + (int) Math.pow(10, i));
        } else if (digit == 9) {
          neighbors.add(combination - 9 * (int) Math.pow(10, i));
          neighbors.add(combination + (int) -Math.pow(10, i));
        } else {
          neighbors.add(combination + (int) -Math.pow(10, i));
          neighbors.add(combination + (int) Math.pow(10, i));
        }
      }

      return neighbors;
    }
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuffer sb = new StringBuffer();
    int cases = Integer.parseInt(br.readLine().trim()), invalidCases = 0, source = 0, destination = 0;
    Graph graph = new Graph();

    for (int y = 0; y < cases; y++) {

      source = Integer.parseInt(
          br.readLine().replaceAll("[^0-9]", ""));
      destination = Integer.parseInt(
          br.readLine().replaceAll("[^0-9]", ""));

      invalidCases = Integer.parseInt(
          br.readLine().replaceAll("[^0-9]", ""));

      for (int i = 0; i < invalidCases; i++) {
        graph.invalid[Integer.parseInt(br.readLine().replaceAll("[^0-9]", ""))] = true;
      }

      graph.bfs(source);

      if (graph.parent[destination] == -1) {
        sb.append("-1\n");
      } else {
        sb.append(graph.findPath(source, destination) + "\n");
      }

      if (y != (cases-1)) {
        br.readLine();
      }
    }

    System.out.print(sb);
  }
}

[brianfry713]

My AC C++ code reads the input using cin >> int.

[drseergio]

I've been solving another problem and ran into a similar problem. I think the issue is with how I use BufferedReader. In the other problem I was able to fix it by using Scanner object. I will check this out further and will update the thread once I am able to submit it.

[ygge]

I had the same problem, got Runtime error for my submission in Java.
I played around a bit and got it to accepted when i didn't assume that there was an empty row between test cases but instead read row after row until I got a row that had som info when I needed it:

Code: Select all

    private static int parseNumber(BufferedReader in) throws IOException {
        String row;
        while ((row = in.readLine()).trim().length() == 0);
        return Integer.parseInt(row.replaceAll(" ", ""), 10);
    }


[achan8501]

On this case:
1
9 9 9 9
0 0 0 0
1
9 9 9 9

The code I just submitted and got AC with returns -1, if you'd rather believe your WA code and UVAtoolkit's 4 that's up to you, let us know if you can get AC with that logic. Others in this thread that have got AC agreed that it should be -1.

My AC code returns 4 on that input, but -1 for
1
9 9 9 9
0 0 0 0
1
0 0 0 0
One can only assume that the case you proposed was not in the test data at all.

Edit: In fact, my output matches his line for line, so there should be no troublesome cases in the judge at all.