Just as the title suggests, this SRM was a bitter disappointment for me. The easy problem was easy, but it took me some time to come up with a simplified solution. I made up for this delay with a successful challenge in the challenge phase. But the sad part was the medium problem. By reading the problem statement, I instantly knew it was a DP, and that the greedy solution won’t work. Part of my jumping straight to a DP solution was because of my current love for DP problems and thus being always preoccupied with a solution containing DP. But alas, things didn’t work as planned…

**DIV-2 Medium: CasketOfStarEasy:**

It didn’t take me long to come up with a basic skeleton for a DP solution to this problem. And even though I started on the correct lines, I couldn’t finalize a correct solution to the problem till the end. What is sad though is that while I was fixing my DP, many people had already submitted quite a fast solution to it. And as I later found out, it was because the variation of this problem for DIV-2 had such low constraints, that DP wasn’t necessary and it could easily be solved using brute force. The constraint on size of weights is <=10. So one can easily try all permutations on the length of weights, which at max would be 10P10 (actually 8P8 as you do not need to permute on the first and last weight). Later in the practice I was able to fix my DP, and also try the brute force solution.

**DP:**

Let dp[i][j] be the solution to the subproblem given weights from position i to position j. Our final solution will be dp[0][weight.size()-1]. Base case for this DP is going to be when the length of the subproblem is 3 or less. When 3, the solution is weight[i]*weight[j]. When less then three, the solution is 0, since we don’t have a middle element to eliminate.

When the length is greater then 3, we recursively solve the problem, by trying all possible partitions of the weights, and choosing the one yielding maximum energy. Thus the recurrence is:

dp[i][j] = 0 when j-i<2

dp[i][j] = weight[i]*weight[j] when j-i==2

dp[i][j] = max(dp[i][x]+dp[x][j]+(weight[i]*weight[j]) for i+1<=x<=j-1) when j-i>2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
[sourcecode language="c++"] class CasketOfStarEasy { public: vector<vector<int> > dp; vector<int> w; int rec(int i, int j) { int &r = dp[i][j]; if(r!=-1) return r; if(j-i<2) r = 0; else if(j-i==2) { r = w[i]*w[j]; } else { for(int k=i+1;k<j;k++) { r = max(r, rec(i, k)+rec(k, j)+w[i]*w[j]); } } return r; } int maxEnergy(vector <int> _w) { w = _w; vector<vector<int> > dp2(_w.size(), vector<int>(_w.size(), -1)); dp = dp2; return rec(0, _w.size()-1); } }; [/sourcecode] |

**Brute Force:**

For brute force solution, remember that we do not need to worry about the first and last weight, as these two are always going to be the last ones to get multiplied and added to the total energy. We would permute over the weights between first and last, and calculate which permutation yields the max energy.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
[sourcecode language="c++"] class CasketOfStarEasy { public: int calc(vector<int> w, vector<int> v) { int r = 0; for(int i=1;i+1<v.size();i++) { int k, l; k = l = i; for(int j=i+1;j<v.size();j++) { if(v[j]>v[i]) { k = j; break; } } for(int j=i-1;j>=0;j--) { if(v[j]>v[i]) { l = j; break; } } r += w[k]*w[l]; } return r; } int maxEnergy(vector <int> w) { vector<int> v(w.size()); int i=1; for(;i+1<v.size();i++) v[i] = i; v[0] = ++i; v[v.size()-1] = ++i; int r=0; do { r = max(r, calc(w, v)); }while(next_permutation(v.begin()+1, v.end()-1)); return r; } }; [/sourcecode] |

All this problem asks for is to check whether the given string is a concatenation of any number of these three strings, “pi”, “ka”, “chu”. The way I eventually solved it is to start iterating over the string, and discard the substring I have thus far iterated over if it equals to any of the three given strings. At the end, I’ll either have discarded the whole string, which would mean it entirely consisted of the concatenation of the given three strings and the answer is “YES”, or I will be left with some portion of the string, which would mean this left over portion wasn’t equal to any of “pi”, “ka”, or “chu”, and thus the answer is “NO”.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
[sourcecode language="c++"] class PikachuEasy { public: string check(string w) { string n=""; for(int i=0;i<w.size();i++) { n+=w[i]; if(n=="pi" || n=="ka" || n=="chu") { n = ""; } } if(n.size()==0) return "YES"; return "NO"; } }; [/sourcecode] |

**Conclusion**

I was able to get a challenge right, which I guess saved me from a total destruction in rating, but not enough. I ended up losing 45 points in rating. Meh!