INOI 2017 Problem 2 - Training

Question

INOI 2017, Problem 2, Training
Ash and his Pokemon Pikachu are going on a journey. Ash has planned his route for the journey so that it passes through N cities, numbered 1, 2, …, N, and in this order.

When they set out, Pikachu has an initial strength of Sin as well as an experience value (XV) of 0. As they travel they may increase his strength and experience value in a manner to be described below. In each city, Ash can choose either to train Pikachu or let Pikachu battle the Gym-leader (but not both). The Gym-leader in ith city has experience E[i]. If Pikachu enters a city i with strength S and decides to train, then this increases his strength by the cube of the sum of the digits in his current strength.

For example, if he entered a city with a strength of 12, then training will increase his strength to 12 + (1+2)3 = 39. On the other hand, if he enters city i with strength S and battles the Gym-leader, then this increases his experience value XV by S*E[i]. Ash wants your help to find out the maximum XV that Pikachu can attain at the end of his journey.

Input
The first line contains two space separated integers, N and Sin, which are the number of cities, and the initial strength, respectively.
The second line contains N space separated integers, which correspond to E[1], E[2],..., E[N].

Output
A single integer which is the maximum XV that Pikachu can attain. Constraints

For all test cases you may assume that: 1 ≤ N ≤ 5000 0 ≤ Sin ≤ 109 0 ≤ E[i] ≤ 104

Subtask 1: For 10% of the score, N ≤ 20 and Sin = 1
Subtask 2: For further 40% of the score, E[i] = k for all i i.e. E[i] is some constant k, for all i Subtask 3: For further 50% of the score, No further constraints.

============================================================================

I managed to solve the first subtask by employing a brute force solution (O(2^n)). But for the second and third subtasks I don't think that a brute force solution will be optimal.
Also, for the second subtask I have a vague idea. Taking X to be the number of trainings, then N-X is the number of battles. By maximizing experience gained from N-X battles, we might get the answer, but I'm not sure if it's the right way.
I do not have any idea of how to solve the 3rd Subtask without using a brute force algorithm. Help would be appreciated. Edit: Link to the above question in the IARCS website : https://www.iarcs.org.in/inoi/2017/

Answer 1

It's a 2d dynamic programming question.

Note that if Pikachu trains in a gym, his strength increases, and if he fights a leader his experiences increases.

Also note that his strength depends only on his strength and nothing else

Therefore, it is possible to have a separate array, s[i] which computes the value of Pikachu's strength, assuming that he's trained i times.

This can be done using a single loop calling a function to calculate his increase in strength

It's is also possible to have a another array, dp[i][j], denoting pikachu's XP at the ith city, assuming that he's trained at j citites.

How would this work? It's easy -

dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]+(s[j]*e[i])

What this essentially does is takes the maximum value of pikachu training and pikachu fighting

If Pikachu trains, his XP won't increase, and he ends up training at 1 more gym. As a result, his xp would be the same as what it had been in the last city.

If pikachu fights, the number of gyms the number of gyms he's trained at remains the same(thus j doesn't change, while his a part of his xp would be the xp he had in the city before)

The next part, is essentially calculating whatevers been given to us in the question. It's E[i] as that's the E[i] is the ith value of the gym leader, as taken from the input and he's in the ith city

It's multiplied by s[j] as that's his total strength after training in j gyms

After this just find the maximum over all dp[i][j]

Answer 2

Here is how I would approach it. Yes, dynamic programming is a way to solve this problem efficiently.

A few notations to note before hand :

1. prefix[k] = sum of all terms from 0 to k ( k included ).
2. best[k] = max possible XV till term k ( k included )

Algorithm :

 1. prefix[0] = A[i];
 2. best[0] = cubed sum A[i]

 for array A:
    // max ( m,n ) --> max of m and n.
    3. best[i] = max ( cubed sum (prefix[i-1] + A[i]), best[i-1] * A[i]);

 return best[n]. n --> size of array.

In other words, you choose the max value of either including the current strength into sum or by competing.