July 25, 2016
Problem statement
Julia spent 3+ hours to score 13 out of 40 points, she enjoyed the time to work on the problem.
A few issues: wrong answer, time out, run time error.
More than 3 submissions, failed to solve time out issue.
1.
C# solution
2. Add memorization using Dictionary to save time, failed to solve issues.
C# solution
3. add one more memorization, failed to solve issues.
C# solution
4. Review code and then add some comment, and analyse design issues:
C# solution
Review the design, try to find the flaws - a few ideas to improve timeout, no run-time error issue.
review code and then add comment for function countingPalindromes:
| /* |
| * use two loops |
| * |
| * get 0110 pairs |
| * get 1001 paris |
| * |
| * Think about DP solution - dynamic programming - not working, too complicate |
| * |
| * brute force solution: |
| * 0 - start char, end char, and then, count how many possibilities |
| * Go through O(n*n) case, for any two 0 in pseudo string, check in-between |
| * |
| * For example: |
| * 001010110 |
| * |
| * The above case, there are 5 '0', |
| * position of '0' is 0, 1, 3, 5, 8, |
| * So, any two '0' combinations are 5*4/2*1 = 10 |
| * |
| * A: 0, 1, in between, there is no chars, n/a |
| * B: 0, 3, 2 chars in between - "01", count how many '1' in the substring, only 1. |
| * C: 0, 5, 4 chars in between - "0101", two one inside, so how many combination |
| * of 11, only 1 choice. |
| * D: 0, 8, 7 chars in-between - "0101011", four one's in the substring, how many combination - 4*3/2 = 6 choices |
| */ |
Add comment for function getPseudoString(...)
| /* |
| * using 0 and 1 to construct the string |
| * 1001 |
| * 0110 |
| * |
| * There are 26 chars in alphabetic string, any two combination is 26*25/2*1 > 250 |
| * Instead, using 0 and 1 to stand for two distinct characters. |
| * for example, abab |
| * 0101 |
| * So, we can conclude one thing: |
| * ababa |
| * 01010 |
| * or |
| * 10101 |
| * So, use memorization, 01010 and 10101 should be same key |
| * See if this can solve time out issues - July 25, 2016 |
| * |
| * reverse of string should be same key |
| */ |
It took Julia more than 3 hours to gain 13/40 point, but learning experience was so great, and she enjoyed the coding experience.
Starting from brute force solution, she made some progress to gain 13 points; go through optimal solution - DP, should be next step.
Statistics:
450 score 40/40
1600 score above 12/40
Total submission: 2180
Facts about HackerRank:
aiming brute force, 30% score.
Dynamic solution:
detail from editiorial notes.
The idea of DP from the above website:
string length is n
pattern to search
xyyx
xy ends position at i - iterate from 1 to n-1,
denote l[i]
yx starts at position i - iteration from i to n-1
denote r2[i]
yx starts at position >=i
denote r[i] = r2[i] + r2[i+1]+...+r2[n-1]
So, to get a solution:
Iterate i from 1 to n-1
sum of l[i] * r[i]
And one more thing,
r[i] = r2[i] + r[i+1]
The idea Julia tried on July 24, 2016 -
suppose that T[i] is the short palindrome like "xyyx" at end of string i, how to construct T[i+1]?
Follow up after 8 months
C# code
Follow up
8/25/2017
I go through the code, and evaluate the code. The fact is that the code is too complicate for a medium level algorithm. Based on the past code contest experience, the code should be very short and concise.
I will put some code review on my last practice, and then write a solution to help the dynamic programming algorithm practice and learning. Make it part of 10 step series.
