Posts

Showing posts from February, 2017

(UVA) Ant's Shopping Mall - Solution

-
Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3942 import java.io.*; import java.util.*; class Main {     public void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         int numTests = sc.nextInt();         for (int test = 0; test < numTests; test++) {             int numRows = sc.nextInt();             int numCols = sc.nextInt();             int[][] matrix = new int[numRows][numCols];         ...
Post a Comment
Read more

(UVA) Wedding of Sultan - Solution

-
Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=666&page=show_problem&problem=4027 import java.io.*; import java.util.*; class Main {     public Deque<Character> trails;         public void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         int numTests = sc.nextInt();         for (int test = 0; test < numTests; test++) {             String seq = sc.next();             char start = seq.charAt(0);                ...
Post a Comment
Read more

(UVA) The Orc Attack - Solution

-
Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1734 The solution below used Floyd-Warshall to solve this problem. import java.io.*; import java.util.*; class Main {     public void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         int numTests = sc.nextInt();         for (int test = 0; test < numTests; test++) {             int numLocations = sc.nextInt();             int numConnections = sc.nextInt();               ...
Post a Comment
Read more

(UVA) Galactic Import - Solution

-
Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=676&page=show_problem&problem=324 The solution below used Breadth-First Search (BFS) to solve this problem. import java.io.*; import java.util.*; class Main {     public HashMap<Character, ArrayList<Info>> adjList;         public char bfs(char start, int numPlanets) {         Queue<Info> queue = new ArrayDeque<>();         queue.add(new Info(start, 0, 0));                 HashSet<Character> visited = new HashSet<>();                 double bestValue = 0;         char bestPlanet = 'Z';         while (queue.size() ...
Post a Comment
Read more

(UVA) Word Transformation - Solution 2

-
Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=676&page=show_problem&problem=370 The solution below used Floyd-Warshall to solve this problem. If you want to see another solution using Breadth-First Search, click here . import java.io.*; import java.util.*; class Main {     public ArrayList<String> mapIntToString;     public Map<String, Integer> mapStringToInt;         public void process() throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         int numTests = Integer.parseInt(br.readLine());         br.readLine();      ...
Post a Comment
Read more

(UVA) Word Transformation - Solution 1

-
Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=676&page=show_problem&problem=370 The solution below used Breadth-First Search (BFS) to solve this problem. For every word that we visit in the BFS method, we check all the other words. If the other word differs only in one character of the current word, we add it in our queue. import java.io.*; import java.util.*; class Main {     public ArrayList<String> words;         public int bfs(String start, String end) {         Queue<Counter> queue = new ArrayDeque<>();         queue.add(new Counter(start, 0));                 HashSet<String> visited = new HashSet<>();                 while (q...
Post a Comment
Read more

(UVA) Y2K Accounting Bug - Solution

-
Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1517 The solution below used Backtracking to solve this problem. import java.io.*; import java.util.*; class Main {     public int s;     public int d;     public int maxSurplus;     public int[] register;         public void rec(int month, int surplus, int lastFive) {         if (month >= 5) {             if (lastFive >= 0) {                 return;             }         }         if (month == 12) {           ...
Post a Comment
Read more

(UVA) Route Change - Solution

-
Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2933 Given a start position, the problem asks us to find the minimum total toll cost for the vehicle to reach the destination city. For this reason, the code below used Dijkstra's algorithm to find the solution. import java.io.*; import java.util.*; class Main {     public ArrayList<ArrayList<Edge>> adjList;     public int citiesServiceRoute;         public int dijkstra(int start, int end) {         Queue<Edge> queue = new PriorityQueue<>();         queue.add(new Edge(start, 0));                 HashSet<Integer> visited = new HashSet<>();             ...
Post a Comment
Read more

(Hacker Rank) The Longest Common Subsequence - Solution

-
import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution {     public static int sizeSeqA;     public static int sizeSeqB;     public static int[] seqA;     public static int[] seqB;     public static int[][] memo;             public static int lcs(int indexA, int indexB) {         if (indexA == sizeSeqA || indexB == sizeSeqB) {             return 0;         }                    if (memo[indexA][indexB] != -1) {             return memo[indexA][indexB];         }       ...
Post a Comment
Read more

(UVA) Oreon - Solution 2

-
Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3649 If you want to see another solution for this problem, click here . This solution used Prim's algorithm to solve this problem. import java.io.*; import java.util.*; class Main {     public ArrayList<ArrayList<Edge>> adjList;     public Queue<Edge> edges;         public void prim(int start, int numCities) {         Queue<Edge> queue = new PriorityQueue<>();         queue.add(new Edge(start, 0, -1));                 HashSet<Integer> visited = new HashSet<>();                 while (queue.size() > 0) {     ...
Post a Comment
Read more