## 321 - The New Villa

Moderator: Board moderators

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

### 321 - The New Villa

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
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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...

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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...

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

### Some testcases

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
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
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

Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:
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,

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
I got Accepted..
this is a very interesting problem ,
isnt it?

gmacar
New poster
Posts: 5
Joined: Thu May 18, 2006 9:44 am
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:
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
Oh, didn't know that. Thank you

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 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
what kind of "time errors" ?

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 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

### Re: Problem 321

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

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 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++)
{
}

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][1] = 1 << 1;
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());

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());

{
//printf("go to %d %s\n", room, bit(new_lights).c_str());

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;
{

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