## 323 - Jury Compromise

Moderator: Board moderators

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan
I guess its due to algorithm.

Perhaps its not necessary to run all the loops. There may be some ranges to look for the optimum within.

BTW are you going to take part in Sunday's contest or not?
I wrote you several messages, but you keep silence.

craniac
New poster
Posts: 2
Joined: Mon Jun 16, 2003 11:25 pm
Location: Poland

### 323 - Jury compromise - WA

I can't see any mistake in this code - it's dynamic programming. Could you please help me with some test cases?
[pascal]program p323;

type rec=record d,p,ind:byte; end;

var t:array[1..201,-201..201,0..20] of record w:byte; s:integer; end;
x,n,m,j,i,il,sp,sd,l,k,p:integer;
ci,cj:boolean;
tab:array[1..201] of rec;
wyn:array[1..21] of byte;

procedure zeruj;
begin
for i:=1 to n do
for j:=-200 to 200 do
for k:=0 to m do begin t[i,j,k].w:=0; t[i,j,k].s:=0; end;
end;

procedure qsort(l,r:byte);
var a,b,x:byte; y:rec;
begin
a:=l; b:=r; x:=tab[(a+b) div 2].p+tab[(a+b) div 2].d;
repeat
while tab[a].p+tab[a].d>x do inc(a);
while tab.p+tab.d<x do dec(b);
if a<=b then begin
y:=tab[a]; tab[a]:=tab; tab:=y;
inc(a); dec(b);
end;
until a>b;
if a<r then qsort(a,r);
if l<b then qsort(l,b);
end;

procedure qsort1(l,r:integer);
var a,b,x,y:integer;
begin
a:=l; b:=r; x:=wyn[(a+b) div 2];
repeat
while wyn[a]<x do inc(a);
while wyn>x do dec(b);
if a<=b then begin
y:=wyn[a]; wyn[a]:=wyn; wyn:=y;
inc(a); dec(b);
end;
until a>b;
if a<r then qsort1(a,r);
if l<b then qsort1(l,b);
end;

procedure doit;
begin
t[1,tab[1].p-tab[1].d,1].w:=1;
t[1,tab[1].p-tab[1].d,1].s:=tab[1].p+tab[1].d;
if n>1 then for i:=2 to n do begin
x:=tab.p-tab.d;
t[i,x,1].w:=1;
t[i,x,1].s:=tab.p+tab.d;
for j:=-200 to 200 do begin
for k:=1 to m do if t[i-1,j,k].w>0 then begin t[i,j,k].w:=2;
t[i,j,k].s:=t[i-1,j,k].s;
end;
for k:=1 to m-1 do
if (t[i-1,j,k].w>0) and (t[i-1,j,k].s+tab.p+tab.d>=t[i,j+x,k+1].s)
then begin t[i,j+x,k+1].w:=1; t[i,j+x,k+1].s:=t[i-1,j,k].s+tab.p+tab.d;
end;
end;
end;
end;

procedure writeit;
var w1,w2:integer;
begin
i:=0; j:=0;
while (t[n,i,m].w=0) and (t[n,j,m].w=0) do begin
inc(i); dec(j);
end;
if t[n,j,m].w=0 then cj:=FALSE else cj:=TRUE;
if t[n,i,m].w=0 then ci:=FALSE else ci:=TRUE;
if ci then w1:=t[n,i,m].s else w1:=0;
if cj then w2:=t[n,j,m].s else w2:=0;
if w2>w1 then i:=j;
l:=m; p:=i; sp:=0; sd:=0; x:=1;
for i:=n downto 1 do
if t[i,p,l].w=1 then begin
dec(l);
p:=p-tab.p+tab.d;
sp:=sp+tab[i].p; sd:=sd+tab[i].d;
wyn[x]:=tab[i].ind;
inc(x);
end;
writeln('Jury #',il);
writeln('Best jury has value ',sd,' for prosecution and value ',sp,' for defence:');
qsort1(1,m);
for i:=1 to m do write(' ',wyn[i]);
writeln;
end;

begin
n:=1; il:=0;
while not ((n=0) and (m=0)) do begin
if not ((n=0) and (m=0)) then begin
if il>=1 then writeln;
for i:=1 to n do begin
tab[i].ind:=i;
end;
zeruj;
qsort(1,n);
doit;
writeit;
end;
end;
end.[/pascal]
I want to know God's thoughts
The rest are details

horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires
Didn't read your code, but check that the blank lines are as specified (between cases, no blank line at the end of the output) 323's special corrector doesn't handle PE correctly.

Saludos,
HoraPe

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
can you provide me outputs for this following inputs :

Code: Select all

``````2 1
14 4
16 2

24 20
11 15
8 5
11 10
17 5
17 2
9 17
3 16
2 3
16 4
13 2
6 1
7 20
15 13
12 1
13 8
8 10
17 15
7 7
18 3
10 17
14 5
3 1
19 7
7 19

8 3
1 8
18 1
10 14
1 5
2 6
10 19
1 1
7 8

26 20
16 1
20 20
2 5
16 9
11 14
7 14
4 14
6 9
20 6
12 11
5 9
8 5
16 12
3 18
6 2
4 14
17 14
2 4
15 2
1 3
12 14
16 18
17 14
7 3
2 16
20 19

14 9
10 12
9 4
10 18
16 19
18 19
6 13
15 14
12 6
5 11
6 7
13 20
3 17
18 19
2 15

0 0
``````
thanks

-titid-
Kalo mau kaya, buat apa sekolah?

horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires
titid_gede wrote:can you provide me outputs for this following inputs :

...

thanks

-titid-

Code: Select all

``````Jury #1
Best jury has value 14 for prosecution and value 4 for defence:
1

Jury #2
Best jury has value 195 for prosecution and value 192 for defence:
1 2 3 6 7 8 10 11 12 13 14 15 16 17 18 20 21 22 23 24

Jury #3
Best jury has value 29 for prosecution and value 28 for defence:
1 2 6

Jury #4
Best jury has value 237 for prosecution and value 237 for defence:
1 2 4 5 6 7 9 10 13 14 16 17 18 19 21 22 23 24 25 26

Jury #5
Best jury has value 109 for prosecution and value 111 for defence:
1 2 4 5 7 8 9 10 13

horape@elanor:~/acm\$ tail 323.out
1 2 6

Jury #4
Best jury has value 237 for prosecution and value 237 for defence:
1 2 4 5 6 7 9 10 13 14 16 17 18 19 21 22 23 24 25 26

Jury #5
Best jury has value 109 for prosecution and value 111 for defence:
1 2 4 5 7 8 9 10 13
``````
Saludos,
HoraPe

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

I kept getting WA, can someone provide more testcase.

Thanks

b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

### 323 - Jury Compromise

I tried to solve this problem but i can't find good dp solution, the only way i found is use 200*200 size array, but i think that's not the optimal way. it there better way to solve this problem?

Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA
8 4
19 18
5 9
0 9
5 0
4 4
16 9
4 15
20 5

10 5
3 8
15 8
11 8
7 8
1 8
17 8
8 8
2 8
13 8
3 8

18 7
1 1
1 2
2 1
10 10
11 10
10 11
7 7
7 8
8 7
14 14
14 15
15 14
4 4
4 5
5 4
19 19
19 20
20 19

if u can think of it .. u can do it in software.

ErickNascimento
New poster
Posts: 6
Joined: Fri Dec 16, 2005 11:40 pm

### 323 - Jury Compromise WA - Please, Help!

I am getting WA, but don't know why. My code works for the sample input.
Someone please give me inputs and outputs for this problem.
Thank you.

Code: Select all

``````
#include <stdio.h>

#define MOD(a) ((a)>=0?(a):(-(a)))

#define MAXN 200+10
#define MAXM 20+10
#define INFINITO 99999999

#define UP 1
#define UP_LEFT 2

int nCases;

int n, m;
int d[MAXN], p[MAXN];
int D, P;
int diff[MAXN], sum[MAXN];

int C[MAXN+1][MAXM+1]; /* C[i][j] == (D(T)-P(T)) tal que |D(T)-P(T)| == minimal p/
S={1,..,i} e |T|=j */
int M[MAXN+1][MAXM+1]; /* M[i][j] == D(T)+P(T) == maximo p/ S={1,...i} |T|=j */
int E[MAXN+1][MAXM+1]; /* indica qual foi a escolha feita na posicao i, j (UP, ou
UP_LEFT)*/

int itens[MAXM];
int nItens;

/* Determina quais os itens que foram escolhidos */
void getItens(int i, int j){
if(i==0 || j==0) { return; }
if(E[i][j] == UP)
getItens(i-1, j);
else{ /*E[i][j] == UP_LEFT*/
getItens(i-1, j-1);
itens[nItens++] = i-1;
}
}

void knapsack(){
int i, j;

for (i=0; i<n; i++){
diff[i] = d[i] - p[i];
sum[i] = d[i] + p[i];
}

/* Caso Base */
for (j=0; j<=m; j++)
C[0][j] = INFINITO;
for (i=0; i<=n ;i++)
C[i][0] = 0;

for (j=0; j<=m; j++)
M[0][j]=0;
for (i=0; i<=n; i++)
M[i][0]=0;

for (i=1; i<=n; i++) {
for (j=1; j<=m; j++) {
if(MOD(C[i-1][j]) == MOD(C[i-1][j-1]+diff[i-1]) ){
/* Faz a escolha mais vantajosa */
if(M[i-1][j] > M[i-1][j-1]+sum[i-1]){
C[i][j] = C[i-1][j];
M[i][j] = M[i-1][j];
E[i][j] = UP;
}else{
C[i][j] = C[i-1][j-1] + diff[i-1];
M[i][j] = M[i-1][j-1] + sum[i-1];
E[i][j] = UP_LEFT;
}
}else{
if ( MOD(C[i-1][j]) < MOD(C[i-1][j-1]+diff[i-1]) ){
C[i][j] = C[i-1][j];
M[i][j] = M[i-1][j];
E[i][j] = UP;
}else{
C[i][j] = C[i-1][j-1] + diff[i-1];
M[i][j] = M[i-1][j-1] + sum[i-1];
E[i][j] = UP_LEFT;
}

}

}
}

getItens(n, m);
}

int main(){
int i;

nCases=1;
while(1){

scanf("%d %d", &n, &m);
if(n==0 && m==0)
break;
else
if(nCases>1)
printf("\n");

for (i=0; i<n; i++)
scanf("%d %d", &p[i], &d[i]);

printf("Jury #%d\n", nCases++);

nItens=0;
knapsack();

D=0; P=0;
for (i=0; i<m; i++){
D += d[itens[i]];
P += p[itens[i]];
}
printf("Best jury has value %d for prosecution and value %d for defence:\n", P, D);
for (i=0; i<m; i++)
printf(" %d", itens[i]+1);
printf("\n");
}

return 0;
}
``````

rcrezende
New poster
Posts: 7
Joined: Mon Nov 28, 2005 4:53 am

### NP=P???

Ol

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

### Re: 323 - Jury Compromise

Test data generator.

Code: Select all

``````#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[])
{
srand(time(NULL));
for (int cases = 1; cases <= 100; cases++)
{
int n = rand() % 100 + 1;
int m = min(rand() % n + 1, 20);
cout << n << ' ' << m << '\n';
for (int i = 1; i <= n; i++)
{
cout << rand() % 21;
cout << ' ';
cout << rand() % 21;
cout << '\n';
}
cout << '\n';
}
cout << "0 0\n";
return 0;
}
``````