12653 - Buses

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

Moderator: Board moderators

Post Reply
Masum
New poster
Posts: 9
Joined: Tue Jul 10, 2012 11:39 am

12653 - Buses

Post by Masum »

I am getting TLE in this problem. My solution has complexity log(n). But it still gets TLE. I would like some I/O. Though I have tested my program myself for some large inputs near 10^15. I am not posting the code at this stage.

At last accepted. I did a funny mistake. In the function of Matrix exponentiation, I used it as power(Matrix M, int n) instead of power(Matrix M, long long int n) causing the TLE. And could not get it for so long!
Last edited by Masum on Thu Jan 16, 2014 8:10 am, edited 1 time in total.

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

Re: Problem 12653(Bus Coloring)

Post by brianfry713 »

Input:

Code: Select all

8408463890 846930887 1804289384
2121191680 1957747794 1714636916
2982583250 1649760493 719885387
6752450140 1025202363 1189641422
10224488820 1102520060 783368691
7701917135 1365180541 1967513927
175026060 1303455737 304089173
8634782150 294702568 521595369
1393614315 861021531 336465783
2343515680 2145174068 233665124
6578170115 1801979803 1101513930
5629490840 1369133070 635723059
3140875060 2089018457 1059961394
8266886870 1131176230 1656478043
3042068925 1914544920 859484422
9867971625 1734575199 756898538
5647832070 2038664371 149798316
7121344905 412776092 184803527
689034315 749241874 1911759957
677486410 982906997 42999171
9687385425 2084420926 511702306
5795632530 572660337 1827336328
5503306570 1632621730 805750847
421769480 1141616125 1433925858
9994494075 2001100546 939819583
7929951825 610515435 1548233368
7385855440 760313751 1374344044
9449735895 945117277 356426809
2458527020 709393585 1780695789
7373062000 752392755 1918502652
7057748385 1264095061 2053999933
9921050065 943947740 1843993369
7346740475 1749698587 855636227
2317402855 1036140796 1956297540
1585487340 1975960379 2040651435
4638064515 1376710098 1892066602
8439633265 603570493 1330573318
2427801405 959997302 660260757
5974769330 593209442 402724287
9736733100 364228445 894429690
5319790160 270744730 221558441
10039528860 2114738098 1633108118
8050603550 822890676 1469834482
2493889285 631704568 791698928
1636272935 524872354 1255179498
8519823420 269455307 1572276966
800257645 1600028625 352406220
5600244150 112805733 2040332872
8566291355 515530020 378409504
10387433580 1409959709 1573363369
1003738985 1631518150 1373226341
840011230 1117142619 289700724
4954464610 439493452 150122847
8112987445 1231192380 1760243556
10737349210 338888229 111537765
1347207505 1911165194 438792351
9347350625 116087765 2142757035
9911379285 8936988 155324915
1751611140 387346492 1275373744
8801409685 1960709860 841148366
6221582190 1186452552 771151433
1069877040 1476153276 971899229
3267344295 1626276122 1139901475
9423306190 1239036030 2130794396
380329095 1350573794 1605908236
9936155060 1789366144 1605894429
10516593885 1784639530 1875335929
10561278820 1939964444 1597322405
1760593035 1067854539 1432114614
826724095 1909002905 1782436841
6758986850 532670689 1395235129
3402334985 1504569918 492067918
796297355 496987744 706043325
6991477500 480298491 1359512184
3006928225 2086206726 1096689773
1216340700 1544617506 1172755591
10139538350 1272469787 1012502955
9101942325 722308543 968338083
3703796780 6939508 933110198
2511393060 1789376349 1285228805
5174746500 1037127829 1450573623
1960177845 1529195747 654887344
4445116560 87755423 1335354341
6846609010 1447267606 1494613811
6540224395 396473731 745425662
3525893685 1569229321 1346811306
9888242615 434248627 1590079445
2762367085 1402586709 1470503466
2797064625 188213259 1143408283
1006528125 1473442063 1884167638
6192167265 776532037 238962601
3100727755 1431419380 1273911900
3539504870 619290072 1665947469
38424655 2113903882 407487132
2020793305 711845895 1776808934
9866939910 2058657200 937370164
1300764800 1501252997 1642548900
8313698345 824272814 1472713774
9254764635 1967681096 2025187191
5884556705 1704365085 437116467
AC output:

Code: Select all

314969
671552
458947
429807
855481
581445
476201
713881
616013
145792
579807
495561
547003
905907
984960
165259
640885
397812
293360
617980
354048
894377
059587
600891
173888
046395
812485
836255
946721
924501
376051
500580
044011
940096
523281
074816
265793
445598
430347
921875
971441
404416
404288
245248
145472
767191
890625
805393
873280
288441
188850
168365
910351
777600
108606
260694
703125
348988
333184
312640
089497
611041
390908
030656
992960
709769
698370
856361
009991
342800
226849
899968
126144
315001
751930
174941
916419
385273
526336
410281
779249
840995
605281
735247
672575
225309
365063
561401
364029
307003
862123
000000
938725
722240
228995
355264
165101
267904
115776
511965
My code runs this on my machine in .001 second, using matrix multiplication.
Check input and AC output for thousands of problems on uDebug!

abcman13
New poster
Posts: 6
Joined: Sun Apr 07, 2013 6:00 am

Re: Problem 12653(Bus Coloring)

Post by abcman13 »

Thank you. The problem was caused by an overflow.
Last edited by abcman13 on Sun Mar 02, 2014 8:24 am, edited 1 time in total.

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

Re: Problem 12653(Bus Coloring)

Post by brianfry713 »

Input:

Code: Select all

436307330756025 592933108458268 21977880902877
706652928693205 436346063312323 76333303537661
412949498557080 430115897049966 56849756278259
986443405998085 356218531477381 518669311513994
127913646913840 783445561091497 666047646909943
779723597758100 557272102805043 259471652627027
567035780667330 464266724187659 72916209565442
621451154181420 481043763917137 633181295081270
85537402719870 1381169221736 55022590705761
479222404369590 586625887650137 948449036161962
608501598573425 573750799930643 254195388479047
519394010789450 875952967699991 769980485368784
571683572494210 273598608857275 267805517223284
42828600477910 268809379784379 626462369897420
154259619318205 283055707878011 654478682248346
622379006836595 648195747381320 967292612059834
783322470165435 364512596376130 384718356601186
6401450686670 433412493513721 964015168230375
417746721890495 631090085829259 749479894426007
465560108266870 224631559922927 932169279762928
147055954639370 54512368741349 22086174133410
943912222211655 101409749552609 640177988610732
521943337025775 910505252582610 901042981261423
70512769389170 367491347978888 682202535304057
947289095111215 617031864207622 266929999670252
409140310770140 598511664798393 661026615991841
773298904879060 956029680900125 722488152582400
950780447643645 125570735755705 195951570849152
498153355472745 425772682828307 932223938763799
324003553085 700128642958997 778716976840216
22956995880950 615114175232634 19874299520927
754887269467985 846909285891963 360288245174032
836826366514780 571249106749808 3074769252900
136306007913440 547743246239769 500547478522102
578542960414175 355875010968108 680176970668644
339752142675875 331012800993277 497855220833070
862587987619535 376663177056503 837870483709259
660994347629765 988546933337647 914311981693187
795343284410545 883458121480604 360945709849977
237561194594675 30679074098290 384023871164606
431478530373010 395949982913333 409820266423534
614648397404125 6116362802514 390416692714724
183910873727260 182187324843769 8699925849772
101992066486345 747130394934126 781117916084916
861421559093900 973405677107530 203256358369354
184585353937850 394244226035364 94302523777216
541965292009830 318687694505921 354150770655407
281390594122495 992838460289203 766862091524883
649665351077385 541330092242177 977415035866819
405532168322845 908095507837608 58705480357722
328296583243420 862480102931403 594969496360706
40201829931010 40712509833361 583733079634482
759553620683155 408138975356055 258019720739242
409150205306445 815794701702063 308441961287289
572935508766260 792898773114465 353445276905198
63748728192370 163393589349265 941918456915543
634333723187740 276828286009877 531761026273757
318528220728880 801713679859802 949537954599338
249403283515360 910911161740424 422098319103242
324333591755370 761237721961265 97600217851291
625815801210045 213342419569017 164504197744787
286793601817125 450535988220988 184915985799838
962694488129975 590250195975867 774573921546336
402456176375415 740082870683153 443889283047368
912860083521115 507271033606589 975500497846399
514685733836260 92902352352727 240524041262723
747976284465780 702952844334692 307919623779772
72170287452140 195169237401422 963819342599837
205423915330650 716324776885099 722004803825792
906422492303680 488886890415002 880014347119360
88098591957425 932514546696682 559423132683610
559801234399275 323300531063726 784370422759519
289061366397930 539009684232660 961614256920773
349328746774325 439730227485073 58475349445354
255724511643095 725363436687923 485595563619082
454261851527300 270401192708403 445937066186011
952546026916895 213560253271143 727880583991425
114442646192210 515279514759135 66025915815615
850695675876995 866883995305249 872458766899808
151064289306335 611413746432 220967150160274
412823410770805 290285348827822 480939519737397
17866232603350 170344232294003 839361623545686
943060200146785 26956325109981 406403374708368
6103995272940 159165435805464 408749807667374
412489805957525 385039269775342 240348840340574
573880229455260 433346769520173 920677567902599
175102719970545 354319863044109 706084355959445
385420429073895 741471697029510 465243023671373
377246345334350 219113394244926 370005200870318
923607543593200 42522142514373 372458927752387
721625692879245 402437009763226 600713470388528
773995402646425 585332297703110 377934836807224
131125865388765 375756185528143 718110954640302
196912916179730 138674164825072 817625238985572
416595668222545 671866261135672 57070679046361
730279945829640 789945696732444 52573923007154
851135492182895 526622900196225 686205561036752
879397775017930 815449952505557 519851698177623
151206398680030 551884924659826 948448155048685
644236753478695 717088444012552 843190471601985
AC output:

Code: Select all

534068
478080
687881
503945
522456
611739
722243
695751
621025
116003
270947
815969
340109
492261
223831
436800
128320
708631
593875
612177
772131
045465
340740
915737
442560
527589
140625
992825
188925
189237
813023
285227
843456
966231
596864
488353
268527
502767
201764
473920
957023
472640
459541
216960
706176
119104
313153
150000
111623
539200
208075
903803
819715
447785
726639
128568
891102
740736
500096
462881
690063
755328
063843
096385
282560
313436
106944
866989
146873
956736
100352
579024
314133
925509
589111
407139
613707
109375
883553
546688
802750
100215
589005
585216
232256
867953
922379
810700
299712
358468
121984
188480
926747
021952
473800
419136
878625
190032
843101
990448
Check input and AC output for thousands of problems on uDebug!

Masum
New poster
Posts: 9
Joined: Tue Jul 10, 2012 11:39 am

Re: Problem 12653(Bus Coloring)

Post by Masum »

Actually I made too silly a mistake. In the power function, I took the argument as power(Matrix M, int n) but n can be long long. This caused a loop in the function and hence the TLE.

Post Reply

Return to “Volume 126 (12600-12699)”