10557 - XYZZY

[Farid Ahmadov]

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?

[Observer]

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

[Farid Ahmadov]

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.

[gvcormac]

Farid:

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

[Farid Ahmadov]

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.

Thanx in advance.

[rakeb]

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?

[Lain]

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]

Do not use Floyd algo , how to solve it?
I got TLE using BFS.

[Farid Ahmadov]

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.

[cpmicpmi]

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]

Hello everybody,

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

[Lain]

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

The answer is hopeless

Thanks

[Farid Ahmadov]

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.

[Lain]

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?

[Farid Ahmadov]

Yes. Maybe. You can do it with same idea.