Hint needed in solving a problem from TCS contest!

So today there was a practice round of TCS’s coding contest and this was the toughest question. I tried to use DP to solve this but I am unable to divide it into subproblems (is it solvable by DP?) I just need a little hint on how to solve it!

Problem : Isotope
Scientist recently found a new element X, which can have different isotopes upto an atomic value of 199. Speciality of element X is that when two atoms fuse they produce energy multiple of their atomic value and forms an atom with atomic value of their multiple modulus 199.

So,

If atom1 with value 56 and atom2 with value 61 fuse.

They produce energy of 3416 KJ (56 * 61)

Resulting atom will have atomic value (56*61) mod 199 = 33

Scientists created a nuclear reactor to create energy by this method. Everyday they get several atoms of X from supplier in a particular sequence. Since this element highly radioactive they cant risk by changing its sequence. So each atom can fuse only with another atom nearby. Nevertheless scientists can choose order of fusion thereby maximizing total energy produced.

Now, for given sequence of atomic values, output maximum energy that can be produced.


For Eg:

If sequence of atoms are

56,61, 2

Then they can produce 3416KJ by fusing 56&61 which results in an atom of value 33. Then they can fuse 33 and 2 to get energy of 66KJ. So total energy generated is 3482.

But if they cleverly choose to fuse atoms 61 & 2 first then they generate 122 KJ with a resulting atom of value 122. Then if they fuse 122 and 56, they can generate 6832 KJ. So total energy is 6954.

Hence Maximum energy that can be generated from this sequence is 6954.


Input Format

Input starts with a number specifying number of inputs(n) followed by n space separated integers specifying atomic values of n atoms.

Constraints:

0 < ai < 199

1 < n < 1000

OUTPUT:

For Valid Input, print

E, where E is Integer stating maximum energy that can be produced

For Invalid Input,print

INVALID INPUT

This is a classical dp problem…study matrix chain multiplication !! :smiley:
See the question Mixtures from medium section :https://www.codechef.com/problems/MIXTURES
Its the same question !!

2 Likes

Exactly what I was looking for thanks! Funny thing, I recently studied almost all classical questions related to DP except this one!

Haha …Its always the things u leave that come up !! :smiley:

1 Like