Pascal Pyramid

general
, ,
1

Can someone tell me how to solve this question that was asked in TCS CODEVITA ?

Pascal’s triangle giving binomial coefficients is well known. In this triangle, elements in each row can be obtained by adding two adjacent elements in the previous row. The pyramid of numbers we construct in this problem is similar to the Pascal triangle. We start with six numbers at the base of the pyramid, and construct the pyramid one layer at a time by adding the two adjacent numbers in the previous layer. For Example, starting with the numbers 1 2 3 4 5 6 in the base, we get the following pyramid.

The apex of the pyramid is filled with the product of the numbers in the row below instead of the sum.

![alt text][1]

In the above pyramid, the apex is filled with the number 48 x 64 =3072. The aim is to get the largest number possible at the apex of the pyramid.

The input will be a set of N positive integers. Six need to be chosen from these and arranged at the base to get the largest possible number at the top.
Input Format:

The first line of the input is N, the total number of integers that will be given.

The second line is a set of N (not necessarily distinct) comma separated positive integers from which the six numbers at the base need to be selected.
Output Format:

The output is one line with an integer representing the maximum value of the apex of the pyramid when six integers are selected and arranged suitably at the base.

Constraints:

N < 13

Integers provided for selection ≤ 100

Example 1

Input
8

10,4,74,61,8,37,2,35

Output

746415

Explanation

There are 8 numbers given, from which the 6 numbers in the base are to be selected and arranged so as to maximize the apex number. One way of doing this is in the figure below.

The product of the two numbers below the apex is 746415, which is the output.

![alt text][2]

Example 2

Input

10

37,93,56,10,77,82,72,82,39,7

Output

1786212
[1]: https://discuss.codechef.com/upfiles/PascalPyramid1.png
[2]: https://discuss.codechef.com/upfiles/PascalPyramid2.png

2

I have conjectured something to solve this problem but I cannot prove it at the moment or also I cannot test it as you have not provided any link for submission(Please do).

The goal here is to somehow normalize the two integers that you get at the end. In the second last layer, there will be three integers, the middle one should be as high as possible and the peripheral ones must be as normalized as possible. By “normalized” I mean that they must be as close to each other as possible.

To achieve this, you can choose the three integers from the list greedily and then do a recursive procedure. The recursion should go like this: Choose two adjacent pair from the sorted list of the 6 integers, put them as the 3rd and 4th element(This is to maximize the sum you get in the middle in the second last layer) and then for the next two elements you have the option to make them 2nd and 5th or 5th and 2nd element. Try out both and then same goes for the last pair of element. The complexity of this algorithm is O(6+2^3) = O(1) (:P). Since, the time limit if this problem is so low, you can also try out all the possible permutations of the highest 6 elements from the list.

I may be wrong, so please do point out my mistake if there is any :slight_smile:

2 Likes
3

Can you please provide your code?

4

I will say try to use all combinations, As there are only 6 numbers you have to permute so Complexity would be O(1). Here is my simple python code for same:

from itertools import permutations

def findAns(c):
    l = len(c)
    if l == 2:
        return c[0]*c[1]
    else:
        d = []
        for i in range(l-1):
            d.append(c[i+1]+c[i])
        return findAns(d)

n = input()
a = sorted(map(int,raw_input().split(",")))[-6:]
b = permutations(a)
print max([findAns(i) for i in b])

I think ista2000 method should also work and may be we can prove this by saying that middle elements will participate more in upper terms rather than side terms. Same statement can also be stated like, if two top terms are {a_1}, {a_2} then If would try to write {a_1} in terms of side and middle terms then coefficient of middle terms would be greater than side terms.

1 Like
5

http://ideone.com/1O1PrN Here you go. I have used the method of trying all permutations. The first one, even though more efficient, is hard to prove and is an unnecessary optimization.

6

If you notice then you will find that input is separated by comma(’,’) which is impossible for cin to ignore.

Please modify your code according to input giving in example section.

7

Thats just unnecessary implementation :confused:
But anyway, here you go: http://ideone.com/bxahpw

1 Like