10557 - XYZZY

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

Moderator: Board moderators

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

10557 - XYZZY

Post by Farid Ahmadov » Sat Oct 04, 2003 11:42 am

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

Post by Observer » Sat Oct 04, 2003 12:20 pm

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 :D
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

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

Post by Farid Ahmadov » Sat Oct 04, 2003 1:03 pm

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. :cry:
_____________
NO sigNature

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

Post by gvcormac » Sat Oct 04, 2003 2:51 pm

Farid:

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

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

Post by Farid Ahmadov » Sat Oct 04, 2003 5:30 pm

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.
_____________
NO sigNature

User avatar
rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France

Post by rakeb » Sun Oct 05, 2003 9:13 am

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:

Post by Lain » Mon Oct 06, 2003 2:22 am

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

Post by cpmicpmi » Thu Oct 09, 2003 2:49 pm

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

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

Post by Farid Ahmadov » Thu Oct 09, 2003 3:33 pm

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

Post by cpmicpmi » Thu Oct 09, 2003 5:19 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

Post by BiK » Wed Oct 15, 2003 7:30 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:

Post by Lain » Fri Oct 17, 2003 11:00 pm

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
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

Floyd algo

Post by Farid Ahmadov » Sat Oct 18, 2003 1:35 pm

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:

Post by Lain » Sat Oct 18, 2003 3:52 pm

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
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

Post by Farid Ahmadov » Sat Oct 18, 2003 6:25 pm

Yes. Maybe. You can do it with same idea.
_____________
NO sigNature

Post Reply

Return to “Volume 105 (10500-10599)”