10247 - Complete Tree Labeling

[drewsome]

Hi,

I've been working on 10247, but I keep getting alternations between WA and TLE from our dear pal the judge. My program seems to work for the sample inputs. I also ran some other inputs on the program, and here's what I got:

3 6:
1562426428985838116716663847602053919993687706682744920691775
8744958199546630264802237721967380806696892330756741858402075
5507622062129402536831792096303812425155575036742659204190458
2498551746907027633839316542421370591453376229341910810176981
0714012749838397760438014193832135261807625714333233234513722
6481130716418113157184014622513314354933679168157916114107235
3954611569315444940492137110490705291723530485177044087316106
1401493323164247780845903608589631273520040636528697768615106
3527513457828695193551617033164981830497801739428829877691531
3876524608218970561580865505782375733576592914054207130769533
5833920543237254675056946500430178857831621311756371492777361
8482935405375913504118123870290743328543928367041870709181254
9039350824630266637879771959363368245465170333538033856754471
7919434226536732483924569391953454032342740090373684849929837
5319610582187859384514170568487091552266801013221294968869942
4379218965844254667239000397931372150621376330024122134138025
4853940226810293696177640419098445545704205177764021694338973
8358926324810202302466822531052799315778323796003899894292455
8268196422007313773155858863734967579481066684965391173683461
3625096709110604204475252077963928940342371835265118317930171
9076390858969250321112856456261964725283366390938287070315150
3488518398077628825957896676630913122523366985050403490299793
6603688874070907087428485524235623732559160365843830362657453
8015081752455632076818839219277900499079306338916360508099383
1300876378538403920365739752083293701336025929370623092264856
2608307881020545340389250289120538091819770767223292541030618
5630159645926116960236661113566995260011864522421875748669647
8744422649877323106298011112813464341865471383806409817363323
4294630376275206039318390073921042785559397629146256334167884
8519906691612326891947676936654485690706441049273235089601029
6176352400853225649785864825923643823393693175304614481721928
4603814559072877346652498804887350322211569952780283022382474
8890253082192142289548160307719802150883160144391918590378038
3308588186389208099366885700869755992623008111446664293271313
6066777957789067879274175813935010256359253189963948489831195
0733020192677159653402759890777582210793462091375116567172668
1304458578970417684946336965853266676655763901794045423039068
7757321966455677648554868183631034056704000000000000000000000
0000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000

2 7: 2434411425898660167340134123995914965137209025246851730007017
4751901314217005161062905584341466188423842651012693652591528
4822554973789784037398873503480650833540216594475907139644852
6252128249278116374587947952600937789575140974403104763945296
8408005213711806943825057607612078833127550780961233418879109
1918970300719886383496979853547718388432096993476608000000000
0000000000000000000000000000000000000

3 5:
5836131400126203592395137153585148232573038897260233148491512
3704018341172194132762048493612263794229316474184936030663276
4958523207542193417101375270813493546119782764502607968117325
5924015019404422690668320182267740620319363099933827028867728
1407499195305985918789330905621710753686109029296908342175944
9439534278989321020009298285008738232643732902586521355192690
5003591255521518489159536209344897987828520830084792087045885
6326970228684197816408894150214630674320564386168050370199043
1852424569531342072950406076505883750523730618382348251271797
5738851219466101404338685237289096299075862528000000000000000
0000000000000000000000000000000000000000000000000000000000000
000

5 1:
120

5 2:
34111736086958726676480000000

3 3:
35417271278873496315860673177600000000

20 1:
2432902008176640000

Could anyone check some (or all of these inputs/outputs for me? I'll also post my algorithm here, just for completeness:

[cpp]calcTree(int k, int d) {
bignum s = 1;
long long nodes = 0, tnodes = 0;

if (d == 0) {
return s;
}

for (int i = 1; i <= d; i++) {
nodes += exp(k, i);
}
tnodes = nodes;

for (int i = 0; i < k; i++) {
bignum a = ncr(tnodes, nodes/k);
bignum b = calcTree(k, d-1);
s *= a*b;
tnodes -= (nodes/k);
}

return s;
}
[/cpp]

Where ncr is just n choose r, and exp(k, i) is k^i. Any ideas/thoughts? I also use memoization in my answer, plus I use some precaclculated values for certain trees that take a long time to compute.

Any help is much appreciated!

[dieter]

[cpp]

bignum b = calcTree(k, d-1);
for (int i = 0; i < k; i++) {
bignum a = ncr(tnodes, nodes/k);
s *= a*b;
tnodes -= (nodes/k);
}
[/cpp]
Moving the statement outside the loop will make your program run fasetr. I think your output is correct, and how about this one:
5 4:
257457894324384299068847782405450594613969210149433334028403
130097309826668306299621317974861032642934187864360989415653
217268257852830142760812892903533189691128508996607064579609
080094337621802857055807584488445453755237031821299854874927
648883574881010890919754894799814839485168732900641905469482
575706605084916622076622622143389711599645629918744604944309
558383945311605930546124570594554591086317635774942204633941
803626300180317018867620589284418579419002070062641715060709
167615151790835890786485062541913514420051289248468952201344
151613540926245389949971968850519430713047057564344522268073
369314081339735457016964918829681216612087943616210180383220
939740820850950357679961960918368157299302068534906402486026
262672062053338940763733657824914874217421071852583122040437
257521380145162316936514478802176376881714689547916037689740
128840385614451780724259395819927655094838959617331271576004
734517164557263935301312498097023918829696072461604160752091
834315765235848940907759642434568911275567358420981303154154
358494815718240443111020677376179619385165176893056127522873
884611705489989337564084429469792600182103727389470689710982
731458848648066717896542298837505469316187352817821412410797
436283199616592904779233384085520357946517326028308576217212
009958580561296535292197454581845296636447268199107086496115
658190322615675661281048845811726456625236070277520138098833
156856165368861493067467912895727599307295582096309361724277
883418064037815148918806105569042656626023312200159009818614
505009604443774765389909572653690935343013165152383822244315
354612962156599050240000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000

[abishek]

hi, for this question i precalculated all the values like this
is there something badly wrong, i got the answer for all the sample input in the previous post and i would like to know if there are any tricky cases.

Code: Select all

[c]
for (i=1; i<= 21; i++)
for(j=1; j<= 21; j++)
if(i*j <= 21)
{
// precalculate the value of number of kary tree with branching factor i, depth j
}

int k,d;
while(cin>>k>>d)
{
cout<<val[k][d]<<endl;
}
[/c]