SRM 533: Failure

It was about time I had a bad match.

Chat
The chat before coding phase was more interesting than usual because Google engineers were in their lobby room and received questions. Google sent many widely known names in algorithm contests to represent them. What is clear is that google really pay attention to these silly algorithm contests at the time of employing new people. Hopefully TC will release a transcript of all the questions.

Div1 500 - The one with common rows and common columns
This problem beats me. I spent all the match trying to get a viable idea for it that I can prove. It seemed that it would be easy to submit a wrong idea. I kept getting lost in dead ends such as trying to find "something with flow" to solve it. A lot of people submitted a solution to it, which increased the amount of tension during the match for me.

Div1 250 - The one with energy
You have a vector of at least 3 elements. You gain score by removing an element that has an element to its left and an element to its right and then the product of these two other elements is added to your score. Return the maximum possible score.

First of all, since the numbers are always positive, the final vector will always be one in which only the original extremes are left. In other words, for 1,2,3,4 , the last vector will always be {1,4}.

Given a vector, {1,2,3,4,5,6} we know that the last operation will involve multiplying 1 and 6. The trick is to consider this last move. So, let's pick the last element we will remove: If we decide to remove 4 last, this means that we removed all elements that are not the extremes and are not 4 before this last move: {1, .. 4, ... 6 }. Now notice something else, In the previous steps, 1 and 4 and 4 and 6 won't get removed. Imagine the vector split in two parts: {1, 2, 3, 4} and {4,5,6} . We have to pick the best strategy to remove 2,3 or 5. We can treat these two cases as sub-problems of the original problem, because all of the elements are contiguous.

Thus, whenever you have an array with more than 2 elements. Iterate through all the possible elements we can remove as the last step. This will create two subproblems identical to the first. A recurrence comes from this observation, and since the elements will always be contiguous for each subproblem, you can just use dynamic programming.

struct CasketOfStar 
{ 
    vector<int> weight; 
    int mem[50][50]; 
     
    int rec(int a, int b) 
    { 
        int & res = mem[a][b]; 
        if (res == -1) { 
            res = 0; 
            // Pick c - the element we will remove last: 
            for (int c=a+1; c<b; c++) { 
                // if we remove c last, we can find the score of the sub-vector a..c 
                // and c..b to know the best strategy for the previous elements. 
                res = std::max(res, weight[a]*weight[b] + rec(a,c) + rec(c,b) ); 
            } 
        } 
        return res; 
    } 
     
    int maxEnergy(vector <int> weight) 
    { 
         this->weight = weight; 
         memset(mem,-1,sizeof(mem)); 
         return rec(0, weight.size() - 1); 
    } 
}; 

I had issues during the match. Although I thought of the general solution idea quickly. I didn't have it all figured out until after I began coding. So I had to do many corrections and think things through again. Was nervous because I switched to this problem late and I already knew a lot of people had solved both the medium and this problem.

Challenge phase
A lot of solutions failed during challenge phase. Seems 500 was easy to get wrong. I am not even sure I will pass 250 because there might be a mistake somewhere.

What do you think?
Did you like the match? I think the problems were interesting. I wish I was more creative and able to think the solution for 500.

Update: outcome
I like the outcome. I dropped around 30 points in rating, which is not a big deal. I still have more than 2100 points. A rating drop was bound to happen, and it is always nice when it happens lightly.