Moderator: Board moderators

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:
.. 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) {
// 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

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:
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...

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:
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.

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am
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.
To be the best you must become the best!

Gigi's Baby
New poster
Posts: 19
Joined: Thu May 02, 2002 5:47 am
Location: Zhongshan (Sun Yat-sen) University
very good problem!
I like McDull too!

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Contact:

### 10817 : Wt's the Output ???

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 ??

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### Re: 10817 : Wt's the Output ???

My AC gives the same output. (20)

You may find the topics http://online-judge.uva.es/board/viewtopic.php?t=7582 and http://online-judge.uva.es/board/viewtopic.php?t=7533 useful.

good luck

lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:
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) ))

Code: Select all

``````int dp[101][(1<<16) + 1];
``````
use masc
Last edited by lord_burgos on Sun Feb 12, 2006 5:35 am, edited 1 time in total.

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am
lord_burgos
Please correct your forumlae... I don't see why 'S' stopped being an exponent
To be the best you must become the best!

New poster
Posts: 5
Joined: Tue Sep 20, 2005 2:53 pm
Location: iran
Contact:
Hi,
I've got TLE on this problem!
help me plz.

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;
}``````

pdwd
New poster
Posts: 19
Joined: Sat May 15, 2010 4:35 pm