10246 - Asterix and Obelix

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

Moderator: Board moderators

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post by LittleJohn » Thu Mar 14, 2002 9:51 pm

Hi,
I use Dijkstra's algorithm to implement this problem. Two arrays(one stores min cost and the other stores max food cost) are used. From the source point, update these two arrays... But it got Wrong Answer. Can somebody tell me what's wrong with this method, or what else I should pay attention to?(Or a special test case?)
Thanks in advance.
LittleJohn.

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

10246

Post by Subeen » Thu Apr 04, 2002 7:03 am

this prog. got W.A. why? help!

code removed
Last edited by Subeen on Sun Oct 19, 2003 9:53 pm, edited 1 time in total.

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:

Post by ftomi » Fri Apr 05, 2002 11:27 pm

Try the following:
9 9 2
1 10 5 2 3 1 1 20 1
1 2 1
2 3 1
3 6 1
1 4 2
4 5 2
5 6 2
6 7 1
7 8 1
8 9 1
1 6
1 9
0 0 0

ras46
New poster
Posts: 5
Joined: Mon Nov 05, 2001 2:00 am
Location: Taiwan
Contact:

Post by ras46 » Fri Jul 12, 2002 7:51 pm

ftomi wrote:Try the following:
9 9 2
1 10 5 2 3 1 1 20 1
1 2 1
2 3 1
3 6 1
1 4 2
4 5 2
5 6 2
6 7 1
7 8 1
8 9 1
1 6
1 9
0 0 0
My output:
9
29

Is this output correct?
If yes,why I still got a WA?

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:

10246, why i got PE

Post by dwyak » Sun Jul 28, 2002 5:20 am

[cpp][/cpp]
/* @judge_id: XXXXXX 10246 C++ " :( " */
#include <fstream.h>
#include <string.h>

//ifstream fin("10246.txt");
#define fin cin
#define endl '\n'

const int MAX = 100;

int f[MAX], g[MAX][MAX], v[MAX][MAX], p[MAX];

main() {
int cases = 0, c, r, q;
for (fin >> c >> r >> q; c || r || q; fin >> c >> r >> q) {
if (cases) cout << endl;
cout << "Case #" << ++cases << endl;
int i, j, k;
for (i = 1; i <= c; i++)
fin >> f;

memset(g, 0xFF, sizeof(g));
for (i = 0; i < r; i++) {
int c1, c2, d;
fin >> c1 >> c2 >> d;
if (g[c1][c2] == -1 || d < g[c1][c2]) g[c1][c2] = g[c2][c1] = d;
}

for (i = 1; i <= c; i++) {
memset(v, 0xFF, sizeof(v)); v = 0;
memset(p, 1, sizeof(p));
for (j = 1; j < c; j++) {
int MIN = 2147383647, ID;
for (k = 1; k <= c; k++)
if (p[k] && v[k] != -1 && v[k] < MIN)
MIN = v[k], ID = k;
p[ID] = 0;
for (k = 1; k <= c; k++)
if (p[k] && f[k] <= f && g[ID][k] != -1 && (v[k] == -1 || v[i][k] > v[i][ID] + g[ID][k]))
v[i][k] = v[i][ID] + g[ID][k];
}
}

for (i = 0; i < q; i++) {
int c1, c2;
fin >> c1 >> c2;
int MIN = 2147483647;
for (j = 1; j <= c; j++)
if (v[j][c1] != -1 && v[j][c2] != -1 && v[j][c1] + v[j][c2] + f[j] < MIN)
MIN = v[j][c1] + v[j][c2] + f[j];
if (MIN > 2000000000)
cout << -1 << endl;
else
cout << MIN << endl;
}
}

return 0;
}

broderic
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am
Location: Canada

Post by broderic » Fri Aug 30, 2002 12:10 am

I keep getting WA on this problem...can anybody help me out?
I use floyd's (with some extra checking for the feast cost).

Here's my code (I won't leave it up too long, just for a day or two
or until somebody helps me).

Thanks in advance
Last edited by broderic on Thu Sep 05, 2002 8:12 pm, edited 1 time in total.

sobral
New poster
Posts: 2
Joined: Fri Jul 12, 2002 3:51 pm

Hi Broderick

Post by sobral » Thu Sep 05, 2002 5:02 pm

My first solution to this problem was very similiar to yours and I got the same problem as you: a lot of wrong answers :cry: .
One day I just thought that the floyd algorithm wasn`t doing the induction as I wanted, so I ran the floyd algorithm twice and my code got accepted.
I submitted your solution doing the same thing (calling: floyd(); floyd();) and it got accepted too. I`m not really sure why you have to run the floyd algorithm twice on this problem or if there is a solution where you can run the floyd just once.

Try it out and try to understand why it works...

broderic
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am
Location: Canada

Post by broderic » Thu Sep 05, 2002 8:14 pm

Thanks for the idea.
Hmm, I can't think of a reason (or a test case) as to why
you need to call it twice...One more thing to think about
today. :)

Broderick

Amir Aavani
New poster
Posts: 30
Joined: Wed Oct 23, 2002 6:53 am

Post by Amir Aavani » Thu Oct 02, 2003 8:20 am

my program get WA.
i use the same method as you use.
could any one tell me what the answer of the following querry is:

3 0 1
1 2 3
1 2
3 3 0
1 2 3
1 2
1 3
2 3
9 9 2
1 10 5 2 3 1 1 20 1
1 2 1
2 3 1
3 6 1
1 4 2
4 5 2
5 6 2
6 7 1
7 8 1
8 9 1
1 6
1 9
0 0 0

my program says
Case #1
-1

Case #2

Case #3
9
29

Amir Aavani
New poster
Posts: 30
Joined: Wed Oct 23, 2002 6:53 am

Post by Amir Aavani » Thu Oct 02, 2003 5:37 pm

at last i got AC.
my problem was due to the initialization of my array.
i use Pascal, i have an array one Mat which hold the cost of reaching from one city to the other city, at first i try to fillchar this array with 127 that means FillChar (Mat, SizeOf (Mat), 127). and get WA.

consider the following example
2 1 1
1 2
1 2 2147483645
1 2

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Oct 02, 2003 7:22 pm

You can use FillDWord(Mat, sizeof(Mat) div 4,$7fffffff) to set an array of Integer to their maxvalue. See the Free Pascal Reference Manual for more handy functions.

I don't think the input contains these extreme cases, 'cause I use 1000000000 as the value for 'Infinity' for this problem.

koala
New poster
Posts: 7
Joined: Sun Mar 28, 2004 9:41 am
Location: Tsinghua University, Peking, P.R.China
Contact:

something wrong with the description

Post by koala » Tue Apr 06, 2004 12:58 pm

It should be "Print a blank line after each case."

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

10246 - Asterix and Obelix

Post by Riyad » Tue Aug 23, 2005 9:18 pm

the problem seems to be a moderated shortest path problem ..... i am getting WA frequently ......can some one give me some critical input output ...........my algorithm is dijkstra with modified relaxation function .... i have also tested for -ve weight .........but there is not any -ve weight.............can some one plizzzzzz help me with this .......
i have also checked for overflow
thanx in advance
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

I NEED SOME I/O'S ...

Post by nymo » Mon Nov 14, 2005 7:16 pm

Hi, I am getting WAs with this problem. i 've tried dijkstra's shortest path algo( with some modification, off course :) ) and checked with some IOs. But I need more sample input and output ... please, help.

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Post by nymo » Thu Apr 27, 2006 10:25 pm

Is this algorithm correct?

Code: Select all

while (heap is not empty) 
{ 
    Let u be the node with minimum cost 
    i.e. u = extractMinFromHeap(); 
    Update data related to u(i.e. shortest path cost) 

    if (u == destination) 
        break; 

    for each node adjacent to u 
    { 
        Let v be a node adjacent to u 

        if (v is still in queue) 
        { 
            /* 
            RELAXATION 
            */ 
            Let cityCost be the highest cost of the feast in the path to u 
                	and 
            feastCost[k] contains the cost of feast in city k 
                
            if (cityCost < feastCost[v]) 
            { 
       	        temp = feastCost[v] - citycost; 
       	        highest cost of the feast in the path to v is feastcost[v] 
            } 
            else 
            { 
   	        temp = 0; 
       	        highest cost of the feast in the path to v is cityCost 
            } 

            temp = shortest[u] + temp + cost to go from u to v; 
                
            if (temp < current distance of v [in the heap]) 
            { 
       	        HeapDecreaseKey(); 
            } 
        } 

    } 
} 

It produces WA..... Am I missing something??? Can anybody post some IO???
Last edited by nymo on Thu Apr 27, 2006 10:27 pm, edited 1 time in total.

Post Reply

Return to “Volume 102 (10200-10299)”