====== Zadání - Building Binomial Heaps ======

https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=binomialheaps2

====== Řešení - Building Binomial Heaps ======

Úloha je především o dvou tématech, a to permutacích a binomiálních stromech. Nejprve je potřeba udělat si pořádek v pochopení permutací. Vstup dostanete jeko dvě permutace, které zároveň definují interval prohledávaných permutací. Je tedy potřeba naprogramovat funkci, která bude schopná iterovat od první permutace do té poslední. Example 1:

^  π  ^  VAL(π) ^
|  0  |  0 1 2  |
|  1  |  0 2 1  |
|  2  |  1 0 2  |
|  3  |  1 2 0  |
|  4  |  2 0 1  |
|  5  |  2 1 0  |

Zajímavé je že hodnota **π není potřeba počítat**. Bylo by to také dost nepraktické, protože může být dost velká (teoreticky až 100!) ;-).

Nyní co je to **extended permutation**? Není to nic jiného než že dáte původní permutaci (N/M)-krát za sebe a ke každé další sérii přičtete M. Uvedu příklad rozšířené permutace na Example 2:

VAL(EP(π, N)) = { 0 2 4 1 3 | 5 7 9 6 8 | 10 12 14 11 13 | 15 17 19 16 18 | 20 22 24 21 23 }

Dále je potřeba vytvořit binomiální haldu z rozšířené permutace. **Binomiální halda** je seznam binomiálních stromů hloubky N. Každý strom má 2^N uzlů a binomiální halda neopsahuje dva stromy se stejnou hloubkou. Které stromy budou zastoupeny se dá jednoduše rozhodnout z binárního zápisu celkového poštu uzlů. Příklad:

N = 25 >> 0b11001 >> halda budo obsahovat stromy hloubek { 0, 3, 4 } >> N = 2^0 + 2^3 + 2^4 = 1 + 8 + 16 = 25

Uzly jsou vkládány postupně v jasném pořadí, a proto můžeme dopředu jednoznačně rozhodnout, které hodnoty budou ve kterém stromu. Neboli prvních 16 hodnot bude uloženo v binomiálním stromu hloubky 4, dalších 8 hodnotu bude uložena ve stromu hloubky 4 a poslední do stromu hloubky 0. (Kdo mi nevěří, že to tak dopadne, ať si algoritmus vkládání podrobně projde) 8-)

Máme tedy tři stromy obsahující v příkladu 2: { **0** 2 4 1 3 | 5 7 9 6 8 | 10 12 14 11 13 | **15** }; { 17 19 **16** 18 | 20 22 **24** 21 }; { **23** }.

Za úkol máme vypočítat hodnotu (MAX(B(i)) - ROOT(B(i))) pro každý strom B(i). Kořen binomiálního stromu obsahuje vždy nejmenší hodnotu, a proto je to stejné jako (MAX(B(i)) - MIN(B(i))). Nepotřebujeme tedy vůbec znát strukturu binomiálních stromů, ale tato hodnota lze vypočítat pouze ze seznamu uzlů jednotlivých stromů z předchozího kroku. 

DIFF(BH) = MAX(B(4)) - MIN(B(4)) + MAX(B(3)) - MIN(B(3)) + MAX(B(0)) - MIN(B(0)) = 15 - 0 + 24 - 16 + 23 - 23 = **23** 

^ Není tedy potřeba vytvořit žádnou binomiální haldu, je to absolutně zbytečné!  ^


~~DISCUSSION~~


----
By stradja3: mám pocit, že jsem to maximálně optimalizoval a přesto mi to nestíhá "test05" - nemáte nějaký obecný trik jak to zrychlit? Na všechno používám obyčejná pole, co se týče složitosti, tak to mám: (počet_permutací)*(3*M+N)

By Rozion: muzete nekdo poradit jak generovat permutace mezi 1. a 2. permutaci?