arpit_aditya's blog

By arpit_aditya, history, 3 weeks ago, In English

Stuck in the newbie Zone

So I started C.P around 18 months back and I have done DSA quite well, I can write code for basic algos quick,merge,topo,scc,kruskal,prims e.t.c I know some advanced algos which i keep on forgetting but I can quickly revise them. This was to give you background of my knowledge.On one of the community post I saw that you only need binary search and dfs to break out of newbie zone. However it does not seems to be the case with me, you can also look at my profile I have given quite ample amount of contest and still I have seen no progress.

Eventually I pondered over this question , Is competitive programming not meant for me ? Should I quit it?. Your guidance will be highly appreciated. Thank you!!!

Full text and comments »

  • Vote: I like it
  • -19
  • Vote: I do not like it

By arpit_aditya, history, 4 months ago, In English

So, I started Learning Dynamic Programming and I came across this question - Cherry Pickup 741

I am following simple approach of walking simultaneously from (0,0)->(N-1,N-1) && (N-1,N-1)->(0,0) if any point they are on the same cell I add it only once.

Here is my code-

class Solution {
    public int minCost(int row_start,int col_start,int row_end,int col_end,int grid[][]){
        if(row_start==grid.length-1 && col_start==grid[0].length-1){
            return grid[row_start][col_start]; //if the first person reaches last cell (n-1,n-1)
        }
        if(row_end==0 && col_end==0){
            return grid[0][0];//if the 2nd person reaches 0,0
        }
        if(row_start>=grid.length || row_end>=grid.length || col_start>=grid[0].length || col_end>=grid[0].length ||row_start<0 || row_end<0 || col_start<0 || col_end<0){//edge case
            return (int)-1e8;
        }
        if(grid[row_start][col_start]==-1 || grid[row_end][col_end]==-1){
            return (int)-1e8;
        }
        //intialising the vlaues of movement
        int right_up=grid[row_start][col_start];
        int right_left=grid[row_start][col_start];
        int down_up=grid[row_start][col_start];
        int down_left=grid[row_start][col_start];
        if(row_start==row_end && col_start==col_end){
            // if they are on the same cell only add once
            right_up=right_up+minCost(row_start,col_start+1,row_end-1,col_end,grid);
            right_left=right_left+minCost(row_start,col_start+1,row_end,col_end-1,grid);
            down_up=down_up+minCost(row_start+1,col_start,row_end-1,col_end,grid);
            down_left=down_left+minCost(row_start+1,col_start,row_end,col_end-1,grid);
        }else{
            // if they are on different cells add both of them.
            right_up=right_up+grid[row_end][col_end]+minCost(row_start,col_start+1,row_end-1,col_end,grid);
            right_left=right_left+grid[row_end][col_end]+minCost(row_start,col_start+1,row_end,col_end-1,grid);
            down_up=down_up+grid[row_end][col_end]+minCost(row_start+1,col_start,row_end-1,col_end,grid);
            down_left=down_left+grid[row_end][col_end]+minCost(row_start+1,col_start,row_end,col_end-1,grid);

        }
       
        return Math.max(right_up,Math.max(right_left,Math.max(down_up,down_left)));


    }
    public int cherryPickup(int[][] grid) {
       return minCost(0,0,grid.length-1,grid.length-1,grid);
    }
}

This is giving me wrong answer for the first testcase. I have seen some solutions where they are assuming two paths from start to end. saying that moving from (0,0) to (n-1,n-1) is same as going from (n-1,n-1) to (0,0) but then why is my solution giving me wrong answer?

Full text and comments »

  • Vote: I like it
  • -3
  • Vote: I do not like it

By arpit_aditya, history, 5 months ago, In English

Hey, fellow programmers. Hope you all are doing good.I don't want to waste your precious time so let's cut to the chase. As you can see I'm a newbie so pardon me if what i ask is way above my league. Believe me I'm trying but this competitive programming is difficult for me but sooner or later i will become good at this.

This was one of the questions asked in Amazon Hackathon round please help me solve this. Since I'm a newbie you can also share the links to article and knowledge resources that might be required to solve this. Please do not provide code directly as answer. Let me know how to solve and approach this problem.

The question is as follows-

/*****************************************

You are given N non negative integers namely-D1,D2,D3...DN. You have to find all the labelled trees that can be constructed such that the out-degrees of each vertex(1<=i<=N) is Dn. It is guaranteed that the sum of D1,D2....Dn is N-1.

Example test case- First line is number of integer and second line contains degree of each edges. Input-

4

0 1 0 2

--------------------------------------------------------------- Output- 5

A total of 5 labelled trees can be formed with given out-degrees.

Input-

5

0 1 1 1 1

Output-

125

A total of 125 labelled trees can be formed with given out-degrees.

*************************************************************/

Full text and comments »

  • Vote: I like it
  • -12
  • Vote: I do not like it