## 10557 - XYZZY

Moderator: Board moderators

Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

### 10557 - XYZZY

Hi people. I get WA. My algo is so:
First I build graph where g[i,j] = energy[j] (energy of the second room)
The I run Floyd algo and find maximal energy (weight) between all rooms.
If there is cycle where energy>0 then we can always win: if g[i,i]>0;
we can always win because we can continue cycling as much as we need.
If there is no cycle then we look at g[1,n] the energy between 1-st and last rooms. If this enery>-100 then we win and lose if we cannot win.

What is wrong with this algo?
_____________
NO sigNature

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
are u sure that Floyd can handle negative edges/ cycles?

and u wrote:
If there is cycle where energy>0 then we can always win
what if the cycle doesn't lead to the destination? Try this case (i found it on the Web):
7
0 1 2
0 2 3 5
-100 1 4
-100 1 7
1 1 6
0 1 5
0 0
Output should be:
hopeless
Hope it helps
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan
Thank you for your help. I used it. I am sure about negatives.

My floyd is:
[pascal]for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if connected[i,k] and connected[k,j] then
begin
if not connected[i,j] then
begin
d[i,j]:=d[i,k]+d[k,j];
connected[i,j]:=true;
end else
begin
if d[i,j]<d[i,k]+d[k,j] then d[i,j]:=d[i,k]+d[k,j];
end;
end;[/pascal]

Now I check for if we can reach destination from cycle and check if cycle is reachable from sourse:
[pascal]for i:=1 to n do
if (d[i,i]>0)and(connected[1,i])and(connected[i,n]) then win:=true;
if d[1,n]>-100 then win:=true;[/pascal]
For your testcase I get "hopeless". But I still get WA.
_____________
NO sigNature

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:
Farid:

Check that your definition of "connected" corresponds to the problem statement.

Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan
gvcormac what do you mean?

connected is initialized as, if there is a door from this room to other then connected[this room, other room]:=true;

And it corresponds to the problem statement I think. What is not OK? Why I get WA? Isn't my algo right. Can anyone give example where I am wrong.

_____________
NO sigNature

rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France
This process continues until she wins by entering the finish room
or dies by running out of energy (or quits in frustration).
did u consider the case in bold letter?
Rakeb

Lain
New poster
Posts: 11
Joined: Sun Sep 21, 2003 5:45 pm
Location: Russia, PetrSU
Contact:
2Farid:

Let you found cycle d[i,i]. For examle it:
i--(-10)--> j --(11)--> i, and when you entered i you had less then 11 points of energy, then you'll die before room j, but using your algorithm you will be still alive and have 1 point per cycle =).

cpmicpmi
New poster
Posts: 3
Joined: Thu Oct 09, 2003 2:41 pm
Do not use Floyd algo , how to solve it?
I got TLE using BFS.

Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan
There are many ways to solve it and one of them is floyd. BFS will do also.
I didn't check if there can be energy overflow and that is why I decided to do it with floyd. But now BFS will also do. Floyd is better I think.
_____________
NO sigNature

cpmicpmi
New poster
Posts: 3
Joined: Thu Oct 09, 2003 2:41 pm
Here is my code.Could you tell me what's wrong in it??

Code: Select all

``````#include<iostream>
#include<fstream>
#include<queue>
#include<memory.h>
using namespace std;
ifstream fin("10557.in");
int eg[101][101];
bool way[101][101];

bool go(int n)
{
int i,j,k;
if(n==1)return true;

for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(!way[j][i])continue;
for(k=0;k<n;k++)
{
if(way[i][k])
{
if(eg[j][k]<eg[j][i]+eg[i][k] || !way[j][k])
{
eg[j][k]=eg[j][i]+eg[i][k];
}
way[j][k]=1;
}
}
}
}

if(way[0][n-1])
{
if(eg[0][n-1]>-100)return true;
for(i=0;i<n;i++)
if(eg[i][i]>0 && (way[0][i] && way[i][n-1]) && eg[0][i]>-100)
return true;
}
return false;
}

int main()
{
int i,j,n,m;
while(fin>>n && n>=0)
{
int a,b;
memset(way,0,sizeof(way));
memset(eg,0,sizeof(eg));
for(i=0;i<n;i++)
{
fin>>a>>m;
for(j=0;j<m;j++)
{
fin>>b;b--;
eg[i][b]=a;
way[i][b]=1;
}
}
if(go(n) && n)
cout<<"winnable\n";
else
cout<<"hopeless\n";
}
return 0;
}``````

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm
Hello everybody,

Could somebody explain how this problem is solved through the Ford-Fulkerson method?

Lain
New poster
Posts: 11
Joined: Sun Sep 21, 2003 5:45 pm
Location: Russia, PetrSU
Contact:
May smb. explain how to solve this problem using floyd?
And how it works with this test?

5
0 1 4
100 1 5
-80 1 2
-90 1 3
0 0

Thanks

Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

### Floyd algo

Lain why the answer is hopeless???

From room 0 we go to room 4 then to 3 then to 2 and then to 5.
• [x; y]
Where x is room number and y is current energy
________-90_________-80_______+100________0
[0; +100] ----> [4; +10] ----> [3; -70] ----> [2; +30] ----> [5; +30] and YOU WIN
After you run Floyd algo you will get above graph, but you must pay attention at your current energy not to be greater then +100 and less than -100. To make this just add this to facts into your Floyd algo and I think that you will solve. My idea is to run this Floyd. After it we have a path. Now using DP we can solve it. We walk on this path saving maximal energy till your current position. If on our way we have a positive cycle then we get maximal points from this cycle. I think that will do. Good luck.
_____________
NO sigNature

Lain
New poster
Posts: 11
Joined: Sun Sep 21, 2003 5:45 pm
Location: Russia, PetrSU
Contact:
Farid:

May be I misundrestood the problem, but there is said that:
This process continues until she wins by entering the finish room or dies by running out of energy (or quits in frustration).
And when you enters the room 3 you have negative energy(running out of energy). That's why it is hopeless. Is it wrong?