This was my first non TCO div1 SRM, as last SRM advanced me to division 1. With this extra joy, came the nervousness of competing in a room where almost everyone else was supposed to be much better then me. Anyway, I had decided to focus on just the easy problem, as solving it alone would have raised my probability of gaining in rating. After struggling with it initially, I came up with the right approach to solve it. Unfortunately, I couldn’t get the implementation subtleties correct till the end, and ended up with non positive score. After the SRM, I entered practice room to validate that my DP was right, and also tried a simpler recursive method that worked as well.

**DIV-1 Easy, DIV-2 Medium; CuttingBitString:**

Constraints restrict the string to no more then 50 characters. So first thing I did was to generate binary representation of all powers of 5 with length no more then 50. Turns out there are only 22 such integers.

**DP Solution:**

A string of length 0 has 0 possible splits. For any string of length “i” greater then 0, we find solution to it by the following recurrence:

dp[i] = min(dp[i], 1+dp[j]) for j=0 to i-1, if dp[j]>=0 and substring(j, i) is power of 5)

If solution not found, then dp[i] = -1.

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 56 57 58 59 60 61 62 |
#define INF 100000 class CuttingBitString { public: int getmin(string S) { string arr[] = {"1", "101", "11001", "1111101", "1001110001", "110000110101", "11110100001001", "10011000100101101", "1011111010111100001", "111011100110101100101", "100101010000001011111001", "10111010010000111011011101", "1110100011010100101001010001", "1001000110000100111001110010101", "101101011110011000100000111101001", "11100011010111111010100100110001101", "10001110000110111100100110111111000001", "1011000110100010101111000010111011000101", "110111100000101101101011001110100111011001", "100010101100011100100011000001001000100111101", "10101101011110001110101111000101101011000110001", "1101100011010111001001101011011100010111011110101"}; vector<int> v(S.size()+1); v[0] = 0; for(int i=0;i<S.size();i++) { v[i+1] = INF; for(int j=0;j<=i;j++) { string s=""; if(v[j]>=0) { for(int k=j;k<=i;k++) { s+=S[k]; } } for(int k=0;k<22;k++) { if(s==arr[k]) { v[i+1] = min(v[i+1], v[j]+1); } } } if(v[i+1]==INF) v[i+1] = -1; } return v[S.size()]; } }; |

**Recursive:**

A non dp recursive solution using the same array of pre generated powers of 5 is as following. Try each power of five if it is a prefix of the string, if it is, then you can you split the string into two, the prefix, and the rest of the string. Recursively do the same with the second part of the string, and your solution is 1 + (ways of splitting the rest of the string). You return the minimum of the solutions found with trying each power of 5 as the prefix.

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 |
#define INF 100000 string arr[] = {"1", "101", "11001", "1111101", "1001110001", "110000110101", "11110100001001", "10011000100101101", "1011111010111100001", "111011100110101100101", "100101010000001011111001", "10111010010000111011011101", "1110100011010100101001010001", "1001000110000100111001110010101", "101101011110011000100000111101001", "11100011010111111010100100110001101", "10001110000110111100100110111111000001", "1011000110100010101111000010111011000101", "110111100000101101101011001110100111011001", "100010101100011100100011000001001000100111101", "10101101011110001110101111000101101011000110001", "1101100011010111001001101011011100010111011110101"}; class CuttingBitString { public: int solve(string S) { if(S=="") return 0; int r = INF; for(int i=0;i<22;i++) { if(S.find(arr[i])==0) { r = min(r, 1+solve(string(S.begin()+arr[i].size(), S.end()))); } } return r; } int getmin(string S) { int r = solve(S); if(r==INF) return -1; return r; } }; |

**Conclusion:**

It was an easy problem. I rushed a bit too quick into trying to implement my initial complex solution instead of trying to come up with a simpler solution. And once I did come up with a simpler solution, the time wasted on trying to get a complicated solution to work made it worse to get implementation right for the simpler one. Result; I got demoted to div2 :(.

oh wow :)

;p