{{ $university }}                                                                                        

{{ $slogan }}

{{ $teamname }}

{{ $university }}


Contents

Problem Cues        4

BFS        4

Flood FIll        4

Brute Force        4

Backtracking        4

Dijkstra        4

A*        4

Default project        5

JAVA        5

Algorithms        5

Sieve - Primes        5

Priority Queue        5

Dijkstra        6

Datastructures        7

Hashmap Keys sorting with SortedSet  - Industrial Spy        7

Hashmap sorting with Collections.sort   - Grandpa Bernie        7

Priority Queue      - Assigning Workstations        7

});
Queue      - FIFO
        7

Deque      - Double Ended Queue        7

Stack      - FILO        7

Programming Tricks        8

Number base conversion        8

Math        8

Solutions        8

Wet Tiles (FLOOD FILL)        8

Problem        8

Solution        10

Levenshtein (string compare)        11

Brute force with doubles        12

Brute force without doubles        12

File I/O        13

Per line I/O        13

Problem Cues

BFS

Flood FIll

Brute Force

Backtracking

Dijkstra

A*


Default project

JAVA

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

public class Main {

   
public static void main(String[] args) throws IOException {
       BufferedReader in =
new BufferedReader(new InputStreamReader(System.in));

       
while (true) {
           
int firstLine = Integer.parseInt(in.readLine());

           
if (firstLine != -1) {

               
for (int i = 0; i < firstLine; i++) {
                   StringTokenizer tk =
new StringTokenizer(in.readLine());
               }

               System.out.println(
"output");
           }
else {
               
break;
           }
       }
   }
}

Algorithms

Sieve - Primes

boolean notPrime[] = new boolean[MAX_PRIME];
public static boolean[] sieve(boolean[] notPrime, int MAX_PRIME) {
        notPrime[
0] = notPrime[1] = true;
        
for (int i = 4; i < MAX_PRIME; i += 2) {
                notPrime[i] =
true;
        }
        
for (int i = 3; i * i <= MAX_PRIME; i += 2) {
                
for (int j = i * i; j < MAX_PRIME; j += i) {
                        notPrime[j] =
true;
                }
        }
                
        
return notPrime;
}

Priority Queue

final class Node implements Comparable<Node>
{
        
boolean visited = false;
        
public int dist = Integer.MAX_VALUE;
        
char desc = 'B';
        
int x = Integer.MAX_VALUE;
        
int y = Integer.MAX_VALUE;
        
@Override
public int compareTo(Node arg0)
        {
                
return dist - arg0.dist;
        }
}
                                        
PriorityQueue<Node> q =
new PriorityQueue<Node>();        

Dijkstra

Function DIJKSTRA (matrix[][] x)
        
Priority_queue<NODE>;
        Priority_queue.add (STARTNODE);
        
While(queue != empty)
                Node n = queue.pop
                
If node is not yet visited
                         
IF SOLUTION
                                Store solution
                                
BREAK
                
For each neighbour of node that is not visited
                        distance = n.distance + cost
                        
if(distance < neighbor.distance)
                                neighbor.distance = distance;
                                queue.push(neighbor);


Datastructures

Hashmap Keys sorting with SortedSet                - Industrial Spy

HashMap<String, Integer> spies = new HashMap<>();

Set<String> spyset = spies.keySet();

SortedSet<String> spy = new TreeSet<String>(spyset);

Hashmap sorting with Collections.sort                 - Grandpa Bernie

Map<String, List<Integer>> countriesWentTo = new HashMap<>();

Set<String> sortedLists = new HashSet<>();

if (!sortedLists.contains(country)) {

        sortedLists.add(country);

Collections.sort(countriesWentTo.get(country));

}

Priority Queue                                         - Assigning Workstations

PriorityQueue<int[]> researcherQueue = new PriorityQueue<>(intitialSize, new  Comparator<int[]>() {

         @Override
         public int compare(int[] t1, int[] t2) {

            return (t1[0] - t2[0]);
         }

});
Queue                                                - FIFO

Queue<Integer> queue = new LinkedList<Integer>();

for (int i = time; i >= 0; i--)
        queue.add(i);

while (!queue.isEmpty()) {
        System.out.println(queue.remove());
}

Deque                                                - Double Ended Queue

Stack                                                - FILO


Programming Tricks

Number base conversion

// To binary or some other base with integer, base
Integer.toString(INTEGER, BASE);

Math

Functions

a2-b2          = (a+b)*(a-b)

√( a x )          = √a* √x

Solutions

Wet Tiles (FLOOD FILL)

Problem

Alice owns a construction company in the town of Norainia, famous for its unusually dry weather. In fact, it only rains a few days per year there. Because of this phenomenon, many residents of Norainia neglect to do roof repairs until leaks occur and ruin their floors. Every year, Alice receives a deluge of calls from residents who need the leaks fixed and floor tiles replaced. While exquisite in appearance, Norainia floor tiles are not very water resistant; once a tile becomes wet, it is ruined and must be replaced. This year, Alice plans to handle the rainy days more efficiently than in past years. She will hire extra contractors to dispatch as soon as the calls come in, so hopefully all leaks can be repaired as soon as possible. For each house call, Alice needs a program to help her determine how many replacement tiles a contractor team will need to bring to complete the job.

For a given house, square floor tiles are arranged in a rectangular grid. Leaks originate from one or more known source locations above specific floor tiles. After the first minute, the tiles immediately below the leaks are ruined. After the second minute, water will have spread to any tile that shares an edge with a previously wet tile. This pattern of spreading water continues for each additional minute. However, the walls of a house restrict the water; if a damaged area hits a wall, the water does not penetrate the wall. We assume there are always four outer walls surrounding the entire house. A house may also have a number of additional “inner” walls; each inner wall is comprised of a connected linear sequence of locations (which may or may not be connected to the outer walls or to each other).

As an example, Figure 1 shows water damage (in gray) that would result from three initial leaks (each marked with a white letter ‘L’) after each of the first five minutes of time. Tiles labeled ‘2’ become wet during the second minute, tiles labeled ‘3’ become wet during the third minute, and so forth. The black areas designate inner walls that restrict the flow of water. Note that after 5 minutes, a total of 75 tiles have been damaged and will need to be replaced. Figures 2 through 4 show other houses that correspond to the example inputs for this problem.


Input

The input is composed of TT test cases (1⩽T⩽201⩽T⩽20), each representing a house.

Each house is described beginning with a line having five integral parameters: X Y T L WX Y T L W. Parameters XX and YYdesignate the dimensions of the rectangular grid, with 1⩽X⩽10001⩽X⩽1000 and 1⩽Y⩽10001⩽Y⩽1000. The coordinate system is one-indexed, as shown in the earlier figures. Parameter TT designates the number of minutes that pass before a team of contractors arrives at a house and stops the leaks, with 1⩽T⩽2000001⩽T⩽200000. The parameter L designates the number of leaks, with 1⩽L⩽1001⩽L⩽100. Parameter WW designates the number of inner walls in the house, 0⩽W⩽1000⩽W⩽100.

The following 2⋅L2⋅L integers in the test case, on one or more lines, are distinct (xy)(xy) pairs that designate the locations of the LL distinct leaks, such that 1⩽x⩽X1⩽x⩽X and 1⩽y⩽Y1⩽y⩽Y.

If W>0W>0, there will be 4⋅W4⋅W additional integers, on one or more lines, that describe the locations of the walls. For each such wall the four parameters (x1,y1)(x1,y1), (x2,y2)(x2,y2) describe the locations of two ends of the wall. Each wall replaces a linear sequence of adjoining tiles and is either axis-aligned or intersects both axes at a 45 degree angle. Diagonal walls are modeled as a sequence of cells that would just be touching corner to corner. If the two endpoints of a wall are the same, the wall just occupies the single cell at that location. Walls may intersect with each other, but no leak is over a wall.

A line with a single integer -1 designates the end of the input.

Output

For each house, display the total number of tiles that are wet after TT minutes.

Input 1

Output 1

12 12 5 3 5
2 11 3 3 9 5
1 9 6 9 1 7 4 4 7 1 7 4
10 9 10 12 11 4 12 4
9 7 8 1 3
4 3
2 2 6 6 6 2 2 6 8 2 8 2
6 7 50 1 3
3 4
2 2 2 6 3 6 5 4 5 4 3 2
12 12 5 3 0
2 11 3 3 9 5
-1

75
17
4
94

Solution

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

 
public static void main(String[] args) throws IOException {
     BufferedReader in =
new BufferedReader(new InputStreamReader(System.in));
     
int[][] directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

     
while (true) {
        String firstLine = in.readLine();

       
if (!firstLine.equals("-1")) {
           
int wetTiles = 0;
           
// Parse X, Y, T, L and W
           StringTokenizer tk =
new StringTokenizer(firstLine);
           
int X = Integer.parseInt(tk.nextToken());
           
int Y = Integer.parseInt(tk.nextToken());
           
int T = Integer.parseInt(tk.nextToken());
           
int L = Integer.parseInt(tk.nextToken());
           
int W = Integer.parseInt(tk.nextToken());

           
// Create board
           
int[][] board = new int[X][Y];
           Queue<Point> sources =
new LinkedList<>();

           
// Fill stack with leak sources
           
for (int i = 0; i < L; i++) {
             
if (!tk.hasMoreTokens()) {
                 tk =
new StringTokenizer(in.readLine());
              }
             
int x = Integer.parseInt(tk.nextToken()) - 1;
             
int y = Integer.parseInt(tk.nextToken()) - 1;
              board[x][y] =
1;
              wetTiles++;
              sources.add(
new Point(x, y));
           }

           
// Create the walls
           
for (int i = 0; i < W; i++) {
             
if (!tk.hasMoreTokens()) {
                 tk =
new StringTokenizer(in.readLine());
              }
             
int x = Integer.parseInt(tk.nextToken()) - 1;
             
int y = Integer.parseInt(tk.nextToken()) - 1;
             
int x2 = Integer.parseInt(tk.nextToken()) - 1;
             
int y2 = Integer.parseInt(tk.nextToken()) - 1;

             
while (x != x2 || y != y2) {
                 board[x][y] = -
1;

                 
// Update the position according to wall direction
                 
if ((x2 - x) > 0) x++;
                 
else if ((x2 - x) < 0) x--;
                 
if ((y2 - y) > 0) y++;
                 
else if ((y2 - y) < 0) y--;
              }
              board[x][y] = -
1;
           }

           
// Update the board until Time
           
for (int i = 0; i < T - 1; i++) {
             
if (sources.isEmpty()) break;
              Queue<Point> temp =
new LinkedList<>();
             
while (sources.peek() != null) {
                 Point p = sources.poll();
                 
for (int j = 0; j < 4; j++) {
                   
int x = p.x + directions[j][0];
                   
int y = p.y + directions[j][1];
                   
if (x < X && x >= 0 && y < Y && y >= 0) {
                       
if (board[x][y] == 0) {
                          board[x][y] =
1;
                          wetTiles++;
                          temp.add(
new Point(x, y));
                       }
                    }
                 }
              }
              sources = temp;
           }
           System.out.println(wetTiles);
        }
else {
           
break;
        }
     }
  }
}

Levenshtein (string compare)

public class LevenshteinDistance {
        
private static int minimum(int a, int b, int c) {
                
return Math.min(Math.min(a, b), c);
        }

        
public static int computeLevenshteinDistance(String str1, String str2) {
                
int[][] distance = new int[str1.length() + 1][str2.length() + 1];

                
for (int i = 0; i <= str1.length(); i++)
                        distance[i][
0] = i;
                
for (int j = 1; j <= str2.length(); j++)
                        distance[
0][j] = j;

                
for (int i = 1; i <= str1.length(); i++)
                        
for (int j = 1; j <= str2.length(); j++)
                                distance[i][j] = minimum(
                                        distance[i -
1][j] + 1,
                                        distance[i][j -
1] + 1,
                                        distance[i -
1][j - 1]+ ((str1.charAt(i - 1) == str2.charAt(j - 1)) ? 0 : 1));

                
return distance[str1.length()][str2.length()];
        }
}

Brute force with doubles

static String[] arrayToTest =  {"the", "red", "fox"};
        
 
public static void main(String[] args)
  {
        
int[] n = new int[3];
        
int Nr[] =
        {
2, 2, 2 };
        printPermutations(n, Nr,
0);
  }

 
public static void printPermutations(int[] n, int[] Nr, int idx)
  {
        
if (idx == n.length)
        {
// stop condition for the recursion [base clause]
                
// add logic here
                System.out.println( arrayToTest[n[
0]] + " " +  arrayToTest[n[1]] + " " + arrayToTest[n[2]] );
          
return;
        }
        
for (int i = 0; i <= Nr[idx]; i++)
        {
           n[idx] = i;
           printPermutations(n, Nr, idx +
1); // recursive invokation, for next
                                              
// elements
        }
  }

Brute force without doubles

public class Main
{
        
public static void printCombinations(int length) {
           printCombinations(
new int[length], 0, 0, length);
        }

        
private static void printCombinations(int[] combinations, int idx, int mask, int max) {
          
if (idx == combinations.length) {
                 
// LOGIC
                   
for(int i = 0; i < combinations.length; i++)
                           System.out.print(combinations[i] +
" " );
                   System.out.println();
              
return;
           }
          
for (int i = 0; i < max; i++) {
              
int mask2 = 1 << i;
              
if ((mask2 & mask) == 0) {
                   combinations[idx] = i;
                   printCombinations(combinations, idx +
1, mask | mask2, max);
               }
           }
        }

        
public static void main(String[] args) throws Exception {
               printCombinations(
3);

File I/O

BufferedReader f = new BufferedReader(new FileReader("input.in"));

        PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(

                "output.out")));

out.write("Output_zelf");

        out.close();

Per line I/O

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

String input = br.readLine();
System.out.println();