You are not logged in. Please login at www.codechef.com to post your questions!

×

LAALRANG - EDITORIAL( IEMCO16)

8
1

PROBLEM LINK:

Practice
Contest

Author: Rohit Anand
Tester: Shashank Singh
Editorialist: Rohit Anand

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

COMBINATORICS,MODULAR MULTIPLICATIVE INVERSE

PROBLEM:

A Binary heap of n nodes is given.You have to answer how many possible permutations of nodes numbered from 1 to n is possible.

QUICK EXPLANATION:

Considering min heap,root is the smallest element. So, 1 will be root.Now, we will divide the remaining nodes into two sub-trees recursively by following the property of binary heap.

EXPLANATION:

We are provided with n nodes of Binary heap.Our aim is to arrange the nodes numbered from 1 to n such that properties of Binary heap remains intact. So, there are many such permutations possible for given n.

Lets consider min heap.Hence, Root will always be occupied by node 1.Now, the remaining nodes will be divided into left and right sub-trees. Since,Binary heap is a Complete Binary tree, so it will always be inclined towards left and every level except the last will always be completely filled.Hence, we will first try to fill the left sub-tree and then move the remaining elements in right sub-tree. In order to produce different arrangements, we have to do this process recursively such that property of binary heap is also followed. Now, we will fill the heap in breadth first fashion ie we will fill the nodes level wise ie the nodes in the lowest level will go to the left-sub tree and then any excess nodes will go to right-sub tree. Hence for given n number of nodes,the number of binary heaps with n distinct elements can be calculated as,

f(1)=1
f(n)=(n-1CL$*$f(L)$*$f(R))%MOD
, C is combinations and MOD=109+7


where L=No. of elements in Left Sub-tree.
R=No. of elements in Right Sub-tree.


L=2(k−1)−1+min(2(k−1),M)
R=2(k−1)−1+max(0,M−2(k−1))
M=1+N−2k
, M is number of nodes in bottom level of tree.


k is level number.

ALTERNATIVE SOLUTION:

There is one observation here.Lets calculate answers for some n values.
n=1, answer=1
n=2, answer=1
n=3, answer=2
n=4, answer=3
n=5, answer=8
n=6, answer=20 and so on.


This actually forms a pattern, which can be calculated using formula,


f(n)= ((n!)/(Product of size of all sub-trees in the heap)).You can verify it.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here
Tester's solution can be found here

asked 13 Nov '16, 17:33

rohit_0801's gravatar image

5★rohit_0801
3049
accept rate: 10%

edited 17 Nov '16, 23:30


Thanks for the shortcut approach ! Learnt something new :)

link

answered 13 Nov '16, 19:16

renesmee's gravatar image

4★renesmee
993
accept rate: 50%

2

@renesmee the alternative approach is just observation based!!:)

(14 Nov '16, 17:06) rohit_08015★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×900
×347
×55
×47
×23

question asked: 13 Nov '16, 17:33

question was seen: 925 times

last updated: 17 Nov '16, 23:30