Ah the elusive division one. Seems like I have to wait even more then I expected to be part of that elite(!). Because this SRM didn’t go that well for me. The easy problem was solved by many, very fast. My guess is that most of the people just looked at the examples, noticed a pattern, and submitted a solution on that. That is how I came up with the solution too, but I took a bit of time to prove the solution to myself. This delay caused me precious points that proved to be decisive in my rating lost at the end. The medium problem was a tricky one. I spent a lot of time trying to come up with a solution, and tried many fancy ways, but nothing seemed to work. In the very last few minutes I realized that there could be a brute force solution, but I went about implementing that the wrong way. With just one easy solved, submitted few precious seconds late then many, I ended up losing 28 points in my rating.

**DIV2 easy; P8XMatrixTransformation:**

By inspecting the example cases given, it is kind of intuitive to come up with the solution. If the number of 1s and 0s are same in the original and target pattern, the answer is “YES”. Otherwise, “NO”. The only rule allows you to permute any row or column any number of times. Since the only two characters in the pattern are 0 and 1, this allows you to move a 1, or 0, from any position, to any other position. Thus the only thing you need to do to come up with an answer is to count the number of 1s and 0s in both original, and target, and check for equality.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
string solve(vector <string> o, vector <string> t) { int o1, t1; o1=t1=0; for(int i=0;i<o.size();i++) { for(int j=0;j<o[i].size();j++) { if(o[i][j]=='1') o1++; if(t[i][j]=='1') t1++; } } if(o1==t1) return "YES"; else return "NO"; } |

Thanks to vexorian for explaining this one. A connected graph with N nodes and N-1 edges is a tree. This suggests that there could be a recursive solution, hinting at DP, because a tree is a recursive structure, where each node is the root of its own subgraph.

The solution is to start with a parent node, and the available children nodes. Connect one of the children nodes to the parent. For the remaining children, decide what amount connected to the parent, and what to the new child, maximizes the total score. The recursive function is “int calculate(int currentDegree, int availableChildren)”. If score for a node with this currentDegree and availableChildren is already calculated, return it. Otherwise, set the score to 0, from the availableChildren, connect one to the parent (if availableChildren>0), this increases the parent’s degree by 1. And from the remaining k children, where k=availableChildren-1, decide recursively how many connected to the parent, and how many to the new child, maximises the total score.

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 |
class P8XGraphBuilder { public: vector<int> s; vector<vector<int> > mem; int calculate(int cD, int aC) { if(mem[cD][aC]==-1) { mem[cD][aC] = 0; if(aC==0) { if(cD!=0) mem[cD][aC] = s[cD-1]; } else { for(int k=0;k<aC;k++) { mem[cD][aC] = max(mem[cD][aC], calculate(cD+1, aC-1-k)+calculate(1, k)); } } } return mem[cD][aC]; } int solve(vector <int> scores) { s = scores; vector<vector<int> > m(100, vector<int>(100, -1)); mem = m; return calculate(0, scores.size()); } }; |