Problem:-
Given an array A of N integers A[0], A[1], ..., A[N-1] and a string B
which is a permutation of "12345".
You have to find a subsequence of 5 elements from A having distinct
values such that their relative order is same as B.
Meaning that, if (i0, i1, i2, i3, i4) are the indexes of such a
subsequence (0 <= i0 < i1 < i2 < i3 < i4 < N) then:
A[i0] is the B[0]-th smallest element among the 5 numbers.
A[i1] is the B[1]-th smallest element among the 5 numbers.
A[i2] is the B[2]-th smallest element among the 5 numbers.
A[i3] is the B[3]-th smallest element among the 5 numbers.
A[i4] is the B[4]-th smallest element among the 5 numbers.
Input
The first line of input contains T(<=60) which is the number of tests
cases. The first line of each test case will be an integer N
(5<=N<=1000) and a string B containing a permutation of "12345". Next
line will contain N integers A[0], A[1], ..., A[N-1]. Each of them
will be between -109 and +109 (inclusive).
Output
For each test case output five space separated integers in ascending
order which are the indexes (i0, i1, i2, i3, i4) of a five length
subsequence described before. You may output any solution. If there is
no solution just output "-1" without quotes.
Example
Input:
2
7 32145
6 17 5 3 13 8 10
7 12345
10 20 30 40 40 20 10
Output:
0 2 3 5 6
-1
And here is my solution....
import java.util.Arrays;
public class subsequence {
public int[] test(String seq){
int a[]={6,17,5,3,13,8,10};
int b[]=new int[a.length];
//{10, 20, 30, 40, 40, 20, 10};
int cpy[]=new int[a.length];
int pos[]=new int[a.length];
int value=0,m=0;
int neg[]=new int[1];
cpy=Arrays.copyOf(a,a.length);
Arrays.sort(a);
for(int i=0,j=0;i<a.length-1;i++){
if(a[i]!=a[i+1]){
b[m++]=a[i];
}
}
b[m]=a[a.length-1];
// for(int i=0;i<a.length;i++)
// System.out.println(b[i]+" pos is "+(i)+" "+cpy[i]);
for(int i=0;i<seq.length()-1&&value!=-1;i++){
if(b[i]<b[i+1]){
//System.out.print("in sorted ");
}
else{
value=-1;
neg[0]=value;
//System.out.println("got negative");
}
}
//System.out.println(value);
if(value!=-1){
for(int i=0;i<b.length;i++){
for(int j=0;j<b.length;j++)
{
if(b[i]==cpy[j]){
pos[i]=j;
//System.out.print(j+" ");
}
}
}
}
else
{
//value=-1;
}
Arrays.sort(pos,0,seq.length());
int res[]=new int[seq.length()];
if(value!=-1)
res=Arrays.copyOf(pos,seq.length());
else
res=Arrays.copyOf(neg,neg.length);
return res;
}
public static void main(String a[])
{
String tes="32145";
int result[]=new int[tes.length()];
result=new subsequence().test(tes);
for(int i=0;i<result.length;i++)
System.out.print(result[i]+" ");
}
}
So can anyone modify this code such that it'll take input as described
above....i.e.
In first line no. of test cases
and then input for each test case
and then output as described above in same manner.
And second thing is when input is:- 6 17 5 3 13 8 10 6 3 then in that
case output must be the same....0 2 3 5 6
So someone pls help with this input and output format,means which
classes and member function should i use to correct the problem(in
JAVA only).
Thanks a lot....
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en.
