## 923 - One Against Many

Moderator: Board moderators

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:

### 923 - One Against Many

I've tried dp on this problem, but the input size definitely makes it tle.
Next, I tried pruning, and always get wrong answer. I think the problem is that I can't deal with the floor functions properly, or that I need a more efficient formulation of the dp.

The following is my tle dp. I think i need something better.
By the way, t is the winning so far, i is the current subject, and k is the number of opponents left in the game.
I think I should remove the t from the dp, and replace with the number of remaining rounds, but I don't see anyway of doing it because I can't decompose the floor functions.

Code: Select all

``````int f(int t,int i,int k) {
if(k==0) return t;
if(M.find(make_pair(make_pair(t,i),k))==M.end()) {
int r = 0, tt = t-t*p[i]/100;
FOR(l,1,k) {
int v = f(tt+R*l/k,(i+1)%n,k-l);
r >?= v;
}
M[make_pair(make_pair(t,i),k)] = r;
}
return M[make_pair(make_pair(t,i),k)];
}
``````

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain
Hi,

I'm trying this problem but I can't figure out how to solve it. I have thought the obvious DP (N^3), but obviously I'll get TLE with this one. So, could anybody say how solve it? I think must be a good prunning, I have tried some of them with DFS but any of them were not OK. I have thought try with BFS but I think I'll get MLE before TLE. So, any reply will be appreciated

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
I used the property that the subjects cycles to sovle this problem.
I think this is the key point of this problem.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain
Yeah! i was trying it yesterday with that, but i was getting TLE although now I'm thinking I was using the floor() function of math.h. So, that could be a good reason to get TLE(stupid of me). I saw your memory allocated to solve the problem and I thought my "cycle method" could be OK, since it had the same memory allocated. I'll try it another time later.