10131 - Is Bigger Smarter?

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
jiayaoyu
New poster
Posts: 5
Joined: Fri Jun 14, 2002 1:10 am
Location: Lancaster.UK

10131 - Is Bigger Smarter?

Post by jiayaoyu » Sun Jan 19, 2003 1:40 pm

[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<w[j]&&s>s[j])
{
if(lens+1>lens[j])
{
pre[j] = i;
lens[j] = lens+1;
if(lens[j]>max)
{
max = lens[j];
last = j;
}
}
}
}
printf("%d\n",max);
output(last);

return 0;
}
[/c]


Thanks!

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

10131- is bigger smarter? WA

Post by titid_gede » Sat Mar 22, 2003 7:24 am

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

[/c]

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Sun Mar 30, 2003 10:41 am

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

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Mon Mar 31, 2003 6:33 am

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....

----
:oops: :oops: :oops: :oops: :oops:
"Everything should be made simple, but not always simpler"

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Wed Apr 02, 2003 2:58 pm

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

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Thu Apr 03, 2003 4:50 am

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-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Thu Apr 03, 2003 7:53 am

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

fhysics
New poster
Posts: 3
Joined: Sun Apr 13, 2003 5:36 am

10131, WA, plz help this newbie.

Post by fhysics » Sun Apr 13, 2003 5:48 am

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==j)
{ children[numChildren]=i;
numChildren++;
}
}

for (i=0; i<numChildren; i++)
{ len[children]+=diff;
if (len[children]>maxLen)
{ maxLen = len[children];
maxPos = children;
}
update(children, 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=-1;
len=1;
}


for (i=0; i<count; i++)
for (j=0; j<count; j++)
if (weight<weight[j] && iq>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
New poster
Posts: 3
Joined: Sun Apr 13, 2003 5:36 am

did u get it accept after the change?

Post by fhysics » Sun Apr 13, 2003 5:52 am

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

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Mon Apr 14, 2003 11:39 am

Whats your output for your sample input?

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

User avatar
rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France

Post by rakeb » Mon Apr 14, 2003 12:01 pm

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 :)
Rakeb

fhysics
New poster
Posts: 3
Joined: Sun Apr 13, 2003 5:36 am

@_@

Post by fhysics » Sat Apr 19, 2003 6:44 am

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

rlatif119
New poster
Posts: 16
Joined: Mon Mar 01, 2004 4:00 pm
Location: Dhaka

10131.....WA

Post by rlatif119 » Fri May 07, 2004 5:28 pm

The same old problem.......WA :roll:
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.w);
if(feof(stdin))
break;
scanf("%d",&ele.s);
length = 1;
ele.c=i+1;
predecessor = -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.w)
{
if (length + 1 > length[j])
{
length[j] = length + 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.s > x.s);

if(i<j)
{
temp = ele;
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]

User avatar
Yu Fan
New poster
Posts: 26
Joined: Thu Nov 13, 2003 3:52 am

10131 WA

Post by Yu Fan » Thu Jun 03, 2004 10:38 am

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&&m[j].weight<m.weight&&m[j].iq>m.iq) {
maxe=maxe[j]+1;
pre=j;
}
if(maxe>longest) {
longest=maxe;
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
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am

DP LIS

Post by jackie » Wed Jul 21, 2004 9:44 am

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.

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest