Seedr

 Seedr.cc is the best torrent Stream site free service I had ever seen. I used a lot of sites before, also paid sites, but I had never seen like this site and it’s amazing services before. Seedr allows to you to download torrents very quickly, sometimes you don’t have to wait, because when I add torrent link, I found it’s already there :) and ready for downloading it in very high speed. It also makes you streaming the torrent videos without the need of downloading. And it’s surprised me when I didn’t have to pay for it, because it’s gives you a lot of offers to get more free space. The site gives you 2 GB limit after registration. By inviting 8 friends you got 500 MB for each one, and there a lot of others methods to increase you space, and it’s totally free. I highly recommended this amazing site, you’ll never find site like this in the whole internet. Click to my invite link, and you’ll get 500 Mb more space to be 2.5 GB as total starting space: https://www.seedr.cc/?r=151880

LeetCode 931. Minimum Falling Path Sum

Link:- https://leetcode.com/problems/minimum-falling-path-sum/

Summary:

Given a square array of integers A, we want the minimum sum of a falling path through A.

A falling path starts at any element in the first row and chooses one element from each row.  The next row's choice must be in a column that is different from the previous row's column by at most one.

For Example:
Input:

[[1,2,3],[4,5,6],[7,8,9]]

Output:
12

Logic:

Given array A with row ->n and column ->n

now create matrix say ans[n][m]

copy first row of A into ans

i.e ans[0] = A[0]

Why?

since we can start from any column in first row

now for rest of the row and column say i and j (1<=i<n, 0<=j<m)

ans[i][j] = A[i][j] + min(ans[i][j-1], ans[i-1][j-1], ans[i-1][j+1]

return min(ans[n-1])

i.e minimum of all values in last row

Why?

because we can end at any column of last row.

To View My Solution:

https://github.com/shivam04/codes/blob/master/leetcode/minimum-falling-path-sum.cpp

LeetCode 1140. Stone Game II

Link:- https://leetcode.com/problems/stone-game-ii/

Summary:

Alex and Lee continue their games with piles of stones.  There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i].  The objective of the game is to end with the most stones. 

Alex and Lee take turns, with Alex starting first.  Initially, M = 1.

On each player's turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M.  Then, we set M = max(M, X).

The game continues until all the stones have been taken.

Assuming Alex and Lee play optimally, return the maximum number of stones Alex can get.

For Example:
Input:

[2,7,9,4,4]

Output:
10

Logic:

You can easily solve this question recursion.

So Alex will try to get the maximum point as he is playing optimally

if player == 1 (or Alex)

 alexPoint = max(alexPoint, sum[s to s+x-1]  stoneGameIIUtil(piles, s+x, max(x,m), n ,1-p));

also, Lee is playing optimally and try to reduce Alex points

if player == 0 (or Lee)

 alexPoint = min(alexPoint, stoneGameIIUtil(piles, s+x, max(x,m), n ,1-p));

1<=x<2*M

Will this solution gives TLE?

Yes

as 1<=N<=100 (total number of piles)

We can't use recursion here.

How can we optimize it?

One solution that I think of is using memorization. We can create a matrix say dp

and store current state dp[s][m][p]

s -> starting index

m -> for picking stones from piles i.e (1<=x<=2*m)

p -> 0/1 (Lee/Alex)

Now if we reach this state again we don't need to compute again and return dp[s][m][p]

(Yahi battein to bad me yaad  ayengi 😛)

Can we further optimize it?

Yes.

For calulationg sum[s to s+x-1]

we can use prefixSum array 

so sum[s to s+x-1] will be prefixSum[s+x-1] - prefixSum[s-1]

To View My Solution:

https://github.com/shivam04/codes/blob/master/leetcode/stone-game-ii.cpp