10131 - Is Bigger Smarter?

[jiayaoyu]

[c]

#include <stdio.h>
int w[1001];
int s[1001];
int pre[1001];
int lens[1001];

void output(int last)
{
if(pre[last]==-1)
printf("%d\n",last+1);
else{
output(pre[last]);
printf("%d\n",last+1);
}
}
int main(int argc, char *argv[]) {
int num=0,i,j,max = 1,last = 0;
while(scanf("%d %d",&w[num],&s[num])>1) {
pre[num] = -1;
lens[num] = 1;
num++;
}

//D.P
for(i = 0;i<num;i++)
for(j = 0;j<num;j++)
{
if(i==j)continue;
if(w[i]<w[j]&&s[i]>s[j])
{
if(lens[i]+1>lens[j])
{
pre[j] = i;
lens[j] = lens[i]+1;
if(lens[j]>max)
{
max = lens[j];
last = j;
}
}
}
}
printf("%d\n",max);
output(last);

return 0;
}
[/c]


Thanks!

[titid_gede]

i found this problem not difficult, but always got WA. i've modified programs several times. i have read problems several times carefully, but didnt find anything wrong. perhaps i missed something? i use DP

[c]/*@JUDGE_ID: XXXXX 10131 C*/
#include <stdio.h>

#define MAX 1000

typedef struct {
int w;
int iq;
} tdata;

tdata data[MAX];
int len[MAX], pred[MAX];

int printres (int mx) {
if (mx == -1)
return 1;
printres (pred[mx]);
printf ("%d\n", mx+1);
return 1;
}
int main () {
int jumdata, i, j, max, mx;

jumdata = 0;
while (1) {
if (scanf ("%d %d", &i, &j) != 2) break;
data[jumdata].w = i;
data[jumdata++].iq = j;
}

for (i = 0; i < jumdata; i++) {
len[i] = 1;
pred[i] = -1;
}
max = 1; mx = 0;
for (i = 0; i < jumdata; i++)
for (j = 0; j < jumdata; j++)
if ((data[i].w < data[j].w) && (data[i].iq > data[j].iq))
if (len[i]+1 > len[j]) {
len[j] = len[i]+1;
if (len[j] > max) {
max = len[j];
mx = j;
}
pred[j] = i;
}
printf ("%d\n", max);
printres (mx);
return 0;
}

[/c]

[titid_gede]

hello any body can help me? what's wrong with my code? or can you just give me sample input?

[anupam]

i am trying for a several dayz..
but would u please change your code without using structure....
i rarely use structure..
would u try and perhaps it will help u....

----

[titid_gede]

i dont think that change by not using structure would make my code correct. can you give me sample inputs?

[turuthok]

Hello titid, ... try this input:

Code: Select all

2 8
1 9
3 7


Output should be:

Code: Select all

3
2
1
3


-turuthok-

[titid_gede]

aha, i found it, i should update the successor, i'll fixed it. thank you Pak Haryanto.

[fhysics]

this s a dynamic progrmming problem
basicallly i have 2 loops one contain another, iterate through all data,
when i goes before j, i set parent[j]=i, and update length of all children of j (maybe predecessor and successor is more appropiate)
but i got WA. plz help.

[cpp]
#include <iostream.h>

#define MAX 1000

int weight[MAX], iq[MAX];
int parent[MAX];
int count;
int maxLen;
int maxPos;
int len[MAX];


void printP(int mid)
{ if (parent[mid]!=-1)
printP(parent[mid]);
cout << mid+1<<endl;
}


void update(int j, int diff)
{ int children[MAX];
int numChildren=0;
int i;
for (i=0; i<count; i++)
{ if (parent[i]==j)
{ children[numChildren]=i;
numChildren++;
}
}

for (i=0; i<numChildren; i++)
{ len[children[i]]+=diff;
if (len[children[i]]>maxLen)
{ maxLen = len[children[i]];
maxPos = children[i];
}
update(children[i], diff);
}
}

void main()
{
count=0;
while (cin >> weight[count])
{ cin>> iq[count];
count++;
}

int i, j;
int diff;


maxLen = 1;
maxPos = 0;
for (i=0; i<MAX; i++)
{ parent[i]=-1;
len[i]=1;
}


for (i=0; i<count; i++)
for (j=0; j<count; j++)
if (weight[i]<weight[j] && iq[i]>iq[j])
{
if (len[j]<len[i]+1)
{ diff = len[i]+1-len[j];
len[j]+=diff;
parent[j]=i;
if (len[j]>maxLen)
{ maxLen = len[j];
maxPos = j;
}

update(j, diff);
}
}
if (false)//count==0)
cout <<"0"<<endl;
else
{ cout << maxLen<<endl;
printP(maxPos);
}


}

/*
6008 1300
6000 2100
500 2000
1000 4000
1100 3000
6000 2000
8000 1400
6000 1200
2000 1900


4 6
5 5
1 9
3 7
2 8
0 10


*/[/cpp]

[fhysics]

i have something very similiar and i did update the len for all successors but still WA

[Red Scorpion]

Whats your output for your sample input?

My output for your second input is:
6
6
3
5
4
1
2

[rakeb]

i think the most easiest way is to first sort the data in W[a[1]] < W[a[2]] < ... < W[a[n]] and S[a[1]] > S[a[2]] > ... > S[a[n]] order.Then do the LSS algorithm. This may not give u the sample output but u will get ac

[fhysics]

thanks for helping.
i read the problem over, but dont see anything wrong w/ the output for my second test case..

[rlatif119]

The same old problem.......WA
Can somebody help me?

Here is my code:

[c]
#include<stdio.h>

struct list{
int w;
int s;
int c;
};
void Longest_sequence(void);
void Qsort(int p, int r);
int Partition(int p, int r);
void display(int i);

int total,count;
int length[1100],predecessor[1100];
struct list ele[1100];

main()
{
long i,j,n,fl;
fl = 0;
count=0;
i=0;
while(1)
{
scanf("%d",&ele[i].w);
if(feof(stdin))
break;
scanf("%d",&ele[i].s);
length[i] = 1;
ele[i].c=i+1;
predecessor[i] = -1;

i++;
}

total = i;
Qsort(0,total-1);
Longest_sequence();

}


void Longest_sequence(void)
{
int i,j,x;

for (i=0; i<total-1;++i)
{
for (j=i+1;j<total;++j)
{
if (ele[j].w > ele[i].w)
{
if (length[i] + 1 > length[j])
{
length[j] = length[i] + 1;
x=j;
predecessor[j]=i;
}
}
}
}

printf("%d\n",length[x]);
display(x);

}

void Qsort(int p, int r)
{
long q;
if(p<r)
{
q = Partition(p,r);
Qsort(p,q);
Qsort(q+1,r);
}
}
int Partition(int p, int r)
{
struct list x,temp;
int i,j;

x = ele[p];

i = p-1;
j = r+1;
while(i<=j)
{
do {
--j;
}while(ele[j].s < x.s);
do {
++i;
}while(ele[i].s > x.s);

if(i<j)
{
temp = ele[i];
ele[i] = ele[j];
ele[j] = temp;
}

else
return j;
}

}
void display(int i)
{
if(predecessor[i]!=-1)
{
display(predecessor[i]);
}

printf("%d\n",ele[i].c);
}[/c]

[Yu Fan]

I can't find the bug...
This is my code:

#include <iostream>
#include <algorithm>
using namespace std;
struct elephant{
int weight,iq,number;
};
bool compare(elephant a,elephant b) {
return a.iq>b.iq;
}
elephant m[1000];
int n=0,i,j,maxe[2000]={1},pre[2000]={-1},longest=1,end=0;
void show(int e);
int main() {
while(cin>>m[n].weight>>m[n].iq)
m[n].number=++n;
sort(m,m+n,compare);
longest=1;
for(i=0;i<n;i++) {
for(j=0;j<i;j++)
if(maxe[j]>=maxe[i]&&m[j].weight<m[i].weight&&m[j].iq>m[i].iq) {
maxe[i]=maxe[j]+1;
pre[i]=j;
}
if(maxe[i]>longest) {
longest=maxe[i];
end=i;
}
}
cout<<longest<<endl;
show(end);
return 0;
}
void show(int e) {
if(maxe[e]>1)
show(pre[e]);
cout<<m[e].number<<endl;
}

[jackie]

rakeb is right.
I use DP LDS algorithm O(n * lg(m)) and got AC in 0.004 sec after got a lot of WA.

you can sort the input first, then just for the second element in the array do the LDS DP , you get the answer.

BTW, you should remember the order of each input in order to output the sequence.