321 - The New Villa

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

Moderator: Board moderators

jacklebot
New poster
Posts: 1
Joined: Tue Oct 21, 2003 3:02 am
Contact:

321 - The New Villa

Post by jacklebot » Tue Oct 21, 2003 3:06 am

I've been banging my head on problem 321 for a bit now, and I think I've reasoned it into being a state table. Any comments or extra hints?
Jacklebot

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Sat Aug 28, 2004 3:26 am

I made it into an unweighted graph with 10*2^10 nodes, and I'm running BFS on it, but I keep getting WA. Does anyone have any tricky cases? I tried this:

Code: Select all

Input:
3 2 3
1 2
3 1
1 2
2 3
3 1

Output:
Villa #1
The problem can be solved in 7 steps:
- Switch on light in room 2.
- Move to room 2.
- Switch on light in room 3.
- Move to room 1.
- Switch off light in room 2.
- Move to room 3.
- Switch off light in room 1.

If only I had as much free time as I did in college...

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Sat Aug 28, 2004 3:26 am

Got it.
Eeeeevil test case! Poor guy if he has a house like that.
If only I had as much free time as I did in college...

User avatar
Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:

Some testcases

Post by Hadi » Mon Aug 29, 2005 8:21 am

Input Data:
1 0 1
1 1

1 0 0

2 0 0

5 4 5
1 2
1 3
1 4
1 5
1 2
2 3
3 4
4 5
5 1

5 4 5
1 2
1 3
2 4
1 5
1 2
2 3
3 4
4 5
5 1

10 9 13
1 2
2 3
3 4
1 5
4 6
1 7
4 8
1 9
4 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
2 1
3 2
4 3
10 4

0 0 0

Output:
Villa #1
The problem can be solved in 0 steps:

Villa #2
The problem can be solved in 0 steps:

Villa #3
The problem cannot be solved.

Villa #4
The problem can be solved in 19 steps:
- Switch on light in room 2.
- Move to room 2.
- Switch on light in room 3.
- Move to room 1.
- Move to room 3.
- Switch on light in room 4.
- Move to room 1.
- Move to room 4.
- Switch on light in room 5.
- Move to room 1.
- Move to room 3.
- Switch off light in room 4.
- Move to room 1.
- Move to room 2.
- Switch off light in room 3.
- Move to room 1.
- Switch off light in room 2.
- Move to room 5.
- Switch off light in room 1.

Villa #5
The problem can be solved in 21 steps:
- Switch on light in room 2.
- Move to room 2.
- Switch on light in room 3.
- Move to room 1.
- Move to room 3.
- Switch on light in room 4.
- Move to room 1.
- Move to room 2.
- Move to room 4.
- Switch on light in room 5.
- Move to room 2.
- Move to room 1.
- Move to room 3.
- Switch off light in room 4.
- Move to room 1.
- Move to room 2.
- Switch off light in room 3.
- Move to room 1.
- Switch off light in room 2.
- Move to room 5.
- Switch off light in room 1.

Villa #6
The problem can be solved in 70 steps:
- Switch on light in room 2.
- Move to room 2.
- Switch on light in room 3.
- Move to room 3.
- Switch on light in room 4.
- Move to room 4.
- Switch on light in room 5.
- Move to room 3.
- Move to room 2.
- Move to room 1.
- Move to room 5.
- Switch on light in room 6.
- Move to room 1.
- Move to room 2.
- Move to room 3.
- Move to room 4.
- Move to room 6.
- Switch on light in room 7.
- Move to room 4.
- Move to room 3.
- Move to room 2.
- Move to room 1.
- Move to room 7.
- Switch on light in room 8.
- Move to room 1.
- Move to room 2.
- Move to room 3.
- Move to room 4.
- Move to room 8.
- Switch on light in room 9.
- Move to room 4.
- Move to room 3.
- Move to room 2.
- Move to room 1.
- Move to room 9.
- Switch on light in room 10.
- Move to room 1.
- Move to room 2.
- Move to room 3.
- Move to room 4.
- Move to room 8.
- Switch off light in room 9.
- Move to room 4.
- Move to room 3.
- Move to room 2.
- Move to room 1.
- Move to room 7.
- Switch off light in room 8.
- Move to room 1.
- Move to room 2.
- Move to room 3.
- Move to room 4.
- Move to room 6.
- Switch off light in room 7.
- Move to room 4.
- Move to room 3.
- Move to room 2.
- Move to room 1.
- Move to room 5.
- Switch off light in room 6.
- Move to room 1.
- Move to room 2.
- Switch off light in room 1.
- Move to room 3.
- Switch off light in room 2.
- Move to room 4.
- Switch off light in room 3.
- Switch off light in room 5.
- Move to room 10.
- Switch off light in room 4.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Sat Dec 10, 2005 7:05 am

so what should be the algorithm
does bfs work?
i think no
Which algorithm should i use to solve this problem
or this kind of problem..
will modification on bfs work??

help, help

User avatar
Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:

Post by Hadi » Sat Dec 10, 2005 10:42 am

BFS works for this problem since we have 10*2^10 = 10240 states which is not too much.
10*2^10 = (In which room you are)*(which lights are on)
Do you need any other help?

Regards,
Hadi Moshayedi

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Tue Mar 28, 2006 10:43 am

Thanks Hadi,
I got Accepted..
this is a very interesting problem ,
isnt it?

gmacar
New poster
Posts: 5
Joined: Thu May 18, 2006 9:44 am

Post by gmacar » Tue Jun 06, 2006 4:29 pm

Hi all,
here is my input:

Code: Select all

6 6 10
1 2
2 3
3 4
3 5
4 5
4 6
1 2
1 6
2 3
3 5
5 3
5 4
4 3
4 1
6 4
6 2

0 0 0
Which is the correct output??
The shortest sequence has 16 steps (?) but there are at least six solutions with 16 steps...

TY
Giuseppe

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

Post by mf » Tue Jun 06, 2006 4:38 pm

Yes, 16 steps is optimal.

Problems marked with yellow sign (and 321 is one of them) has a special judge program. This means that there can be several correct outputs, and any of them will be accepted.

gmacar
New poster
Posts: 5
Joined: Thu May 18, 2006 9:44 am

Post by gmacar » Tue Jun 06, 2006 4:45 pm

Oh, didn't know that. Thank you

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Wed Jun 14, 2006 2:42 am

Hmmmm.... I had run time errors that showed up as WAs by the judge.
Why did this happen?

gmacar
New poster
Posts: 5
Joined: Thu May 18, 2006 9:44 am

Post by gmacar » Wed Jun 14, 2006 1:12 pm

what kind of "time errors" ? :o

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Thu Jun 15, 2006 4:35 am

My bad, it was not a run time error but rather just accessing rooms that were out of bounds with respect to R.

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: Problem 321

Post by Articuno » Sun Aug 23, 2009 11:55 am

My code is getting TLE. Is there anyone who can check my code please????

Code: Select all

AC
May be tomorrow is a better day............ :)

sgasioro
New poster
Posts: 1
Joined: Mon Nov 02, 2009 9:59 pm

Re: Problem 321

Post by sgasioro » Mon Nov 02, 2009 10:06 pm

Hello everyone! :)
I'm trying to solve this problem, but I'm still getting Presentation error. Can anyone tell me what is wrong with this code?
My outputs are exactly the same as sample outputs.
I've tried to remove last new line, or leave it, and tries many configurations with new lines and without and every single time it is PE.

Code: Select all

#include<cstdio>
#include<vector>
#include<algorithm>
#include <sstream>
using namespace std;
typedef long long LL;

string int2str(int i) {
	 ostringstream os;
	 os << i;
	 return os.str();
}

struct vertex
{
	 int room;
	 int light;
};

vector<int> conn[11];
vector<int> light[11];

int skad[11][(1 << 11)+1][3];

int q[(1 << 12) + 1];
int p, k;

string bit(int a)
{
	 string s = "";
	 for (int i=0; i<10; i++)
	 {
		  if (a & 1)s += "1";
		  else s += "0";

		  a /= 2;
	 }

	 return s;
}

int main()
{
	 int r, d, s;

	 int vv = 1;
	 while (1)
	 {	  
		  scanf("%d %d %d", &r, &d, &s);

		  if (r == 0)break;

		  if (vv > 1)printf("\n");

		  for (int i=0; i<=r; i++)
		  {
				for (int o=0; o<=(1<<11); o++)
				{
					 skad[i][o][0] = -1;
					 skad[i][o][1] = -1;
					 skad[i][o][2] = -1;
				}

				conn[i].clear();
				light[i].clear();
		  }

		  for (int i=0; i<d; i++)
		  {
				int a, b;
				scanf("%d %d", &a, &b);
				conn[a].push_back(b);
				conn[b].push_back(a);
		  }

		  for (int i=0; i<s; i++)
		  {
				int a, b;
				scanf("%d %d", &a, &b);
				light[a].push_back(b);
		  }

		  p = 0;
		  k = 0;

		  q[0] = (1 << 16) | (1 << 1);
		  skad[1][1 << 1][0] = 1;
		  skad[1][1 << 1][1] = 1 << 1;
		  skad[1][1 << 1][2] = 0;
		  k = 1;

		  while (p < k)
		  {
				int room = (q[p] >> 16);

				int lights = q[p] & 0x0000FFFF;
				p++;

				//printf("ruch %d %s %d\n", room, bit(lights).c_str(), skad[room][lights][2]);

				if (room == r && lights == (1 << r))
				{
					 break;
				}


				for (vector<int>::iterator i=conn[room].begin(); i!=conn[room].end(); ++i)
				{
					 int v = *i;
					 v = v << 16;

					 v |= lights;

					 if (skad[*i][lights][0] == -1 && ((lights >> *i) & 1))
					 {
						  //printf("go to %d %s\n", *i, bit(lights).c_str());
						  skad[*i][lights][0] = room;
						  skad[*i][lights][1] = lights;
						  skad[*i][lights][2] = skad[room][lights][2] + 1;

						  q[k] = v;
						  k++;
					 }
				}

				for (vector<int>::iterator i=light[room].begin(); i!=light[room].end(); ++i)
				{
					 int v = room << 16;
					 
					 if (*i == room)continue;

					 int new_lights = lights ^ (1 << *i);

					 v |= new_lights;
					
					 //printf("maybe go to %d %s\n", room, bit(new_lights).c_str());

					 if (skad[room][new_lights][0] == -1)
					 {
						  //printf("go to %d %s\n", room, bit(new_lights).c_str());

						  skad[room][new_lights][0] = room;
						  skad[room][new_lights][1] = lights;
						  skad[room][new_lights][2] = skad[room][lights][2] + 1;

						  q[k] = v;
						  k++;
					}
				}
		  }

		  printf("Villa #%d\n", vv++);
		  
		  if (skad[r][1 << r][0] != -1)
		  {
				printf("The problem can be solved in %s steps:", int2str(skad[r][1 << r][2]).c_str());
				/*if (skad[r][1 << r][2] > 0)*/printf("\n");

				string s = "";
				int room = r;
				int light = 1 << r;
				while (skad[room][light][0] != room || skad[room][light][1] != light)
				{
					 int poproom = skad[room][light][0];
					 int poplight = skad[room][light][1];

					 if (poproom != room)
						  s = "- Move to room " + int2str(room) + ".\n" + s;
					 else
					 {
						  light ^= poplight;

						  for (int i=1; i<=r; i++)
						  {
								if ((light >> i) & 1)
								{
									 if ((poplight >> i) & 1)
										  s = "- Switch off light in room " + int2str(i) + ".\n" + s;
									 else
										  s = "- Switch on light in room " + int2str(i) + ".\n" + s;

									 break;
								}
						  }
					 }

					 room = poproom;
					 light = poplight;
				}

				printf("%s", s.c_str());

				/*if (s.length() > 0)
				{
					 s[s.length()-1] = 0;

					 printf("%s", s.c_str());
				}*/
		  }
		  else
				printf("The problem cannot be solved.\n");

	 }

	 //printf("\n");

	 return 0;
}
Thanks:)

Post Reply

Return to “Volume 3 (300-399)”