Project Euler #82: Path sum: three ways Discussions |

Sort 11 Discussions, By:

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.

4 years ago+ 0 comments

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

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

12 months ago+ 0 comments

I used Dijkstra's Algorithm (using heapq (similar to priority queue) of Python), graph is such that there is a source vertex and n^2 other vertices. Edges from source vertex to the vertices of the first column are having weight = grid(i,0) for i=0 to n-1 and all other vertices (i,j) have incoming edges (from left to right, up to down, down to up) with weight=grid(i,j). Then take the minimum dist(i,n-1) for i=0 to n-1.
Works fine in Python 3 but avoid creating a "Graph". Use list not dictionary. dict is very slow. Only for source, adjacent vertices have a condition, for all other vertices, the conditions are same so it can be solved without actually building a graph with adjacency lists and costs.
Even Dijkstra's Algorithm worked in O(n^2) by just adding one extra vertex.

1 year ago+ 0 comments

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;
}

Load more conversations