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 | |
| */ |
Starting from brute force solution, she made some progress to gain 13 points; go through optimal solution - DP, should be next step.
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]?
C# code
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
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.
I’ve tasted success and I’m hungry for more. I’ll prove I’ve got what it takes to win. #CreateYourMark pic.twitter.com/jansdjv9pG— Lucas Pouille (@la_pouille) May 20, 2016
