Solution for the second problem: Observe that only the number of trainings before the i’th training determines the strength and not the order in wich they took place.
DP(t,i)=0 if i > n;
DP(t,i) = max( DP(t+1,i+1),DP(t,i+1)+tvals[t]*arr[i])
tvals[t] stores the strength after t trainings,
arr[i] stores the XV coefficient for the cities.
The first part of max refers to training in the i’th city while the second part to battling.
Answer is given by
Overall complexity is
O(n^2) after memoization.
The first problem was overall easy, but my code was a little bit bad, as I used sets and comparators for the points.Complexity was
Expecting 200, but do not know about system testing.
I gave the exam in Kolkata, and the overall environment was good, although, there was a one hour delay.
However, no problems occurred during the exam.
EDIT : I gave the second solution too, but I think it is in the next page or later down in this page.