Page 2 of 2
Posted: Mon Feb 21, 2005 5:17 am
by technobug
.. wrote:My algorithm has runtime O(n * 3^s). As I want to reduce the memory usage, I use 2 pieces of 3^s memory, on start of very loop I copy one to another(I guess you know what I say...
O(n*3^s) here...... but it gets faster and with less memory as it goes bottom up using just one table size (3 ^ s). Just a little bit of memory needed...
But then, if you use the (3^s) * 2 table, you can always use a trick a friend of mine tought me:
Code: Select all
int actual = 0;
int other = 1;
for(i -> n) {
// do your stuff, reading from "actual" and writing to "other"
// after everything is done, change their values
actual = !actual;
other = !other;
}
// at the end, you have the result on table 'ACTUAL'
So you dont have to copy the data from one to the other everytime
Posted: Sun Mar 06, 2005 5:38 pm
by stubbscroll
uzurpatorul wrote:out
58000
154000
35000
Thanks for the sample i/o. It confirmed what I thought, I've misunderstood the problem. I thought that there had to be at least one serving teacher and at least one applicant for each subject. Since there is no serving teacher for subject 4 in the first input above, my program finds no solution. But why is the answer 58000, and not 56000 (using 1000 1 2, 5000 1 2 3 4 and 50000 3 4)? What is the difference between a serving teacher and an applicant in this problem? Is the difference above due to the fact that serving teachers always must be chosen? I hope someone can explain...
Posted: Sun Mar 06, 2005 6:28 pm
by stubbscroll
It seems the thinking needed to write the above post helped me a lot! Of couse the serving teachers are employed at the school and they are always chosen
. I just got accepted. Btw, I use only one 3^n table, it's possible when reversing the inner loop (counting down instead of up) in the DP.
Posted: Mon Mar 07, 2005 10:20 am
by Destination Goa
With O(n*4^s) DP I got TL during the contest. It's better to index back and forth all 3^s states into 4^s map.
Posted: Mon May 09, 2005 8:24 pm
by Gigi's Baby
very good problem!
I like McDull too!
10817 : Wt's the Output ???
Posted: Sun Sep 18, 2005 4:37 pm
by L I M O N
pls anyone gives me the output :
input :
4 2 2
10 1 2 3 4
10 1 2 3 4
1 1 2 3 4
1 1 2 3 4
0 0 0
my program outputs : 20
is it right one ??
Re: 10817 : Wt's the Output ???
Posted: Fri Sep 23, 2005 2:50 am
by Martin Macko
Posted: Thu Feb 09, 2006 1:38 am
by lord_burgos
Destination Goa wrote:With O(n*4^s) DP I got TL during the contest. It's better to index back and forth all 3^s states into 4^s map.
My algorithm use DP whit O( N * ( 2^(2*S) ))
use masc
Posted: Thu Feb 09, 2006 2:46 am
by Destination Goa
lord_burgos
Please correct your forumlae... I don't see why 'S' stopped being an exponent
Posted: Tue Oct 10, 2006 6:09 pm
by Tirdad
Hi,
I've got TLE on this problem!
help me plz.
thanks in advance
Code: Select all
#include <iostream>
#include <memory>
#include <assert.h>
using namespace std;
int dp[100000];
bool applicant[100][8];
int appVal[100];
int M,N,S;
int count ;
void dfs(int i,int state,int soFarVal)
{
if ( state > ( (1<<(2*S)) - 1 ) || state >= 100000) // looking for sooti
{
state = 0 ;
state = 1/state ;
}
if ( state ==( (1<<(2*S)) - 1 ))//reach end State
{
if((dp[state] >= soFarVal && soFarVal != 0) || dp[state] == 0) // set the so
dp[state] = soFarVal;
return ;
}
if ( i == N )
return;
if(dp[state] != 0 && soFarVal != 0)
{
if(dp[state] >= soFarVal)
dp[state] = soFarVal;
else
return ;
}
else
if(soFarVal != 0)
dp[state]= soFarVal;
int newState = state;
for(int j=0;j<S;j++)
{
if(!applicant[i][j])
continue;
if(!(newState & (1 << (2*j))) )
newState |= (1<<(2*j));
else
newState |= (1<<(2*j + 1));
}
dfs(i+1,state,soFarVal);
if(state !=newState)
dfs(i+1,newState,soFarVal + appVal[i]);
}
int main()
{
while(cin >> S)
{
if ( !S ) break;
cin>>M>>N;
count = 0 ;
//memset(dp,0,sizeof dp);
for ( int i=0 ; i<(1<<2*S) ; i++ ) dp [i] = 0 ;
for(int i=0;i<100;i++)
for ( int j=0 ; j<S ; j++ )
applicant [i][j] = 0 ;
int soFarCost=0,temp;
int state = 0;
bool flag;
for(int i =0 ;i<M;i++)
{
cin>>temp;
soFarCost+=temp;
while(cin.peek()!= '\n')
{
cin.get() ;
cin>>temp;
temp--;
if(!(state&(1<<(2*temp))))
state |=(1<<(2*temp));
else
state |=(1<<(2*temp + 1));
}
}
for(int i =0 ;i<N;i++)
{
cin>>appVal[i];
while(cin.peek()!= '\n')
{
cin.get();
cin>>temp;
applicant[i][temp-1] = true;
}
flag = true;
for(int course=0;course<S;course++)
{
if(applicant[i][course]&& (!( state & (1 <<(2*course)) ) || !(state&(1<<(2*course + 1)))))
flag = false;
}
if(flag)
{
for(int course=0;course<S;course++)
applicant[i][course] = false;
N--;
i--;
}
}
dfs(0,state,0);
int bestVal = dp[((1<<(2*S))-1)];
cout<<bestVal + soFarCost<<endl;
}
return 0;
}
Re: 10817 - Headmaster's Headache
Posted: Thu Aug 26, 2010 7:34 am
by pdwd
Can somebody explain me how to get:
a) time complexity O(n*4^s)
b) time complexity O(n*3^s)
I have O(n*s*2^(2s)) for each masc 'M' I must compute the set 'S' for actual applicant than I can substract from this masc min(dp[M], dp[M-S]). I cannot compute 'S' at the begining of processing actual applicant because it depends on masc 'M' wheter in some subjects applicant is a first or second teacher.