hwer.han
BAN USERHere is the output for input
a=[\
[2, 3, 4, 5],\
[4, 5, 10, 11],\
[20, 6, 9, 12],\
[6, 7, 8, 40]
]
output:
step 9 : [ 1 0 ] 4
step 8 : [ 1 1 ] 5
step 7 : [ 2 1 ] 6
step 6 : [ 3 1 ] 7
step 5 : [ 3 2 ] 8
step 4 : [ 2 2 ] 9
step 3 : [ 1 2 ] 10
step 2 : [ 1 3 ] 11
step 1 : [ 2 3 ] 12
Here is one solution (maybe not optimal)
first it picks up smallest element in the matrix, search a longest increasing sub seq starting at this element, mark all the element on the seq using direct[][] and dist_2_end[][]
driect[i][j] means one the longest sub seq, what is the direction of next movement at i,j
dist_2_end[i][j] means the distance between i,j and the end of the longest sub seq
second, pick up the smallest element which is not marked yet, search a longest increasing sub seq starting at this elements, the search can be simplified if we search some element which is already marked. That means the rest of search should follow the longest sub seq starting at this element.
then mark the longest seq and repeat the second step while all the matrix is marked.
def findmin(a,direct):
sx=-1
sy=-1
mini=999999
for i,a1 in enumerate(a):
for j,a2 in enumerate(a1):
# print a2,
if a2<mini and direct[i][j]==-1:
sx, sy, mini = (i,j,a2)
# print
return (sx, sy)
def findlongpath(sx, sy, a, direct,dist_2_end,offset):
if direct[sx][sy]>=10:
return 0,[]
if direct[sx][sy]>=0:
return dist_2_end[sx][sy],[]
maxlen, maxdirect,maxpath= (0,-2, [])
direct[sx][sy]=10
for i,oi in enumerate(offset):
nx,ny =(sx+oi[0], sy+oi[1] )
if nx<0 or nx>=len(a) or ny<0 or ny>=len(a):
continue
# here is for the condition you want to applt yo the sequence
if a[nx][ny]!=a[sx][sy]+1:
continue
pathlen, path = findlongpath(nx,ny, a,direct, dist_2_end, offset)
if pathlen>maxlen:
maxlen=pathlen
maxpath=path[:]
maxdirect=i
direct[sx][sy]=-1
maxpath.append([sx,sy,maxdirect])
return maxlen+1, maxpath
def setpath(path,pathlen, direct, dist_2_end):
for p in path:
sx, sy, d= (p[0], p[1], p[2])
direct[sx][sy] = d
dist_2_end[sx][sy] = pathlen
pathlen-=1
a=[\
[10,10,1 ,23,-4, 5, 6,23, 7],\
[-6,10,12,3 ,-4, 5,-3,10, 7],\
[10,10,-200,23,-4,-200, 6,23,-7],\
[-2, 3,1 ,99,99, 5,32, 0,-7],\
[10, 4,7 ,8,9, 5, 6,-5,-7],\
[3 , 5,6 ,99,99,-5,-3,-5, 7],\
[18,-6,1 ,23,-4,-200, 6,4 , 7],\
[2 ,10,1 ,-2,14, 5,10,10, 7],\
[2 ,10,1 ,23,-4, 5, 2,2 , 7]\
]
N=len(a)
offset=[[1,0],[0,1],[-1,0],[0,-1]]
direct=[[-1 for j in range(N)] for i in range(N)]
dist_2_end=[[0 for j in range(N)] for i in range(N)]
sx,sy = findmin(a, direct)
lx,ly=(-1,-1)
ml,mx,my = (0,-1,-1)
while (lx!=sx or ly!=sy):
pathlen, path=findlongpath(sx,sy,a,direct,dist_2_end,offset)
path.reverse()
if ml<pathlen:
ml, mx, my=(pathlen, sx, sy)
setpath(path,pathlen, direct, dist_2_end)
lx, ly =(sx, sy)
sx,sy=findmin(a, direct)
sx, sy=(mx, my)
while ml>0:
d=direct[sx][sy]
print 'step',ml,':','[',sx, sy,']', a[sx][sy]
if d<0:
break
sx, sy = (sx +offset[d][0], sy+offset[d][1])
ml-=1
Here is my solution. It is inspired by the classic problem of finding max subarray in 1D array. Here the program tries to find a max submatrix which ends at {i,j}. Then the max submatrix should be the maximum among the max submarices ending at all i's and j's.
To search {i,j} start at j=0, for each i, it needs O(n) to find a max submatrix for each {i,j},
for j>0, the results from j-1 can be used which is basically in a DP way.
Overall complexity should be O(n^3)
#include<stdlib.h>
#include<stdio.h>
#define N 9
#define AT(a,b,c) (*((a)+(b)*N+(c)))
void findMaxEnd(int *a,
int *max,int *max_i, int *max_end,
int i,int j,
int *maxe, int *max_height, int *max_posi)
{
int height;
int pos=i;
int hi;
int s=0;
*maxe=-999999;
for (hi=i;hi>=0;hi--)
{
s+=AT(a,hi,j);
AT(max_end, pos, i-hi)+=s;
if (s>AT(max_end, pos, i-hi))
{
AT(max_end, pos, i-hi)=s;
AT(max_i,pos,i-hi)=j;
}
if (*maxe<AT(max_end,pos,i-hi))
{
*maxe=AT(max_end,pos,i-hi);
*max_height = i-hi;
*max_posi = AT(max_i,pos,i-hi);
}
}
}
int main()
{
int a_0[N*N]={
10,10,1 ,23,-4, 5, 6,23, 7,
-6,10,12,3 ,-4, 5,-3,10, 7,
10,10,-200,23,-4,-200, 6,23,-7,
-2, 3,1 ,99,99, 5,32, 0,-7,
10, 4,1 ,99,99, 5, 6,-5,-7,
3 , 5,1 ,99,99,-5,-3,-5, 7,
18,-6,1 ,23,-4,-200, 6,4 , 7,
2 ,10,1 ,-2,14, 5,10,10, 7,
2 ,10,1 ,23,-4, 5, 2,2 , 7
};
int s_0[N];
int max_0[N*N], max_i0[N*N], max_end0[N*N];
int *a=a_0,*s=s_0,*max=max_0,
*max_i=max_i0,*max_end=max_end0;
int maxe,max_height,max_posi;
int all_maxe=-999999, all_max_height, all_max_posi,
all_i=-1, all_j=-1;
int i,j;
for (i=0;i<N;i++)
for (j=0;j<N;j++)
{
AT(max_end,i,j)=-999999;
AT(max_i,i,j) = 0;
}
for (j=0;j<N;j++)
for (i=N-1;i>=0;i--)
{
findMaxEnd(a,max,max_i,max_end,i,j,&maxe,&max_height,&max_posi);
printf("%d %d %d %d %d\n",j,i,maxe,max_height,max_posi);
if (all_maxe<maxe)
{
all_maxe=maxe;
all_max_height=max_height;
all_max_posi=max_posi;
all_i=i;
all_j=j;
}
}
printf("Max submatrice:\n");
for (i=all_i-all_max_height;i<=all_i;i++)
{
for (j=all_max_posi;j<=all_j;j++)
printf("%5d",AT(a,i,j));
printf("\n");
}
return 0;
}
here is the python code
a=[1,2,-1,0,2,0,0,3,-1,4,-2,0,3,4,0,0,2,-2,-3,0]
ptr_left=0
ptr_right=len(a)-1;
nzero_left=0
nzero_right=0
while ptr_left<=ptr_right:
if a[ptr_left]>0 and a[ptr_right]<0:
t=a[ptr_left]
a[ptr_left]=a[ptr_right]
a[ptr_right]=t
if a[ptr_left]<0:
if nzero_left>0:
a[ptr_left-nzero_left]=a[ptr_left]
a[ptr_left]=0
ptr_left+=1
elif a[ptr_left]==0:
nzero_left+=1
ptr_left+=1
if a[ptr_right]>0:
if nzero_right>0:
a[ptr_right+nzero_right]=a[ptr_right]
a[ptr_right]=0
ptr_right-=1
elif a[ptr_right]==0:
nzero_right+=1
ptr_right-=1
print ptr_left, ptr_right, nzero_left, nzero_right
print a
here is the output
0 18 0 1
[1, 2, -1, 0, 2, 0, 0, 3, -1, 4, -2, 0, 3, 4, 0, 0, 2, -2, -3, 0]
1 17 0 1
[-3, 2, -1, 0, 2, 0, 0, 3, -1, 4, -2, 0, 3, 4, 0, 0, 2, -2, 0, 1]
2 16 0 1
[-3, -2, -1, 0, 2, 0, 0, 3, -1, 4, -2, 0, 3, 4, 0, 0, 2, 0, 2, 1]
3 15 0 1
[-3, -2, -1, 0, 2, 0, 0, 3, -1, 4, -2, 0, 3, 4, 0, 0, 0, 2, 2, 1]
4 14 1 2
[-3, -2, -1, 0, 2, 0, 0, 3, -1, 4, -2, 0, 3, 4, 0, 0, 0, 2, 2, 1]
4 13 1 3
[-3, -2, -1, 0, 2, 0, 0, 3, -1, 4, -2, 0, 3, 4, 0, 0, 0, 2, 2, 1]
4 12 1 3
[-3, -2, -1, 0, 2, 0, 0, 3, -1, 4, -2, 0, 3, 0, 0, 0, 4, 2, 2, 1]
4 11 1 3
[-3, -2, -1, 0, 2, 0, 0, 3, -1, 4, -2, 0, 0, 0, 0, 3, 4, 2, 2, 1]
4 10 1 4
[-3, -2, -1, 0, 2, 0, 0, 3, -1, 4, -2, 0, 0, 0, 0, 3, 4, 2, 2, 1]
5 9 1 4
[-3, -2, -1, -2, 0, 0, 0, 3, -1, 4, 0, 0, 0, 0, 2, 3, 4, 2, 2, 1]
6 8 2 4
[-3, -2, -1, -2, 0, 0, 0, 3, -1, 0, 0, 0, 0, 4, 2, 3, 4, 2, 2, 1]
7 8 3 4
[-3, -2, -1, -2, 0, 0, 0, 3, -1, 0, 0, 0, 0, 4, 2, 3, 4, 2, 2, 1]
8 7 3 4
[-3, -2, -1, -2, -1, 0, 0, 0, 0, 0, 0, 0, 3, 4, 2, 3, 4, 2, 2, 1]
Here is my one pass algorithm:
let ptr_left points to the left end of the array a[] and ptr_right points to the right end
let nzero_left is the counts of zero from left sides; nzero_right for right side
nzero_left=0; nzero_right=0;
while (ptr_left<=ptr_right)
{{
if (a[ptr_left]==positive and
a[ptr_right]==negative)
swap a[ptr_left] and a[ptr_right]
if a[ptr_left] is negative
{
if nzero_left>0:
shift 0 toward the center of array by letting
a[ptr_left-nzero_left]= a[ptr_left]; a[ptr_left]=0;
ptr_left++;
}
else if a[ptr_left] is zero
{
increase nzero_left by 1
ptr_left++;
}
similarly,
if a[ptr_right] is positive
{
if nzero_right>0:
shift 0 toward the center of array by letting
a[ptr_right-nzero_right]= a[ptr_right]; a[ptr_right]=0;
ptr_right--;
}
else if a[ptr_right] is zero
{
increase nzero_right by 1
ptr_right--;
}
}}
eventually, ptr_left and ptr_right meet somewhere in middle,
A slight modification of main() can also consider consecutive substring:
Once we found any substring with M chars, we just check if M chars immediately after the substring are the same to the substring. Here is the modified main()
int main()
{
Stree root;
root.key=0;
char s[10000];
char *t_s=NULL;
int i;
std::cin>>s;
int slen=strlen(s);
char *s_end=s+slen;
for (i=slen,t_s = s_end-1; t_s>=s; t_s--,i--)
{
int M=findMem(root, t_s);
if (M<2) continue;
bool valid=true;
for (int j=0;j<M;j++)
{
if (t_s+M+j>=s_end) {valid=false;break;}
if (*(t_s+j)!=*(t_s+M+j)) {valid=false;break;}
}
if (valid)
{
t_s[M]=0;
cout<<"The string has consecutive repeated substring: "<<t_s<<"\n";
return 0;}
}
return 0;
}
we can use a suffix array to find repeat pattern:
e.g. abcabc# (# only for end of string)
suffices will be
c#
bc#
abc#
cabc#
bcabc#
abcabc#
first we have c#, then we see how long are the common string between bc# and c# when both strings are aligned to their left sides; similarly, how long are the common string between abc# and any of bc# or c#; as long as we have found a common string longer than 1 char, then we consider the input string is a valid string.
In this case:
bcabc# will have a common string 'bc' with bc# (always align strings to their left sides when in comparison), so the input string is valid.
Finally, using tries will make comparison very fast, below the solution codes:
#include<iostream>
#include<vector>
#include<string.h>
using std::vector;
using std::cout;
struct suftree{
char key;
vector<struct suftree> child;
};
typedef struct suftree Stree;
typedef std::vector<Stree>::iterator iterator;
int findMem(Stree& root, char *s)
{
if (!s[0]) return 0;
int nmatch=0;
bool found=false;
for (iterator it=root.child.begin();
it!=root.child.end()&&!found; it++)
if ((*it).key==s[0])
{
nmatch=1+ findMem ((*it), s+1);
found=true;
}
if (!found)
{
Stree temp;
temp.key=s[0];
root.child.push_back(temp);
int n=root.child.size();
findMem(root.child[n-1], s+1);
}
return nmatch;
}
int main()
{
Stree root;
root.key=0;
char s[10000];
char *t_s=NULL;
std::cin>>s;
int slen=strlen(s);
for (t_s = s+ slen-1; t_s>=s; t_s--)
if (findMem(root, t_s)>=2)
{cout<<"The string has repeated continous substring.\n";
return 0;}
return 0;
}
given T(n) is n th number in the output sequence:
T(n) = T(n-1) + d(n)
d(n) is anther sequence having following pattern:
0 1 (N-1) N -(N-1) -(N-1) 1 (N-1) (N-1) (N-1) N ...
^0 -(N-1) ^1 (N-1) ^2 -(N-1) ^3 (N-1)
once the number of |N-1| increases to N-1, the number of IN-1| starts to decrease at the next repeat.
Also 1 and N inbetween those (N-1)s has following pattern:
..1..N..1..N..1 (N-1 times of |N-1|) 1...N..1...N...1...
or
..1..N..1..N..1..N (N-1 times of |N-1|) N..1...N..1...N...1...
Reason:
given N=3
We have
1 2 3
4 5 6
7 8 9
if we move right on the top or bottom edge of matrix
1+1==> 2
2+1 ==>3
x+1 ==> the right neighbor of x
similarly
on the left and right edges:
x+N==> the element below x
if we move along diagonals
x+(N-1) ==> move toward bottom-left
x-(N-1) ==> move toward top-right
Here is the solution using DP
#include <iostream>
#include <cstdlib>
int main (int argc, char * const argv[]) {
int s;
scanf("%d",&s);
int nc =6;
int coin[]={1,2,5,10,20,25};
int i,j;
float *max_v=new float [(nc+1)*(s+1)];
int *min_c = new int [(nc+1)*(s+1)];
for (i=0;i<=s;i++)
{
min_c[0*(s+1)+i] = 0;
max_v[0*(s+1) + i] = 0.f;
}
for (i=1;i<=nc;i++)
for (j=0;j<=s;j++)
{
if (j>=coin[i-1])
{
int idx_now = i*(s+1)+j;
int idx_i_1 = (i-1)*(s+1) + j;
int idx_j_c = i*(s+1) +j -coin[i-1];
float last_max_v = max_v[idx_j_c];
int last_min_c = min_c[idx_j_c];
float new_max_v = last_max_v*(float)last_min_c
+(float)coin[i-1];
new_max_v/=(float)(last_min_c+1);
if (new_max_v>max_v[idx_i_1])
{
max_v[idx_now]=new_max_v;
min_c[idx_now]=last_min_c+1;
}
else
{
max_v[idx_now]=max_v[idx_i_1];
min_c[idx_now]=min_c[idx_i_1];
}
}
else
{
int idx_now = i*(s+1)+j;
int idx_i_1 = (i-1)*(s+1) + j;
max_v[idx_now]=max_v[idx_i_1];
min_c[idx_now]=min_c[idx_i_1];
}
//show_ij(i,j,s,min_c, max_v);
}
float maxv=0.01;
int max_dx=-1;
for (i=1;i<=nc;i++)
if (maxv<max_v[i*(s+1)+s])
{
maxv=max_v[i*(s+1)+s];
max_dx = i;
}
if (maxv>0.01)
{
std::cout<<min_c[max_dx*(s+1)+s]<<" coins.\n";
}
delete [] min_c;
delete [] max_v;
}
#include <iostream>
#include <cstdlib>
bool min_coin (int s, int& try1,int *coin, int nc);
int main (int argc, char * const argv[]) {
int s;
scanf("%d",&s);
int nc =6;
int coin[]={1,2,5,10,20,25};
int min_c = s;
int found=0;
for (int i=0;i<nc;i++)
{
int try1;
if (s-coin[i]>0)
if (min_coin (s-coin[i], try1,coin, nc))
{
if (try1+1<min_c) min_c=try1+1;
found=1;
}
}
if (!found) std::cout<<"No solution.\n";
else std::cout<<min_c<<" coins.\n";
return 0;
}
bool min_coin (int s, int& try1,int *coin, int nc)
{
//std::cout<<s<<" "<<try1<<"\n";
for (int i=0;i<nc;i++)
if (s==coin[i])
{
try1=1;
return true;
}
if (s<0) exit(1);
int min_c=s;
int found=0;
for (int i=0;i<nc;i++)
{
int try_c;
if (s-coin[i]>0)
if (min_coin (s-coin[i], try_c,coin, nc))
{
if (try_c+1<min_c) min_c=try_c+1;
found=1;
}
}
if (found)
{
try1 = min_c;
return true;
}
return false;
}
Basic Idea: given b1<b2<b3 in B, a1<a2<a3<a4 in A, then b1<=a1, b2<=a2 and b3<=a4
#include<iostream>
int main ()
{
//assume imput is sorted
int four_num[]={2,4,6,7};
char num[11],mark[31];
int i,j,k,l;
memset(num,0,11);
memset(mark,0,31);
for (i=0;i<4;num[four_num[i++]]=1);
for (i=1;i<=four_num[0];i++)
{
mark[i]=1;
for (j=i+1;j<=four_num[1];j++)
{
mark[j]=1;
mark[i+j]=1;
for (k=j+1;k<four_num[3];k++)
if (k!=i+j)
{
mark[k]=1;
mark[i+k]=1;
mark[j+k]=1;
mark[i+k+j]=1;
int t=0;
for (l=1;l<=10;l++)
t+=(mark[l]&num[l]);
if (t>=4)
printf("Results are: %d %d %d\n",i,j,k);
mark[k]=0;
mark[i+k]=0;
mark[j+k]=0;
mark[i+k+j]=0;
}
mark[i+j]=0;
mark[j]=0;
}
mark[i]=0;
}
}
Does this run on O(n)?
- hwer.han August 27, 2012