uva: 11060 – Beverages (Topological sort)

11060 - Beverages (Topological sort)

#include <stdio.h>
#include <iostream>
#include <map>
#include <vector>
#include <queue>
#include <string>
//#include <conio.h>

using namespace std;

typedef pair<string,int> namval;
typedef pair<int,string> valnam;
typedef vector vi;

struct compareval
{
	bool operator()(const int& a, const int& b)
	{
		return a > b;
	}
};

int main()
{
	int vertex, edge,tc=0;
	string str, start, end;

	while(scanf("%d", &vertex)==1)
	{
		map<string,int> name_value;
		map<int, string> value_name;

		for(int i=0; i < vertex; i++)
		{
			cin>>str;
			name_value.insert(namval(str, i));
			value_name.insert(valnam(i, str));
		}

		scanf("%d", &edge);
		vector adjList;
		adjList.assign(vertex,vi());

		vi indegree = vi(vertex);
		indegree.assign(vertex,0);

		for(int i=0; i < edge; i++)
		{
			cin>>start;
			cin>>end;

			int u = name_value.find(start)->second;
			int v = name_value.find(end)->second;

			adjList.at(u).push_back(v);
			indegree[v] +=1;
		}

		priority_queue<int, vector<int>, compareval> pq;

		for(int i=0; i < vertex; i++)
		{
			if(indegree[i] == 0)
			{
					pq.push(i);
			}
		}

		vi order = vi();

		while(!pq.empty())
		{
			int u = pq.top(); pq.pop();
			order.push_back(u);

			for(int i=0; i < adjList[u].size(); i++)
			{
				 int v = adjList[u][i];
			 	 indegree[v]--;
				 if(indegree[v]==0 )
						 pq.push(v);
			}
		}

		printf("Case #%d: Dilbert should drink beverages in this order: %s",++tc, value_name[order[0]].data() );
		for(int i = 1; i < order.size(); i++)
		{
			printf(" %s",  value_name[order[i]].data());
		}
		printf(".\n\n");
	}
	//getch();
return 0;
}

//
/*

http://uva.onlinejudge.org/external/110/11060.html

Sample Input

3
vodka
wine
beer
2
wine vodka
beer wine

5
wine
beer
rum
apple-juice
cachaca
6
beer cachaca
apple-juice beer
apple-juice rum
beer rum
beer wine
wine cachaca

10
cachaca
rum
apple-juice
tequila
whiskey
wine
vodka
beer
martini
gin
11
beer whiskey
apple-juice gin
rum cachaca
vodka tequila
apple-juice martini
rum gin
wine whiskey
apple-juice beer
beer rum
wine vodka
beer tequila

Sample Output

Case #1: Dilbert should drink beverages in this order: beer wine vodka.

Case #2: Dilbert should drink beverages in this order: apple-juice beer wine rum cachaca.

Case #3: Dilbert should drink beverages in this order: apple-juice wine vodka beer rum cachaca tequila whiskey martini gin.

*/

Advertisements

uva: 10305 Ordering Tasks ( Topological sort )

10305 Ordering Tasks ( Topological sort )

Problem and solution –

import java.io.IOException;
import java.util.PriorityQueue;
import java.util.Queue;


class Main_10305_OrderingTasks {
	
	static String readInputLine() throws IOException
	{

		int byt,index=0;
		byte[] bytes= new byte[255];

		while(true)
		{
			byt = System.in.read();
			if(byt==-1 || byt =='\n') break;
			bytes[index++] += byt;
		}

		if(bytes.length==0) return null;

		return new String(bytes);
	}

	public static void main(String[] args) throws IOException {
		String line;
		String[] tempArr;
		int vertex, edge, u,v;
		int[][] graph;
		int[] indegree;
		StringBuilder order;
		Queue q = new PriorityQueue(100+1);

		while(true)
		{

			line = readInputLine();
			if(line == null) break;

			tempArr = line.trim().split(" ");
			vertex = Integer.parseInt(tempArr[0]);
			edge = Integer.parseInt(tempArr[1]);

			if(vertex ==0) break;

			graph = new int[vertex+2][vertex+2];
			indegree = new int[vertex+1];
			order = new StringBuilder();
			
			for(int i=1; i<=edge; i++)
			{
				tempArr=  readInputLine().trim().split(" ");
				u = Integer.parseInt(tempArr[0]);
				v = Integer.parseInt(tempArr[1]);

				graph[u][v] = 1;
				indegree[v] +=1;
			}	

			//start processing tasks/vertex
			q.clear();
			while(true)
			{
				u=v=-1;
				for(int i=1; i<=vertex; i++)
				{
					if(indegree[i] == 0 )
					{		
						q.add(i);
						indegree[i] = -1; //task in queue
						order.append(i+" ");//output data											
					}
				}
				
				//if no task to process then break
				if(q.isEmpty()) break;
				u = q.poll();
				//reduce indegree from source/u task to dependent tasks
				for(v=0; v <= vertex; v++)
				{
					if(graph[u][v]==1) 
					{
						graph[u][v] = 0;
						indegree[v] -= 1;
					}
				}
			}
			//output tasks order
			System.out.println(order.toString().trim() );
			
		}
		//System.out.println(str);
	}

}




/*

Sample Input

5 4
1 2
2 3
1 3
1 5
0 0
Sample Output

1 4 2 5 3

*
*/

uva: 11831 Sticker Collector Robots

Problem and solution analysis: it is simple graph traversal problem.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


 class Main_11831_StickerCollectorRobots {

	/**
	 * TL
	 * Graph Traversal
	 * http://uva.onlinejudge.org/external/118/11831.html
	 * 
	 * `.' -- normal cell;
`*' -- cell which contains a sticker;
`#' -- cell which contains a pillar;
`N' - North, `S' - South, `L' - EAST, `O' - West -- cell where the robot starts the rally

D -``turn 90 degrees to the right"
E- ``turn 90 degrees to the left" 
F - ``move forward one cell"
	 */
	
	
	private  static  final char RIGHT='D',LEFT='E', MOVE='F';
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String dirs = "NLSO";//NESW
		int[] dr = {-1,0,1, 0};//NESW
		int[] dc = { 0,1,0,-1};//		
		char[][] graph;
		int NRow, MCol, SIns, stickerCount, index;
		int currentDir, currentRow, currentCol, newr, newc;		
		String instruction;
		String[] strArray;
		char ch;
		

		while(true)
		{
			strArray = br.readLine().trim().split(" ");
			
			NRow = Integer.parseInt(strArray[0]);
			if(NRow == 0) break;

			MCol = Integer.parseInt(strArray[1]);
			SIns = Integer.parseInt(strArray[2]);			
			currentRow = 0;
			currentCol =0;
			currentDir = 0;
			graph = new char[NRow][MCol];
			
			for(int i=0; i < NRow; i++)
			{				
				graph[i] = br.readLine().trim().toCharArray();

				for(int j=0; j < MCol; j++)
				{					
					index = dirs.indexOf(graph[i][j]);
					if(index>=0)
					{						
						currentDir = index;
						currentRow = i;
						currentCol = j;							
					}
				}
			}

			instruction = br.readLine().trim();
			stickerCount = 0;
			for(int i=0; i < SIns; i++)
			{
				ch = instruction.charAt(i);
				if(ch==RIGHT )
					currentDir= (currentDir + 1) % 4;
				else if(ch == LEFT)
					currentDir= (currentDir + 3) % 4;
				else if(ch == MOVE)
				{
					newr = currentRow +  dr[currentDir];
					newc = currentCol + dc[currentDir];
					if(newr>=0 && newc>=0 && newr < NRow && newc < MCol && graph[newr][newc] != '#')
					{						
						if(graph[newr][newc]=='*')
						{
							stickerCount++;
							graph[newr][newc] = '.';							
						}
						currentRow = newr;
						currentCol = newc;
					}
				}
			}
			
			System.out.println(stickerCount);
		}
	}
}

/*

 Sample Input 

3 3 2
***
*N*
***
DE
4 4 5
...#
*#O.
*.*.
*.#.
FFEFF
10 10 20
....*.....
.......*..
.....*....
..*.#.....
...#N.*..*
...*......
..........
..........
..........
..........
FDFFFFFFEEFFFFFFEFDF
0 0 0

Sample Output 

0
1
3


 * */

uva: 10405 – Longest Common Subsequence (LCS)

10405 – Longest Common Subsequence

Problem analysis:

Given two sequences of characters, print the length of the longest common subsequence of both sequences. For example, the longest common subsequence of the following two sequences:

abcdgh
aedfhr

is adh of length 3.

Solution analysis:

• LCS – solution of this problem is standard LCS  algorithm

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.lang.System;

class Main_10405_LCS {
    /**
     * Author: Mohammad Moniruzzaman
     * UVa ID: 457490     
     */

    public static void main(String[] args) {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc = new Scanner(br);
        String str1, str2;
        int[][] lcs;
        int i,j,m,n;
        
        while(sc.hasNext())
        {
            str1 = sc.nextLine();
            str2 = sc.nextLine();
            m = str1.length();
            n = str2.length();
            
            lcs = new int[m+1][n+1];
            
            for(i=1; i <= m; i++)
            {
                for(j=1; j <= n; j++)
                {
                    if(str1.charAt(i-1) == str2.charAt(j-1))
                    {
                        lcs[i][j] = lcs[i-1][j-1] + 1;
                    }
                    else
                    {
                        lcs[i][j] = Math.max( lcs[i-1][j], lcs[i][j-1] );
                    }                    
                }
            }
            System.out.println(lcs[m][n]);            
        }
        sc.close();
        sc = null;
    }

}

uva: 10066 – The Twin Towers ( LCS )

10066 – The Twin Towers

Problem analysis:

•  Given the descriptions of two dissimilar towers you are asked only to find out the number of tiles in the highest twin towers that can be built from them.
• For each pair of towers in the input first output the twin tower number followed by the number of tiles (in one tower) in the highest possible twin towers that can be built from them. Print a blank line after the output of each data set.

Soltion analysis:

•  LCS – solution of this problem is standard LCS  algorithm

C++ solution:

#include<stdio.h>

#define MAX 100
#define max(a,b) ((a)<(b) ? (b):(a))

int N1, N2;
int firstT[MAX+1];
int secondT[MAX+1];
int c[MAX+1][MAX+1];
int lcsLength, nCase;

int main10066()
{
	int i,j;

	//int firstT[MAX]={0};
	//int secondT[MAX]={0};

	while(true)
	{
		scanf("%d %d", &N1, &N2);

		if(N1 ==0 && N2==0) break;

		for(i=1; i<=N1; i++)
			scanf("%d",&firstT[i]);

		for(i=1; i<=N2; i++)
			scanf("%d",&secondT[i]);

		/*for(i=0;i <=N1; i++)
			for(j=0;j<=N2; j++)
				c[i][j] = 0;*/

		for(i=1; i<= N1; i++)
			for(j=1; j<= N2; j++)
			{
				if(firstT[i] == secondT[j])
				{
					c[i][j] = c[i-1][j-1] + 1;
				}
				else
				{
					c[i][j] = max(c[i-1][j], c[i][j-1]);
				}
			}

		printf("Twin Towers #%d\n",++nCase);
		printf("Number of Tiles : %d\n\n",c[N1][N2]);
	}
return 0;
}

Sample Input
7 6
20 15 10 15 25 20 15
15 25 10 20 15 20
8 9
10 20 20 10 20 10 20 10
20 10 20 10 10 20 10 10 20
0 0

Sample Output
Twin Towers #1
Number of Tiles : 4

Twin Towers #2
Number of Tiles : 6

uva: 11631 Dark Roads ( MST – Prim)

11631 Dark Roads

Problem analysis:

• There will still be at least one illuminated path from every junction (vertex) in Byteland to every other junction(vertex)
•  What is the maximum daily amount of money the government of Byteland can save, without making their inhabitants feel unsafe?
• Connecting all the vertexes/nodes with minimum  lighting costs  and finding saving of operating roads lighting

Solution Hints:

• This problem can be solved using Minimum Spanning Tree (MST) Prim’s, Kruskal’s  algorithms   –
  • Here it is solved using Prim’s
• Firstly, find the total costs of roads lighting
• Secondly, find the minimum costs at least one illuminated path for connecting all junctions (vertexes)
• Then, daily saving is deduction minimum costs from total costs.

Solution in Java and C++ are as follows:

 Solution in Java:

//TL
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

class EdgeDR implements Comparable
{
    int u;
    int v;
    int w;    
    public EdgeDR(int u, int v, int w)
    {
        this.u = u;
        this.v = v;
        this.w = w;
    }

    @Override
    public int compareTo(EdgeDR other) {        
        return this.w - other.w;
    }
}

class VertexDR implements Comparable
{
    int id;
    int key;
    public VertexDR(int id, int key)
    {
        this.id = id;
        this.key = key;
    }

    @Override
    public int compareTo(VertexDR other) {
        return this.key - other.key;
    }
}

class Main_11631_DarkRoads_MST_Prims {

    public static void main(String[] args) {        
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc = new Scanner(br);
        
        final int INF = Integer.MAX_VALUE;
        int V,E, v1, v2,u, w;
        int totalCost, minCost;            
        int[] key;        
            
        ArrayList mstTree;
        ArrayList<arraylist<EdgeDR>> graph;
        PriorityQueue pq;

        while(true)
        {
            V = sc.nextInt();
            E = sc.nextInt();

            if(V==0) break;            

            totalCost = 0;        
            key= new int[V];
            pq =  new PriorityQueue(V);
            mstTree = new ArrayList(V);
            graph =  new ArrayList<ArrayList<EdgeDR>>(V);

            Arrays.fill(key, INF);

            for(int i=0; i
            {
                graph.add(new ArrayList<EdgeDR>());                    
            }

            for(int i=0;i<E;i++)
            {
                v1 = sc.nextInt();
                v2 = sc.nextInt();
                w = sc.nextInt();

                totalCost += w;
                graph.get(v1).add(new EdgeDR(v1,v2,w));
                graph.get(v2).add(new EdgeDR(v2,v1,w));                
            }    

            minCost = 0;
            key[0] = 0;            
            pq.add(new VertexDR(0,0));

            while(!pq.isEmpty())
            {        
                u = pq.poll().id;
                if(!mstTree.contains(u))
                {
                    minCost += key[u];
                    mstTree.add(u);
                }
                
                for(EdgeDR e:graph.get(u))
                {
                    if(!mstTree.contains(e.v) && e.w < key[e.v])
                    {
                        key[e.v] = e.w;                            
                        pq.add(new VertexDR(e.v, key[e.v]));
                    }
                }

            }

            System.out.println(totalCost - minCost);
        }

    }

}

Solution in C++:

c++ code here

Sample Input

7 11
0 1 7
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
4 6 9
5 6 11
0 0

Sample Output

51

 

 

uva: 544 – Heavy Cargo ( Floyd Warshall MaxiMin )

544 – Heavy Cargo

Problem analysis:

• Given start and destination city, your job is to determine the maximum load of the Godzilla V12 so that there still exists a path between the two specified cities.

Solution analysis:

• It is solvable using Floyd Warshall Maximin algorithm

Java solution:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Hashtable;
import java.util.Map;
import java.util.Scanner;

class Main_544_HeavyCargo {

    /**
     * Author: Mohammad Moniruzzaman    
     */

    public static void main(String[] args) {
        final int INF = Integer.MIN_VALUE;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc = new Scanner(br);

        Map<String, Integer> cities;
        String line, start, end;
        int numVertexes, numEdges, load, testCase=0,source, dest;
        int[][] graph;

        while(true)
        {
            testCase++;

            numVertexes = sc.nextInt();
            numEdges = sc.nextInt();

            if(numVertexes ==0 ) break;

            cities =  new Hashtable<string, integer="">(numVertexes);
            graph = new int[numVertexes+1][numVertexes+1];

            for(int i=0; i < numVertexes; i++)
                for( int j=i; j < numVertexes; j++)
                    graph[i][j] = graph[j][i] = INF;
            
            //skip empty line
            sc.nextLine();
            
            for(int i=0; i < numEdges ; i++)
            {
                line = sc.nextLine();

                start = line.split(" ")[0];
                end = line.split(" ")[1];
                load = Integer.parseInt(line.split(" ")[2]);
                
                if(! cities.containsKey(start)) cities.put(start, cities.size());
                
                if(! cities.containsKey(end)) cities.put(end, cities.size());
                
                graph[cities.get(start)][cities.get(end)] = load;    
                graph[cities.get(end)][cities.get(start)] = load;
            }

            line = sc.nextLine();

            source = cities.get( line.split(" ")[0]);
            dest = cities.get(line.split(" ")[1]);

            ///Floyd-Warshall - MaxiMin            
            for(int k=0; k < numVertexes; k++)
                for(int i=0; i < numVertexes; i++)
                    for(int j=0; j < numVertexes; j++)
                    {
                        if(graph[i][k] != INF && graph[k][j] != INF)
                        {
                            graph[i][j] = Math.max(graph[i][j], Math.min(graph[i][k], graph[k][j]));
                        }
                    }

            System.out.printf("Scenario #%d%n",testCase);
            System.out.printf("%d tons%n%n",graph[dest]);
        }

    }

}

 

Sample Input 

4 3
Karlsruhe Stuttgart 100
Stuttgart Ulm 80
Ulm Muenchen 120
Karlsruhe Muenchen
5 5
Karlsruhe Stuttgart 100
Stuttgart Ulm 80
Ulm Muenchen 120
Karlsruhe Hamburg 220
Hamburg Muenchen 170
Muenchen Karlsruhe
0 0

Sample Output 

Scenario #1
80 tons

Scenario #2
170 tons