UVa_10158_War.cpp

Problem Links:

UVa10158,

Problem:

Problem B: War

    A war is being lead between two countries, A and B. As a loyal citizen of C, you decide to help your country’s espionage by attending the peace-talks taking place these days (incognito, of course). There are n people at the talks (not including you), but you do not know which person belongs to which country. You can see people talking to each other, and through observing their behaviour during their occasional one-to-one conversations, you can guess if they are friends or enemies. In fact what your country would need to know is whether certain pairs of people are from the same country, or they are enemies. You may receive such questions from C’s government even during the peace-talks, and you have to give replies on the basis of your observations so far. Fortunately nobody talks to you, as nobody pays attention to your humble appearance.

  Abstract

    Now, more formally, consider a black box with the following operations:

               setFriends(x, y)     shows that x and y are from the same country

               setEnemies(x, y)   shows that x and y are from different countries

               areFriends(x, y)     returns true if you are sure that x and y are friends

               areEnemies(x, y)   returns true if you are sure that x and y are enemies

    The first two operations should signal an error if they contradict with your former knowledge. The two relations ‘friends’ (denoted by ~) and ‘enemies’ (denoted by *) have the following properties:

              ~ is an equivalence relation, i.e.

1.      If x ~ y and y ~ z then x ~ z  (The friends of my friends are my friends as well.)

2.      If x ~ y then y ~ x                  (Friendship is mutual.)

3.      x ~ x                                       (Everyone is a friend of himself.)

              * is symmetric and irreflexive

4.      If x * y then y * x                  (Hatred is mutual.)

5.      Not x * x                                (Nobody is an enemy of himself.)

              Also

6.      If x * y and y * z then x ~ z   (A common enemy makes two people friends.)

7.      If x ~ y and y * z then x * z   (An enemy of a friend is an enemy.)

    Operations setFriends(x, y) and setEnemies(x, y) must preserve these properties.

  Input

     The first line contains a single integer, n, the number of people.

     Each of the following lines contains a triple of integers, c x y, where c is the code of the operation:

            c = 1, setFriends

            c = 2, setEnemies

            c = 3, areFriends

            c = 4, areEnemies

     and x and y are its parameters, which are integers in the range [0, n), identifying two (different) people. The last line contains 0 0 0.

    All integers in the input file are separated by at least one space or line break.

  Output

     For every ‘areFriends’ and ‘areEnemies’ operation write 0 (meaning no) or 1 (meaning yes) to the output. Also for every ‘setFriends’ or ‘setEnemies’ operation which contradicts with previous knowledge, output a –1 to the output ; note that such an operation should produce no other effect and execution should continue. A successful ‘setFriends’ or ‘setEnemies’ gives no output.

    All integers in the output file must be separated by at least one space or line break.

  Constraints

    n < 10000, the number of operations is unconstrained.

  Sample Input

            10

            1 0 1

            1 1 2

            2 0 5

            3 0 2

            3 8 9

            4 1 5

            4 1 2

            4 8 9

            1 8 9

            1 5 2

            3 5 2

            0 0 0

  Sample Output

            1

            0

            1

            0

            0

            -1

            0

---

Source Code:

Using Union-Find data structure, Parent tells the root of the tree, while rank tells which side it is on.

//Wed Jun  9 23:10:38 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define MMAX 10000
using namespace std;

class War
{
public:
 int parent;
 int rank; //0, means friends; otherwise, enemy;
};

vector<War> v(MMAX);

void Makeset(int N)
{
 for (int i = 0; i <= N; i++)
 {
  v[i].parent = i;
  v[i].rank = 0;
 }
}

int Find(int x)
{
 if (x == v[x].parent)
  return x;
 int temp = v[x].parent;
 v[x].parent = Find(temp);
 // v[x].rank = v[temp].rank == 0 ? v[x].rank : (1 - v[x].rank);
 // int temp = Find(v[x].parent);
 v[x].rank = (v[x].rank + v[temp].rank) & 1;
 // v[x].parent = temp;
 return v[x].parent;
}

void Union(int t1, int t2, int x, int y, int d)
{
 v[t2].parent = t1;
 //v[t2].rank = v[x].rank == v[y].rank ? d : (1 - d);
 v[t2].rank = (v[x].rank + v[y].rank + d) & 1;
 Find(x);
}

int Judge(int t1, int t2, int x, int y)
{
 if (t1 == t2)
 {
  if (v[x].rank == v[y].rank)
   return 0; //Friends;
  else
   return 1; //Enemy;
 }
 return -1;
}

int main(int argc, char* argv[])
{
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
 int N;
 cin >> N;
 Makeset(N);
 int a, b, c;
 while (cin >> a >> b >> c && (a + b + c))
 {
  int t1, t2;
  if (a == 1)
  {
   t1 = Find(b);
   t2 = Find(c);
   if (Judge(t1, t2, b, c) == 1)
    cout << -1 << endl;
   else
    Union(t1, t2, b, c, 0);
  }
  else if (a == 2)
  {
   t1 = Find(b);
   t2 = Find(c);
   if (Judge(t1, t2, b, c) == 0)
    cout << -1 << endl;
   else
    Union(t1, t2, b, c, 1);
  }
  else if (a == 3)
  {
   t1 = Find(b);
   t2 = Find(c);
   if (Judge(t1, t2, b, c) == 0)
    cout << 1 << endl;
   else
    cout << 0 << endl;
  }
  else if (a == 4)
  {
   t1 = Find(b);
   t2 = Find(c);
   if (Judge(t1, t2, b, c) == 1)
    cout << 1 << endl;
   else
    cout << 0 << endl;
  }
 }
// fclose(stdin);
// fclose(stdout);
 return 0;
}

Find pair of integers sums to x

Given a set of S containing n real numbers, and a real number x. We seek an algorithm to determine whether two elements of S exist whose sum is exactly x

1. Assume that S is unsorted. Give an O(nlogn) algorithm for the problem.
2. Assume that S is sorted. Give an O(n) algorithm for the problem.

For the first case,
     1st, sort the set with a O(nlgn) sorting algorithm.
     2nd, go through every element in the set, for each element, use binary search to find (x - element) in the set.

For the second case,
     1st, find the complementary array, which is subtracted each of array from x.
     2nd, it's like walking face to face, and at some point, they will meet each other.

import java.util.Arrays;

/**
 * 
 */

/**
 * @author antonio081014
 * @time: Sep 26, 2012, 11:04:55 AM
 */
public class Main {

    public static void main(String[] args) {
	Main main = new Main();
	main.run();
	System.exit(0);
    }

    public void run() {
	int[] array1 = { 1, 3, 5, 9, 8, 4, 2 };
	handleUnsorted(array1, 7);

	int[] array2 = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	handleSorted(array2, 10);
    }

    public void handleUnsorted(int[] array, int x) {
	Arrays.sort(array); // O(nlgn);
	for (int i = 0; i < array.length; i++) { // O(n);
	    int found = x - array[i];
	    int low = 0;
	    int high = array.length - 1;
	    while (low <= high) {// O(lgn);
		int mid = (low + high) / 2;
		if (mid != i && array[mid] == found) {
		    System.out.println("Found it: " + array[i] + ", "
			    + array[mid]);
		    return;
		} else if (array[mid] < found)
		    low = mid + 1;
		else
		    high = mid - 1;
	    }
	} // O(nlgn);
    }

    public void handleSorted(int[] array, int x) {
	int n = array.length;
	int[] implementArray = new int[n];
	for (int i = 0; i < n; i++)
	    implementArray[i] = x - array[i];
	for (int i = 0, j = 0; i < n && j < n;) { // O(n);
	    if (implementArray[j] == array[i] && i != j) {
		// avoid using one elements twice.
		System.out.println("Found it: " + (x - array[i]) + ", "
			+ implementArray[j]);
		return;
	    } else {
		if (array[i] < implementArray[j])
		    i++;
		else
		    j++;
	    }
	}
    }
}

Demo: Merge-Sort

This article shows a simple demo about how the merge-sort works, which follows divide-and-conque.

BTW, Java is strickly passing by value.

For other type of array, the only thing you need to care is Claim of the type and the comparison of the objects in that type.

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * A Simple Demo for Merge-Sort.
 */

/**
 * @author antonio081014
 * @time: Sep 24, 2012, 8:52:26 AM
 */
public class A {

    public static void main(String[] args) throws Exception {
 A main = new A();
 main.run();
 System.exit(0);
    }

    public void run() throws Exception {
 int[] test = { 2, 1, 4, 6, 7, 3, 5, 0, 9 };
 System.out.println(Arrays.toString(test));
 mergesort(test, 0, test.length - 1);
 System.out.println(Arrays.toString(test));
    }

    public void mergesort(int[] array, int low, int high) {
 if (low < high) {
     int middle = (low + high) / 2;
     mergesort(array, low, middle);
     mergesort(array, middle + 1, high);
     merge(array, low, middle, high);
 }
    }

    public void merge(int[] array, int low, int middle, int high) {
 Queue<Integer> list1 = new LinkedList<Integer>();
 Queue<Integer> list2 = new LinkedList<Integer>();
 for (int i = low; i <= middle; i++)
     list1.add(array[i]);
 for (int i = middle + 1; i <= high; i++)
     list2.add(array[i]);
 int i = low;
 while (!list1.isEmpty() && !list2.isEmpty()) {
     if (list1.peek() <= list2.peek()) {
  array[i++] = list1.poll();
     } else {
  array[i++] = list2.poll();
     }
 }

 while (!list1.isEmpty())
     array[i++] = list1.poll();
 while (!list2.isEmpty())
     array[i++] = list2.poll();
    }
}

UVA_850_Crypt_Kicker_II.java

Problem Links:

UVa850,

Problem:

Crypt Kicker II

A common but insecure method of encrypting text is to permute the letters of the alphabet. That is, in the text, each letter of the alphabet is consistently replaced by some other letter. So as to ensure that the encryption is reversible, no two letters are replaced by the same letter.
A common method of cryptanalysis is the known plaintext attack. In a known plaintext attack, the cryptanalist manages to have a known phrase or sentence encrypted by the enemy, and by observing the encrypted text then deduces the method of encoding.
Your task is to decrypt several encrypted lines of text, assuming that each line uses the same set of replacements, and that one of the lines of input is the encrypted form of the plaintext

the quick brown fox jumps over the lazy dog

Input 

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

The input consists of several lines of input. Each line is encrypted as described above. The encrypted lines contain only lower case letters and spaces and do not exceed 80 characters in length. There are at most 100 input lines.

Output 

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

---

Source Code:

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

class Main {

    private static final String plain = "the quick brown fox jumps over the lazy dog";
    private int count;
    private String[] matrix;
    private int[] map;

    public static void main(String[] args) throws Exception {
 Main main = new Main();
 main.run(args);
 System.exit(0);
    }

    public void run(String[] args) throws Exception {
 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 int cases = Integer.parseInt(br.readLine());
 String tmp = br.readLine();
 matrix = new String[100];
 while (cases-- > 0) {
     count = 0;
     boolean found = false;
     while ((tmp = br.readLine()) != null && tmp.length() != 0) {
  matrix[count] = tmp;
  found = found || checkLine(tmp);
  count++;
     }
     if (found) {
  print();
     } else {
  System.out.println("No solution.");
     }
     if (cases > 0)
  System.out.println();
 }
    }

    public void print() {
 for (int i = 0; i < count; i++) {
     int len = matrix[i].length();
     for (int j = 0; j < len; j++) {
  if (matrix[i].charAt(j) == ' ')
      System.out.print(' ');
  else
      System.out.print((char) map[matrix[i].charAt(j) - 'a']);
     }
     System.out.println();
 }
    }

    public boolean checkLine(String aLine) {
 int len = aLine.length();
 if (plain.length() != len)
     return false;
 map = new int[26];
 for (int i = 0; i < len; i++) {
     int index1 = aLine.charAt(i) - 'a';
     if (aLine.charAt(i) == ' ') {
  if (plain.charAt(i) != ' ')
      return false;
     } else {
  if (map[index1] == 0)
      map[index1] = plain.charAt(i);
  else if (map[index1] != plain.charAt(i))
      return false;
     }
 }
 return true;
    }
}

USACO: Prime Cryptarithm

Problem: Link.
Solution:
Code:

/*
 * ID: ***
 * LANG: JAVA
 * PROG: crypt1
 */
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;

/**
 * Method One: solve1(), using the features of the length of numbers;
 * Method Two: solve2(), iterate all of the possible numbers from the existing
 * digit set.
 * */

/**
 * @author antonio081014
 * @since Feb 18, 2012, 4:18:05 PM
 */
public class crypt1 {

    public static void main(String[] args) throws Exception {
        crypt1 main = new crypt1();
        main.solve2();
        System.exit(0);
    }

    public void solve1() throws Exception {
        BufferedReader br = new BufferedReader(new FileReader("crypt1.in"));
        BufferedWriter out = new BufferedWriter(new FileWriter("crypt1.out"));
        int N = Integer.parseInt(br.readLine());
        String strLine = br.readLine();
        strLine = strLine.replaceAll("\\s", "");
        int count = 0;
        for (int i = 100; i < 1000; i++) {
            if (checkString(Integer.toString(i), strLine) == false)
                continue;
            for (int j = 10; j < 100; j++) {
                if (checkString(Integer.toString(j), strLine) == false)
                    continue;
                // int a = j % 10 * i;
                // int b = j / 10 * i;
                String a = Integer.toString(j % 10 * i);
                String b = Integer.toString(j / 10 * i);
                String c = Integer.toString(j % 10 * i + (j / 10 * i) * 10);
                if (a.length() == 3 && b.length() == 3 && c.length() == 4
                        && checkString(a, strLine) && checkString(b, strLine)
                        && checkString(c, strLine))
                    count++;
            }
        }
        out.write("" + count + "\n");
        out.close();
    }

    public boolean checkString(String a, String b) {
        for (int i = 0; i < a.length(); i++) {
            if (b.contains("" + a.charAt(i)) == false)
                return false;
        }
        return true;
    }

    public void solve2() throws Exception {
        BufferedReader br = new BufferedReader(new FileReader("crypt1.in"));
        BufferedWriter out = new BufferedWriter(new FileWriter("crypt1.out"));
        int N = Integer.parseInt(br.readLine());
        String strLine = br.readLine();
        strLine = strLine.replaceAll("\\s", "");
        int count = 0;
        for (int a = 0; a < N; a++) {
            for (int b = 0; b < N; b++) {
                for (int c = 0; c < N; c++) {
                    int p = Integer.parseInt("" + strLine.charAt(a)
                            + strLine.charAt(b) + strLine.charAt(c));
                    for (int d = 0; d < N; d++) {
                        String tmp1 = Integer.toString(p
                                * (strLine.charAt(d) - '0'));
                        if (tmp1.length() != 3
                                || checkString(tmp1, strLine) == false)
                            continue;
                        for (int e = 0; e < N; e++) {
                            String tmp2 = Integer.toString(p
                                    * (strLine.charAt(e) - '0'));
                            if (tmp1.length() != 3
                                    || checkString(tmp2, strLine) == false)
                                continue;
                            String tmp3 = Integer.toString(p
                                    * (strLine.charAt(d) - '0' + 10 * (strLine
                                            .charAt(e) - '0')));
                            if (tmp3.length() == 4
                                    && checkString(tmp3, strLine))
                                count++;
                        }
                    }
                }
            }
        }
        out.write("" + count + "\n");
        out.close();
    }
}

USACO: Calf Flac

Problem: Link.
Solution:
Code:

/*
 * ID: ***
 * LANG: JAVA
 * PROG: calfflac
 */
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;

/**
 * 1st, String.substring will take much time.
 * 2nd, String.toLower will take much time. Don't translate to lower case
 * every time, just translate it at the very first beginning.
 * It takes me more than 36 hrs.
 * 
 * Time Complexity: O(N*M)
 * N is the length of the total string.
 * M is the length of the longest palindrome string.
 * 
 * 12th submission passed the test.
 * */

/**
 * @author antonio081014
 * @since Feb 17, 2012, 10:44:40 AM
 */
public class calfflac {

    public String store;
    public int    max;
    int           From;
    int           To;

    public static void main(String[] args) throws Exception {
        calfflac main = new calfflac();
        main.solve();
        System.exit(0);
    }

    public void solve() throws Exception {
        BufferedReader br = new BufferedReader(new FileReader("calfflac.in"));
        BufferedWriter out = new BufferedWriter(new FileWriter("calfflac.out"));
        String strLine = "";
        String str;
        while ((str = br.readLine()) != null) {
            strLine += str + "\n";
        }
        max = 0;
        From = 0;
        String text = strLine.toLowerCase();
        int N = strLine.length();
        for (int i = 0; i < N; i++) {
            palindrom1(i, text, N);
            palindrom2(i, text, N);
        }
        out.write("" + max + "\n");
        for (int i = From; i <= To; i++)
            out.write(strLine.charAt(i));
        out.write("\n");
        // out.write(strLine.substring(From, To + 1) + "\n");
        out.close();
    }

    //Check for BBABB;
    public void palindrom1(int index, String s, int N) {
        int start = index;
        int end = index;
        int count = isAlpha(s.charAt(index)) ? 1 : 0;
        for (int i = index - 1, j = index + 1; i >= 0 && j < N;) {
            while (i >= 0 && isAlpha(s.charAt(i)) == false)
                i--;
            while (j < s.length() && isAlpha(s.charAt(j)) == false)
                j++;
            if (i < 0 || j >= N)
                break;
            if (s.charAt(i) != s.charAt(j)) {
                if (count > max) {
                    From = start;
                    To = end;
                    max = count;
                }
                return;
            }
            else {
                count += 2;
                start = i;
                end = j;
                i--;
                j++;
            }
        }
        if (count > max) {
            From = start;
            To = end;
            max = count;
        }
        // return count;
        // return Math.min(index, s.length() - index - 1) * 2 + 1;
    }
    
    //Check for BBAABB;
    public void palindrom2(int index, String s, int N) {
        int start = index;
        int end = index;
        int count = 0;
        for (int i = index, j = index + 1; i >= 0 && j < N;) {
            while (i >= 0 && isAlpha(s.charAt(i)) == false)
                i--;
            while (j < s.length() && isAlpha(s.charAt(j)) == false)
                j++;
            if (i < 0 || j >= N)
                break;
            if (s.charAt(i) != s.charAt(j)) {
                if (count > max) {
                    From = start;
                    To = end;
                    max = count;
                }
                return;
                // return 2 * (j - index - 1);
            }
            else {
                count += 2;
                start = i;
                end = j;
                i--;
                j++;
            }
        }
        if (max < count) {
            From = start;
            To = end;
            max = count;
        }
        // return count;
        // return Math.min(index + 1, s.length() - index - 1) * 2;
    }

    public boolean isAlpha(char a) {
        if (a >= 'a' && a <= 'z')
            return true;
        if (a >= 'A' && a <= 'Z')
            return true;
        return false;
    }
}