10131 - Is Bigger Smarter?

[algill7]

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 ?

Please help

[Darko]

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]

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]

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]

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]

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]

Hi,

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

[Darko]

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 {
				b = System.in.read();
			} 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]

Yh,I finally got it! ^_^

[tmdrbs6584]

#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]

Hi!

Sort both in descending order. And run your LIS.

Hope it helps.

[sectroyer]

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]

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]

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]

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;
    read(w);
    read(iq);

    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;
	read(w);
	read(iq);
       	n:=n+1;
    end;
  
    if (totales > 0) then begin
        quicksort(a,0,n-1);
	resolver();
    end;

end.

[/code]