Page 1 of 1

11545 - Avoiding Jungle in the Dark

Posted: Sat Oct 25, 2008 6:56 pm
by srrajesh
I don't why my code gives WA!
IMHO, I think that having S and D in the question really complicates the understanding of the problem.
I still don't understand what is the nature of S and D. Are they plains?
If they are plains, is the question about moving from left of S to left of D, or right of S to right of D?!
So, assuming that we move from left of S to left of D, here is the code:

I assume that 6AM is 0, and therefore 6PM is 12.

Code: Select all

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <ctime>
#include <map>
#include <set>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cassert>
using namespace std;

#define GI ({int t;scanf("%d",&t);t;})
#define dbg(x) cout << #x << " -> " << x << "\t" << flush;
#define dbge(x) cout << #x << " -> " << x << "\t" << endl;
#define LET(x,a) typeof(a) x(a)
#define FORI(i,a,b) for(LET(i,a);i!=(b);++i)
#define FOR(i,a,b) for(LET(i,a);i < (b);++i)
#define FORZ(i,n) FOR(i,0,n)
#define EACH(i,v) FOR(i,(v).begin(),(v).end())
#define CS c_str()
#define PB push_back
#define SZ size()
#define INF (int)1e9+1
typedef unsigned long long LL;
int arr[1001][25][25];
string str;
int solve(int ind, int time, int howCont)
{
    if(ind == str.SZ - 1)
	return 0;
    int& ret = arr[ind][time][howCont];
    if(ret != -1)
	return ret;
    int x = 0;
    ret = INT_MAX;
    if(howCont == 16) 
	if(str[ind] == '.')
    {
	howCont = 0;
	time += 8;
	time %= 24;
	x += 8;
    }
	else
	    return ret = INT_MAX;
    if(str[ind] == '*')
	if(time >= 12)
	    return ret = INT_MAX;
/*	{
	    if(str[ind - 1] == '.')
		while(time >= 12)
		{
		    howCont = 0;	
		    time += 8;
		    time %= 24;
		    x += 8;
		}
	    else
		return ret = INT_MAX;
	}
*/
    int val = solve(ind + 1, (time + 1)%24, howCont + 1);
    if(val != INT_MAX)
	ret <?= x + 1 + val;
    if(str[ind] == '.')
    {
	x += 8;
	time += 8; time %= 24;
	val = solve(ind + 1, (time + 1)%24, 1);
	if(val != INT_MAX)
	    ret <?= solve(ind + 1, (time + 1)%24, 1) + x + 1;
	x += 8;
	time += 8; time %= 24;
	val = solve(ind + 1, (time + 1)%24, 1);
	if(val != INT_MAX)
	    ret <?= solve(ind + 1, (time + 1)%24, 1) + x + 1;
	x += 8;
	time += 8; time %= 24;
	val = solve(ind + 1, (time + 1) % 24, 1);
	if(val != INT_MAX)
	    ret <?= solve(ind + 1, (time + 1) % 24, 1) + x + 1;
    }
    return ret;
}
int main()
{
    int nC = GI;
    FORZ(nc, nC)
    {
	cin >> str;
	memset(arr, -1, sizeof arr);
       str[0] = '.';
	int ret = solve(0,0,0);
	if(ret == INT_MAX)
	    ret = -1;
	printf("Case #%d: %d\n", nc+1, ret);
    }
}

Re: 11545 Avoiding Jungle in the Dark

Posted: Sat Oct 25, 2008 7:15 pm
by shamim
Your understanding of left of S to left of D is correct. That description was there to remove ambiguity of border regions between jungle and plain lands. It was implied that, you are strictly located on one land and one hour later, you will be located in the next, having no concern about the intermediate journey.

You start on S at 6 AM, so it was safe to be located there during dark hours, hence it can be considered a plain(safe) land. D is the destination and you can reach there during dark hours also, although this wasn't explicitly mentioned in the problem statement.

Re: 11545 Avoiding Jungle in the Dark

Posted: Sat Oct 25, 2008 7:38 pm
by srrajesh
shamim wrote:Your understanding of left of S to left of D is correct. That description was there to remove ambiguity of border regions between jungle and plain lands. It was implied that, you are strictly located on one land and one hour later, you will be located in the next, having no concern about the intermediate journey.
You start on S at 6 AM, so it was safe to be located there during dark hours, hence it can be considered a plain(safe) land. D is the destination and you can reach there during dark hours also, although this wasn't explicitly mentioned in the problem statement.
Thanks for your reply.
I think my code, satisfies all the conditions you said.
Can you give me some test cases?

Re: 11545 Avoiding Jungle in the Dark

Posted: Sun Oct 26, 2008 7:46 am
by shamim
I didn't look into your code thoroughly, but check to see if you are handling "sleeping inside danger zone" properly.

Re: 11545 Avoiding Jungle in the Dark

Posted: Sun Oct 26, 2008 11:07 am
by srrajesh
shamim wrote:I didn't look into your code thoroughly, but check to see if you are handling "sleeping inside danger zone" properly.
Yeah, you are right, I don't rest inside "danger zone" at all, though it is permitted to rest there during the day! thanks!
Anyway, even after including that, my code gives WA!

Code: Select all

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <ctime>
#include <map>
#include <set>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cassert>
using namespace std;

#define GI ({int t;scanf("%d",&t);t;})
#define dbg(x) cout << #x << " -> " << x << "\t" << flush;
#define dbge(x) cout << #x << " -> " << x << "\t" << endl;
#define LET(x,a) typeof(a) x(a)
#define FORI(i,a,b) for(LET(i,a);i!=(b);++i)
#define FOR(i,a,b) for(LET(i,a);i < (b);++i)
#define FORZ(i,n) FOR(i,0,n)
#define EACH(i,v) FOR(i,(v).begin(),(v).end())
#define CS c_str()
#define PB push_back
#define SZ size()
#define INF (int)1e9+1
typedef unsigned long long LL;
int arr[1001][25][25];
string str;
int solve(int ind, int time, int howCont)
{
    if(ind == str.SZ - 1)
	return 0;
    int& ret = arr[ind][time][howCont];
    if(ret != -1)
	return ret;
    int x = 0;
    ret = INT_MAX;
    if(howCont > 16) 
	return ret = INT_MAX;
    if(str[ind] == '*')
	if(time >= 12)
	    return ret = INT_MAX;
    int val = solve(ind + 1, (time + 1)%24, howCont + 1);
    if(val != INT_MAX)
	ret <?= x + 1 + val;
    FORZ(i, 8)//Just added more than enough rest!
    {
	if(str[ind] == '*' && time >= 12)
	    break;
	x += 8;
	time += 8; time %= 24;
	if(str[ind] == '*' && time >= 12)
	    break;
	val = solve(ind + 1, (time + 1)%24, 1);
	if(val != INT_MAX)
	    ret <?= solve(ind + 1, (time + 1)%24, 1) + x + 1;
    }
   return ret;
}
int main()
{
    int nC = GI;
    FORZ(nc, nC)
    {
	cin >> str;
	memset(arr, -1, sizeof arr);
	str[0] = '.';
	int ret = solve(0,0,0);
	if(ret == INT_MAX)
	    ret = -1;
	printf("Case #%d: %d\n", nc+1, ret);
    }
}
If anyone, can give some random test case or find what is error in the code, I will be happy!
Thanks, in advance.

Re: 11545 Avoiding Jungle in the Dark

Posted: Sun Oct 26, 2008 12:32 pm
by greve

Code: Select all

9
S.**....*****D
S.****..*****D
S*.**.*.*****D
S**.....*****D
S**...*.*****D
S**.*...*****D
S**.*.*.*****D
S**.***.*****D
S****.*.*****D
According to my AC program all answers are -1. Your code outputs 29 on all of them. You can get the expected answers for your own input sets on my homepage, http://www.uvatoolkit.com.

Re: 11545 Avoiding Jungle in the Dark

Posted: Tue Oct 28, 2008 2:11 pm
by Leonid
Some input for anyone having trouble with the problem:

Code: Select all

11
S........*****.*****D
S.........****...*****......*..***..**D
S...***.......**.....***....***...**.......****D
S........**..****..........***........*****......*****....**D
S....****.....**..****D
S........*****...***........*****....**..........****.......*.***.........**.***D
S.........**......*..........*.**..****D
S..........****.....*****.......*.......**..****.....*****.......****........****.........***D
S..****......*****.........*****.***.......****.......**......*****...*..........***....***D
S.......*..**......***D
S......*****.****D
output:

Code: Select all

Case #1: 36
Case #2: 102
Case #3: 103
Case #4: 108
Case #5: 54
Case #6: 152
Case #7: 79
Case #8: 221
Case #9: 179
Case #10: 54
Case #11: 33

Re: 11545 Avoiding Jungle in the Dark

Posted: Fri Nov 07, 2008 6:38 am
by rhsumon
Hello,
Here the problem says the person can take rest any time after he completed one rest session but again it says that one can rest exactly 8 hours... I can't understand

Re: 11545 Avoiding Jungle in the Dark

Posted: Fri Nov 07, 2008 6:45 am
by shamim
The two statements describe two different situations without conflicting with each other.

the person can take rest any time after he completed one rest session

This means, after taking a rest for 8 hours, he can decide to take another one for 8 hours.

One can rest exactly 8 hours

This means, he has to rest for exactly eight hours in one rest session, that is he can't rest for 7 hours or 9 hours or any other value for that matter.

I hope I could clarify the statements.

Re: 11545 Avoiding Jungle in the Dark

Posted: Fri Nov 07, 2008 5:10 pm
by rhsumon
thanks shamim vai.
I got it.......

Re: 11545 - Avoiding Jungle in the Dark

Posted: Fri Dec 26, 2008 2:37 pm
by bourne
I get correct answer for every test case on this forum still OJ gives me WA. I am not able to find the bug.

Code: Select all

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<sstream>
#include<map>
#include<stack>
#include<set>
#include<cmath>
#include<iomanip>
using namespace std;
#define INF 200000000

char a[1005];
int n,dp[1005][24][18];
int solve(int pos,int t,int h)
{
	if(pos==n) return 0;
	int& res=dp[pos][t][h];
	if(res!=-1) return res;
	res=INF;
	int tt;
	
	//resting
	bool ok=1;
	if(a[pos]=='*'){
		for(int i=t;i<t+8;i++)
		{
			tt=i%24;
			if(tt<=6 || tt>=18){
				ok=0;
				break;
			}	
		}		
	}	
	if(ok) res=min(res,8+solve(pos,(t+8)%24,0));
	
	//move at night
	if(a[pos]=='*' && h<16 && t>6 && t<18) res=min(res,1+solve(pos+1,(t+1)%24,h+1));
	
	//move during day
	if(a[pos]!='*' && h<16) res=min(res,1+solve(pos+1,(t+1)%24,h+1));
	
	return res;
}
int main()
{
	int t;
	cin>>t;
	for(int kase=1;kase<=t;kase++)
	{
		cin>>a;
		n=strlen(a);
		memset(dp,-1,sizeof(dp));
		int res=solve(0,6,0);
		printf("Case #%d: ",kase);
		if(res>=INF)
			printf("-1\n");
		else	
			printf("%d\n",res-1);
	}
}

Re: 11545 - Avoiding Jungle in the Dark

Posted: Tue Dec 30, 2008 12:45 pm
by Jan
Try the cases.

Input:

Code: Select all

2
S**..*.**.......D
S*.*.*.*.*......D
Output:

Code: Select all

Case #1: 16
Case #2: 16
Hope these help.

Re: 11545 - Avoiding Jungle in the Dark

Posted: Sun Aug 08, 2010 5:58 pm
by stormbind
Hello,

I'm having big troubles with this problem. I can't find a testcase where it fails. I've tested a lot of them, I post them here (using the AC homepage of greve you can find output).

Code: Select all

118
SD
S*D
S.D
S.**....*****D
S.****..*****D
S*.**.*.*****D
S**.....*****D
S**...*.*****D
S**.*...*****D
S**.*.*.*****D
S**.***.*****D
S****.*.*****D
S........*****.*****D
S.........****...*****......*..***..**D
S...***.......**.....***....***...**.......****D
S........**..****..........***........*****......*****....**D
S....****.....**..****D
S........*****...***........*****....**..........****.......*.***.........**.***D
S.........**......*..........*.**..****D
S..........****.....*****.......*.......**..****.....*****.......****........****.........***D
S..****......*****.........*****.***.......****.......**......*****...*..........***....***D
S.......*..**......***D
S......*****.****D
S**..*.**.......D
S*.*.*.*.*......D
S****D
S*****D
S******D
S*******D
S********D
S*********D
S**********D
S***********D
S************D
S*************D
S**************D
S***************D
S****************D
S*****************D
S.*.*.*.*D
S.*.*.*.*.*D
S.*.*.*.*.*.*D
S.*.*.*.*.*.*.*D
S.*.*.*.*.*.*.*.*D
S.*.*.*.*.*.*.*.*.*D
S.*.*.*.*.*.*.*.*.*.*D
S.*.*.*.*.*.*.*.*.*.*.*D
S.*.*.*.*.*.*.*.*.*.*.*.*D
S.*.*.*.*.*.*.*.*.*.*.*.*.*D
S.*.*.*.*.*.*.*.*.*.*.*.*.*.*D
S.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*D
S.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*D
S.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*D
S*.*.*.*.D
S*.*.*.*.*.D
S*.*.*.*.*.*.D
S*.*.*.*.*.*.*.D
S*.*.*.*.*.*.*.*.D
S*.*.*.*.*.*.*.*.*.D
S*.*.*.*.*.*.*.*.*.*.D
S*.*.*.*.*.*.*.*.*.*.*.D
S*.*.*.*.*.*.*.*.*.*.*.*.D
S*.*.*.*.*.*.*.*.*.*.*.*.*.D
S*.*.*.*.*.*.*.*.*.*.*.*.*.*.D
S*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.D
S*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.D
S*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.D
S.*.*.*.*.D
S.*.*.*.*.*.D
S.*.*.*.*.*.*.D
S.*.*.*.*.*.*.*.D
S.*.*.*.*.*.*.*.*.D
S.*.*.*.*.*.*.*.*.*.D
S.*.*.*.*.*.*.*.*.*.*.D
S.*.*.*.*.*.*.*.*.*.*.*.D
S.*.*.*.*.*.*.*.*.*.*.*.*.D
S.*.*.*.*.*.*.*.*.*.*.*.*.*.D
S.*.*.*.*.*.*.*.*.*.*.*.*.*.*.D
S.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.D
S.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.D
S.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.D
S*.*.*.*.*D
S*.*.*.*.*.*D
S*.*.*.*.*.*.*D
S*.*.*.*.*.*.*.*D
S*.*.*.*.*.*.*.*.*D
S*.*.*.*.*.*.*.*.*.*D
S*.*.*.*.*.*.*.*.*.*.*D
S*.*.*.*.*.*.*.*.*.*.*.*D
S*.*.*.*.*.*.*.*.*.*.*.*.*D
S*.*.*.*.*.*.*.*.*.*.*.*.*.*D
S*.*.*.*.*.*.*.*.*.*.*.*.*.*.*D
S*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*D
S*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*D
S*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*D
S.*D
S..*D
S...*D
S....*D
S.....*D
S......*D
S.......*D
S........*D
S.........*D
S..........*D
S...........*D
S............*D
S.............*D
S..............*D
S...............*D
S................*D
S...........*...........*D
S...........*...........*...........*D
S...........*............*D
S...........*...........*............*D
S......................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................D
S.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*D
S***********.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.*******.**D

Code: Select all

#include <stdio.h>
#include <queue>

using namespace std;

struct state
{
    unsigned char hour;
	int nhours;
	unsigned char travelled;
	short int pos;
};

bool operator<(const state &e1, const state &e2)
{
    if(e1.nhours > e2.nhours) return true;
	if(e1.nhours < e2.nhours) return false;
	if(e1.pos < e2.pos) return true;
	if(e1.pos > e2.pos) return false;
	if(e1.travelled > e2.travelled) return true;
	if(e1.travelled < e2.travelled) return false;	
	return e1.hour < e2.hour;
}

char buff[1<<20];

int main() 
{
	int ncases;
	scanf("%d",&ncases);
	for(int c=1;c<=ncases;c++) {
		scanf("%s",buff);
		buff[0] = '.';
		priority_queue<state> q;
		state start;
		start.hour = 6;
		start.pos = 0;
		start.nhours = 0;
		unsigned hash[25][17][1003];
		memset(hash,-1,sizeof(hash));
		q.push(start);
		bool found = false;
		while(!q.empty()) {
			state cur = q.top();
			q.pop();
			
			if(buff[cur.pos] == 'D') {
				printf("Case #%d: %d\n",c,cur.nhours);
				found = true;
				break;
			}
						
			if(buff[cur.pos] == '*') {
				if((cur.hour > 6) && (cur.hour < 18)) {
					if((((cur.hour + 8)%24) > 6) && (((cur.hour + 8)%24) < 18)) {
						state sleep;
						sleep.hour = (cur.hour + 8)%24;
						sleep.pos = cur.pos;
						sleep.travelled = 0;
						sleep.nhours = cur.nhours + 8;
						if(hash[sleep.hour][sleep.travelled][sleep.pos] > sleep.nhours) {
							hash[sleep.hour][sleep.travelled][sleep.pos] = sleep.nhours;
							q.push(sleep);
						}
					}
					if(cur.travelled < 16) {
						state jungle;
						jungle.hour = cur.hour + 1;
						jungle.pos = cur.pos + 1;
						jungle.travelled = cur.travelled + 1;
						jungle.nhours = cur.nhours + 1;
						if(hash[jungle.hour][jungle.travelled][jungle.pos] > jungle.nhours) {
							hash[jungle.hour][jungle.travelled][jungle.pos] = jungle.nhours;
							q.push(jungle);
						}
					}
				}
			} else {
				state sleep;
				sleep.hour = (cur.hour + 8)%24;
				sleep.pos = cur.pos;
				sleep.travelled = 0;
				sleep.nhours = cur.nhours + 8;
				if(hash[sleep.hour][sleep.travelled][sleep.pos] > sleep.nhours) {
					hash[sleep.hour][sleep.travelled][sleep.pos] = sleep.nhours;
					q.push(sleep);
				}
								
				if(cur.travelled < 16) {
					state plane;
					plane.hour = (cur.hour + 1)%24;
					plane.pos = cur.pos + 1;
					plane.nhours = cur.nhours + 1;
					plane.travelled = cur.travelled + 1;
					if(hash[plane.hour][plane.travelled][plane.pos] > plane.nhours) {
						hash[plane.hour][plane.travelled][plane.pos] = plane.nhours;
						q.push(plane);
					}
				}
			}
		}
		if(!found) printf("Case #%d: -1\n",c);
	}
	return 0;
}
Thank you very much to help me finding a wrong output of my code.

Re: 11545 - Avoiding Jungle in the Dark

Posted: Wed Jul 13, 2011 6:44 pm
by Shafaet_du
consider consecutive asterix's+1 as the distance between the node before 1st asterix and the node after the last asterix. Dont travel at night if distance between two node is greater than 1. Run a bfs with 3states.(current pos,current time,current energy)