jicheninsjtu
BAN USERso, no linear programming allowed ?
- jicheninsjtu July 23, 2013correct above
fval =18.0 for this case
fval is the total distance
x is an vector which indicates each floor's number of being passed by from either left or right.
in this case x is pretty tight which means no extra step needed.
Also, exp time complexity is not acceptable. So don't waste your time to find opt solution.
Try approximation solution or Random solution
I have a Integer Linear Programming solution:
I give an example:
(6)(5)(4)(3)(2)(1)
first consider floor1: it has p6. so p6 must be moved to f6. Thus floor5~floor6 each must be passed by the lift from the bottom once. or for convenient, be passed by the lift from the left;
then consider the floor2. it has p5 so floor5~floor3 each be passed by from left once!
continue doing this until floor6: it has p1 so floor1~floor5 each be passed by from right once!
we let Xn be the times floorN be passed by from left
we let Yn be the times floorN be passed by from right;
thus we have the following equations:
* x1>=0 y1>=1;
* x2>=1 y2>=2
* x3>=2 y3>=3
* x4>=3 y4>=2
* x5>=2 y6>=1
* x6>=1 y6>=0
also notice that the lift must be moved continuely through the building: it must visit floor4 if
it go from floor3 to floor5.
how to restrict that? for a certain floor, the difference of its left passed number and right passed number should not be more than one ! Thus |Xn-Yn|<=1 for every n;
and our propose is to minimize the total lift distance. notice that if a floor is passed by either from left or right, it means the lift move One floor distance. so our goal is to
min(X1+....X6+Y1+....Y6)
you solve this ILP problem and you get the optimal solution.
I give my Matlab Code to solve this problem. Matlab has linprog function to solve LP
You can also use other LP solver to solve this problem. Don't try to write your own!!
Also notice that we have restriction that all Xn and Yn must be Integer which turn this problem from a LP to ILP.
ILP is a NPC problem. You're not supposed to have polynomial time solution !! Otherwise rearrange your desk for the Turing Award.
c=[1;1;1;1;1;1;1;1;1;1;1;1];
A=[ -1 0 0 0 0 0 0 0 0 0 0 0 ;
0 -1 0 0 0 0 0 0 0 0 0 0;
1 -1 0 0 0 0 0 0 0 0 0 0 ;
-1 1 0 0 0 0 0 0 0 0 0 0 ;
0 0 -1 0 0 0 0 0 0 0 0 0;
0 0 0 -1 0 0 0 0 0 0 0 0;
0 0 1 -1 0 0 0 0 0 0 0 0 ;
0 0 -1 1 0 0 0 0 0 0 0 0;
0 0 0 0 -1 0 0 0 0 0 0 0;
0 0 0 0 0 -1 0 0 0 0 0 0 ;
0 0 0 0 1 -1 0 0 0 0 0 0 ;
0 0 0 0 -1 1 0 0 0 0 0 0 ;
0 0 0 0 0 0 -1 0 0 0 0 0;
0 0 0 0 0 0 0 -1 0 0 0 0 ;
0 0 0 0 0 0 1 -1 0 0 0 0 ;
0 0 0 0 0 0 -1 1 0 0 0 0;
0 0 0 0 0 0 0 0 -1 0 0 0;
0 0 0 0 0 0 0 0 0 -1 0 0 ;
0 0 0 0 0 0 0 0 1 -1 0 0 ;
0 0 0 0 0 0 0 0 -1 1 0 0;
0 0 0 0 0 0 0 0 0 0 -1 0;
0 0 0 0 0 0 0 0 0 0 0 -1 ;
0 0 0 0 0 0 0 0 0 0 1 -1 ;
0 0 0 0 0 0 0 0 0 0 -1 1 ;
];
b=[0;-1;1;1;-1;-2;1;1;-2;-3;1;1;-3;-2;1;1;-2;-1;1;1;0;-1;1;1];
[x,fval]=linprog(c,A,b,[],[],[]);
x=18.0 for this case.
correct me if i solved this problem wrong
wrong solution.
(3)(5)(1)()()
()(5)(3,1)()()
(1)(5)(3)()()
extra one step: move lift from floor 1 to 2
(1)()(3)()(5)
total =9
doesn't work. it may give extra step.
Think about this case (6)(5)(4)(3)(2)(1)
Actually this case we could come up with a no extra step method
()(6,5)(4)(3)(2)(1)
()(6)(5,4)(3)(2)(1)
()(6)(5)(4,3)(2)(1)
()(6)(5,3)(4)(2)(1)
move p5 to f5
()(6)(3)(4)(2,5)(1)
move p2 to f2
()(6,2)(3)(4)(5)(1)
move p6 to f6
()(2)(3)(4)(5)(1,6)
move p1 to f1
(1)(2)(3)(4)(5)(6)
since there is no extra step, this is the optimal solution
this case we don't need extra lift. this is the most easy case.
what about (2)(1)(3)(5)(4) ? two cycles and you need 3 extra lift.
i think the answer is wrong. you should:
move p2 to f2and p1 to f1
then lift to f4
move p5 to f5 and p4 to f4
extra move is from f1 to f4 = 3step
and your solution extra step is 4 step
public class MinInnerProduct {
public int solve(int[] array1,int[] array2){
Arrays.sort(array1);
Arrays.sort(array2);
int toReturn=0;
int negative1=negative(array1);
int negative2=negative(array2);
int l1=0;
int r1=array1.length-1;
int l2=0;
int r2=array2.length-1;
while(l1<=negative1 && r2>negative2){
toReturn+=(array1[l1]*array2[r2]);
l1++;
r2--;
}
while(l2<=negative2 && r1>negative1){
toReturn+=(array2[l2]*array1[r1]);
l2++;
r1--;
}
while(l1<=r1){
toReturn+=array1[l1]*array2[l2];
l1++;
}
return toReturn;
}
private int negative(int[] array){
if(array[0]>=0){return -1;}
for(int i=0;i<array.length;i++){
if(array[i]>=0){
return i-1;
}
}
return array.length-1;
}
public static void main(String[] args){
MinInnerProduct mip=new MinInnerProduct();
int[] array1={-2,0,2};
int[] array2={-2,-3,1};
System.out.println(mip.solve(array1, array2));
}
}
correct me if i did this wrong
- jicheninsjtu July 21, 2013long fib2(int n){
double sqrt5=Math.sqrt(5);
double a=(1+sqrt5)/2;
double b=(1-sqrt5)/2;
double A=(1+sqrt5)/(sqrt5*2);
double B=(-1+sqrt5)/(sqrt5*2);
return Math.round(( Math.pow(a, n)*A+Math.pow(b, n)*B)) ;
}
- jicheninsjtu July 21, 2013public class ThreeString {
public int solve(String S) {
//modified KMP
int[] pi = new int[S.length()];
int matched = -1;
pi[0] = -1;
for (int i = 1; i < S.length(); i++) {
while (matched != -1 && S.charAt(i) != S.charAt(matched + 1)) {
matched = pi[matched];
}
if (S.charAt(i) == S.charAt(matched + 1)) {
matched++;
}
pi[i] = matched;
}
int possible = pi[S.length() - 1];
while (possible != -1 && possible + 1 > S.length() / 3) {
possible = pi[possible];
}
if (possible == -1) {
return 0;
}
pi = Arrays.copyOf(pi, possible + 1);
// 012345678
// aaaaaaaaa
// 012
matched = -1;
int max = 0;
for (int i = 0; i < S.length(); i++) {
while (matched != -1 && S.charAt(i) != S.charAt(matched + 1)) {
matched = pi[matched];
}
if (S.charAt(i) == S.charAt(matched + 1)) {
matched++;
}
max = Math.max(
max,
Math.min(Math.min(i - matched, matched + 1), S.length() - 1
- i));
if (matched == pi.length - 1) {
matched = pi[matched];
max = Math.max(
max,
Math.min(Math.min(i - matched, matched + 1), S.length()
- 1 - i));
}
}
return max;
}
public static void main(String[] args) {
ThreeString ts = new ThreeString();
String[] S = { "123451234512345", "a", "aa", "aaa", "aaaa", "aaaaa",
"aaaaaa","aaaaaaaa","aaaaaaaaa"};
for (int i = 0; i < S.length; i++) {
System.out.println(S[i]+"= "+ts.solve(S[i]));
}
StringBuilder sb=new StringBuilder("");
for(int i=0;i<200;i++){
sb.append("a");
}
for(int i=0;i<300;i++){
sb.append("b");
}
for(int i=0;i<200;i++){
sb.append("a");
}
System.out.println(ts.solve(sb.toString()));
}
}
if K=M, and K means different followers, then the problem is exactly the Set Cover problem which is NP-Complete.
- jicheninsjtu July 18, 2013
so wrong...what if the some arr[i]<0?
- jicheninsjtu July 29, 2013