321 - The New Villa

[jacklebot]

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

[Abednego]

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.

[Abednego]

Got it.
Eeeeevil test case! Poor guy if he has a house like that.

[Hadi]

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.

[emotional blind]

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

[Hadi]

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

[emotional blind]

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

[gmacar]

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]

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]

Oh, didn't know that. Thank you

[daveon]

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

[gmacar]

what kind of "time errors" ?

[daveon]

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

[Articuno]

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

Code: Select all

AC

[sgasioro]

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:)