Introduction
Life is not easy to compete the week code on Hackerrank, now Julia's ranking is following behind around 2900 out of 9985 at 11:54am, 1/14/2016. In order to get into the top 25%, she has to continue to work on the problem solving. It will be a lot of fun, a lot of mistakes, and trial and errors.
Have some images to show the progress first, comparison to one in the ranking of 2000:
Comparison to one in the ranking of 1000:
Julia just found out through the above graph, she had some issues with the algorithm The Great XOR. Spent 5 minutes to look into detail. She did not have any test case failure when she worked on the algorithm, the hackerrank has issues to run so slow, only at the end of day, all test cases will be run. She lost almost 10 points on the algorithm.
Usually, Julia likes to focus on easy and medium level algorithms, now in order to get a bronze medal, she has to learn to work on hard, advanced and expert algorithms, and try to do some research, read the discussion, and come out a simple idea to make extra points.
Lucky Number Eight
Julia did remember the algorithm was scored 18 instead of 10.80, now there are over 5 test case timeout. Six more test cases are added and she failed all of test cases because of timeout.
Comparison to rank 515
Instead, Julia can choose to walk around the outdoor, and get some physical exercise done first.
Study, research, code
Suffix Rotation - problem statement
1. Work on a test case:
string abc, there are 6 variations:
abc-> no rotation, answer is 0
acb-> abc, 1 rotation
bac->acb->abc, 2 rotations, second rotation starting from c
bca->cab->abc, 1 rotation, but circular rotation 2 times
cab->abc, 1 rotation
cba->bac->acb->abc, 2 rotations
2. Work on a test case with multiple instances of char:
string abcbb, what is difference?
abbbc,
if we use counting sort, we can determine the char by counting the number, and then calculate difference.
abbbc
c should be in position of 2, starting from index = 0, but actually it is in position of 4
rotation twice move 4 to 2, and also one of b is in position of 4, it should be in 2, also moved forward.
3. Work on a test case, abcdb,
so c should be in position 4, but it is in 2; 4 - 2 = 2, 1 rotation,
Try to use recursion solution to gain a few points first. And get some ideas about the issues.
Test Case: "cababc"
After more than 3 hours coding, at 10:13pm, Julia studied the discussion related to the test case, Julia found out that there are more than one solution, but need to find minimum move.
string cababc, using her naive solution, it will take 3 moves:
cababc ->
ababcc ->
aabccb ->
aabbcc
but the minimum move only needs 2 moves:
first 'a' is to use the second 'a' in the string "cababc", after first rotation, the string will be "abccab", and the second move is to use second b in the string "abccab", then final string "aabbcc".
How to get the minimum move? Use brute force, then calculate each option for any char from a to z.
Try to find something to think about:
cababc-> ababcc
abccab
From two strings to choose a small one, how to choose?
abccab -> aabbcc
ababcc -> aabccb
Google Search: suffix rotation minimum
ACM ICPC 2003 - the algorithm discussion is here.
One more reading is here.
Review Suffix Array and Longest Common Prefix
Study code review
Ashton and String Hackerrank
my favorite algorithm teacher - JS1
Actionable Items:
Work on the minimum value by simply comparison. Try to get at least 1 point first.
1. check into to document latest progress:
1/15/2017 11:05am
Using my code in C# to test the cases seen in the discussion - link is here.
test case 1: hackerrank - 6
test case 2: suffixrotation - 9
Using queue, and calculate all the possible selections.
But my C# submission still scores 0, pass test case 0, and time out 1 and 2, and runtime error test case 3 on 1.97s.
Rotation definition - misunderstanding
2. Need to look into the rotation definition, see if it is making sense or not.
Choose index bigger than prior move.
but, at the index, perform circular rotation in either direction.
So, work on the example, abcdefjghi, at index 6, with char j, can rotate clock wise or anti-clockwise.
jghi -> anti-clockwise -> ijgh -> hijg ->..
jghi -> clockwise -> ghij -> hijg ->..
So, work on the example: cababc
first work on index 0, work on second a,
clockwise, abccab
anti-clockwise, abaccb
work on first a,
clockwise, ababca
anti-clockwise, accbab
and then, work on second char - index = 1, there are 4 choices.
Because Julia's C# code has wrong answer, probably it is because of her rotation misunderstanding, missing two cases.
Good workout and great learning
Suffix Rotation C# practice - score 0, but perfect learning experience. Julia learns the importance to challenge herself to work on hard algorithm, come out the solution to work ok with sample test cases. She spent more than 5 hours to work on the problem on Saturday January 14, 2016 and two more hours on January 15, 2016.
Have a very excellent experience to work on string manipulation, queue, and also read all discussions to get basic test cases with expected results.
Make some points on hard algorithm in future week code contest. It seems that week of code is most popular contest on HackerRank, and the difficulty level is up-to-most-top-standard.
After contest
code study - link is here.
Code review - rewrite the C# code, study and debug, code is here.
More study on the code, and 2nd version before code review, code is here.
3rd version, code is here.
Status report
Julia finds out that there are so many solutions to study, and she does not have a lot of time to catch up so many things. Just go one by one.
She will work hard on the algorithm, through the contest, she understood that it is most important to stay humble, and she is thankfulness to enjoy the practice. Just learn one thing a time.
Actionable Items:
Work on the minimum value by simply comparison. Try to get at least 1 point first.
1. check into to document latest progress:
1/15/2017 11:05am
Using my code in C# to test the cases seen in the discussion - link is here.
test case 1: hackerrank - 6
test case 2: suffixrotation - 9
Using queue, and calculate all the possible selections.
But my C# submission still scores 0, pass test case 0, and time out 1 and 2, and runtime error test case 3 on 1.97s.
Rotation definition - misunderstanding
2. Need to look into the rotation definition, see if it is making sense or not.
Choose index bigger than prior move.
but, at the index, perform circular rotation in either direction.
So, work on the example, abcdefjghi, at index 6, with char j, can rotate clock wise or anti-clockwise.
jghi -> anti-clockwise -> ijgh -> hijg ->..
jghi -> clockwise -> ghij -> hijg ->..
So, work on the example: cababc
first work on index 0, work on second a,
clockwise, abccab
anti-clockwise, abaccb
work on first a,
clockwise, ababca
anti-clockwise, accbab
and then, work on second char - index = 1, there are 4 choices.
Because Julia's C# code has wrong answer, probably it is because of her rotation misunderstanding, missing two cases.
Good workout and great learning
Suffix Rotation C# practice - score 0, but perfect learning experience. Julia learns the importance to challenge herself to work on hard algorithm, come out the solution to work ok with sample test cases. She spent more than 5 hours to work on the problem on Saturday January 14, 2016 and two more hours on January 15, 2016.
Have a very excellent experience to work on string manipulation, queue, and also read all discussions to get basic test cases with expected results.
Make some points on hard algorithm in future week code contest. It seems that week of code is most popular contest on HackerRank, and the difficulty level is up-to-most-top-standard.
After contest
code study - link is here.
Code review - rewrite the C# code, study and debug, code is here.
More study on the code, and 2nd version before code review, code is here.
3rd version, code is here.
Status report
Julia finds out that there are so many solutions to study, and she does not have a lot of time to catch up so many things. Just go one by one.
She will work hard on the algorithm, through the contest, she understood that it is most important to stay humble, and she is thankfulness to enjoy the practice. Just learn one thing a time.
No comments:
Post a Comment