We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #82: Path sum: three ways
  4. Discussions

Project Euler #82: Path sum: three ways

Problem
Submissions
Leaderboard
Discussions

Sort 13 Discussions, By:

votes

Please Login in order to post a comment

  • PatilKrishna
    2 years ago+ 1 comment

    This is my code it is not working on test case 5 and 6.

    #include <bits/stdc++.h>
    using namespace std;
    
    #define ll unsigned long long int
    #define MAX 1002
    
    struct Cell{
        int x, y;
        ll sum;
        Cell(){}
        Cell(int _x, int _y, ll _sum){
            x=_x, y=_y, sum=_sum;
        }
    };
    
    class compare{
        public:
            bool operator()(Cell a, Cell b){
                return a.sum > b.sum;
            }
    };
    
    ll pathsum(ll grid[MAX][MAX], int n){
    
        if (n==0)   return 0;
    
        int visited[MAX][MAX];
        memset(visited, 0, sizeof(visited));
    
        priority_queue<Cell, vector<Cell>, compare> que;
    
        for (int i=0; i<n; i++){
            que.push(Cell(i, 0, grid[i][0]));
            visited[i][0] = 1;
        }
    
        ll min_sum = INT_MAX;
    
        while (!que.empty()){
            
            Cell cell = que.top();
            que.pop();
    
            if (cell.y==n-1) {
                min_sum = min(min_sum, cell.sum);
                return min_sum;
            }
    
            //down
            if (cell.x+1>=0 && cell.x+1<n && cell.y>=0 && cell.y<n && visited[cell.x+1][cell.y]==0){
                visited[cell.x+1][cell.y]=1;
                que.push(Cell(cell.x+1, cell.y, cell.sum+grid[cell.x+1][cell.y]));  
            }
    
            //right
            if (cell.x>=0 && cell.x<n && cell.y+1>=0 && cell.y+1<n && visited[cell.x][cell.y+1]==0){
                visited[cell.x+1][cell.y]=1;
                que.push(Cell(cell.x, cell.y+1, cell.sum+grid[cell.x][cell.y+1]));  
            }
    
            //up
            if (cell.x-1>=0 && cell.x-1<n && cell.y>=0 && cell.y<n && visited[cell.x-1][cell.y]==0){
                visited[cell.x-1][cell.y]=1;
                que.push(Cell(cell.x-1, cell.y, cell.sum+grid[cell.x-1][cell.y]));  
            }
    
    
        }
    
        return (min_sum==INT_MAX)?-1:min_sum;
    }
    
    
    int main() {
    
        int n;        
        cin >> n;
        ll grid[MAX][MAX];
    
        for (int i=0; i<n; i++){
            for (int j=0; j<n; j++){
                cin >> grid[i][j];
            }
        }
    
        cout << pathsum(grid, n) << endl;
    
        return 0;
    }
    
    1|
    Permalink
  • kitchent
    4 years ago+ 1 comment

    After finishing Problem 83 with Dijkstra, I came back here to try this problem also with Dijkstra. It is interesting how the difference in the size constraint makes it implausible to construct the graph in advance. Doing so results in Runtime Error in Python for the last 3 test cases, which I suppose is related to the memory-heavy nature of dict data type.

    It is also noticeable that using Dijkstra is not necessarily faster than a naive loop-the-whole-thing-until-nothing-can-be-changed approach.

    1|
    Permalink
  • shashikrishna
    5 years ago+ 0 comments

    I am getting 2 test cases right. For rest of the cases segmentation faults are coming.

    1|
    Permalink
  • NourSamir
    7 years ago+ 1 comment

    this problem is so weird to me i tried to solve it using DP here is my solution idea : func(x,y) : check limits of the grid , if(y = last col) return grid[x][y] , minmize between func(x+1,y), func(x-1,y), func(x,y+1) + grid[x][y] . but this solution crash and goes into infinite recursive calls , hints pleaee

    1|
    Permalink
  • vizzy205
    3 weeks ago+ 0 comments

    I rotated the matrix so the starting becomes the right side and then used normal dp and in the end calculation i just take the minimum of last column. Sow why is my logic failing. It only passes 2 test cases and wrong answer for others but why?

    import sys
    l=[]
    for _ in range(int(input())):
        l.append(list(map(int,input().strip().split(" "))))
    
    n=len(l)
    cost=[]
    
    for i in range(n):
        cost.append(l[i][::-1])
    #print(cost)
    
    dp=[[0 for i in range(n)] for j in range(n)]
    
    for i in range(n):
        dp[i][0]=dp[i-1][0]+cost[i][0]
        
    for j in range(n):
        dp[0][j] = dp[0][j-1] + cost[0][j]   
    
    for i in range(1,n):
        for j in range(1,n):
            dp[i][j]=min(dp[i-1][j],dp[i][j-1]) + cost[i][j]
            
    #print(dp)      
    minimum=sys.maxsize
       
    for i in range(0,n-1):
        if minimum>dp[i][n-1]:
            minimum=dp[i][n-1]
            
    print(minimum)
        
    
    0|
    Permalink
Load more conversations

Need Help?


View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature