Problem Links
Author: Ankur Goel
Tester: Ankur Goel
Editorialist: Ankur Goel
Difficulty
Medium
Prerequisites
Factorial
Problem
In a secret government project there are N investors who can invest X1,X2.........XN amount in millions such that X1,X2.........XN are all distinct i.e the amount they are ready to invest are different and the amount is not in fraction (i.e example X1= 1 million is valid but X1=1.5 million is invalid).There is a policy for forming groups among investors.Two investors who are ready to invest (suppose X1 and X2 amount individually) when grouped together,they feel confident and wish to invest more such that their total invested amount is equal to the sum of product of their individual investments added to their individual amount to be invested(i.e individually they could invest X1 and X2 amounts but after grouping together they can invest a total amount of X1+X2+X1*X2).Investors can further be combined with other investors and groups but by using the grouping policy mentioned before.
The Target is to find the maximum amount of money the government can fetch from the n investors.
Quick Explanation
Ans= (Factorial(N+1)-1)%M
Explanation
The Problem is simply based on the Factorial. Lets have a close look at this problem by with the help of an example.Let N=3, and X1=1, X2=2 and X3=3. It does not matter which two of the investors should be grouped at any point of time because whichever two you group at any time, the final answer will be same. Let us first group X1 and X2
=> X(1,2)=1+2+1*2=5
Now Lets group X(1,2) and X3
=> X(X(1,2),3) = X(5,3) = 5+3+5*3= 23 = Factorial(4)-1
In General for n investors, Ans= (Factorial(n+1)-1)%M
Use 64 bit int and take modulo at every step in calculating factorial to prevent the overflow.
Author's Solution
Author’s solution can be found here