431 - Trial of the Millennium
Moderator: Board moderators
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.
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.
this code is wrong answer but i can't see where the defect is.
can anybody help?
thanks
[cpp]/* CODE DELETED */[/cpp]
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.
-
- 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:
The answer is obvious, but your program cannot output correctly.
If you need more random generated i/o, write pm to me.
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.
-
- 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
or should it be
Does it matter?
Code: Select all
Score Time Description
----- ---- -----------
7 1 E
9 1 N
Total score: 16 points
Total time: 2 hours
Code: Select all
9 1 N
7 1 E
If only I had as much free time as I did in college...
-
- 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.
Can anyone offer comments?
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.
Can anyone offer comments?
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...
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:
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
431 WA
I keep getting WA for 431, here is my code
any one can tell me where I get it wrong or give me some test cases that expose my error?
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
readln(t);
k:=0;
repeat
readln(s);
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
readln(c);
readln;
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.
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
http://online-judge.uva.es/board/viewto ... hlight=431
Ami ekhono shopno dekhi...
HomePage
HomePage
-
- Experienced poster
- Posts: 122
- Joined: Sun Nov 13, 2005 10:25 am
- Location: Taiwan
This is my code give for that input.mf wrote:Code: Select all
1 10 10 1 A 20 4 B 10 7 C
Code: Select all
Score Time Description
----- ---- -----------
10 1 A
20 4 B
Total score: 30 points
Total time: 5 hours
-
- 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[105][250];
int path[105][250];
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] = 0;
path[i][0] = 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[0][s] >= mm ) mm = dp[0][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;
}
Any Help will be Appreciated...
cheers,
vijay
vijay
-
- New poster
- Posts: 48
- Joined: Sun Jun 22, 2014 6:14 am
Re: 431 - Trial of the Millennium
I'm getting WA for this:
Any help is appreciated.
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 MASK(k) (BIT(k)-1UL)
#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;
}
-
- 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:
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
// Verdict: Wrong Answer
// 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[110][250], choices[110][250], 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;
}
metaphysis: http://uhunt.onlinejudge.org/id/95895
My solutions for UVa problems: https://github.com/metaphysis/Code.
My solutions for UVa problems: https://github.com/metaphysis/Code.