## 10246 - Asterix and Obelix

Moderator: Board moderators

Well, shortest path Floyd algo also works - only for some unknown reason you need to use it twice (yes, don't be surprised). For when used once it gives WA, twice - AC!
serur
A great helper

Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Thanks serur, I actually implemented dijkstra's shortest path algo. with binary heap and tried to get ACC to check the correctness of my implementation. This implementation gives ACC for 423... however, it is WA here , so, I am quite puzzled about the correctness of my implementation of dijkstra or is it something with the logic for this specific problem(data structure or some stuff like that) : 10246..... okay, I will sometime try with FW... Thanks for your help. It is really appreciated
regards,
nymo
nymo
Experienced poster

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

For this

Input:
Code: Select all
`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`

Output:
Code: Select all
`Case #1926`

The second case returns 26. Because from 1 to 9 the path is
Code: Select all
`Path   Cost1 2      12 3      13 6      16 7      17 8      18 9      1And among these, the costliest city is 9 and the cost is 20So, total cost is 26.`

Hope it helps.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

### Re:

serur wrote:Well, shortest path Floyd algo also works - only for some unknown reason you need to use it twice (yes, don't be surprised). For when used once it gives WA, twice - AC!

Does anyone have idea why do we need to run Floyd Warshall twice on the same matrix? I also get WA for only one run.

Relaxation condition:
Code: Select all
`cost[i][j] + large[i][j] > cost[i][k] + cost[k][j] + max ( large[i][k], large[k][j] )`
emiraga
New poster

Posts: 1
Joined: Sat Apr 19, 2008 2:22 am

### Re: 10246 - Asterix and Obelix

A simpler example where single Floyd-Warshall is too greedy: it discards shorter path over city 3 because it's expensive to party there, even though a more expensive city (5) is inevitably encountered later.
Code: Select all
`5 5 110 10 20 10 301 2 21 3 12 4 23 4 14 5 51 5`

I'm guessing running the algorithm the second time helps because we then know the most expensive (inevitable) city in every path (?). I'm not convinced you can't come up with a counter-example that would fail even if F-W is run twice..

Would a proper F-W based solution have to store every path with it's max_feast between each pair of cities?
iggy
New poster

Posts: 3
Joined: Mon May 05, 2008 10:44 am

### Re: 10246 - Asterix and Obelix

Hi,
I've checked with many sets of inputs from file and it works perfectly but getting WA from OJ. Could there be any tricky input which i might be missing?
hasib_bd
New poster

Posts: 14
Joined: Wed Apr 30, 2008 12:39 pm

### Re: 10246 - Asterix and Obelix

My code is below. Always getting WA. The code may seem hasty. Please somebody help me to point out the error. Please help.

Code: Select all
`deleted`
hasib_bd
New poster

Posts: 14
Joined: Wed Apr 30, 2008 12:39 pm

### Re: 10246 - Asterix and Obelix

Some test cases

Code: Select all
`8 25 50 3 48 7 48 2 24 225 7 175 4 303 7 26 5 311 3 255 8 331 8 347 8 02 7 316 3 404 3 332 5 491 5 484 2 317 6 343 2 258 6 77 1 458 2 381 2 167 4 241 6 186 2 253 8 81 4 77 25 23 53 41 430 400 505 33 36 49 21 0 49 37 18 37 28 43 11 17 5 45 16 31 22 36 31 15 13 46 24 45 24 48 47 9 19 21 65 7 4720 12 3923 19 465 11 167 26 524 1 610 2 2922 18 1910 18 261 22 1024 20 4127 16 1812 16 97 13 3711 6 2729 20 3628 5 2425 12 1114 11 320 10 326 18 138 3 029 28 3023 6 458 27 54 28 1712 30 1927 28 3210 11 196 25 2427 30 431 29 356 7 365 30 123 16 4117 22 422 8 2024 13 1621 5 35 19 4722 8 226 10 276 15 3624 4 4315 29 4721 14 101 10 375 17 3628 3 4519 16 3328 21 269 25 2417 25 2015 24 930 20 2818 28 4417 26 1823 4 463 22 402 9 143 26 249 30 2919 27 1216 14 62 6 2218 12 2023 22 2917 1 4320 15 93 19 365 18 192 15 425 2 620 28 3217 4 49 5 3530 25 813 25 2019 9 318 15 1526 25 105 22 2120 27 3714 12 215 29 622 27 3717 24 3320 5 301 26 1027 2 473 11 2921 23 74 11 3321 30 3325 27 479 28 4312 2 485 27 4530 28 2620 7 420 1 127 24 123 2 2513 29 4520 16 322 3 3917 11 3029 23 3217 6 56 8 31 7 328 23 01 6 93 20 266 14 828 25 2626 16 718 20 272 7 1523 1 3626 14 4717 13 930 18 114 19 2018 23 146 20 378 26 207 11 1919 2 206 24 321 6 452 1 027 23 269 26 829 11 4219 6 3329 6 4013 9 3628 1 58 1 1919 25 1930 15 1010 12 412 7 4412 24 028 16 2121 20 1713 19 371 19 409 23 1515 17 354 30 3014 9 4226 2 392 4 4422 14 1319 14 151 25 198 28 333 13 3510 6 4512 4 2310 8 1325 3 4813 18 4916 17 2222 7 2416 21 3421 3 286 12 4112 15 4619 8 349 24 2016 7 329 4 469 21 4924 23 2421 24 4619 10 3325 24 323 25 1826 12 1124 2 3815 21 4412 17 4228 13 3629 26 82 20 2215 4 522 10 1611 20 1115 27 234 7 261 15 930 24 4424 8 176 9 2715 10 4413 15 3619 15 223 10 337 10 1811 15 3521 12 3127 17 227 9 217 10 459 22 4518 1 137 23 313 24 2027 4 1024 5 2312 29 2712 27 3711 23 45 6 3013 10 1515 3 4426 20 4115 16 1830 17 1410 28 2823 30 468 7 257 15 4227 18 4419 12 1624 18 268 16 3530 14 2029 24 468 30 118 8 96 28 3513 11 305 12 185 10 462 14 813 22 3316 24 3417 29 2116 22 2213 23 447 3 353 4 2719 28 2220 23 2613 2 277 19 625 16 2830 13 2618 19 2826 22 89 20 511 27 241 9 3018 9 713 12 189 15 3627 29 312 9 454 5 1127 7 4428 2 2323 28 4527 10 2721 18 819 11 4927 1 1030 2 393 5 4729 2 254 8 394 10 443 1 2222 15 19 16 488 21 1230 6 2716 11 2818 3 4917 7 1021 29 2425 21 34 9 2028 22 430 29 4017 9 2817 28 3625 5 1816 30 1225 4 186 4 724 11 4816 5 120 17 327 25 4310 14 714 15 3314 7 2611 2 4217 19 2010 29 4524 28 496 27 2616 29 401 5 2620 22 1919 24 294 26 2611 12 429 14 2218 4 3122 19 2114 5 1214 24 481 14 28 25 123 9 3210 9 3223 17 483 23 4620 25 3413 16 213 12 4422 30 3210 21 1726 11 4228 7 48 17 1620 8 464 14 3126 27 3428 14 443 17 2818 17 1229 3 1925 11 208 29 2010 23 4013 8 474 16 37 21 71 30 3812 22 2818 2 1526 18 3426 19 4615 23 2925 29 4926 15 279 27 1513 6 1213 26 2514 25 1113 5 616 3 2111 18 2514 3 917 14 2618 7 1216 6 3013 20 1511 22 131 12 3422 25 2628 11 3221 1 614 13 34 21 2714 23 3027 14 441 13 488 15 285 23 2030 19 174 20 3430 3 2922 24 162 17 1511 8 178 14 166 3 472 16 915 28 175 8 2821 13 4820 14 282 21 926 6 1416 1 4727 3 2225 18 4511 1 3223 26 1029 19 354 13 4716 18 471 133 109 2728 824 2316 299 1721 429 2313 38 1721 243 2010 326 42 74 1529 172 1715 1130 111 112 1417 515 117 2715 515 1918 163 1724 2121 2615 217 2610 2930 1715 816 108 912 165 2613 223 321 2024 256 3017 275 194 525 270 0 0`

Code: Select all
`Case #15592677414Case #22250395452544556554545524650595454594742283350361446324457455256455455304058515453383743493546405347`
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

plamplam
Experienced poster

Posts: 151
Joined: Fri May 06, 2011 11:37 am

### Re: 10246 - Asterix and Obelix

Can any one explain me the sample 1st test case of this problem?Why the answer for "1 5" is 45?
rumman
New poster

Posts: 1
Joined: Sun Nov 04, 2012 2:02 pm

### Re: 10246 - Asterix and Obelix

brianfry713
Guru

Posts: 1870
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Previous