So a year of Topcoder SRMs came to end. It was the last SRM of the year today. It wasn’t an ideal SRM for me, should have done much better. But still, I ended gaining in rating, however little it be (+3).

Wasn’t such a great year for me to be honest. I had set a goal for myself much higher then where I eventually have got to. But slow and steady wins the race, eh? So I hope next year is much better for me. In order to improve faster, I’ve decided to blog every contest I participate in, specially Topcoder SRMs and Codeforces rounds.

**DIV-2 Easy; MinCostPalindrome:**

For a div-2 easy, I think this is a very nice problem. I hoped there would be many people not correctly getting the special case where a palindrome isn’t even possible. But to my surprise, not a single participant in my room seemed to have missed that. I initially submitted it with a slight bug, and had to resubmit, costing me precious points. All you have to do for this problem is to iterate over the string, from both directions, and checking that at each step, the characters from both ends are either same and not ‘?’, or both are ‘?’ in which case you add the minimum of the two costs (xCost, oCost) to the total cost, or only one of the two characters is a ‘?’ in which case you add the cost of the other character to the total cost. If both characters are not ‘?’ and also different, then a palindrome isn’t possible since you can’t change the two, and you return -1. In the contest I implemented it slightly different as you can see below. I first make all the changes to the string, and only at the end do I check whether or not a palindrome was formed.

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 |
[sourcecode language="c++"] class MinCostPalindrome { public: int getMinimum(string s, int oCost, int xCost) { int i=0; int j=s.size()-1; int count = 0; for(int i=0;i<s.size();i++, j--) { if(s[i]=='?') { if(s[i]==s[j]) { count+=2*min(oCost, xCost); s[i]=s[j] = 'x'; } else { count += s[j]=='x' ? xCost : oCost; s[i] = s[j]; } } } if(s!=string(s.rbegin(), s.rend())) return -1; return count; } }; [/sourcecode] |

There is a greedy solution to this one. Notice that any eel with length L that is a multiple of 10, requires (L/10)-1 cuts, to produce L/10 pieces of length 10. While those which are not multiples of 10, require (L/10) cuts to produce L/10 pieces of length 10. That is why to utilize our cuts efficiently, we first cut all those eels which are multiples of 10. Also, since we have limited number of cuts allowed, we want to start with the shortest eel, so that it is possible for us to end up with the last cut leaving two pieces of length 10 for us. Fox example if you have two eels of length 50, and 20, and you are allowed only one cut. If you first cut the eel of length 50, you will produce only one eel of length 10, and another of 40. But if you start with the 20 length eel, one cut will produce two eels of length 10. Thus, the solution is to sort the eels, first cut the eels which are multiples of 10. Then cut the rest of them.

I first submitted without realizing the need for sorting the eels. This caused a resubmission. Then I resubmitted once more, seeing that at each step, I am making a single cut, reducing the length of the eel by 10. I suspected this could cause a timeout. But in fact it won’t. Since the maximum value for allowed cuts could be 1000. And thus no more then that amount of steps would have been taken. This unnecessary resubmission, cost me dear precious points. :/

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 54 55 |
[sourcecode language="c++"] class Cut { public: int getMaximum(vector <int> eL, int mC) { bool flag = true; int count = 0; sort(eL.begin(), eL.end()); int cuts; while(mC && flag) { flag = false; for(int i=0;i<eL.size();i++) { if(eL[i]%10==0 && eL[i]>10) { cuts = min(mC, (eL[i]/10)-1); count += cuts; mC -=cuts; flag = true; eL[i] -=(cuts*10); break; } } } flag = true; while(mC && flag) { flag = false; for(int i=0;i<eL.size();i++) { if(eL[i]%10!=0 && eL[i]>10) { cuts = min(mC, eL[i]/10); count += cuts; mC -= cuts; flag = true; eL[i] -= (cuts*10); break; } } } for(int i=0;i<eL.size();i++) { if(eL[i]==10) count++; } return count; } }; [/sourcecode] |

I couldn’t get this one right in the contest time. But there is a very nice and simple solution to this one. All we need to do is to take each pair of mosquitoes, and calculate at what time, if any, will be two apart by distance of 2*R. And then find all mosquitoes which are located between these two at the calculated instance of time.

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 54 |
[sourcecode language="c++"] class Mosquitoes { public: int getMaximum(vector <int> xI, vector <int> v, int R) { int r = 1; for(int i=0;i<xI.size();i++) { for(int j=0;j<xI.size();j++) { if(i==j) continue; double t1 = ((2.0*R)-xI[i]+xI[j])/(v[i]-v[j]); double t2 = ((2.0*R)+xI[i]-xI[j])/(v[j]-v[i]); if(t1>=0) { double t=t1; int rr = 0; for(int k=0;k<xI.size();k++) { double p = xI[k]+(double)(v[k]*t); double p1 = xI[i]+(double)(v[i]*t); double p2 = xI[j]+(double)(v[j]*t); if(p1>p2) swap(p1, p2); if(p>=p1 && p<=p2) rr++; } r = max(r, rr); } if(t2>=0) { double t=t2; int rr = 0; for(int k=0;k<xI.size();k++) { double p = xI[k]+(double)(v[k]*t); double p1 = xI[i]+(double)(v[i]*t); double p2 = xI[j]+(double)(v[j]*t); if(p1>p2) swap(p1, p2); if(p>=p1 && p<=p2) rr++; } r = max(r, rr); } } } return r; } }; [/sourcecode] |

**Challenge Phase and System Tests:**

I was hoping to get a few challenges right to make up for my resubmissions. But ever since I got bitten by wrong challenges, I have started to get very careful with challenges. This extra care led to no challenges for me, and thus no bonus points. Though a lot of solutions failed in system tests, as I expected and hoped ( ;) ), and thus I got a somewhat respectable standing at the end.