java - HackerRank Grid Search challenge - Code Review Stack Exchange

java - HackerRank Grid Search challenge - Code Review Stack Exchange

This is usually a cause for concern:

Solution solution = new Solution();

Programming contests do not generally require much object design. And in this particular case, instance methods just obfuscate reading. Make them public static. And if it gets so big that you need to divvy it up, do it properly, then.

This is usually a cause for concern, too:

    }catch(IOException e){          e.printStackTrace();      }

Just throw the exception, if you cannot do anything with it. And some automated judges show you the STDERR but not STDOUT, so you may be wasting your chance to see whether something went wrong or you returned wrong answer, and what went wrong. (Just knowing if your program has thrown an exception is good. If the automated judge does not support exception but supports process exit codes, you do a System.exit if an exception thrown.)

Performance

Some contests test your code with just small and large data sets, which means you need to find and algorithm with good average complexity. Some contest, such as ACM, tests the code also with the known worst case scenarios of the best known algorithms that could be used to solve the problem. In that case you need to find good worst case complexity.

Some contests have inputs to weed out naive implementations as your current one. One such case would be 1000X1000 grid of 1s, and 500X500 pattern of 1s with a 2 in the bottom right corner. Against such a case you can try an algorithm like :

• Scan the pattern, find the row with most diversity (e.g. with the most elements which have a different value to its right)
• for each row in the grid do a KMP substring search.
• for each match compare the rest of the pattern in the grid, using the row and column offset of the match.

Which, I believe, will have a complexity : O(R(C+c) + m(rc)), where m is the number of the matches for the pattern row used; which can still be bad for large m. In that case you can do a search for a pattern column in parallel (real or simulated).

Read full article from java - HackerRank Grid Search challenge - Code Review Stack Exchange