kuroobi
BAN USERMinimum value will be a[0] + b[j] or a[i] + b[0]
Note#
a[0] + b[0] is the special case, we need to be careful for
this case.
k > N case is also special case.
so the answer is
int[] firstKMin(int k, int[] a, int b []){
int i = 1;
int j = 1;
int index = 1;
if( K >= 2N){
// invalid input
retrun null;
}
int[] answer = new int[k];
// This is special case
answer[0] = a[0] + b[0];
while(i < N && j < N){
x = a[i] + b[0];
y = a[0] + b[j];
if(x < y){
answer[index] = x;
i++;
}else{
answer[index] = y;
j++;
}
c++;
}
if(index < k){
if(i == N){
for(int l = j; l < N; l++){
answer[index] = a[0] + b[l];
index++;
}
}
if(j == N){
for(int l = i; l < N; l++){
answer[index] = a[i] + b[0];
index++;
}
}
}
return answer;
}
Minimum value will be a[0] + b[j] or a[i] + b[0]
so the answer is
int[] firstKMin(int k, int[] a, int b []){
int i = 1;
int j = 1;
int index = 1;
int[] answer = new int[k];
// This is special case
answer[0] = a[0] + b[0];
while(i < N && j < N){
x = a[i] + b[0];
y = a[0] + b[j];
if(x < y){
answer[index] = x;
i++;
}else{
answer[index] = y;
j++;
}
c++;
}
if(index < k){
if(i == N){
for(int l = j; l < N; l++){
answer[index] = a[0] + b[l];
index++;
}
}
if(j == N){
for(int l = i; l < N; l++){
answer[index] = a[i] + b[0];
index++;
}
}
}
return answer;
}
Minimum value will be a[0] + b[j] or a[i] + b[0]
so the answer is
int[] firstKMin(int k, int[] a, int b []){
int i = 1;
int j = 1;
int index = 1;
int[] answer = new int[k];
// This is special case
answer[0] = a[0] + b[0];
while(i < N && j < N){
x = a[i] + b[0];
y = a[0] + b[j];
if(x < y){
answer[index] = x;
i++;
}else{
answer[index] = y;
j++;
}
c++;
}
if(index < k){
if(i == N){
for(int l = j; l < N; l++){
answer[index] = a[0] + b[l];
index++;
}
}
if(j == N){
for(int l = i; l < N; l++){
answer[index] = a[i] + b[0];
index++;
}
}
}
return answer;
}
This question asks "the amount of", so the answer should be some value.
In here, I would like to show O(N) answer.
Let's define functions A,B and C
A(N) is the amount of all possible cases a string is consists of a, b, and c with length N
B(N) is the amount of all possbile cases a string is consists of a, b, and c with length N have consecutive a,b,c
C(N) is the amount of all possible strings of length N that don't of have consecutive a,b,c
A(N) = 3^N
B(N) = C(N-2) * Combination(N, 3)
= C(N-2) * (N ) * (N - 1)* (N - 2) / 3 * 2* 1
C(0) = 1
C(1) = 1
C(2) = 1
C(N) = A(N) - B(N)
We can caclurate C using DP.
long calcAmount(int N){
assert N > 2;
long[] dp = new long[N+1]; // 1 indexed
dp[0] = 1;
dp[1] = 1;
dp[2] = 1;
for(long i = 3; i <= N; i++){
dp[i] = (long) Math.pow(i, 3) - dp[i - 2] * i * (i - 1) * (i - 2) / 6L;
}
return dp[N];
}
class BytesStreamReader{
Deque<Character> buffer;
BytesStreamReader(){
buffer = new Deque<Character>();
}
public char read_sync_byte(){
while(buffer.size() < 3){
char c = read_byte();
if(c == null){
break;
}
buffer.addLast(c);
}
if(buffer.get(0) == 0 && buffer.get(1) == 0 && buffer.get(2) == 3){
buffer.pollLast();
char c = read_byte();
if(c != null){
buffer.addLast(c);
}
}
if(buffer.isEmpty()){
return null;
}
return buffer.pollFirst();
}
}
Solution A:
Construct graph. Then do the BFS for each word.
Solution B:
But there is no need to BFS, if we see z is the special case of u.
if the word is z , search path for u and we can add DOWN + OK
if the previous word is z , add UP then use u as start point.
Let's work on B
import java.util.ArrayList;
import java.util.List;
public class CharSeq {
public static String map = "abcdefghijklmnopqrstuvwxy";
public static int cols = 5;
public static void addNTimes(List<String> list, String word, int times) {
for (int i = 0; i < times; i++) {
list.add(word);
}
}
public static List<String> charSeq(String word) {
int x = 0;
int y = 0;
List<String> answer = new ArrayList<String>();
word = word.toLowerCase();
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (c == 'z') {
c = 'u';
}
int index = map.indexOf(c);
int cx = index % cols;
int cy = index / cols;
if (cy < y) {
addNTimes(answer, "Up", y - cy);
} else if (y < cy) {
addNTimes(answer, "Down", cy - y);
}
if (cx < x) {
addNTimes(answer, "Left", x - cx);
} else if (x < cx) {
addNTimes(answer, "Right", cx - x);
}
if (word.charAt(i) == 'z') {
answer.add("Down");
answer.add("Ok");
if (i + 1 < word.length()) {
answer.add("Up");
}
} else {
answer.add("Ok");
}
x = cx;
y = cy;
}
return answer;
}
public static void main(String[] argv) {
System.out.println(charSeq("CON"));
}
}
{{
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
public class TreePrinter {
public static class Relation {
String parent;
String child;
public Relation(String parent, String child) {
this.parent = parent;
this.child = child;
}
}
public static void print(int i, String key) {
System.out.println("line " + i + ": " + key);
}
public static class Node{
String key;
Node parent;
List<Node> childlen;
Node(String key){
this.key = key;
childlen = new LinkedList<Node>();
}
public int printOut(int i){
print(i,key);
i++;
for(Node child:childlen){
i = child.printOut(i);
}
return i;
}
}
public static void printTree(Iterable<Relation> rs) {
// your code
Map<String, Node> map = new LinkedHashMap<String, Node>();
for (Relation r : rs) {
Node parent = map.get(r.parent);
if(parent == null){
parent = new Node(r.parent);
map.put(r.parent, parent);
}
Node child = map.get(r.child);
if(child == null){
child = new Node(r.child);
map.put(r.child, child);
}
parent.childlen.add(child);
child.parent = parent;
}
int index = 1;
for (String key : map.keySet()) {
if (map.get(key).parent == null) {
index = map.get(key).printOut(index);
}
}
}
public static void main(String[] argv) {
List<Relation> input = new ArrayList<Relation>();
input.add(new Relation("animal", "mammal"));
input.add(new Relation("animal", "bird"));
input.add(new Relation("lifeform", "animal"));
input.add(new Relation("cat", "lion"));
input.add(new Relation("mammal", "cat"));
input.add(new Relation("animal", "fish"));
printTree(input);
}
}
}}
mergesort is NMlog(NM)
my answer is
log(N)*NM on worst case
{{import java.util.Arrays;
import java.util.Set;
import java.util.TreeSet;
class Converter{
int[][] array;
class Point implements Comparable{
int r,c;
Point(int r, int c){
this.r = r;
this.c = c;
}
int get(){
return array[r][c];
}
int compaireTo(Point b){
return new Integer(get()).compareTo(b.get());
}
@Override
public int compareTo(Object b) {
// TODO Auto-generated method stub
Point pb = (Point) b;
return new Integer(get()).compareTo(pb.get());
}
}
int[] convert2Dto1D(int[][] array){
this.array = array;
TreeSet<Point> candidates = new TreeSet<Point>();
int L = array.length * array[0].length;
int[] answer = new int[L];
candidates.add(new Point(1, 0));
candidates.add(new Point(0, 1));
answer[0] = array[0][0];
for(int i = 1; i < L; i++){
Point p = candidates.pollFirst();
if(p == null){
continue;
}
answer[i] = p.get();
if(p.r + 1 < array.length){
candidates.add(new Point(p.r + 1, p.c));
}
if(p.c + 1 < array[0].length){
candidates.add(new Point(p.r, p.c + 1));
}
}
return answer;
}
public static void main(String[] argv){
int[][] array = {{0, 1, 5}, {2, 4, 6}, {3, 7, 8}};
Converter c = new Converter();
System.out.println(Arrays.toString(c.convert2Dto1D(array)));
}
}
}}
public class WordCheck {
public static boolean check(String input) {
if (input == null)
return false;
char[] chars = new char[] { 'h', 'i', 'r', 'e' };
int index = 0;
for (int i = 0; i < input.length(); i++) {
if (chars[index] == input.charAt(i))
continue;
int next = (index + 1) % 4;
if (chars[next] == input.charAt(i)){
index = next;
continue;
}
return false;
}
if (index != 3) {
return false;
}
return true;
}
public static void main(String[] argv) {
assert true == check("hire");
assert true == check("hirehire");
assert true == check("hhiiiirrrreeeee");
assert true == check("hhiiiirrrreeeeehirrree");
assert true == check("hhiiiirrrreeeeehirrreehirree");
assert false == check("hhiiiirrrreeeeehirr");
assert false == check("hhiiiirrhirr");
assert false == check("");
assert false == check(null);
}
}
Do you have more test cases?
import java.util.ArrayList;
import java.util.List;
class Point {
int x, y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
public String toString() {
return "(" + x + "," + y + ")";
}
}
class PointUtil {
public static Point calcCenter(List<Point> points) {
if (points == null)
return null;
if (points.size() == 0)
return null;
Point center = new Point(0, 0);
for (Point p : points) {
center.x += p.x;
center.y += p.y;
}
center.x /= points.size();
center.y /= points.size();
return center;
}
public static void main(String[] args) {
List<Point> points = new ArrayList<Point>();
points.add(new Point(0, 0));
points.add(new Point(0, 4));
System.out.println(calcCenter(points));
}
}
Let’s say, we have an array that has w,x,y,z by sorted.
a[0] will be smallest element in w,x,y,z. a[3] will be maximun.
The answer is
summ[0] = a[3]
summ[1] = a[0]
summ[2] = a[2]
summ[3] = a[1]
public int answer(int w, int x, int y, int z){
int[] a = new int[4];
a[0] = w;
a[1] = x;
a[2] = y;
a[3] = z;
Arrays.sort(a);
return Math.abs(a[3] - a[0]) + Math.abs(a[0] - a[2]) + Math.abs(a[2] - a[1]);
}
Note I don't think sorting a is O(n), because 4 is the constant.
if this sorting means O(n), then func(summ) should be O(n) thus we can't solve
this problem.
Calculate possible set of possible sums, then count walprime
Let’s define dp as follows.
dp[i] is a set of possible number if we use i numbers.(dp[1] uses only input[0])
dp[0] should be only contain 0 because we don’t use any number.
Let’s define k as number of numbers we combine.
For example, if k = 3, we comine input[i - 0] and input[i-1] and input[i-2].
Also. let’s define numK as the combined number.
For example if k = 3, numK = input[i - 0]*100 + input[i-1]*10 + input[i-2]
We can build dp[i] for possible k using
//Calculate numK
//then
{{
for(int j:dp[i-k]){
dp[i].add(numK + j)
dp[i].add(numK - j)
}
}}
Then we can count walprimes in the set of dp[N+1].
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
class Walprime {
public static void add(Map<Integer,Integer> map,int key,int value){
if(map.containsKey(key)){
map.put(key, value % 1000000007 + map.get(key) % 1000000007);
}else{
map.put(key, value % 1000000007);
}
}
public static int solve(String inputString) {
int N = inputString.length();
int M = 2*3*5*7;
int[] input = new int[N];
for(int i = 0; i < N;i++){
input[i] = Integer.parseInt(inputString.charAt(N - i - 1) + "");
}
Map<Integer,Integer>[] dp = new Map[N + 1];
for (int i = 0; i <= N; i++) {
dp[i] = new HashMap<Integer, Integer>();
}
dp[0].put(0, 1);
//dp[1].put(input[0], 1);
for (int i = 1; i <= N; i++) {
for (int k = 1; k <= i; k++) {
int numK = 0;
for (int l = i; l > i - k; l--) {
numK = numK * 10 + input[l - 1];
numK %= M;
}
for (int j : dp[i - k].keySet()) {
add(dp[i], (numK + j)%M, dp[i-k].get(j));
add(dp[i], (numK - j)%M, dp[i-k].get(j));
}
}
}
int answer = 0;
for (int i : dp[N].keySet()) {
if (i % 2 == 0 || i % 3 == 0 || i % 5 == 0 || i % 7 == 0 || i == 0)
answer = answer + dp[N].get(i) % 1000000007;
}
return answer / 2; // dp[0] case will be double counted (+ and -). so we need to get half the answer
}
public static void main(String[] argv) throws IOException {
BufferedReader r = new BufferedReader(new InputStreamReader(System.in),
1);
// We don’t assume illegal input.
int num = Integer.parseInt(r.readLine());
String[] inputs = new String[num];
for (int i = 0; i < num; i++) {
inputs[i] = r.readLine();
}
for (String input : inputs) {
System.out.println(solve(input));
}
}
}
Note: Additional test cases
11 1+1=2 :1
12 1+2=3 :1
13 1+3=4 1
14 1+5=5 1-4=-3 14: 3
21 2+1=3,21 :2
I couldn't estimate time complexity and space complexity.
This code works up to 20 digits.
# I believe 0 isn't prime number.. but the problem statements says so, I have written such code.
I would like to know the datasets also.
- kuroobi January 10, 2014