SPOJ Dynamic Programming: KNAPSACK

Today I started with solving Dynamic Programming problems and the first one on the refresher list was the classical 0/1-Knapsack.

I found an online judge, SPOJ, testing solutions to this problem here: https://www.spoj.com/problems/KNAPSACK/

Here is my accepted(https://www.spoj.com/status/KNAPSACK,chandniverma/) solution to the same:

import java.util.*;
import java.lang.*;

class Main
{
 public static void main (String[] args) throws java.lang.Exception
 {
  Scanner sc = new Scanner (System.in);
  int s = sc.nextInt();
  int n = sc.nextInt();
  
  int[] size = new int[n+1];
  long[] val = new long[n+1];
  for (int i=1; i<=n; i++) {
   size[i] = sc.nextInt();
   val[i] = sc.nextInt();
  }
  sc.close();
  
  long[][] memo = new long[n+1][s+1];
  for (int i=0; i<=n; i++) {
   for (int j=0; j<=s; j++) {
    memo[i][j] = -1;
   }
  }
  System.out.println(getMaxVal(size, val, s, n, memo));
 }

 private static long getMaxVal(int[] size, long[] val, int s, int n, long[][] memo) {
  if (n<=0 || s<=0)
   return 0;

  if (memo[n][s] != -1)
   return memo[n][s];

  if ((s-size[n]) >= 0) {
   return memo[n][s] = Math.max (
    val[n] + getMaxVal(size, val, s-size[n], n-1, memo),
    getMaxVal(size, val, s, n-1, memo)
    );
  } else {
   return memo[n][s] = getMaxVal(size, val, s, n-1, memo);
  }
 }
}

This solution works with a complexity of O(n*s) where n is the number of items under consideration and s is the size or capacity of the bag.

You can always find my SPOJ profile with solved problem list at https://www.spoj.com/users/chandniverma/.

You can also checkout my recent-most submissions at SPOJ on https://www.spoj.com/status/chandniverma/.

Feel free to share optimisations and improvisations in comments below!

See ya next time!

<3✌

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

[Problem3 SPOJ:ROBOTGRI] A problem for lovers of mazes!

PROBLEM: http://www.spoj.com/problems/ROBOTGRI/

This was a tough nut!

Its a graph problem. Its actually a combination of 2 problems in one! I have voted it as hard and given it my recommendation.

I went through the following resources (none has the actual solution but all serve as hints) to finally come up with a solution for it:

https://www.cs.bu.edu/teaching/alg/maze/
https://www.hackerearth.com/practice/notes/dynamic-programming-problems-involving-grids/
http://www.geeksforgeeks.org/count-possible-paths-top-left-bottom-right-nxm-matrix/
http://www.geeksforgeeks.org/count-number-ways-reach-destination-maze/
https://www.youtube.com/watch?v=PwxGTHraMNg&feature=youtu.be
http://www.geeksforgeeks.org/applications-of-breadth-first-traversal/



SOLUTION: https://github.com/glassrose/CPP_Problem_Solving/blob/master/SPOJ-ROBOTGRI.cpp
Tested and Accepted: http://www.spoj.com/status/ROBOTGRI,chandniverma/

Time complexity in the worst case: O(n^2 + E)
where n = number of rows (or columns) in the grid
and E = number of edges in the connected graph containing the starting cell 'S'.

Space complexity: O(n^2)