Google Code Jam Qualification Round 2019 - My submissions and Post Contest Analysis

Hello World!

As promised in my last post, here are my submissions along with post contest analysis for GCJ Qualification Round 2019.

In all, I made 2 successful submissions (and one mis-formatted output submission that costed me some penalty) and with that I was able to score sufficient points for clearing the round and advancing to the next level! :) 👊
I also went through the third problem in the contest and came up with a solution but I couldn't push it in in time. I'll upsolve and share the remaining un-submitted problems here shortly.
So, without much ado, here are the problems that I did:

Problem 1: Forgone Solution
The solution I coded was written with all 3 and specially the largest hidden test set in mind. As N can be upto 10^100 digits long in the largest test set, it makes the problem obviously a string manipulation problem and thus the below solution is such.
Worst case run time complexity: O(n) where n is the number of digits in N.


Problem 2: You Can Go Your Own Way
This was a maze problem the solution for which was again written with the time constraints for the largest test set in mind. The solution you want should be no more than O(n^2) complex which was possible with a classic dynamic programming approach to it which I had used. All went well and visible tests got passed but the hit was the hidden test set which was executed post the end of contest where my solution couldn't satisfy the memory constraints. The verdict was Memory Limit Exceeded. It turns out that I have been spendthrift in the memory actually and some optimizations could be deployed to avoid that. I'll up-solve it with a more space-optimal solution for the problem and test it under the practice round but until then, the DP solution is as follows.
Worst case run time complexity: O(N^2) where N is the input - length of one side of the NxN maze.



Congratulations to all those who made it through to the next round! Hope to see you coming out with flying colors! See you at the score board of the hall of fame!!

As always, feel free to point out optimizations or share your suggestions to my approach to the problems shared here. Until then,

Love and Luck,
~glassrose