11492 - Babel

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

mmfrb
New poster
Posts: 13
Joined: Thu Aug 30, 2012 3:21 pm

Re: 11492 - Babel

Post by mmfrb » Tue Oct 16, 2012 12:04 pm

Is it because of "cin" ? is there a way to submit offline to see how much time does it take? Plzz help

phantom11
New poster
Posts: 7
Joined: Thu Sep 12, 2013 12:36 am

11492 - Babel

Post by phantom11 » Mon Sep 23, 2013 3:53 pm

I am getting Runtime Error. Is there a problem in the test cases ?
Here is my code:

Code: Select all

import java.util.List;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.PriorityQueue;
import java.util.Hashtable;
import java.util.ArrayList;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.StringTokenizer;
import java.util.AbstractCollection;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Lokesh Khandelwal
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		OutputWriter out = new OutputWriter(outputStream);
		Babel_11492 solver = new Babel_11492();
		solver.solve(1, in, out);
		out.close();
	}
}

class Babel_11492 {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int m, i, a, b, x;
        String start, finish, p;
        String l1, l2;
        int s, d, upperLimit = (1<<30);
        Hashtable<String, Integer> table = new Hashtable<String, Integer>();
        List<Edge> graph[] = new List[2000];
        for(i=0;i<2000;i++) {
            graph[i] = new ArrayList<Edge>();
        }
        while (true) {
            m = in.nextInt();
            if(m == 0)
                break;
            start = in.next();
            finish = in.next();

            table.clear();
            for(i=0;i<2000;i++) {
                graph[i].clear();
            }

            x = 0;
            for(i=0;i<m;i++) {
                l1 = in.next();
                l2 = in.next();
                p = in.next();
                if(table.containsKey(l1))
                    a = table.get(l1);
                else {
                    table.put(l1, x);
                    a = x++;
                }
                if(table.containsKey(l2))
                    b = table.get(l2);
                else {
                    table.put(l2, x);
                    b = x++;
                }
                int l = p.length();
                Edge e1 = new Edge(l, p.charAt(0), b);
                Edge e2 = new Edge(l, p.charAt(0), a);
                graph[a].add(e1);
                graph[b].add(e2);
            }

            if(!table.containsKey(start)) {
                out.printLine("impossivel");
                continue;
            }
            if(!table.containsKey(finish)) {
                out.printLine("impossivel");
                continue;
            }
            s = table.get(start);
            d = table.get(finish);
            if(s == d) {
                out.printLine("impossivel");
                continue;
            }
            int key[] = new int[2000];
            Arrays.fill(key, upperLimit);
            PriorityQueue<Vertex> pq = new PriorityQueue<Vertex>();
            pq.add(new Vertex(s, '!', 0));
            key[s] = 0;
            while (!pq.isEmpty()) {
                Vertex u = pq.poll();
                key[u.index] = Math.min(key[u.index], u.key);
                for(Edge e : graph[u.index]) {
                    if(u.parent != e.dest && u.key + e.length < key[e.dest] && e.firstChar != u.label) {
                        Vertex v = new Vertex(e.dest, e.firstChar, e.length + u.key);
                        v.parent = u.index;
                        pq.add(v);

                    }
                }
                //for(Vertex v : pq)
                //    DebugUtils.print(v.index, v.key, v.parent, v.label);
                //DebugUtils.print("........");
            }
            if(key[d] == upperLimit) {
                out.printLine("impossivel");
            }
            else out.printLine(key[d]);
        }
    }
    class Vertex implements Comparable<Vertex> {
        int index, key, parent;
        char label;
        public Vertex(int index, char label, int key) {
            this.index = index;
            this.label = label;
            this.key = key;
            parent = -1;
        }
        public int compareTo(Vertex x) {
            return this.key - x.key;
        }
    }
    class Edge {
        int length;
        char firstChar;
        int dest;
        public Edge(int length, char fChar, int destIndex) {
            this.length = length;
            this.firstChar = fChar;
            this.dest = destIndex;
        }
    }
}

class InputReader
{
    BufferedReader in;
    StringTokenizer tokenizer=null;

    public InputReader(InputStream inputStream)
    {
        in=new BufferedReader(new InputStreamReader(inputStream));
    }
    public String next()
    {
        try{
            while (tokenizer==null||!tokenizer.hasMoreTokens())
            {
                tokenizer=new StringTokenizer(in.readLine());
            }
            return tokenizer.nextToken();
        }
        catch (IOException e)
        {
            return null;
        }
    }
    public int nextInt()
    {
        return Integer.parseInt(next());
    }
    }

class OutputWriter {
	private final PrintWriter writer;

	public OutputWriter(OutputStream outputStream) {
		writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
	}

	public OutputWriter(Writer writer) {
		this.writer = new PrintWriter(writer);
	}

	public void print(Object...objects) {
		for (int i = 0; i < objects.length; i++) {
			if (i != 0)
				writer.print(' ');
			writer.print(objects[i]);
		}
	}

	public void printLine(Object...objects) {
		print(objects);
		writer.println();
	}

	public void close() {
		writer.close();
	}
}


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11492 - Babel

Post by brianfry713 » Fri Oct 11, 2013 9:12 pm

If there are 2000 words, each connecting 2 unique languages, then there may be up to 4000 languages total.
Check input and AC output for thousands of problems on uDebug!

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

Re: 11492 - Babel

Post by raj » Sat Feb 22, 2014 3:42 am

I am getting Runtime Error. Is there a problem in the test cases ?
while(true) is not an actual way
as sir brainfry mentioned that if 4000 lines than what happened?
in the case of
while(true) that means user take input infinite number of times that will not happen when a computer cheque your code.
They will cheque your code with limited number of lines of input. Then after completing their chequed inputs in your code. Your program will still taking the input which
occurs NullPointerException.

so in java if you use scanner use while(scanner.hasNext())
on the other hand if you use BufferedReader use like this.
String line;
while((line = bufferedReader.readLine())!=null){}

Post Reply

Return to “Volume 114 (11400-11499)”