323 - Jury Compromise

[Andrey Mokhov]

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]

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
readln(n,m);
if not ((n=0) and (m=0)) then begin
if il>=1 then writeln;
for i:=1 to n do begin
readln(tab[i].d,tab[i].p);
tab[i].ind:=i;
end;
inc(il); readln;
zeruj;
qsort(1,n);
doit;
writeit;
end;
end;
end.[/pascal]

[horape]

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]

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-

[horape]

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]

hello, everyone.

I kept getting WA, can someone provide more testcase.

Thanks

[b3yours3lf]

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?

thanks in advance

[jagadish]

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

[ErickNascimento]

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]

Ol

[metaphysis]

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;
}