All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

K Cut and Product
Tag(s):

Algorithms, Dynamic Programming, Easy, Two dimensional

Problem
Editorial
Analytics

You are given an array $$A$$ of $$N$$ elements. Now, you need to perform exactly $$K$$ cuts in the array such that the array is divided into $$K + 1$$ non-empty subarrays. Now, after the array is divided into different parts you need to take the product of elements in each of the part and then take the sum of all these products. Since, there are lots of ways to partition the array into $$K + 1$$ subarrays so you need to print this sum of products over all possible cuts. Print the value of this sum modulo $$720720$$.

Note: Please checkout the sample explanation carefully for better understanding of the problem.

Input Format
The first line contains an integer $$N$$ as input that denotes the total number of elements in the array.
The next line contains $$N$$ space-separated integers that denote the elements of the array.
The next line of the input contains an integer $$K$$ that denotes the total number of cuts that need to be made on the array $$A$$.

Output Format
In the output, you need to print the sum of products of all the subarrays across all the possible different cuts modulo $$720720$$.

Constraints
$$2 \le N \le 100$$
$$1 \le K \le N - 1$$
$$1 \le A[i] \le 10^9$$

SAMPLE INPUT
4
1 2 3 4
2
SAMPLE OUTPUT
35
Explanation

There are 3 ways to perform 2 cuts in the given array:

1 | 2 | 3 4
1 | 2 3 | 4
1 2 | 3 | 4

For the first cut, the sum of products is 1 + 2 + 3 x 4 = 15
For the second cut, the sum of products is 1 + 2 x 3 + 4 = 11
For the third cut, the sum of products is 1 x 2 + 3 + 4 = 9
So, the final sum is 15 + 11 + 9 = 35

Time Limit: 2,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Danske IT

Challenge Name

Danske IT .Net Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Уведомления
View All Notifications

?