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

algill7
New poster
Posts: 1
Joined: Fri Oct 28, 2005 11:48 am

10131 is bigger smarter ? WA

Hello ,

I am getting WA in 10131 all along. Here's my algo:

1. I sort the elephants by their IQ in decreasing order
2. Then I find the LIS of the weights of the sorted elepahnts and
that is my answer.

Is it correct ?

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Is there anything tricky in judge's input?

I tried both sorting by weight and getting LDS and sorting by IQ and getting LIS. Of course, I made sure those were all strictly increasing/decreasing and whatnot...

I tried different sorting algorithms and swapping when equal and not swapping... I really don't know what I am doing wrong. For the two inputs above, I get the same length of sequences, they are correct (although different from the above solutions).

I really have no idea what I could be doing wrong, can someone help with an insight?

Darko

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
Hi, Darko.
I solved this problem just now.
I took one year to understand what my code was wrong.

My method is here.

At first, sort by their IQ in decreasing order.
If there are same IQ and different weights,
then sort by their weights in decreasing order.

Second, LIS by their weight.
In this case, LIS try to find n maximum lengths.
Each of the i-th maximum lengths contains i-th elephant.
Refer here -> Method to solve http://www.comp.nus.edu.sg/~stevenha/pr ... _(LIS/LDS).
After this step, we can find the longest length of n maximum lengths by a single-loop. I call the longest length 'LL' for my explanation.

Finally, try to find the concrete order of elephants.
Make a single-loop (n to 1), and search each of the minimum weights of LL-th to 1-th longest length.
Although N to 1 loop can keep the sorted data consistency, 1 to N loop will failed.

Because of my English is poor, I'll explain by using sample input.
Initial data set :

Code: Select all

``````6008 1300
6000 2100
500 2000
1000 4000
1100 3000
6000 2000
8000 1400
6000 1200
2000 1900
``````
After sorting by IQ :

Code: Select all

``````1000 4000
1100 3000
6000 2100
6000 2000
500 2000
2000 1900
8000 1400
6008 1300
6000 1200
``````
Result of LIS : 1 2 3 3 1 3 4 4 4
(This result is same form as 'Methods to Solve')
Then we can know the longest length LL is 4.

Make a single-loop (N to 1) and search. This case N = 9.
i = 9, min_weight(4) = min(infinity, 6000) = 6000.
i = 8, min_weight(4) = min(6000, 6008) = 6000.
i = 7, min_weight(4) = min(6000, 8000) = 6000.
i = 6, min_weight(3) = min(infinity, 2000) = 2000.
i = 5, skip because the min_weight(2) is not found yet.
i = 4, min_weight(3) = min(2000, 6000) = 2000.
i = 3, min_weight(3) = min(2000, 6000) = 2000.
i = 2, min_weight(2) = min(infinity, 1100) = 1100.
i = 1, min_weight(1) = min(infinity, 1000) = 1000.

Then we can get the answer.
1000 4000
1100 3000
2000 1900
6000 1200

If you want to know why your code get WrongAnswer,
please check by using the second input which I posted previous.
Your code may be able to find the longest length '55', but how about the elephants order?
Perhaps, although IQs are sorted, weights are an inconsistent order.

Thank you.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Well, I keep track of the previous element of the sequence as I go along, and then I just print them.

Here's my output for that input:
55
625
234
150
222
490
215
362
126
221
110
563
736
746
381
262
115
519
552
712
10
14
431
684
359
282
573
170
212
50
631
566
376
213
433
375
465
79
616
293
124
76
485
145
612
750
205
683
732
103
470
578
516
639
559
382
These are the elephants (probably easier to look at):
55
171 9926
214 9899
278 9769
661 9759
697 9578
712 9245
947 9231
973 9007
1161 8704
1508 8538
1628 8492
1944 8339
2250 8314
2535 8205
2728 8129
2770 7848
2804 7798
2944 7463
3161 7375
3256 7347
3320 6294
3398 6291
3411 5552
3494 5509
3947 5457
4092 5392
4557 5380
4861 4748
5125 4711
5290 4639
5339 4470
5450 4164
5629 4112
5784 3649
5804 3584
5819 3451
5942 3203
5951 3168
6173 2815
6217 2757
6312 2533
6639 2502
6843 2227
6919 1919
7001 1866
7287 1759
7301 1636
7806 1451
8257 873
8294 821
8306 698
8784 586
8901 457
8989 322
9358 58
I am missing something and I have no idea what. And it has nothing to do with "normal" cases, I just can't see what those "abnormal" ones might be (I check for 0 and 1 elephant and print 0 for 0 and 1\n1 for 1 - is that ok?)

Darko

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
Darko wrote:I am missing something and I have no idea what. And it has nothing to do with "normal" cases, I just can't see what those "abnormal" ones might be (I check for 0 and 1 elephant and print 0 for 0 and 1\n1 for 1 - is that ok?)

Darko
My code also prints 0 for no elephants, and 1\n1 for 1 elephant.
And your output looks good.

Other check points are :
- the case of the existence of same weights or IQs.
- size of array

I can't guess any further now....

Code: Select all

``````1 1
1 2
1 9998
1 9999
1 10000
2 1
2 2
2 9998
2 9999
2 10000
9998 1
9998 2
9998 9998
9998 9999
9998 10000
9999 1
9999 2
9999 9998
9999 9999
9999 10000
10000 1
10000 2
10000 9998
10000 9999
10000 10000
1 1
2 1
9998 1
9999 1
10000 1
1 2
2 2
9998 2
9999 2
10000 2
1 9998
2 9998
9998 9998
9999 9998
10000 9998
1 9999
2 9999
9998 9999
9999 9999
10000 9999
1 10000
2 10000
9998 10000
9999 10000
10000 10000
``````
My output as sample :

Code: Select all

``````5
5
9
38
34
30

/////
1 10000
2 9999
9998 9998
9999 2
10000 1
``````
Best regards.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Thanks for your patience, tan_Yui.

I get the same elephants, difference is that they are the first ones in the list (5, 9, 13, 17, 21).

I will try what you originally suggested and look for the last ones (first from behind), but if that's the case... I don't know what to say.

Darko

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Hi,

I did the same thing.
How did you sort the elephants if they have the same IQ?

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
OK, I came back to this one, coded it from scratch - same result.

After a couple of hours of frustration, I coded exactly the same thing in C. And it got accepted. I still get "different" output for those samples (lengths are OK).

(EDIT: hm, just noticed I never did anything about 0 or 1 case in C code... so there is no such input)

I really have no idea what is wrong with this (if someone can take time to look through it, great):

Code: Select all

``````import java.io.IOException;
import java.util.StringTokenizer;

class Main {

void work() {
String line;
StringTokenizer st;
Elephant[] bunch = new Elephant[1010];
int n = 0;
while ((line = readLine()) != null) {
if(line.length()==0) continue;
st = new StringTokenizer(line);
bunch[n++] = new Elephant(n, parseInt(st
.nextToken()), parseInt(st.nextToken()));
}
// sort them first
for (int i = 0; i < n; i++) {
for (int j = n - 1; j > i; j--) {
if (bunch[j].compare(bunch[j-1]) < 0) {
Elephant tmp = bunch[j];
bunch[j] = bunch[j - 1];
bunch[j - 1] = tmp;
}
}
}
if (n == 0) {
System.out.println(0);
} else if (n == 1) {
System.out.println("1\n1");
} else {
int maxLen = 0;
int lastIndex = -1;
bunch[0].prev = -1;
bunch[0].lensofar = 1;
for (int i = 1; i < n; i++) {
int prevIndex = -1;
int max = 0;
for (int j = 0; j < i; j++) {
if (bunch[j].w < bunch[i].w && bunch[j].s > bunch[i].s) {
if (bunch[j].lensofar > max) {
max = bunch[j].lensofar;
prevIndex = j;
}
}
bunch[i].prev = prevIndex;
bunch[i].lensofar = max + 1;
if (bunch[i].lensofar > maxLen) {
maxLen = bunch[i].lensofar;
lastIndex = i;
}
}
}
System.out.print(maxLen);
StringBuffer res = new StringBuffer();
for (int i = 0; i < maxLen; i++) {
res.insert(0, bunch[lastIndex].num);
res.insert(0, '\n');
lastIndex = bunch[lastIndex].prev;
}
System.out.println(res);
}
}

private int parseInt(String s) {
// what if s.length() == 0 ?
int result = 0;
int sign = (s.charAt(0) == '-') ? -1 : 1;
if (sign == -1)
s = s.substring(1);
int i = 0, max = s.length();
if (max > 0) {
while (i < max) {
result *= 10;
result += s.charAt(i++) - 48;
}
}
return sign * result; // could be 0 if not an integer
}

private String readLine() {
StringBuffer sb = new StringBuffer("");
int b = 0;
while (b != '\n' && b >= 0) {
try {
} catch (IOException e) {
return null;
}
if (b != '\r' && b != '\n' && b >= 0)
sb.append((char) b);
}
if (sb.length() == 0 && b < 0)
return null;
return sb.toString().trim();
}

public static void main(String args[]) {
Main myWork = new Main();
myWork.work();
}
}

class Elephant {
int num, w, s, prev, lensofar;

Elephant(int num, int w, int s) {
this.num = num;
this.w = w;
this.s = s;
prev = -1;
lensofar = 1;
}

public int compare(Elephant e2){
if(w == e2.w){
return e2.s - s;
}
else{
return w - e2.w;
}
}

public String toString() {
return w + " " + s;
}
}``````
Darko

tekkie_c
New poster
Posts: 1
Joined: Wed Mar 29, 2006 2:11 pm

Yh,I finally got it! ^_^

tmdrbs6584
Learning poster
Posts: 98
Joined: Sat Jan 21, 2006 12:45 pm
Location: Busan,Corea(Republic of)

10131 Bigger Smarter WA :-(

#include<fstream.h>
#include<string.h>
int n,cnt;
int a[101],b[101],d[101],pos[101],path[101];
int e[101],f[101],idx1[101];
int main(){
int i,j;
while(cin >> n){
for(i=0;i<n;i++){
cin >> a >> b;
idx1=i;
}
for(i=0;i<n;i++){
int t;
for(j=0;j<i;j++){
if(b>=b[j]){
t=a;a=a[j];a[j]=t;
t=b;b=b[j];b[j]=t;
t=idx1;idx1=idx1[j];idx1[j]=t;
}
}
}
int max=0,idx;
for(i=0;i<n;i++)
pos[i]=-1;
for(i=0;i<n;i++){
d[i]=1;
for(j=0;j<i;j++){
if(a[i]>a[j] && d[i]<d[j]+1){
d[i]=d[j]+1;
pos[i]=j;
}
}
if(max<d[i]){
max=d[i];
idx=i;
}
}
int maxx=0;
path[cnt++]=idx;
while(pos[idx]!=-1){
path[cnt++]=pos[idx];
idx=pos[idx];
}
for(i=cnt-1;i>=0;i--){
e[cnt-1-i]=a[path[i]];
f[cnt-1-i]=b[path[i]];
idx1[cnt-1-i]=idx1[path[i]];
}
cout << max << endl;
for(i=cnt-1;i>=0;i--){
cout << idx1[path[i]]+1 << endl;
}
for(i=0;i<101;i++)
a[i]=b[i]=d[i]=e[i]=f[i]=idx1[i]=path[i]=0;
cnt=0;
}
return 0;
}
Why WA?
I sorted decreasing by IQ, And I used LIS with by weight

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
Hi!

Sort both in descending order. And run your LIS.

Hope it helps.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

sectroyer
New poster
Posts: 8
Joined: Mon Nov 28, 2005 4:55 pm

wa

Can anyone help me? I have no idea what is wrong with my code.
I am unable to find a tricky input
#include <stdio.h>

typedef struct {
int waga;
int iq;
int pos;
} tslo;
int cmp(void *a1, void *a2)
{
tslo *a,*b;
a=(tslo*)a1;
b=(tslo*)a2;
if(a->waga==b->waga)
{
return a->iq-b->iq;
}
else
{
return a->waga-b->waga;
}
}
int main(int argc, char *argv[])
{
tslo slo[2000];
int wyn[200000];
int pos[200000];
int i1,i2,wg,iq,ile,tmp,tmp2;
for(i1=0;scanf("%d",&wg)==1;i1++)
{
scanf("%d",&iq);
slo[i1].waga=wg;
slo[i1].iq=iq;
slo[i1].pos=i1+1;
}
ile=i1;
qsort(slo,ile,sizeof(tslo),cmp);
for(i1=0;i1<200000;i1++)
{
wyn[i1]=0;
}
for(i1=0;i1<ile;i1++)
{
/*
printf("%d %d %d\n",slo[i1].pos,slo[i1].waga,slo[i1].iq);
*/
tmp=wyn[slo[i1].iq+1]+1;
tmp2=slo[i1].pos;
for(i2=slo[i1].iq;i2>0;i2--)
{
if(tmp >= wyn[i2])
{
wyn[i2]=tmp;
pos[i2]=tmp2;
}
}
}
printf("%d\n",wyn[1]);
tmp=0;
for(i1=200000;i1>0;i1--)
{
if(tmp!=pos[i1])
{
printf("%d\n",pos[i1]);
tmp=pos[i1];
}
}
return 0;
}

sectroyer
New poster
Posts: 8
Joined: Mon Nov 28, 2005 4:55 pm

wa

Can anyone help me?
I have no idea what is wrong with my code.
Moreover I am unable to find any tricky input
#include <stdio.h>

typedef struct {
int waga;
int iq;
int pos;
} tslo;
int cmp(void *a1, void *a2)
{
tslo *a,*b;
a=(tslo*)a1;
b=(tslo*)a2;
if(a->waga==b->waga)
{
return a->iq-b->iq;
}
else
{
return a->waga-b->waga;
}
}
int main(int argc, char *argv[])
{
tslo slo[2000];
int wyn[200000];
int pos[200000];
int i1,i2,wg,iq,ile,tmp,tmp2;
for(i1=0;scanf("%d",&wg)==1;i1++)
{
scanf("%d",&iq);
slo[i1].waga=wg;
slo[i1].iq=iq;
slo[i1].pos=i1+1;
}
ile=i1;
qsort(slo,ile,sizeof(tslo),cmp);
for(i1=0;i1<200000;i1++)
{
wyn[i1]=0;
}
for(i1=0;i1<ile;i1++)
{
/*
printf("%d %d %d\n",slo[i1].pos,slo[i1].waga,slo[i1].iq);
*/
tmp=wyn[slo[i1].iq+1]+1;
tmp2=slo[i1].pos;
for(i2=slo[i1].iq;i2>0;i2--)
{
if(tmp >= wyn[i2])
{
wyn[i2]=tmp;
pos[i2]=tmp2;
}
}
}
printf("%d\n",wyn[1]);
tmp=0;
for(i1=200000;i1>0;i1--)
{
if(tmp!=pos[i1])
{
printf("%d\n",pos[i1]);
tmp=pos[i1];
}
}
return 0;
}

Gaizka
New poster
Posts: 7
Joined: Wed May 24, 2006 12:37 am
Well, but the judges input doesn't have the cases where the weights are equal, because a sent an algorithm that doesn`t checked it and output without the strict inequalities and got accepted.

jabenitez
New poster
Posts: 1
Joined: Mon Mar 03, 2008 1:30 am

10131 - Wrong answer

Hello, I have a problem and I am desperate I have twelve days with this problem..

Code: Select all

``````Program elefantes(input,output);
Const numEle = 999;

Type
tElefante = record
w: integer;
iq: integer;
num: integer;
end;
tElefantes = array [0..numEle] of tElefante;

Var
a: tElefantes;
prev,opt,opt_i: array [0..numEle+1] of integer;
n,m,totales,w,iq : integer;
f: array [0..numEle] of integer;

Function buscar(w:integer):integer;
Var l,r,k:integer;
Begin
l := 1;
r := m;
while (l <= r) do
begin
k := (l+r) div 2;
if (w > opt[k]) then l := k+1
else r := k-1;
end;
buscar := l;
End;

Procedure resolver();
Var  wk,j,i :integer;
Begin
m := 1;
opt[1] := a[0].w;
opt_i[1] := 0;
for i := 1 to totales-1 do
Begin
wk := a[i].w;
j := buscar(wk);
if (m < j) then
begin
m := m + 1;
opt[m] := wk;
opt_i[m] := i;
prev[i] := opt_i[m-1];
end
else begin
if (wk < opt[j]) then begin
opt[j] := wk;
opt_i[j] := i;
prev[i] := opt_i[j-1];
end;
end;
end;

j := m-1;
i := opt_i[m];
while (j >= 0) do begin
f[j] := i;
i := prev[i];
j := j - 1;
end;

writeln(m);
for i:=0 to m-1 do writeln (a[f[i]].num);

end;

Procedure quicksort(var a:tElefantes;iz,de:integer);
var i,j,x:integer;
aux:tElefante;
porpeso:boolean;
begin
porpeso := TRUE;

i:=iz;
j:=de;

if (a[i].iq = a[j].iq) then porpeso := FALSE;

if porpeso then
begin
x:=a[(iz+de)div 2].iq;
repeat
while (a[i].iq > x) and (i<de) do i:=i+1;
while (a[j].iq < x) and (j>iz) do j:=j-1;
if i<=j then
begin
aux := a[i];
a[i] := a[j];
a[j] := aux;
i:=i+1;
j:=j-1;
end;
until i>j;
if iz<j then quicksort(a,iz,j);
if i < de then quicksort(a,i,de);
end

else begin
x:=a[(iz+de)div 2].w;
repeat
while (a[i].w < x) and (i<de) do i:=i+1;
while (a[j].w > x) and (j>iz) do j:=j-1;
if i<=j then
begin
aux := a[i];
a[i] := a[j];
a[j] := aux;
i:=i+1;
j:=j-1;
end;
until i>j;
if iz< j then quicksort(a,iz,j);
if i < de then quicksort(a,i,de);
end;

end;

begin
n:=0;  totales := 0;w:= 0; iq := 0;

while (n<1000) do
begin
if (w<>0) or (iq<>0) then
begin
a[totales].iq := iq;
a[totales].w := w;
a[totales].num := n+1;
totales := totales + 1;
end;