## 431 - Trial of the Millennium

Moderator: Board moderators

tokei
New poster
Posts: 5
Joined: Tue Aug 20, 2002 7:27 am

### 431 - Trial of the Millennium

Hmmm ....

I was wondering how to solve this problem.

First, I try to solve this problem like a 0/1 knapsack problem.

However, after I found the maximum points and the optimal number of evidence presentations within the time constraint, I had another problem which is how to find the sequence of the evidence presentations.

For example, I got maximum points: 62 and 14 tasks(evidence presentations) for the sample Input.

Then, I tried to use DFS to find the sequence.
However, this is too slow.....

My program cannot finish in 10 seconds....

Can anyone help me on this problem?

Thanks in advance. nealzane
New poster
Posts: 23
Joined: Tue Dec 10, 2002 2:13 am
Location: China
Contact:
this code is wrong answer but i can't see where the defect is.

can anybody help?

thanks

[cpp]/* CODE DELETED */[/cpp]
Last edited by nealzane on Sat Aug 30, 2003 2:26 pm, edited 1 time in total. LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
Hello Neal,
I just got AC and generated an input file to compare my answer with yours.
The following is one of the case that differs:

Code: Select all

``````1

2
4 1 M
9 4 Y
7 1 E
2 2 B
6 4 W
9 1 N
6 3 F
``````
If you need more random generated i/o, write pm to me.
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
What is the answer to this test case? Is it

Code: Select all

``````Score  Time  Description
-----  ----  -----------
7      1   E
9      1   N

Total score: 16 points
Total time: 2 hours
``````
or should it be

Code: Select all

``````  9      1   N
7      1   E
``````
Does it matter?
If only I had as much free time as I did in college...
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
I don't know what's wrong with my code. :-(
Does the order of items in the output matter?
Does the order of selecting the items during the DP matter?
If there are 0 items in the ouput, should the footer with the total value and total time appear?
I think I deal correctly with the case of 0 items.

Code: Select all

``````code fixed.
``````
Last edited by Abednego on Tue Jun 28, 2005 8:40 am, edited 1 time in total.
If only I had as much free time as I did in college...
mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Hi, Igor. I see you haven't still solved the problem.

My AC program sorts the output table, in this order: on time (in ascending order), on score (descending), on description (ascending). I don't know if it's necessary, I just followed the sample output. Also, during DP I minimize the total time.

Your program gave wrong output for this input:

Code: Select all

``````1

10
10 1 A
20 4 B
10 7 C``````
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
Thanks! Your example found my bug. I need to practice DP more...
If only I had as much free time as I did in college...
niangjun
New poster
Posts: 3
Joined: Mon Dec 18, 2006 11:40 am

### 431 WA

I keep getting WA for 431, here is my code

Code: Select all

``````program acm_431;
var score,time:array[1..100] of integer;
des:array[1..100] of string;
c,m,t,sum,i,n:integer;
f:array[0..100,0..240] of integer;
take:array[1..300,1..300] of integer;
mem:array[1..300,1..300] of integer;
ev:array[1..100] of integer;

procedure init;
var i,j,k:integer;  s,s1,s2,s3:string;
begin
k:=0;
repeat
i:=1;
while (i<=length(s)) and (s[i]=' ') do i:=i+1;
j:=length(s);
while (j>0) and (s[j]=' ') do j:=j-1;
s:=copy(s,i,j-i+1);
if (s<>'') then begin
k:=k+1;
i:=pos(' ',s);
s1:=copy(s,1,i-1);
while (i<=length(s)) and (s[i]=' ') do i:=i+1;
s:=copy(s,i,length(s)-i+1);
i:=pos(' ',s);
s2:=copy(s,1,i-1);
while (i<=length(s)) and (s[i]=' ') do i:=i+1;
s:=copy(s,i,length(s)-i+1);
des[k]:=s;
val(s1,score[k],j);
val(s2,time[k],j);
end;
until (s='');
m:=k;
end;

procedure calc;
var i,j,k,l:integer;    p1,p2,m1,m2:integer;
begin
fillchar(f,sizeof(f),0);
fillchar(take,sizeof(take),0);
fillchar(mem,sizeof(mem),0);
for i:=1 to m do
for j:=1 to t do
if (time[i]>j) then begin f[i,j]:=f[i-1,j]; take[i,j]:=0; mem[i,j]:=1; end
else if (f[i-1,j]>=f[i-1,j-time[i]]+score[i])
then begin
f[i,j]:=f[i-1,j];
take[i,j]:=0;
mem[i,j]:=1;
end
else begin
f[i,j]:=f[i-1,j-time[i]]+score[i];
take[i,j]:=1;
mem[i,j]:=2;
end;
sum:=f[m,t];
end;

procedure backtrack;
var i,j,k,l:integer;
begin
fillchar(ev,sizeof(ev),0);
i:=m;
j:=t;
k:=0;
while (mem[i,j]<>0) do
begin
if (take[i,j]=1) then begin k:=k+1; ev[k]:=i; end;
if (mem[i,j]=1) then i:=i-1
else begin j:=j-time[i]; i:=i-1; end;
end;
n:=k;
end;

procedure sort;
var i,j,k,l:integer;
begin
for i:=2 to n do
begin
j:=1;
l:=ev[i];
while (j<i) and
((time[ev[j]]<time[ev[i]]) or (time[ev[j]]=time[ev[i]]) and (score[ev[j]]>score[ev[i]]))
or ((time[ev[j]]=time[ev[i]]) and (score[ev[j]]=score[ev[i]]) and (des[ev[j]]<des[ev[i]])) do j:=j+1;
if (j<i) then begin
for k:=i downto j+1 do ev[k]:=ev[k-1];
ev[j]:=l;
end;
end;
end;

procedure output;
var i,j,k:integer; tt:integer;
begin
tt:=0;
writeln('Score  Time  Description');
writeln('-----  ----  -----------');
for i:=1 to n do
begin
if (13+length(des[ev[i]])=80) then
write(score[ev[i]]:3,time[ev[i]]:7,'   ',des[ev[i]])
else writeln(score[ev[i]]:3,time[ev[i]]:7,'   ',des[ev[i]]);
tt:=tt+time[ev[i]];
end;
writeln;
writeln('Total score: ',sum,' points');
writeln(' Total time: ',tt,' hours');
end;

begin
for i:=1 to c do
begin
init;
calc;
backtrack;
sort;
if (f[m,t]=0) then
writeln('There is not enough time to present any evidence. Drop the charges.')
else output;
end;
end.
``````
any one can tell me where I get it wrong or give me some test cases that expose my error?
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
First search your problem in the forum. And if you find a thread use it. Otherwise open a new one. Check the link below.
http://online-judge.uva.es/board/viewto ... hlight=431
Ami ekhono shopno dekhi...
HomePage
Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan
mf wrote:

Code: Select all

``````1

10
10 1 A
20 4 B
10 7 C``````
This is my code give for that input.

Code: Select all

``````Score  Time  Description
-----  ----  -----------
10      1   A
20      4   B

Total score: 30 points
Total time: 5 hours``````
Is it right?
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Yes, it's correct.
Ami ekhono shopno dekhi...
HomePage
vijay_comc
New poster
Posts: 3
Joined: Sat Nov 03, 2007 6:01 pm

### Re: 431 - Trial of the Millennium

Code: Select all

``````#include<iostream>
#include<string>
#include<vector>
#include<sstream>
using namespace std;
#define GI ({int t;scanf("%d",&t);t;})
#define sz size()
#define pb push_back

typedef vector<int> vi;
typedef vector<string> vs;
int dp;
int path;
int main()
{
int t =GI;
string str;
while(t-->0)
{
int lim = GI;
memset(dp,0,sizeof(dp));
memset(path,0,sizeof(path));
getchar();
vi time, score;
vs desc;
int n = 0;
while(true) {
getline(cin,str);
if(str.sz == 0) break;
stringstream in(str);
int score_, time_;
string desc_;
in >> score_ >> time_;
getline(in,desc_);
//			cout << score_ << " " << time_ << " " << desc_ << endl;
score.pb(0), time.pb(0), desc.pb(string());
int i;
for(i = n-1; i >= 0 && time[i] > time_; i--)
{
time[i+1] = time[i], score[i+1] = score[i], desc[i+1] = desc[i];
}
time[i+1] = time_, score[i+1] = score_, desc[i+1] = desc_;
n++;
}

for (int i = n; i --> 0; )
{
if(i == n-1) {
if(time[i] <= lim) dp[i][time[i]] = score[i], path[i][time[i]] = 1;
dp[i] = 0;
path[i] = 0;
}
else
for (int s = lim; s >= time[i]; s--)
{
dp[i][s] = dp[i+1][s];
if(dp[i][s] < score[i] + dp[i+1][s-time[i]]) {
dp[i][s] = score[i] + dp[i+1][s-time[i]];
path[i][s] = 1;
}
}
}
int mm = 0, maxs = -1;
for( int s = lim; s >= 0; s--)
{
if( dp[s] >= mm ) mm = dp[s], maxs = s;
}
if(mm == 0) printf("There is not enough time to present any evidence. Drop the charges.\n");
else {
printf("Score  Time  Description\n");
printf("-----  ----  -----------\n");
for(int i = 0, s = maxs; i < n; i++)
{
if(path[i][s]) {
s -= time[i];
printf("%3d%7d   %s\n",score[i],time[i],desc[i].c_str());
}
}
printf("\n");
printf("Total score: %d points\n",mm);
printf(" Total time: %d hours\n",maxs);
}
if(t)
printf("\n");
}
return 0;
}
``````
Guys, I am Getting PE for this...
Any Help will be Appreciated...
cheers,
vijay
red_apricot
New poster
Posts: 48
Joined: Sun Jun 22, 2014 6:14 am

### Re: 431 - Trial of the Millennium

I'm getting WA for this:

Code: Select all

``````/*
* 431. Trial of the Millenium
* TOPIC: dp
* status:
*/
#include <assert.h>
#include <ctype.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 0x80
#define MAXT BIT(9)
#define FG (ptr = fgets(buff,sizeof buff,stdin))
#define oo 0xfffffffful
#define S 8
#define BIT(k) (1UL<<(k))
#define enc(x,y) ((x)|((y)<<S))

int empty( char *ptr ) {
for (;*ptr && *ptr != '\n' && isspace(*ptr); ++ptr );
return !*ptr || *ptr == '\n';
}

int m,T,n,score[N],tm[N],TT,idx[N];
char buff[0x400],*ptr,
desc[N][0x400];
unsigned int z[N][MAXT],way[N][MAXT];

int cmp( const void *a, const void *b ) {
int *x = (int *)a,
*y = (int *)b;
if ( tm[*x] == tm[*y] ) {
if ( score[*x] == score[*y] ) {
return strcmp(desc[*x],desc[*y]);
}
return score[*x]>score[*y]?-1:1;
}
return tm[*x]<tm[*y]?-1:1;
}

void dump( int k, int t ) {
int pk,pt;
if ( t == 0 || k == 0 ) return ;
pk = (way[k][t]&MASK(S)), pt = (way[k][t]>>S);
if ( pt != t ) {
/*printf("%3d %6d   %s\n",score[k],tm[k],desc[k]);*/
idx[m++] = k;
}
dump(pk,pt);
}

unsigned int max ( unsigned int x, unsigned int y ) { return x<y?y:x; }

unsigned int calc_z( int k, int t ) {
if ( z[k][t] < +oo ) return z[k][t];
if ( k == 0 || t == 0 ) return z[k][t] = 0;
assert( t >= 1 );
assert( k >= 1 );
z[k][t] = calc_z(k-1,t), way[k][t] = enc(k-1,t);
if ( tm[k] <= t && calc_z(k-1,t-tm[k]) < +oo ) {
if ( z[k][t] < z[k-1][t-tm[k]]+score[k] )
z[k][t] = z[k-1][t-tm[k]]+score[k], way[k][t] = enc(k-1,t-tm[k]);
}
return z[k][t];
}

typedef struct {
int score,t;
char d[0x80];
} cell;

int cm( const void *a, const void *b ) {
cell *x = (cell *)a,
*y = (cell *)b;
if ( x->t == y->t ) {
if ( x->score == y->score ) {
return strcmp(x->d,y->d);
}
return x->score>y->score?-1:1;
}
return x->t<y->t?-1:1;
}

cell c[N];

int main() {
int i,j,k,l,cs = 0,ts;
unsigned int w;
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
#endif
for ( sscanf(FG,"%d",&ts), FG; ts--; ) {
for ( k = (1<<29), sscanf(FG,"%d",&T), n=0; FG && !empty(ptr); ++n ) {
assert( 3 == sscanf(ptr,"%d %d %[^\n]",score+n+1,tm+n+1,desc[n+1]) );
if ( tm[n+1] < k ) k = tm[n+1];
c[n+1].score = score[n+1], c[n+1].t = tm[n+1], strcpy(c[n+1].d,desc[n+1]);
}
/*
qsort(c+1,n,sizeof *c,cm);
for ( i = 1; i <= n; ++i )
tm[i] = c[i].t, score[i] = c[i].score, strcpy(desc[i],c[i].d);
*/
for ( i = 0; i <= n; ++i )
for ( j = 0; j <= T; z[i][j++] = +oo );
w = calc_z(n,T);
if ( w == 0 ) {
puts("There is not enough time to present any evidence. Drop the charges.");
if ( ts ) putchar('\n');
continue ;
}
/*
for ( w = 0, j = 0; j <= T; ++j )
for ( i = 0; i <= n; ++i )
if ( calc_z(i,j) < +oo && calc_z(i,j) > w )
k = i, l = j, w = calc_z(i,j);
*/
puts("Score  Time  Description");
puts("-----  ----  -----------");
for ( TT = 0; TT <= T && calc_z(n,TT) != w; ++TT );
assert( calc_z(n,TT) == w );
m = 0, dump(n,TT), qsort(idx,m,sizeof *idx,cmp);
for ( i = 0; i < m; ++i )
printf("%3d%7d   %s\n",score[idx[i]],tm[idx[i]],desc[idx[i]]);
printf("\nTotal score: %u points\n",w);
printf(" Total time: %d hours\n",TT);
if ( ts ) putchar('\n');
}
return 0;
}
``````
Any help is appreciated.
metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

### Re: 431 - Trial of the Millennium

After tons of submit, I always got WA, so I turn to UVa BBS for help.
It is a classical 0-1 knapsack problem. I have considered various boundary test cases:
(1)the total allowed time equal to 0;
(2)evidences with time 0;
(3)evidences with same score and time, I choose the item which description ascii smaller;
(4)the description with additional space before the first character or after the last character(I kept it);
(5)I sorted the output first by time, and then by score, last by description ascii ascending.
Is the special judge has some bugs?
Below is my solution:

Code: Select all

``````// Trial of the Millennium
// UVa ID: 431
// Submission Date: 2018-09-20
// UVa Run Time: 0.070s

#include <bits/stdc++.h>

using namespace std;

struct evidence
{
int index, score, hour;
string description;

bool operator<(const evidence &data) const
{
if (hour != data.hour)
return hour < data.hour;
if (score != data.score)
return score > data.score;
return description < data.description;
}
};

int main(int argc, char *argv[])
{
string line;
int scores, choices, n, cases;

cin >> cases;
for (int cs = 1; cs <= cases; cs++)
{
int time_limit;
cin >> time_limit;
cin.ignore(256, '\n');

vector<evidence> evidences;
int count = 1;
while (getline(cin, line), line.length() > 0)
{
if (line.length() == 0) break;
evidence data;
data.index = count++;
istringstream iss(line);
iss >> data.score >> data.hour;
getline(iss, data.description);
data.description.erase(data.description.begin());
evidences.push_back(data);
}

if (cs > 1) cout << '\n';

sort(evidences.begin(), evidences.end());
evidence empty;
evidences.insert(evidences.begin(), empty);

memset(scores, 0, sizeof(scores));
memset(choices, 0, sizeof(choices));
n = evidences.size() - 1;

for (int i = 1; i <= n; i++)
for (int j = 1; j <= time_limit; j++)
{
if (j >= evidences[i].hour && scores[i - 1][j - evidences[i].hour] + evidences[i].score > scores[i - 1][j])
{
choices[i][j] = 1;
scores[i][j] = scores[i - 1][j - evidences[i].hour] + evidences[i].score;
}
else scores[i][j] = scores[i - 1][j];
}

vector<int> selected;
int last_index = n, pre_time_limit = time_limit;
int used_hours = 0, max_points = 0;

while (last_index)
{
if (choices[last_index][pre_time_limit])
{
selected.push_back(last_index);
pre_time_limit -= evidences[last_index].hour;
used_hours += evidences[last_index].hour;
max_points += evidences[last_index].score;
}
last_index--;
}
reverse(selected.begin(), selected.end());

if (time_limit == 0)
{
max_points = 0;
selected.clear();
for (int i = 1; i <= n; i++)
if (evidences[i].hour == 0)
{
selected.push_back(i);
max_points += evidences[i].score;
}
}

if (max_points == 0)
{
cout << "There is not enough time to present any evidence. Drop the charges.\n";
continue;
}

cout << "Score  Time  Description\n";
cout << "-----  ----  -----------\n";
for (auto item : selected)
{
cout << setw(3) << right << evidences[item].score;
cout << "    ";
cout << setw(3) << right << evidences[item].hour;
cout << "   ";
cout << evidences[item].description << '\n';
}
cout << '\n';
cout << "Total score: " << max_points << " points\n";
cout << " Total time: " << used_hours << " hours\n";
}

return 0;
}
``````