# Project Euler #81: Path sum: two ways

# Project Euler #81: Path sum: two ways

ajboss + 6 comments i thought this could help you https://www.youtube.com/watch?v=lBRtnuxg-gU

hruday_kohli + 1 comment [deleted]ajboss + 0 comments anytime (y)

varun21 + 0 comments thanks man

dnadanushka + 0 comments This was really helpfull.Thanks man!!

Rohit123456 + 0 comments Thanks man!

NickFi + 0 comments You made it too easy. I already started learning Dijkstra algorithm just to solve this problem :)

arijitsingh + 0 comments thaks

maja1668 + 1 comment I'm new to this. Is there a way to find out what the tests inputs are? I would love to know where my code stumbled.

learner_geek + 0 comments if u will run your program and it will successfully submitted then you will get test input and check your program.....if your code is perfect then it will pass the test ......otherwise check your program by test input putting inside one by one!!!!

Kevinagin + 1 comment A very nice problem to do after Euler 67.

Crafter_Artisan + 0 comments Yep. This is basically problem 67 rotated counterclockwise by 45 degrees

Rishab_arora + 1 comment Nice question to brush up your basic skills on dp !!

ryuzakaceAsked to answer + 0 comments yes my friend

vasanirushabh24 + 0 comments Why am i getting RUN TIME ERROR in all testcases after TC2.I think my code is perfact I have done it with memoization.If anyone have the reason please answer me.. EDITED: I noticed that it fails when N crosses exactly 500.

tangluo + 0 comments Wrong answers for some test cases for using integer array. Use long array to avoid this.

ErikTillema + 0 comments Easy DP, no Dijkstra or advanced math necessary.

NiceBuddy + 0 comments I dont understand whats wrong with this code. was too easy and tried many matrixes before submission; though went something wrong. only two tests passed!

#include <iostream> using namespace std; int main() { unsigned int N=1; cin>>N; if(N>=1 && N<=100) { unsigned long long int Mat[N][N], sumMat[N][N], ans=0; for(unsigned int r=0; r<N; ++r) { for(unsigned int c=0; c<N; ++c) { cin>>Mat[r][c]; if(r==0) { if(c!=0) sumMat[r][c]=Mat[r][c]+Mat[r][c-1]; else sumMat[r][c]=Mat[r][c]; } else if(c==0 && r!=0) sumMat[r][c]=Mat[r][c]+sumMat[r-1][c]; else { if(Mat[r-1][c]<=Mat[r][c-1]) sumMat[r][c]=Mat[r][c]+sumMat[r-1][c]; else sumMat[r][c]=Mat[r][c]+sumMat[r][c-1]; } } } ans=sumMat[N-1][N-1]; cout<<ans<<endl; } return 0; }

lfkopp + 1 comment to guarantee the lowest path, we need to run every possible combination. How can I optimize it? is gradient descent ok?

import sys n = int(input()) ar = [] ar2 = [] for a in range(n): ar.append([int(x) for x in input().split()]) ar2.append([0 for x in range(5)]) ar2[0][0]=ar[0][0] for i in range(1,n): ar2[0][i]=ar2[0][i-1]+ar[0][i] ar2[i][0]=ar2[i-1][0]+ar[i][0] for i in range(1,n): for j in range(1,n): ar2[i][j]=min(ar2[i][j-1],ar2[i-1][j])+ar[i][j] print(ar2[n-1][n-1])

nitishingde + 1 comment what u did IS THE most optimal algo..

using dijkstra's here is stupid coz it's

1.O(E+Vlog(V))..(using fibo heap)

2.O((E+V)log(V))..(using binary heap)

But since this is a dense graph(complete graph infact), E=n(n-1)/2 (nc2) and V=n^2 which makes dijkstra even slower whereas ur algo runs in exact O(n^2)....XD

lfkopp + 0 comments thanks! just saw the error. ii's not range(5)

vivek_reddy + 0 comments is the minimum path is single or multiple

Sort 22 Discussions, By:

Please Login in order to post a comment