All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.
Moderator: Board moderators
mehankit7
New poster
Posts: 2 Joined: Thu Jan 26, 2012 6:31 pm
Post
by mehankit7 » Thu Jan 26, 2012 6:36 pm
While submitting the following code, I am getting run time error!!
.. Please Help.
Code: Select all
import java.util.*;
import java.io.*;
public class Wheels {
public static void main(String[] args) throws IOException{
BufferedReader inp = new BufferedReader(new InputStreamReader(System.in));
int test = Integer.parseInt(inp.readLine());
while(test>0){
String start = inp.readLine();
StringTokenizer sm = new StringTokenizer(start," ");
String temp = new String("");
while(sm.hasMoreTokens()){
temp = temp+sm.nextToken();
}
int st = Integer.parseInt(temp);
String end = inp.readLine();
StringTokenizer sm2 = new StringTokenizer(end," ");
String temp2 = new String("");
while(sm2.hasMoreTokens()){
temp2 = temp2 + sm2.nextToken();
}
int en = Integer.parseInt(temp2);
int f = Integer.parseInt(inp.readLine());
int forbid[] = new int[f];
int i =0;
while(i<f){
String temp3 = new String("");
StringTokenizer z = new StringTokenizer(inp.readLine()," ");
while(z.hasMoreTokens()){
temp3 = temp3+z.nextToken();
}
forbid[i] = Integer.parseInt(temp3);
i++;
}
System.out.println(compute(st,en,forbid));
if(test!=1){
String s = inp.readLine();
}
test--;
}
}
public static int compute(int st, int end, int[] forbid){
if(st==end) return 0;
LinkedList<Integer> q = new LinkedList<Integer>();
q.offer(st);
HashMap<Integer,Boolean> discovered = new HashMap<Integer,Boolean>();
discovered.put(st,true);
HashMap<Integer,Integer> cost = new HashMap<Integer,Integer>();
cost.put(st,0);
while(!q.isEmpty()){
int current = q.poll();
int k = 0;
int[] child = construct(current);
while(k<8){
if(child[k]==end)return cost.get(current)+1;
if(!search(forbid,child[k])){
if(!discovered.containsKey(child[k])){
discovered.put(child[k],true);
q.offer(child[k]);
cost.put(child[k],cost.get(current)+1);
}
}
k++;
}
}
return -1;
}
public static boolean search(int[] forbid,int val){
for(int i =0;i<forbid.length;i++){
if(forbid[i]==val) return true;
}
return false;
}
public static int[] construct(int current){
int res[] = new int[8];
int digs[] = new int[4];
digs[3] = current%10;
int temp = (current%100);
digs[2] = temp/10;
digs[1] = (current%1000)/100;
digs[0] = (current%10000)/1000;
if(digs[0]==9) {
res[0] = digs[1]*100 + digs[2]*10 + digs[3];
}
else{
res[0] = (digs[0]+1)*1000 + digs[1]*100 + digs[2]*10 + digs[3];
}
if(digs[1]==9) {
res[1] = digs[0]*1000 + digs[2]*10 + digs[3];
}
else{
res[1] = (digs[1]+1)*100 + digs[0]*1000 + digs[2]*10 + digs[3];
}
if(digs[2]==9) {
res[2] = digs[0]*1000 + digs[1]*100 + digs[2]*0 + digs[3];
}
else{
res[2] = digs[0]*1000 + digs[1]*100 + (digs[2]+1)*10 + digs[3];
}
if(digs[3]==9) {
res[3] = digs[0]*1000 + digs[1]*100 + digs[2]*10 + digs[3]*0;
}
else{
res[3] = (digs[0])*1000 + digs[1]*100 + digs[2]*10 + digs[3]+1;
}
if(digs[0]==0) {
res[4] = 9000 + digs[1]*100 + digs[2]*10 + digs[3];
}
else{
res[4] = (digs[0]-1)*1000 + digs[1]*100 + digs[2]*10 + digs[3];
}
if(digs[1]==0) {
res[5] = digs[0]*1000 + digs[2]*10 + digs[3]+900;
}
else{
res[5] = (digs[1]-1)*100 + digs[0]*1000 + digs[2]*10 + digs[3];
}
if(digs[2]==0) {
res[6] = 90+digs[0]*1000 + digs[1]*100 + digs[2]*0 + digs[3];
}
else{
res[6] = digs[0]*1000 + digs[1]*100 + (digs[2]-1)*10 + digs[3];
}
if(digs[3]==0) {
res[7] = 9+digs[0]*1000 + digs[1]*100 + digs[2]*10 + digs[3]*0;
}
else{
res[7] = (digs[0])*1000 + digs[1]*100 + digs[2]*10 + digs[3]-1;
}
return res;
}
}
mehankit7
New poster
Posts: 2 Joined: Thu Jan 26, 2012 6:31 pm
Post
by mehankit7 » Sat Jan 28, 2012 11:55 am
I think its giving NumberFormatException. But do not know why! Please help!
Monty
New poster
Posts: 7 Joined: Fri Feb 17, 2012 10:24 am
Post
by Monty » Tue Apr 03, 2012 4:25 am
Tried every test case in this thread and I pass all of them, still I keep getting WA.. Not sure what else to do, I made sure I handled cases where the start is the target, the target is in the forbidden list, 9+1 goes to 0, 0-1 goes to 9. Are there any other elementary cases I could be tripping up on? Thanks
10 Cases:
Code: Select all
10
9 9 9 9
9 9 9 9
1
9 9 9 9
9 9 9 9
0 0 0 0
1
0 0 0 0
9 9 9 9
0 0 0 0
1
9 9 9 9
3 3 4 2
1 2 0 9
1
3 4 4 2
9 9 9 9
0 0 0 1
3
8 9 0 7
6 5 4 2
2 3 4 5
9 9 9 9
0 0 1 1
3
8 9 0 7
6 5 4 2
2 3 4 5
0 0 0 0
0 0 0 1
3
8 9 0 7
6 5 4 2
2 3 4 5
1 5 7 9
7 4 3 1
6
8 9 0 7
6 5 4 2
2 3 4 5
4 4 4 4
6 5 7 9
8 5 7 9
1 5 7 9
7 4 3 1
6
8 9 0 7
6 5 4 2
2 3 4 5
4 4 4 4
0 0 0 0
8 5 7 9
1 7 1 0
7 0 0 0
6
1 9 0 7
1 4 2 2
1 3 4 5
4 4 4 4
2 5 0 9
1 1 7 9
My Output:
brianfry713
Guru
Posts: 5947 Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA
Post
by brianfry713 » Wed Apr 04, 2012 1:18 am
AC output for your input:
Check input and AC output for thousands of problems on
uDebug !
brianfry713
Guru
Posts: 5947 Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA
Post
by brianfry713 » Thu Apr 05, 2012 7:49 pm
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.
Check input and AC output for thousands of problems on
uDebug !
Monty
New poster
Posts: 7 Joined: Fri Feb 17, 2012 10:24 am
Post
by Monty » Thu Apr 05, 2012 10:26 pm
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
Guru
Posts: 5947 Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA
Post
by brianfry713 » Sat Apr 07, 2012 1:01 am
No critical input besides what you've posted, I used a straightforward BFS.
Check input and AC output for thousands of problems on
uDebug !
drseergio
New poster
Posts: 2 Joined: Tue Jul 31, 2012 4:02 pm
Post
by drseergio » Tue Jul 31, 2012 4:08 pm
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
Guru
Posts: 5947 Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA
Post
by brianfry713 » Wed Aug 01, 2012 3:30 am
My AC C++ code reads the input using cin >> int.
Check input and AC output for thousands of problems on
uDebug !
drseergio
New poster
Posts: 2 Joined: Tue Jul 31, 2012 4:02 pm
Post
by drseergio » Sun Aug 05, 2012 10:02 pm
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
New poster
Posts: 1 Joined: Wed Sep 05, 2012 8:23 pm
Post
by ygge » Wed Sep 05, 2012 8:32 pm
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
New poster
Posts: 6 Joined: Mon Nov 05, 2012 9:13 pm
Post
by achan8501 » Mon Nov 26, 2012 7:40 am
brianfry713 wrote: 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.
mourad.ghafiri
New poster
Posts: 6 Joined: Thu Dec 20, 2012 9:25 pm
Post
by mourad.ghafiri » Thu Dec 20, 2012 9:29 pm
i used the most efficient algorithm and also i handled all cases i think it'll give a wrong answer but still wrong answer ...
any one can help!!
Code: Select all
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Vector;
class LockState implements Comparable<LockState>{
String value;
int hn=0;
int gn=1;
int fn=0;
LockState prev=null;
public LockState() {
}
public LockState(String value) {
this.value=value;
}
@Override
public String toString() {
return this.value + " fn = "+this.fn;
}
public int compareTo(LockState s) {
if(this.fn==s.fn) return 0;
else if(this.fn>s.fn) return 1;
else return -1;
}
}
public class Main{
static Vector<String> Visited = new Vector<String>();
static String initCong = "";
static String goalConf = "";
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int nf ;
for (int i = 0; i < n; i++) {
String forbidden;
Visited.clear();
initCong="";
goalConf="";
if(i != 0) in.nextLine();
for (int j = 0; j < 4; j++) {
initCong+= String.valueOf(in.nextInt());
}
for (int j = 0; j < 4; j++) {
goalConf+= String.valueOf(in.nextInt());
}
nf = in.nextInt();
for (int j = 0; j < nf; j++) {
forbidden="";
for (int k = 0; k < 4; k++) {
forbidden+= String.valueOf(in.nextInt());
}
Visited.add(forbidden);
}
if(i!=n-1){
System.out.print(A_Star(new LockState(initCong)));
}
else {
System.out.println(A_Star(new LockState(initCong)));
}
}
}
static int heuristic(String state){
int g=0;
for (int i = 0; i < state.length(); i++) {
int xi= state.charAt(i) - 48;
int xj= goalConf.charAt(i) - 48;
if((xi<5 && xj>5) || (xi>5 && xj<5)){
g+=(10-Math.abs(xi-xj))%10;
}
else g+=(Math.abs(xi-xj))%10;
}
return g;
}
static Vector<LockState> getNextStates(LockState state){
Vector<LockState> neighbours = new Vector<LockState>();
LockState next;
for (int i = 0; i < state.value.length(); i++) {
char[] tabchar = state.value.toCharArray();
int charint = state.value.charAt(i)-48;
if(charint==0){
tabchar[i]='1';
next = new LockState(String.valueOf(tabchar));
next.hn=heuristic(String.valueOf(tabchar));
neighbours.add(next);
tabchar[i]='9';
next = new LockState(String.valueOf(tabchar));
next.hn=heuristic(String.valueOf(tabchar));
neighbours.add(next);
}
else {
tabchar[i]=(char)('0'+(charint+1)%10);
next = new LockState(String.valueOf(tabchar));
next.hn=heuristic(String.valueOf(tabchar));
neighbours.add(next);
tabchar[i]=(char)('0'+(charint-1)%10);
next = new LockState(String.valueOf(tabchar));
next.hn=heuristic(String.valueOf(tabchar));
neighbours.add(next);
}
}
return neighbours;
}
static int A_Star(LockState s0){
PriorityQueue<LockState> prqueue = new PriorityQueue<LockState>();
Vector<LockState> nexts;
if(initCong.compareTo(goalConf)==0) return 0;
if(Visited.contains(goalConf)) return -1;
prqueue.add(s0);
while(!prqueue.isEmpty()){
LockState test = prqueue.poll();
if(test.value.equals(goalConf)){
return test.gn-1;
}
Visited.add(test.value);
nexts=getNextStates(test);
for (int i = 0; i < nexts.size(); i++) {
if(!Visited.contains(nexts.elementAt(i).value)){
nexts.elementAt(i).prev=test;
nexts.elementAt(i).gn+=test.gn;
nexts.elementAt(i).fn=nexts.elementAt(i).gn+nexts.elementAt(i).hn;
prqueue.add(nexts.elementAt(i));
}
}
}
return -1;
}
}
mourad.ghafiri
New poster
Posts: 6 Joined: Thu Dec 20, 2012 9:25 pm
Post
by mourad.ghafiri » Thu Dec 20, 2012 11:31 pm
finally it is AC
i had a problem in the heuristic function it is incorrect and also i replaced system.out.println in each case by a BuffredString to add up the reslt of each case
and here it is , it works
thank you guys for !!