11432 - Busy Programmer

All about problems in Volume 114. 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
f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

11432 - Busy Programmer

Post by f74956227 » Sun Mar 23, 2008 6:02 pm

Is this a DP program? i use a backtracking method but it is too slow... can someone give me some hints ?plz :(

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11432 - Busy Programmer

Post by Robert Gerbicz » Sun Mar 23, 2008 6:06 pm

f74956227 wrote:Is this a DP program? i use a backtracking method but it is too slow... can someone give me some hints ?plz :(
Yes, this is dp.
You can also send a precomputed table, that fits in 40kb code size.

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Post by andmej » Sun Mar 23, 2008 8:01 pm

I'm trying to define a state for this problem. I'm letting dp be the number of possible schedules using the first i days where the last day is MICRO, and without violating any constraint. (The answer will be 2 * dp[2d], since for every schedule ending at MICRO I can construct the "negation" swapping MICRO for GOO and viceversa.).

I'm having problems filling the table though, because I can't find how to determine if some schedule has used one of the tasks d or more days or if it has used one task the last d-1 days.

Any help?
Thanks.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Test Data

Post by baodog » Sun Mar 23, 2008 8:06 pm

Hi, I keep get wa. Is this i/o correct?

Code: Select all

0 0
1 0
1 1
3 2
3 1
3 0
3 3
4 0
4 1
4 2
4 3
4 4
3 10
33 33
33 12
33 0
33 1
-1 -1

Code: Select all

Case 1: 1
Case 2: 0
Case 3: 2
Case 4: 10
Case 5: 2
Case 6: 0
Case 7: 12
Case 8: 0
Case 9: 2
Case 10: 22
Case 11: 38
Case 12: 40
Case 13: 12
Case 14: 3665248281885181068
Case 15: 3660530221414286026
Case 16: 0
Case 17: 275644373642

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sun Mar 23, 2008 8:24 pm

I get this output:

Code: Select all

Case 1: 1
Case 2: 0
Case 3: 2
Case 4: 10
Case 5: 2
Case 6: 0
Case 7: 12
Case 8: 0
Case 9: 2
Case 10: 24
Case 11: 38
Case 12: 40
Case 13: 12
Case 14: 3665248281885181068
Case 15: 3658824518409873670
Case 16: 0
Case 17: 2

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Post by rushel » Sun Mar 23, 2008 8:26 pm

edited my outputs: me and mf replied almost at same time.

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Post by baodog » Sun Mar 23, 2008 9:59 pm

Thanks! Got ac.

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

Post by f74956227 » Mon Mar 24, 2008 1:25 am

I still can't find the recursive relationship...ORZ

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

Post by sclo » Mon Mar 24, 2008 2:00 am

f74956227 wrote:I still can't find the recursive relationship...ORZ
Hint: figure out what this line does:

Code: Select all

for(int i=1; i<=d; i++) if(n-i>=0) ret+=f(m,n-i,d,!k);
I'm not saying what are m,n,d, or k, you have to figure it out.

H_Hima
New poster
Posts: 18
Joined: Mon Sep 25, 2006 10:56 am
Location: Solar System
Contact:

Post by H_Hima » Fri Mar 28, 2008 8:34 pm

Hi.
Excelent alright.
I used this method in the contest. (backtracking & memorizing and this is my code.
but my answer for case:
33 12
is
3658729080464717380

but I got correct answer for case. 33 33 ?
the above case can be fetch in part of 33 33 solution.
this is my code please help me in my wrong.

Code: Select all

#include<iostream>
#include<fstream>
using namespace std;

unsigned long long res[40][80][40];
bool sws[40][80][40];
int D,G;
bool sw;

unsigned long long fun(int num,int space) {
	if(sws[num][space][G])
		return res[num][space][G];
	int i,j;
	unsigned long long re=0;
	if(num==0)
		re=1;
	else if(num>space)
		re=0;
	else if(num==space) {
		re=0;
		if(num<=G)
			re=1;
	}
	else {
		j=space-num;
		for(i=0;i<G&&i<num;i++) {
			re+=fun(j,space-i-1);
		}
	}
	sws[num][space][G]=true;
	res[num][space][G]=re;
	return re;
}

int main() {
	//ifstream cin("test.in");
	//ofstream cout("test.out");
	int i,j,k,num,space,t=1;
	unsigned long long re;
	for(i=0;i<40;i++)
		for(j=0;j<80;j++)
			for(G=0;G<40;G++)			
				sws[i][j][G]=false;
	cin>>D>>G;
	while(D>=0&&G>=0) {
		num=D;
		space=2*D;
		if(D==0)
			cout<<"Case "<<t++<<": "<<1<<endl;
		else if(G==0) {
			cout<<"Case "<<t++<<": "<<0<<endl;
		}
		else if(G==1)
			cout<<"Case "<<t++<<": "<<2<<endl;
		else {
			for(i=0,re=0;i<num&&i<G;i++)
				re+=fun(num-1,space-i-2);
			re*=2;
			cout<<"Case "<<t++<<": "<<re<<endl;
		}
		cin>>D>>G;
	}
}
thanks alot.

sad2kind
New poster
Posts: 2
Joined: Tue Aug 19, 2008 9:55 pm

Re: 11432 - Busy Programmer

Post by sad2kind » Tue Aug 19, 2008 10:13 pm

In case D=4 G=2 , I can't find only 22 schedules.
  • aabbaabb
    aabbabab
    aababbab
    aabababb
    abbaabab
    abbabaab
    abaabbab
    abaababb
    ababbaab
    ababaabb
    abababab
What is the last one? :(

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

Re: 11432 - Busy Programmer

Post by rio » Wed Aug 20, 2008 12:33 pm

he can not be away from any project for more than G consecutive days. (of course unless a project is already complete.)
aabaabbb
-----
Rio

sad2kind
New poster
Posts: 2
Joined: Tue Aug 19, 2008 9:55 pm

Re: 11432 - Busy Programmer

Post by sad2kind » Wed Aug 20, 2008 2:55 pm

orz.. Thanks! I got AC :D

Post Reply

Return to “Volume 114 (11400-11499)”