Page 1 of 1

Posted: Sat Nov 16, 2002 9:36 am
by 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. :evil:

323 - Jury compromise - WA

Posted: Mon Jun 16, 2003 11:34 pm
by 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]

Posted: Thu Feb 05, 2004 1:33 pm
by 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

Posted: Thu Feb 19, 2004 5:47 pm
by 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-

Posted: Thu Feb 19, 2004 7:07 pm
by horape
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

Posted: Wed Apr 07, 2004 11:01 am
by Red Scorpion
hello, everyone. :lol: :lol:

I kept getting WA, can someone provide more testcase. :cry:

Thanks

323 - Jury Compromise

Posted: Sat Apr 24, 2004 8:10 am
by 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

Posted: Wed Jun 16, 2004 8:58 pm
by 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


323 - Jury Compromise WA - Please, Help!

Posted: Fri Apr 07, 2006 7:01 pm
by 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;
}
 

NP=P???

Posted: Fri May 05, 2006 12:35 am
by rcrezende
Ol

Re: 323 - Jury Compromise

Posted: Wed Sep 19, 2018 11:02 am
by 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;
}