10457 - Magic Car

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

Moderator: Board moderators

ChristopherH
New poster
Posts: 31
Joined: Sun Feb 23, 2003 9:18 pm
Location: Waterloo, Ontario, Canada

Post by ChristopherH »

The are strong similarities between this problem and 10486 "Mountain Villages". A good algorithm for one is likely to translate into a good algorithm for the other.

Personally, I'm a huge fan of union-find (disjoint-set-forest) techniques, so that's what I used for this and for 10486. It worked spectacularly on 10486 and isn't bad on 10457.

My current solution is K*M^2*alpha(N) (where alpha is the inverse ackerman function). The factor of K could be removed with a bit more complexity, but I'm not sure it's worth it since K is only 5.

These are fascinating search problems, with many different elegant methods of solution.

Kovychev R. A.
New poster
Posts: 1
Joined: Sat Jun 07, 2003 11:11 am

10457 O(E^2)

Post by Kovychev R. A. »

Standard (I think) algorithm for O(E^2) for each query. I name it "2-index method".
Main idea:

Code: Select all

 Sort edges e[i] by weight.
 i=j=1 {- these "2 indexes"}
 answer:=infinity;
 while (i<=n) and (j<=n) do
 begin
  if there is a way from start to end using only edges e[i..j]
  then
   begin
    answer:=min(answer,e[j].w-e[i].w);
    i:=i+1
   end
  else
   j:=j+1
 end
Proof is trivial

wiltord
New poster
Posts: 16
Joined: Mon Oct 27, 2003 10:10 am
Location: SiChuan, China

Post by wiltord »

Alexander Grushetsky wrote: And for each step I use Dijkstra with complexity E*logV.
how could Dijkstra be complexity of E*logV?

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. »

By the help of using binary heaps.

You also can achieve something like O(VlgV + E) by using a more sophisticated structure :-?
JongMan @ Yonsei

wiltord
New poster
Posts: 16
Joined: Mon Oct 27, 2003 10:10 am
Location: SiChuan, China

Post by wiltord »

I have found the so called sophisticated structure in <<introduction to algorithms>>,open my eyes. :D

tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

Re: 10457 - Magic Car

Post by tryit1 »

i see lots of wrong answers on this one. Can you give AC outputs for inputs ?

Code: Select all

55 504
11 48 118
11 15 794
11 53 256
11 33 509
8 11 624
11 12 158
1 11 158
11 34 172
11 52 863
9 11 522
11 41 809
11 55 387
4 11 697
11 24 768
11 25 384
10 11 169
11 50 587
11 27 22
11 49 192
11 43 322
3 11 958
11 14 612
11 16 338
11 46 86
5 11 468
11 21 99
11 28 747
11 39 491
11 26 706
11 36 222
11 17 741
11 42 74
11 44 331
11 30 784
11 23 316
11 37 946
11 40 344
11 13 319
11 32 710
11 54 187
11 51 151
11 18 809
11 35 842
11 29 862
7 11 122
11 22 778
2 11 263
11 20 458
6 11 140
11 19 924
11 38 65
11 45 427
11 31 927
2 15 361
2 53 380
2 33 416
2 8 663
2 12 804
1 2 923
2 34 375
2 52 948
2 9 805
2 41 610
2 55 660
2 4 83
2 24 363
2 25 527
2 10 121
2 50 245
2 27 349
2 49 22
2 43 346
2 3 728
2 14 534
2 16 733
2 46 597
2 5 887
2 21 720
2 28 501
2 39 885
2 26 533
2 36 188
2 17 746
2 42 866
2 44 312
2 30 817
2 23 89
2 37 517
2 40 63
2 13 23
2 32 296
2 54 265
2 51 329
2 18 191
2 35 2
2 29 110
2 7 569
2 22 851
2 20 129
2 6 642
2 19 715
2 38 38
2 45 56
2 31 800
13 53 597
13 33 313
8 13 352
12 13 252
1 13 737
13 34 21
13 52 892
9 13 998
13 41 880
13 55 292
4 13 94
13 24 782
13 25 310
10 13 327
13 50 544
13 27 784
13 49 766
13 43 83
3 13 654
13 14 189
13 16 967
13 46 618
5 13 10
13 21 44
13 28 259
13 39 195
13 26 142
13 36 731
13 17 853
13 42 12
13 44 420
13 30 157
13 23 432
13 37 817
13 40 863
13 32 925
13 54 686
13 51 589
13 18 752
13 35 272
13 29 264
7 13 706
13 22 354
13 20 482
6 13 189
13 19 56
13 38 946
13 45 949
13 31 955
30 33 243
8 30 149
12 30 744
1 30 646
30 34 372
30 52 567
9 30 832
30 41 936
30 55 295
4 30 765
24 30 540
25 30 170
10 30 270
30 50 237
27 30 863
30 49 225
30 43 107
3 30 961
14 30 61
16 30 415
30 46 596
5 30 487
21 30 459
28 30 445
30 39 65
26 30 488
30 36 171
17 30 136
30 42 935
30 44 935
23 30 145
30 37 72
30 40 140
30 32 642
30 54 611
30 51 715
18 30 377
30 35 904
29 30 965
7 30 62
22 30 201
20 30 28
6 30 783
19 30 293
30 38 243
30 45 367
30 31 707
7 8 198
7 12 312
1 7 665
7 34 942
7 52 886
7 9 194
7 41 115
7 55 671
4 7 267
7 24 501
7 25 88
7 10 549
7 50 928
7 27 734
7 49 439
7 43 122
3 7 842
7 14 917
7 16 658
7 46 309
5 7 182
7 21 668
7 28 217
7 39 289
7 26 628
7 36 607
7 17 644
7 42 522
7 44 644
7 23 445
7 37 269
7 40 39
7 32 673
7 54 279
7 51 679
7 18 75
7 35 691
7 29 365
7 22 647
7 20 741
6 7 919
7 19 155
7 38 822
7 45 499
7 31 802
9 12 14
1 9 371
9 34 680
9 52 819
9 41 499
9 55 666
4 9 803
9 24 778
9 25 118
9 10 511
9 50 447
9 27 508
9 49 688
9 43 652
3 9 555
9 14 50
9 16 289
9 46 224
5 9 338
9 21 151
9 28 849
9 39 213
9 26 490
9 36 646
9 17 755
9 42 101
9 44 738
9 23 447
9 37 192
9 40 604
9 32 82
9 54 791
9 51 488
9 18 885
9 35 716
9 29 763
9 22 241
9 20 521
6 9 676
9 19 650
9 38 470
9 45 125
9 31 487
1 47 691
34 47 309
47 52 403
9 47 152
41 47 457
47 55 387
4 47 373
24 47 940
25 47 350
10 47 836
47 50 999
27 47 403
47 49 687
11 47 944
43 47 802
3 47 266
14 47 381
16 47 947
46 47 556
5 47 569
21 47 214
28 47 940
39 47 533
26 47 551
36 47 654
17 47 827
42 47 989
44 47 448
30 47 718
23 47 764
37 47 388
40 47 454
13 47 512
32 47 197
47 54 509
47 51 544
18 47 797
35 47 374
29 47 127
7 47 289
22 47 519
2 47 958
20 47 161
6 47 374
19 47 567
38 47 777
45 47 89
31 47 431
28 34 121
28 52 119
28 41 456
28 55 97
4 28 888
24 28 412
25 28 799
10 28 624
28 50 80
27 28 943
28 49 915
28 43 862
3 28 51
14 28 89
16 28 458
28 46 191
5 28 655
21 28 3
28 39 391
26 28 473
28 36 39
17 28 23
28 42 830
28 44 566
23 28 179
28 37 679
28 40 955
28 32 17
28 54 432
28 51 332
18 28 241
28 35 423
28 29 313
22 28 179
20 28 735
6 28 764
19 28 319
28 38 523
28 45 761
28 31 975
35 52 844
35 41 664
35 55 552
4 35 900
24 35 150
25 35 478
10 35 210
35 50 677
27 35 681
35 49 684
35 43 745
3 35 622
14 35 713
16 35 185
35 46 168
5 35 53
21 35 195
35 39 892
26 35 360
35 36 912
17 35 702
35 42 152
35 44 830
23 35 363
35 37 703
35 40 364
32 35 661
35 54 228
35 51 34
18 35 463
29 35 339
22 35 641
20 35 555
6 35 433
19 35 619
35 38 312
35 45 456
31 35 108
22 41 833
22 55 833
4 22 178
22 24 108
22 25 319
10 22 965
22 50 170
22 27 809
22 49 758
22 43 277
3 22 792
14 22 94
16 22 945
22 46 214
5 22 363
21 22 350
22 39 955
22 26 609
22 36 751
17 22 483
22 42 583
22 44 962
22 23 324
22 37 994
22 40 16
22 32 327
22 54 362
22 51 444
18 22 372
22 29 941
20 22 722
6 22 661
19 22 665
22 38 150
22 45 152
22 31 953
21 41 636
21 55 242
4 21 534
21 24 608
21 25 987
10 21 567
21 50 194
21 27 71
21 49 464
21 43 64
3 21 312
14 21 315
16 21 321
21 46 33
5 21 923
21 39 923
21 26 64
21 36 640
17 21 310
21 42 407
21 44 309
21 23 474
21 37 372
21 40 446
21 32 598
21 54 930
21 51 135
18 21 909
21 29 982
20 21 583
6 21 99
19 21 289
21 38 202
21 45 851
21 31 510
51 55 535
4 51 152
24 51 141
25 51 838
10 51 824
50 51 960
27 51 625
49 51 988
43 51 878
3 51 402
14 51 616
16 51 565
46 51 851
5 51 778
39 51 76
26 51 118
36 51 806
17 51 490
42 51 507
66 74
5
12 35
11 16
15 43
39 20
14 39

Code: Select all

157
140
155
162
144

algorithm is to sort the edge weights by edge cost and then start with
2 pointers at the begining i,j=0.
if it is possible with (i,j) , then increment i , otherwise increment
j. For checking possible i use dfs.

j is the maximum energy idx and i is the minimum energy idx.

Code: Select all

vector < pair<int, pair < int, int > > >v[MAX];
vector <pair<int, pair<int,int> > > elist;

int found;
int visit[MAX];
void dfs(int z,int dest,int mni,int mxi){

    if(visit[z]) return;
    if(z==dest) {found=true; return; }
    visit[z]=true;
    int i;
    for(i=0;i<v[z].size();i++){
        if(v[z][i].first>=mni && v[z][i].first<=mxi)
        dfs(v[z][i].second.first,dest,mni,mxi);
        if(found) return;
    }

}

bool possible(int p,int q,int source,int dest){
    memset(visit,0,sizeof(visit));
    found=false;
    if(source==dest) found=true;
    else
    dfs(source,dest,p,q);
    return found;

}

int
main ()
{
  int n, m;
//      while(scanf(" %d %d",&n,&m)!=EOF)
  scanf (" %d %d", &n, &m);
  {
    int i, x, y, s, j;

    for(i=0;i<n+1;i++) v[i].clear();
    elist.clear();
    for (i = 0; i < m; i++)
      {
    scanf (" %d %d %d", &x, &y, &s);
    elist.push_back(make_pair(s,make_pair(x,y)));
    elist.push_back(make_pair(s,make_pair(y,x)));
      }

    int st, et;
    scanf (" %d %d", &st, &et);
    sort(elist.begin(),elist.end());
   for(i=0;i<elist.size();i++){
        s=elist[i].first;
        x=elist[i].second.first;
        y=elist[i].second.second;
        v[x].push_back(make_pair(i,make_pair(y,s)));
    }

    int tc;
    scanf (" %d", &tc);
    while (tc--)
      {
    int b,e,k;
    scanf (" %d %d", &b, &e);
    i=j=0;
    x=elist.size();
    int ans=INF;
    while(i<x and j<x){
        if(possible(i,j,b,e)) ans=min(max(0,elist[j].first - elist
[i].first),ans),i=i+1;
        else j+=1;
    }
    cout <<ans+st+et<<endl;
      }
  }
  return 0; 
}

Post Reply

Return to “Volume 104 (10400-10499)”