April 23, 2017
Introduction
It is most favorite algorithm in the contest. The algorithm is to find the optimal solution using DFS/ BFS, and also need to work on memorization to remove duplicate work, take care of timeout issue.
The problem statement is
here.
Julia spent so many hours to work on DFS - recursive function, or using a stack to do the work. Search the blog using DFS and then a lot of work will be listed
here. But Julia worked on in the contest more than 6 hours from 2 pm to 8pm, and she still could not figure out 5 wrong answer test cases.
Algorithm problem solving is such a fun activities. Through those long hours problem solving, Julia now knew so many things she had to learn and work on. This booking contest just let her know that how challenge the work will be if she lands a job to deal with millions customer.
Code review
The last submission in the contest scored 30 out of maximum score 50. The code is
here.
5 runtime error, not timeout.
The submission scored 25 out of maximum score 50, timeout 5 test cases at least. The code is
here.
The submission score 23.75, timeout and runtime error. The code is
here.
This is the great workout for Julia to learn the algorithm. She replaced recursive solution with a stack, and then she worked on the idea to avoid duplicated calculation. Every node is visited and then sum and maximum value will be recorded, only better candidate can allow to visit again.
From the score 23.75 to 30, Julia worked on the problem solving, understood how important to keep the code as simple as possible. She worked on her last submission to clean up code more than 30 minutes. She learned to discipline herself to show clean and readable code.
Actionable Item
4/26/2017 9:32pm
Work on the test case 9, and then figure out why it is a wrong answer for my submission. Look into the issue. Figure out the solution to pass all test cases first.
Post a code review once I can write a solution to pass all the test cases. Right now, there are 78 players scoring full score 50 in the contest.
Similar question "KnightL on a chessboard" was asked before, the link is
here. The code review is so great and Julia applied the tips from code review through the contest.
4/28/2017
After studying the test cases, Julia found one counter example of her assumption - her design flaw:
matrix
1 1 1 1 1 1 1
1 1 6 7 8
1 6 1 1 1
1 6
1 6
1 6
1 6 6 6 6 6 6
seconds is bigger than 14, for example 20 seconds, we need to count 6, 7, 8 for biggest path 1 1 6 6 6 6 6 6 6 6 6 6, extra 5 seconds will take a visit nodes 6 -> 7 ->8 and back to 6.
Follow up
May 14, 2018
I reviewed the performance of the algorithm in the contest. I did spend over six hours, and submitted over 20 times to try to get more points. And I read the last submission with a few functions, in total there are more than one hundred lines of code. It is too complicated and not practical approach from my point of view.
I believe that the dynamic programming solution can be found and should be easy and clean code. I like to plan to work on this algorithm again, and test how good I can be compared to more than 12 months ago.
Here is my C# algorithm written using dynamic programming.
