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;
}
```

## Wednesday, September 26, 2012

### 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++;
}
}
}
}
```

## Monday, September 24, 2012

### Demo: Merge-Sort

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.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) {
for (int i = low; i <= middle; i++)
for (int i = middle + 1; i <= high; 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();
}
}
```

UVa850,

# 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;

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 {
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;
}
}
```

## Thursday, September 13, 2012

### USACO: Prime Cryptarithm

Solution:
Code:

```/*
* ID: ***
* LANG: JAVA
* PROG: crypt1
*/
import java.io.BufferedWriter;
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 {
BufferedWriter out = new BufferedWriter(new FileWriter("crypt1.out"));
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 {
BufferedWriter out = new BufferedWriter(new FileWriter("crypt1.out"));
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

Solution:
Code:

```/*
* ID: ***
* LANG: JAVA
* PROG: calfflac
*/
import java.io.BufferedWriter;
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 {
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;
}
}
```