923 - One Against Many

All about problems in Volume 9. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

923 - One Against Many

Post by sclo » Sun Nov 26, 2006 2:59 am

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

Post by Emilio » Tue Nov 28, 2006 5:16 pm

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 :)

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Tue Nov 28, 2006 5:27 pm

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

Post by Emilio » Tue Nov 28, 2006 5:51 pm

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.
Thank you for your reply :)

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sun Feb 11, 2007 8:48 pm

How does the cycle method work? In fact, the dp is not cyclic, which got me confused for a while.

Nevermind, I've solved it.
The idea was to define f(i,j) = maximum winning after subject j with i opponent remaining. The constraint that there must be at least 1 loser per round guarantees the dp is acyclic. Watch out for TLE even if your algorithm is O(m^2 * n), where m is the number of initial opponent, n is the number of subject.

Post Reply

Return to “Volume 9 (900-999)”