## Tuesday, August 27, 2013

### SRM589

Level 1 Level 2 Level 3
Div 1 Level 1 Level 2 Level 3
Div 2 Level 1 Level 2 Level 3

## Tutorials:

### Solution

Generally, this problem asks to connect character in the palindrome place. For instance, string "abcde", then, 'a' will group with 'e', 'b' will group with 'd', 'c' will group with 'c'. By default, any English character will group with itself. For another example, string "abcbde", 'a' will group with 'e', 'b' will group with 'd', 'c' will group with 'b', while 'b' and 'd' are in the same group, then 'b', 'c', 'd' are in the same group, so we have two groups, [a,e] and [b,c,d].

So, for this problem, we will count the number of changes from non-maximum characters to the maximum count character for each group.

So, for the first step, grouping each English character is implemented by three different methods.
getmin2 uses Flood Fill (DFS). O(N), N is the length of String S.
getmin3 uses Floyd–Warshall algorithm. O(26^3)
getmin uses Union-Find data structure with Path Compression.  Time Complexity: < O(N)

So, for N <= 50, it looks like the getmin function is the fastest one.

### Source Code:

```public class GooseTattarrattatDiv1 {

private int[] count;
private boolean[] notVisited;

public int getmin2(String S) {
count = new int;
int min = S.length();
int N = S.length();
notVisited = new boolean;
for (int i = 0; i < N; i++) {
int a = S.charAt(i) - 'a';
count[a]++;
notVisited[a] = true;
}
for (int i = 0; i < N; i++) {
min -= dfs(S.charAt(i), S);
}
return min;
}

/**
* Find the maximum number of characters connect to c in s; It's like a
* chain. We need to find the node in the chain with maximum cost; The
* algorithm here is like Flood Fill;
* */
private int dfs(char c, String s) {
if (notVisited[c - 'a'] == false)
return 0;
int max = count[c - 'a'];
notVisited[c - 'a'] = false;
for (int i = 0; i < s.length(); i++) {
if (c == s.charAt(i))
max = Math.max(max, dfs(s.charAt(s.length() - 1 - i), s));
}
return max;
}

/**
* Floyd–Warshall algorithm

* Finding all the connectivity for all the characters from 'a' to 'z'.

* Then, find the maximum and total characters for each group (subgraph),
* make all the rest of characters change to the character holds the
* maximum, Thus, it costs (total - maximum);
* */
public int getmin3(String s) {
int N = s.length();
int[] counter = new int;
boolean[][] connected = new boolean;
for (int i = 0; i < N; i++) {
counter[s.charAt(i) - 'a']++;
}
for (int i = 0; i < N - i; i++) {
int a = s.charAt(i) - 'a';
int b = s.charAt(N - i - 1) - 'a';
connected[a][b] = true;
connected[b][a] = true;
}

for (int i = 0; i < 26; i++)
connected[i][i] = true;
for (int k = 0; k < 26; k++) {
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
connected[i][j] |= connected[i][k] && connected[k][j];
}
}
}
int ret = 0;
for (int i = 0; i < N; i++) {
if (counter[s.charAt(i) - 'a'] <= 0)
continue;
int total = 0;
int max = 0;
for (int j = 0; j < 26; j++) {
if (connected[s.charAt(i) - 'a'][j]) {
total += counter[j];
max = Math.max(max, counter[j]);
counter[j] = 0;
}
}
ret += total - max;
}
return ret;
}

/**
* This problem actually asks to group 'a' - 'z'. Here I use the Union-Find
* data structure to speed this process up;
* */
public int getmin(String S) {
int[] count = new int;
for (int i = 0; i < S.length(); i++) {
count[S.charAt(i) - 'a']++;
}
int min = 0;
Union_Find set = new Union_Find(26);
for (int i = 0; i < S.length() - 1 - i; i++) {
set.union(S.charAt(i) - 'a', S.charAt(S.length() - 1 - i) - 'a');
}
for (int i = 0; i < 26; i++) {
int total = 0;
int max = 0;
for (int j = 0; j < 26; j++) {
if (set.find(j) == set.find(i)) {
total += count[j];
max = Math.max(max, count[j]);
count[j] = 0;
}
}
min += total - max;
}
return min;
}

class Union_Find {
public int[] parents;

public Union_Find(int N) {
parents = new int[N];
for (int i = 0; i < N; i++) {
parents[i] = i;
}
}

public int find(int x) {
if (x == parents[x])
return x;
return parents[x] = find(parents[x]);
}

public void union(int x, int y) {
int xx = find(x);
int yy = find(y);
if (xx != yy) {
this.parents[xx] = yy;
}
}
}
}

```

### Solution

This is a Dynamic Programming problem, people could easily find out the dp state formula for this problem. For every gear, people could choose use it or remove it. So we could either use the current gear or not use current one, which depends on the previous state.

For this problem, I tried to find the number of most gears we could use to work, which equals to the problem finds the fewest removal of gears to make it work.

But this problem has one thing requires your attention, which asks you to make this gear string in circular, that means the first and very last one is connected. This brings the challenge, while bringing the convenience for us. We could start at any point in this circular, so we ideally choose the 0th one to start, but we have to remember for every state that if any current state result depends on using the 0th gear or not. Then at last, we need to check if we use the 0th gear for my last state result, when first and last gear direction is the same. If the result depends on it, then we should not use the last gear, otherwise just use it, since it will bring you one more gear to use.

### Source Code:

```import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class GearsDiv2 {

public int getmin(String dir) {
int[][] dp = new int[dir.length()];
boolean[][] hasFirst = new boolean[dir.length()];
dp = 0;
dp = 1;
hasFirst = false;
hasFirst = true;
for (int i = 1; i < dir.length(); i++) {
if (dp[i - 1] == dp[i - 1]) {
hasFirst[i] = hasFirst[i - 1] && hasFirst[i - 1];
dp[i] = dp[i - 1];
} else if (dp[i - 1] > dp[i - 1]) {
hasFirst[i] = hasFirst[i - 1];
dp[i] = dp[i - 1];
} else {
hasFirst[i] = hasFirst[i - 1];
dp[i] = dp[i - 1];
}
// dp[i] = Math.max(dp[i-1], dp[i-1]);
if (dir.charAt(i) != dir.charAt(i - 1)) {
dp[i] = 1 + dp[i];
hasFirst[i] = hasFirst[i];
} else {
dp[i] = dp[i - 1] + 1;
hasFirst[i] = hasFirst[i - 1];
}
}
// return dir.length() - Math.max(dp[dir.length()-1],
// dp[dir.length()-1]);
if (dir.charAt(dir.length() - 1) != dir.charAt(0)) {
return dir.length()
- Math.max(dp[dir.length() - 1], dp[dir.length() - 1]);
} else {
if (hasFirst[dir.length() - 1]) {
return dir.length() - dp[dir.length() - 1];
} else {
return dir.length() - dp[dir.length() - 1];
}

}
}
// <%:testing-code%>
}```
```// Powered by [KawigiEdit] 2.0!
```

The second solution comes from TC tutorial. The two key ideas of this recursion solution are:
1, Don't be trapped by this circular requirement, for the first and last gears, we only have four possibilities, we keep them both, keep first, keep last and remove them both. Since we are using a recursion to solve this problem, the 4th possibility will come through one of 2nd and 3rd case, since remove one, we could possibly remove the other later. This way, we could get rid of circular trap and treat the new string as a linear problem.
2, In the linear problem, when two adjacent gears are the same, we have to remove one of them, here we absolutely remove the second one. Further detail reason, check out the link.

```public class GearsDiv2 {
public int getmin(String dir) {
int N = dir.length();
int ret = N - 1;
if (dir.charAt(0) != dir.charAt(N - 1))
ret = Math.min(ret, getminLinear(dir));
ret = Math.min(ret, 1 + getminLinear(dir.substring(1)));
ret = Math.min(ret, 1 + getminLinear(dir.substring(0, N - 1)));
return ret;
}

private int getminLinear(String dir) {
if (dir.length() < 2)
return 0;
// change the second one to '_'
if (dir.charAt(0) == dir.charAt(1)) {
return 1 + getminLinear(dir.substring(2));
}
return getminLinear(dir.substring(1));
}
}
```

### Source Code:

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32``` ```import java.util.*; import java.util.regex.*; import java.text.*; import java.math.*; import java.awt.geom.*; public class GooseTattarrattatDiv2 { public int getmin(String s) { int[] count = new int; int max = 0; int index = -1; for(int i=0; i 0 && i != index){ ret += count[i]; } } return ret; } } //Powered by [KawigiEdit] 2.0! ```

## Problem:

Yesterday(8/12/2013), I was asked to implement this problem Binary Tree Level-Order Traversal in a short time. For the first thought, it looks like an easy BFS problem, but quickly I realize a problem how can I track the level of the tree? Haha...

At the end, I gave my solution, but the interviewee said my solution is most weird one he has ever seen. LOL... I don't know what will be coming for me, but it's a great experience, and we'll see.

The following are my solutions for this problem with different strategy. Have Fun.

PS: every solution I provided uses Linear time and space. Approvement might be attached.

## Source Code:

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232``` ```/** * This is a demo class in java
* Implementing Binary Tree Traverse Level By Level with BFS and DFS.
* All of the algorithm I implemented use O(N) time, N here represents the number of nodes in the tree. * */ import java.util.LinkedList; import java.util.Queue; /** * @author Antonio081014 * @since Aug 13, 2013, 9:22:40 AM */ public class Solution { public static void main(String[] args) { Solution main = new Solution(); Node root = main.new Node("3"); root.left = main.new Node("9"); root.right = main.new Node("20"); root.right.left = main.new Node("15"); root.right.right = main.new Node("7"); main.printLevelOrder_Option4(root); System.exit(0); } /** * Tree node structure; * */ class Node { String value; Node left; Node right; public Node(String v) { value = v; left = null; right = null; } } /** * This is the answer I gave when I was in the interview.
* Basically, track the number of children we counted, if all the children * in that level is counted, then we print a newline and increase the tree * level; The flaw of this algorithm is it can not take too many levels, * since integer in java can't exceed 2^32; which means we maximumly will * have 32 levels, even if we use long instead of int, this one is still not * a good choice. * */ private void printLevelOrder_Option0(Node root) { if (root == null) return; Queue queue = new LinkedList(); int level = 1; int count = 0; queue.add(root); while (!queue.isEmpty()) { Node node = queue.poll(); if (count == 0) System.out.print(node.value); else System.out.print(" " + node.value); if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); count += 2; if (count == (int) Math.pow(2, level)) { System.out.println(); level++; count = 0; } } } /** * Generally, this algorithm uses BFS, which involves two queues keep tracks * of node in current level and nodes in next leve;
* Basically,
* 1, When a node is extracted, we print it, while adding its children to * the next level if they are not null;
* 2, When current level queue is empty, which means all of the current * nodes are extracted and printed, also all the children of current level * nodes are added to the next level queue. So we could just copy every * single node in next level queue and add it to the current queue, and * print the newline. * */ private void printLevelOrder_Option1(Node root) { if (root == null) return; Queue currentLevel = new LinkedList(); Queue nextLevel = new LinkedList(); currentLevel.add(root); while (!currentLevel.isEmpty()) { Solution.Node node = currentLevel.poll(); System.out.print(node.value + " "); if (node.left != null) nextLevel.add(node.left); if (node.right != null) nextLevel.add(node.right); if (currentLevel.size() == 0) { System.out.println(); while (!nextLevel.isEmpty()) { currentLevel.add(nextLevel.poll()); } } } } /** * For this algorithm, we use two counters to keep track of number of nodes * in current level, and the number of nodes in next level;
* This idea is very similar with printLevelOrder_Option1(Node root), * however, it uses less memory and doesn't need to copy each node from one * queue to another. * */ private void printLevelOrder_Option2(Node root) { if (root == null) return; Queue queue = new LinkedList(); int nodesInCurrentLevel = 0; int nodesInNextLevel = 0; queue.add(root); nodesInCurrentLevel++; while (!queue.isEmpty()) { Node node = queue.poll(); System.out.print(" " + node.value); nodesInCurrentLevel--; if (node.left != null) { queue.add(node.left); nodesInNextLevel++; } if (node.right != null) { queue.add(node.right); nodesInNextLevel++; } if (nodesInCurrentLevel == 0) { System.out.println(); nodesInCurrentLevel = nodesInNextLevel; nodesInNextLevel = 0; } } } /** * This algorithm uses a trick of BFS.
* Since we are using BFS to traverse this binary tree level by level in a * very nature way. We just add a newline node at the very beginning, then * if this newline node is reached, that means all of nodes of current nodes * has been visited, so we are going to move to the next level, then print * the newline here. * * This trick uses the nature of BFS in binary, very smart. I think the * interviewee was trying to ignite me to this solution. Somehow, I didn't * get it. For this algorithm, user could replace this newline node with * other flag node for other purposes.``` ``` * */ private void printLevelOrder_Option3(Node root) { if (root == null) return; Queue queue = new LinkedList(); queue.add(root); queue.add(new Node("\n"));``` ```queue.add(new Node("\n")); while (queue.size() > 1) { Node node = queue.poll(); System.out.print(node.value + " "); if (node.value.compareTo("\n") == 0) { queue.add(node); continue; } if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); } } /** * This algorithm uses DFS;
* 1, Get the height from root tree node.
* 2, For each level, print the nodes on that level with a newline. * * Although the DFS solution traverse the same node multiple times, it is * not another order slower than the BFS solution. Here is the proof that * the DFS solution above runs in O(N) time, where N is the number of nodes * in the binary tree and we assume that the binary tree is balanced. * * We first compute the complexity of printLevel for the kth level: * * T(k)
* = 2T(k-1) + c
* = 2k-1 T(1) + c
* = 2k-1 + c * * Assuming it’s a balanced binary tree, then it would have a total of lg N * levels. Therefore, the complexity of printing all levels is: * * T(1) + T(2) + ... + T(lg N) = 1 + 2 + 22 + ... + 2lg N-1 + c = O(N) * Finding the maximum height of the tree also takes O(N) time, therefore * the overall complexity is still O(N). * */ private void printLevelOrder_Option4(Node root) { int height = treeLevel(root); for (int i = 1; i <= height; i++) { printLevel(root, i); System.out.println(); } } /** * Print the nodes on Level: level. * */ private void printLevel(Node root, int level) { if (root == null) return; if (level == 1) { System.out.print(root.value + " "); } else { printLevel(root.left, level - 1); printLevel(root.right, level - 1); } } private int treeLevel(Node root) { if (root == null) return 0; return 1 + Math.max(treeLevel(root.left), treeLevel(root.right)); } } ```

USACO_nuggets.

## Problem:

Beef McNuggets
Hubert Chen
Farmer Brown's cows are up in arms, having heard that McDonalds is considering the introduction of a new product: Beef McNuggets. The cows are trying to find any possible way to put such a product in a negative light.
One strategy the cows are pursuing is that of `inferior packaging'. ``Look,'' say the cows, ``if you have Beef McNuggets in boxes of 3, 6, and 10, you can not satisfy a customer who wants 1, 2, 4, 5, 7, 8, 11, 14, or 17 McNuggets. Bad packaging: bad product.''
Help the cows. Given N (the number of packaging options, 1 <= N <= 10), and a set of N positive integers (1 <= i <= 256) that represent the number of nuggets in the various packages, output the largest number of nuggets that can not be purchased by buying nuggets in the given sizes. Print 0 if all possible purchases can be made or if there is no bound to the largest number.
The largest impossible number (if it exists) will be no larger than 2,000,000,000.

### INPUT FORMAT

 Line 1: N, the number of packaging options Line 2..N+1: The number of nuggets in one kind of box

```3
3
6
10
```

### OUTPUT FORMAT

The output file should contain a single line containing a single integer that represents the largest number of nuggets that can not be represented or 0 if all possible purchases can be made or if there is no bound to the largest number.

`17`

## Solution:

1st, check if the answer existed and can be represented. If not return 0;
2nd, Using Dynamic Programming to mark all the possible solution, till reach the boundary.

## Source Code: [on GitHub]

```/*
ID:
LANG: JAVA
PROG: nuggets
*/
import java.io.FileWriter;
import java.io.PrintWriter;

/**
* @author antonio081014
* @time Jul 28, 2013, 3:26:58 PM
*/
public class nuggets {

private static final int SIZE = 100000;
private boolean[] mark;

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

private void run() {
try {
PrintWriter out = new PrintWriter(new FileWriter("nuggets.out"));
int[] array = new int[N];
for (int i = 0; i < N; i++) {
}
in.close();
out.println(solve(array));
out.close();
} catch (Exception e) {
e.printStackTrace();
}
}

private int solve(int[] array) {
mark = new boolean[SIZE];
boolean flag = true;
for (int i = 0; i < array.length; i++)
for (int j = i + 1; j < array.length; j++)
if (gcd(array[i], array[j]) == 1)
flag = false;
if (flag)
return 0;

int max = 0;
mark = true;
for (int i = 0; i < SIZE; i++) {
if (!mark[i])
max = i;
else
for (int j = 0; j < array.length; j++) {
if (i + array[j] < SIZE)
mark[i + array[j]] = true;
}
}
return max;
}

public int gcd(int a, int b) {
if (b == 0)
return a;
else
return gcd(b, a % b);
}
}
```