madno
BAN USERThis is a somewhat different solution, brute force using polish expression for evaluation
and infix to print out the solution (superfluous parentheses are skipped):
import java.util.*;
class CareerCup_5735906000502784{
public static void main(String[]arg){
System.out.println(gen(new int[]{5, 7, 13, 169}, 4));
}
private static char[] OPERATORS = "+-*/".toCharArray();
public static String gen(int[] numbers, int target){
String[] expr = new String[2*numbers.length-1];
for(int j = 0; j < numbers.length; ++j){
expr[j] = ""+numbers[j];
}
int[] selectedOperatorIds = new int[numbers.length-1];
selectedOperatorIds[0] = -1;
int allOperatorComboCount = exp(OPERATORS.length,selectedOperatorIds.length);
for(int i = 0; i < allOperatorComboCount; ++i){
genNextOperatorCombos(expr, numbers.length, selectedOperatorIds);
String ret = find(expr, target, 0, expr.length);
if (ret != null) return ret;
}
return null;
}
private static String find(String[] expr, int target, int lo, int hi){
if (lo == hi){
String ret = eval(expr, target);
return ret;
}
for(int i = lo; i < hi; ++i){
swap(expr, lo, i);
String ret = find(expr, target, lo+1, hi);
if (ret != null) return ret;
swap(expr, lo, i);
}
return null;
}
private static String eval(String[] expr, int target){
Deque<String> stack = new ArrayDeque<>();
for(int i = expr.length-1; i >= 0; --i){
String op = expr[i];
if (isOperand(op)){
stack.push(op);
} else {
String operator = op;
if (stack.isEmpty()) return null;
String a = stack.pop();
if (stack.isEmpty()) return null;
String b = stack.pop();
Integer val = eval(Integer.parseInt(a), operator.charAt(0), Integer.parseInt(b));
if (val == null) return null;
stack.push(val.toString());
}
}
if (stack.isEmpty()) return null;
if (target == Integer.parseInt(stack.pop())){
return polishToInfix(expr);
}
return null;
}
private static String polishToInfix(String[] expr){
Deque<String> stack = new ArrayDeque<>();
for(int i = expr.length-1; i >= 0; --i){
String op = expr[i];
if (isOperand(op)){
stack.push(op);
} else {
stack.push(
String.format("%s%s%s%s%s",
parenthesesIfNeeded(op, "("),
stack.pop(), op, stack.pop(),
parenthesesIfNeeded(op, ")")));
}
}
return stack.pop();
}
private static String parenthesesIfNeeded(String operator, String p){
if (operator.equals("+") || operator.equals("-")) return p;
return "";
}
private static Integer eval(int a, char op, int b){
switch (op){
case '+': return a+b;
case '*': return a*b;
case '-': return a-b;
case '/':
if (b == 0) return null;
else return a/b;
default: throw new IllegalArgumentException(""+op);
}
}
private static boolean isOperand(String s){
return s.charAt(s.length()-1) >= '0' && s.charAt(s.length()-1) <= '9';
}
private static void swap(String[] ss, int from, int to){
String tmp = ss[from];
ss[from] = ss[to];
ss[to] = tmp;
}
private static void genNextOperatorCombos(String[] expr, int shift, int[] selectedOperatorIds){
stepCursor(selectedOperatorIds, OPERATORS.length);
for(int j = 0; j < selectedOperatorIds.length; ++j){
expr[shift+j] = ""+ OPERATORS[selectedOperatorIds[j]];
}
}
private static void stepCursor(int[] cursor, int limit){
for(int i = 0; i < cursor.length; ++i){
int prev = cursor[i];
cursor[i] = (cursor[i]+1)%limit;
if (prev < cursor[i]) break;
}
}
public static int exp(int base, int exp){
int ret = 1;
while(exp > 0){
if ((exp & 1) > 0) ret *= base;
base *= base;
exp >>= 1;
}
return ret;
}
}
public static int count(int[] weights){
int[] arr = new int[151];
for(int w : weights){
++arr[w];
}
int i = 0;
int j = arr.length-1;
int ret = 0;
for(;;){
for(; i < j && arr[i] == 0; ++i);
for(; j > i && arr[j] == 0; --j);
if (i >= j) break;
if (i+j <= 150){
--arr[i];
--arr[j];
} else {
--arr[j];
}
++ret;
}
if (i == j) {
if (i*2 <= 150){
ret += arr[i]/2;
ret += arr[i]%2;
} else {
ret += arr[i];
}
}
return ret;
}
public static void gen(String s){
if (s == null) return;
for(int len = s.length()-2; len > 0; --len){
for(int i = 1, j = i+len; j < s.length(); ++i, ++j){
System.out.print(s.substring(0,i));
System.out.print(len);
System.out.println(s.substring(j));
}
}
System.out.println(s);
}
I could imagine something like this:
public class QuadNode{
private QuadNode[] children;
private Color color;
final Rectangle rectangle;
public QuadNode(boolean boolColor, int x, int y, int w, int h){
this.color = colorFor(boolColor);
rectangle = new Rectangle(x, y, w, h);
}
public void setColor(int x, int y, boolean boolColor){
if (!rectangle.contains(x,y)) throw new IllegalArgumentException(“index out of range”);;
if (isLeaf()){
if (colorMatch(boolColor)){
return;
} else if (rectangle.area() == 1){
setColor(boolColor);
return;
} else {
//adding 4 new children
split();
}
}
QuadNode child = childFor(x,y);
child.setColor(x, y, boolColor);
//all kids have same color
if (isCompressable()){
removeChildren();
setColor(boolColor);
}
}
public int numberOfPixelsGivenColor(boolean boolColor){
if (isLeaf()){
if (colorMatch(boolColor)){
return rectangle.area();
} else {
return 0;
}
}
int ret = 0;
for(QuadNode child : children){
ret += child.numberOfPixelsGivenColor(boolColor);
}
return ret;
}
...
}
class Rectangle{
int x, y, w, h;
....
}
class FunkyMedian {
public static void main(String[]args){
System.out.println(median(10, 1, 5, 0, 11));//...min(0)...1...5...10...max(11)
System.out.println(median(10, 1, 5, 2, 4));//...1...min(2)...max(4)...5...10...
System.out.println(median(10, 1, 5, 2, 11));//...1...min(2)...5...10...max(11)
}
public static Integer median(int a, int b, int c, int min, int max) {
if (min > max) return null;
int[] arr = new int[3];
int i = 0;
if (min <= a && a <= max) {
arr[i] = a;
++i;
}
if (min <= b && b <= max) {
arr[i] = b;
++i;
}
if (min <= c && c <= max) {
arr[i] = c;
++i;
}
if (i == 0) return null;
if (i == 1) return arr[0];
if (i == 2) return arr[0];
return median(a, b, c);
}
public static Integer median(int a, int b, int c) {
if (a < b) {
int tmp = a;
a = b;
b = tmp;
}
if (b < c) {
int tmp = b;
b = c;
c = tmp;
}
if (a < b) {
int tmp = a;
a = b;
b = tmp;
}
return b;
}
}
You have a bug: System.out.println(calculateLogCuttingCost(100, new int[]{}));
Cutting a rod with length 100 without markings costs 0.
Here is my proposal:
/**
The plan
======
M markings => M+2 markings, including the beginning and the end of the log
dp[i][j] = optimum cost cutting up log between marking i and marking j
dp[i][j] = if |j-i| < 2 then 0, same marking or no inbetween markings
dp[i][j] = dp[i][k]+dp[k][j]+logLen(i,j) over all k:i+1..j-1
O(M**2) different (i,j) pairs:
maximum O(M) different cuts between i and j:
1 sum calculation, 1 length calculation -> time:O(1), space:O(M)
dp time: O((M**2)*M), space: O(M**2)
**/
public class CarerrCup_5188262471663616{
public static void main(String[]args){
System.out.println(findMinCost(new int[]{1, 3, 7, 10}, 15));
System.out.println(findMinCost(new int[]{}, 15));
System.out.println(findMinCost(new int[]{1}, 15));
System.out.println(findMinCost(new int[]{23, 34, 35, 68, 71, 88, 93}, 100));
}
private static int findMinCost(int[] markings, int len){
int[] logLen = logLen(markings, len);
int[][] dp = new int[markings.length+2][markings.length+2];
for(int betweenMarkCount = 1;
betweenMarkCount <= markings.length;
++betweenMarkCount){
for(int i = 0;; ++i){
int j = i+betweenMarkCount+1;
if (j >= dp.length) break;
int min = Integer.MAX_VALUE;
int cost = logLen[j]-logLen[i];
for(int k = i+1; k <= j-1; ++k){
min = Math.min(min, dp[i][k]+dp[k][j]+cost);
}
dp[i][j] = min;
}
}
return dp[0][dp.length-1];
}
private static int[] logLen(int[] markings, int len){
int[] ret = new int[markings.length+2];
for(int i = 1; i <= markings.length; ++i){
ret[i] = markings[i-1];
}
ret[ret.length-1] = len;
return ret;
}
}
import java.util.*;
public class CareerCup_15320677{
public static void main(String[]args){
int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
System.out.println(findMatchingPairWithBst(arr, 3));
}
private static Pair findMatchingPairWithBst(int[] arr, int target){
if (arr == null || arr.length == 0) {
return null;
}
Node root = Node.parse(arr);
Deque<Node> leftStack = new LinkedList<Node>();
Deque<Node> rightStack = new LinkedList<Node>();
fillLeft(root, leftStack);
fillRight(root, rightStack);
Node left = nextIncreasing(leftStack);
Node right = nextDecreasing(rightStack);
while(left != right){
int sum = left.val + right.val;
if (sum < target){
left = nextIncreasing(leftStack);
} else if (sum > target){
right = nextDecreasing(rightStack);
} else {
return new Pair(left.val, right.val);
}
}
return null;
}
private static void fillLeft(Node node, Deque<Node> stack){
if (node == null) {
return;
}
while(node != null){
stack.push(node);
node = node.left;
}
}
private static void fillRight(Node node, Deque<Node> stack){
if (node == null){
return;
}
while(node != null){
stack.push(node);
node = node.right;
}
}
private static Node nextIncreasing(Deque<Node> stack){
Node next = stack.pop();
fillLeft(next.right, stack);
return next;
}
private static Node nextDecreasing(Deque<Node> stack){
Node next = stack.pop();
fillRight(next.left, stack);
return next;
}
}
class Pair{
int x, y;
Pair(int x, int y){
this.x = x;
this.y = y;
}
public String toString(){
return String.format("(%d,%d)", x, y);
}
}
class Node{
int val;
Node left;
Node right;
static Node parse(int[] arr){
return parse(arr, 0, arr.length-1);
}
static Node parse(int[] arr, int lo, int hi){
if (lo > hi) {
return null;
}
int mid = lo + (hi-lo)/2;
Node node = new Node();
node.val = arr[mid];
node.left = parse(arr, lo, mid-1);
node.right = parse(arr, mid+1, hi);
return node;
}
}
public class CareerCup_19286747{
public static void main(String[]args){
int[][] arrs = new int[][]{
{2,-1,-2,12,453,-9,2,8}
,{7,-1,4}
,{1,2,3,4,5}
,{-1,-3,-5,-2,-1,-4}
,{2, -1, -2, 1, -4, 2, 8}
};
for(int[] arr : arrs){
Range[] ranges = findRanges(arr);
print(arr, ranges[0], ranges[1]);
}
}
static Range[] findRanges(int[] arr){
Range[] minSumsFromLeft = findMinSumsFromLeft(arr);
Range[] maxSumsFromRight = findMaxSumsFromRight(arr);
int i = findOptimalSplit(minSumsFromLeft, maxSumsFromRight);
Range[] maxSumsFromLeft = findMaxSumsFromLeft(arr);
Range[] minSumsFromRight = findMinSumsFromRight(arr);
int j = findOptimalSplit(maxSumsFromLeft, minSumsFromRight);
int diff1 = optimalValAtSplit(i, minSumsFromLeft, maxSumsFromRight);
int diff2 = optimalValAtSplit(j, maxSumsFromLeft, minSumsFromRight);
if (diff1 > diff2){
return optimalRangesAtSplit(i, minSumsFromLeft, maxSumsFromRight);
} else {
return optimalRangesAtSplit(j, maxSumsFromLeft, minSumsFromRight);
}
}
static Range[] optimalRangesAtSplit(int i, Range[] leftSums, Range[] rightSums){
return new Range[]{leftSums[i], rightSums[i+1] };
}
static int optimalValAtSplit(int i, Range[] leftSums, Range[] rightSums){
return Math.abs(rightSums[i+1].sum - leftSums[i].sum);
}
static int findOptimalSplit(Range[] leftSums, Range[] rightSums){
int maxVal = Integer.MIN_VALUE;
int ans = -1;
for(int i = 0; i < leftSums.length; ++i){
int nextVal = optimalValAtSplit(i, leftSums, rightSums);
if (maxVal < nextVal){
maxVal = nextVal;
ans = i;
}
}
return ans;
}
static Comparator<Integer> NATURAL_ORDER = new Comparator<Integer>(){
public int compare(Integer a, Integer b){
return Integer.compare(a,b);
}
};
static Comparator<Integer> REVERSED_ORDER = Collections.reverseOrder(NATURAL_ORDER);
static Range[] findMinSumsFromLeft(int[] arr){
return findSumsFromLeft(arr, REVERSED_ORDER);
}
static Range[] findMaxSumsFromLeft(int[] arr){
return findSumsFromLeft(arr, NATURAL_ORDER);
}
static Range[] findSumsFromLeft(int[] arr, Comparator<Integer> comparator){
Range[] ans = new Range[arr.length-1];
for(int i = 0, s = i, sum = 0; i < ans.length; ++i){
sum += arr[i];
if (comparator.compare(arr[i], sum)<0){
sum = arr[i];
s = i;
}
ans[i] = new Range(s, i, sum);
}
return ans;
}
static Range[] findMinSumsFromRight(int[] arr){
return findSumsFromRight(arr, REVERSED_ORDER);
}
static Range[] findMaxSumsFromRight(int[] arr){
return findSumsFromRight(arr, NATURAL_ORDER);
}
static Range[] findSumsFromRight(int[] arr, Comparator<Integer> comparator){
Range[] ans = new Range[arr.length];
for(int i = arr.length-1, e = i, sum = 0; i > 0; --i){
if (comparator.compare(arr[i], sum)<0){
sum = arr[i];
e = i;
}
ans[i] = new Range(i, e, sum);
}
return ans;
}
static void print(int[] arr, Range left, Range right){
print(arr, left);
System.out.print(" ");
print(arr, right);
System.out.println();
}
static void print(int[] arr, Range r){
System.out.print("[");
System.out.print(arr[r.start]);
for(int i = r.start+1; i <= r.end; ++i){
System.out.printf(", %d", arr[i]);
}
System.out.print("]");
}
}
class Range{
int start, end, sum;
Range(int start, int end, int sum){
this.start = start;
this.end = end;
this.sum = sum;
}
public String toString(){
return String.format("[%d,%d] sum:%d", start, end, sum);
}
}
" and do O(n logn) sorting..." or use quickselect for O(n) running time on average.
The last case: An exact solution is possible with a distributed system, using binary search. Slaves store segments of data sorted, master drives the binary search: at each iteration for a hi,lo boundary the nodes provide the item count falling in the boundaries.
class NewYearsEve{
public static void main(String[] args) throws java.io.FileNotFoundException {
java.util.Scanner sc = new java.util.Scanner(new java.io.File(args[0]));
int count = sc.nextInt();
for(int i = 1; i<=count; i++){
System.out.println(String.format("Case #%d: %.7f", i, quantity(sc.nextInt(), sc.nextInt(), sc.nextInt())));
}
}
static double quantity(int B, int L, int N){
double influx = influx(B, L, N);
return 250.0*(influx > 1?1:influx);
}
static double influx(int B, int L, int N){
double[][] influx = new double[L][];
influx[0] = new double[1];
influx[0][0] = 3.0*B;
for(int level = 1; level < influx.length; level++){
influx[level] = new double[influx[level-1].length + level + 1];
for(int shift = 1, source = 0; shift <= level; shift++){
for(int j = 0; j<shift; j++, source++){
int targetTop = source;
int targetLeft = targetTop+shift;
int targetRight = targetTop+shift+1;
double residual = Math.max((influx[level-1][source]-1.0)/3.0, 0);
influx[level][targetTop] += residual;
influx[level][targetLeft] += residual;
influx[level][targetRight] += residual;
}
}
}
return influx[L-1][N-1];
}
}
RepJaneBraun, Associate at ASAPInfosystemsPvtLtd
Hi, I am Jane From York,PA.My goal is to create a life that I don’t want to ...
RepLizzieGibson, Cloud Support Associate at Aspire Systems
I'm an engineering student from Huntsville, AL USA. Have more interest in management and stuff related to business. Promptly ...
- madno December 09, 2016