aakarshmadhavan's blog

By aakarshmadhavan, history, 9 hours ago, In English,

Can someone give some hints? I have absolutely no clue how heap or anything else fits into this? Thank you!

Read more »

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

By aakarshmadhavan, history, 12 hours ago, In English,

I feel really very stupid right now.

I am stuck on this problem and it sounding very very easy. I know it has to do with stack but the stupid multiplication and division are making it hard for me.

What can I do?

Read more »

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

By aakarshmadhavan, history, 25 hours ago, In English,

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

The trouble here is how to separate the * and the other operators so I can have a "cumulative" sum. Because

1+3*2 is based on 3*2 and not 1+...

Please help me out. Thanks

Read more »

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

By aakarshmadhavan, history, 37 hours ago, In English,

So I posted a problem here and read the solution Link

But I read the solution and I try to understand but I am not able to apply the techniques from this to other places.

Can someone tell what are the applicable TECHNIQUES I can apply from that problem for example?

I do this a lot where I read the solution think "I got it," next time something I haven't seen pops up and I can't solve it.

Please help me out! Thank you

Read more »

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

By aakarshmadhavan, history, 2 days ago, In English,

The tag says "DP"

I have tried many DP forms

DP[i][j] = true if S[i, j] is a wraparound string`` TLE DP[i] = # of substrign ending at index i``` --> Can't find recurrence because of distinct condition.

Any help?

Read more »

 
 
 
 
  • Vote: I like it  
  • +1
  • Vote: I do not like it  

By aakarshmadhavan, history, 3 days ago, In English,

I am struggling very hard with this easy problem. I am not sure how to solve it at all.

How should I go to it? Should I form a graph?

Ie

Email -> Account ID -> Email -> Account ID etc...?

Thanks

Read more »

 
 
 
 
  • Vote: I like it  
  • +5
  • Vote: I do not like it  

By aakarshmadhavan, history, 5 days ago, In English,

Interesting DP problem:

The formula is supposed to be DP[i][d] = # of arithmetic subsequences slices ending at index i with difference d

Can someone explain how to come up with this and also how to come up with a recurrence relation?

Thanks

Read more »

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

By aakarshmadhavan, history, 5 days ago, In English,

This is supposed to be a greedy problem solved using stack.

Can someone give some ideas on how to proceed with it? I can't think of a proper solution or how to solve this through overall. Any help is appreciated!

If you can explain how to get the greedy strategy for example.

Read more »

 
 
 
 

By aakarshmadhavan, history, 6 days ago, In English,

The recursive is easy, but I am getting TLE and MLE on memoization.

Problem

class Solution {
    int N;
    int [][] stations;
    Map<Integer, Integer> map = new HashMap<>();
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        this.N = stations.length;
        this.stations = stations;
        for(int i = 0; i < stations.length; ++i){
            int [] s = stations[i];
            map.put(s[0], i);
        }
        map.put(0, -1);
        int sol = helper(0, startFuel, target);
        return (sol >= N + 1) ? -1 : sol;
    }
    
    public int helper(int station, int fuel, int target){
        if(station + fuel >= target) return 0;
        if(fuel <= 0) return N + 1;
        int cur = N + 1;
        for(int i = map.get(station) + 1; i < stations.length; ++i){
            int [] current = stations[i];
            if(fuel - (current[0] - station) < 0) continue;
            cur = Math.min(cur, 1 + helper(current[0], fuel - (current[0] - station) + current[1], target));
        }
        
        return cur;
    }
}

But I use 2D Array for memoization, it doesn't work because the array will be too big and also time complexity is bad.

Can someone help me?

Read more »

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

By aakarshmadhavan, history, 6 days ago, In English,

I would be very grateful if someone can help me out here:

Given two arrays `A` and `B` of equal length, the advantage of `A` with respect to `B` is the number of indices `i` for which `A[i] > B[i]`.

Return any permutation of `A` that maximizes its advantage with respect to `B`.

Length of `A` can be upto `10000`

Input: `A = [12,24,8,32], B = [13,25,32,11]`
Output: `[24,32,8,12]`

I want to learn how to do problems like this so I am trying to go step-by-step with the Greedy method.

1Q) Find the greedy strategy

1A) I am struggling very deeply here, I am unable to find a greedy strategy that might work. Can anyone give some idea and motivation here?

Read more »

 
 
 
 
  • Vote: I like it  
  • +6
  • Vote: I do not like it  

By aakarshmadhavan, history, 6 days ago, In English,

Hello!

I am struggling horribly hard with greedy algorithms to the point where I am not able to solve 90% of medium+ greedy problems.

I have watched many videos/lectures but its something very difficult for me.

do you have some resources you can share? How do you come up with greedy strategy and also how in the world do you convince yourself that this strategy will indeed work?

Thank you all

Read more »

 
 
 
 
  • Vote: I like it  
  • +2
  • Vote: I do not like it  

By aakarshmadhavan, history, 7 days ago, In English,

Hello, The problem is just

Count the number of palindromic subsequences in a string (they can be duplicates),
Input : str = "aab"
Output : 4
Explanation :- palindromic subsequence are :"a", "a", "b", "aa" 

Please help me come up with recursive solution.

public int sol(String s, int l, int r){
        if(r < l) return 0;
        if(l == r) return 1;
        
        int ans = 0;
        if(s.charAt(l) == s.charAt(r)){
            ans = 1 + sol(s, l + 1, r) + sol(s, l, r - 1) - sol(s, l + 1, r - 1);
        } else {
            ans = sol(s, l + 1, r) + sol(s, l, r - 1) - sol(s, l + 1, r - 1);
        }
        
        return ans;
    }

For test case s = "aaaa" this has failed (it is outputting 10 when the answer is actually 15)

Where am I going wrong? Thanks!

Read more »

 
 
 
 
  • Vote: I like it  
  • +8
  • Vote: I do not like it  

By aakarshmadhavan, history, 7 days ago, In English,
Given a string S, find the number of different non-empty palindromic subsequences in S, and return that number modulo 10^9 + 7.
A subsequence of a string S is obtained by deleting 0 or more characters from S.
A sequence is palindromic if it is equal to the sequence reversed.
Two sequences A_1, A_2, ... and B_1, B_2, ... are different if there is some i for which A_i != B_i.

**EXAMPLE - 1:**
Input: 
S = 'bccb'
Output: 6
Explanation: 
The 6 different non-empty palindromic subsequences are 'b', 'c', 'bb', 'cc', 'bcb', 'bccb'.
Note that 'bcb' is counted only once, even though it occurs twice.

I am trying to get a recursive algorithm/solution, I will memoize it later on.

So my algorithm right now is:

public int countPalindromicSubsequences(String S) {
        return (int) (helper(S, 0, S.length() - 1)%1000000007);
    }
    
    public int helper(String s, int l, int r){
        if(r - l < 0) return 0;
        if(r - l == 1) return 2;
        if(r - l == 0) return 1;
        int sol = 0;
        if(s.charAt(l) == s.charAt(r)){
            sol = helper(s, l + 1, r - 1);
        } 
        sol += helper(s, l + 1, r);
        sol += helper(s, l, r - 1);  
        return sol;
    }

This doesn't seem to work right now, can someone help me out and point the mistakes/improvements? Thanks

Read more »

 
 
 
 
  • Vote: I like it  
  • +7
  • Vote: I do not like it  

By aakarshmadhavan, history, 8 days ago, In English,

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible. Length of number at most 10002 and is length will be >= k. Num does not contain leading 0's (ie 0200) Input 1: num = "10200", k = 1 Output: "200" ----> Remove leading 1 and the number is 0200 = 200 (cant have leading 0 in answer) Input 2: num = "1432219", k = 3 Output: "1219"----> Remove 3 digits {4, 3, 2} to form "1219" which is the smallest

I think BFS can work but its a pretty shitty solution to use BFS (and it is edge-casey)

I am thinking of either greedy or dynamic programming. I am horrible at greedy and recognizing it. Can anyone help me out here?

Thank you all

Read more »

 
 
 
 
  • Vote: I like it  
  • +5
  • Vote: I do not like it  

By aakarshmadhavan, history, 9 days ago, In English,

I just need some very basic hints.

I am thinking of topological sort + BFS to start. What do you say? (No spoilers plz)

Read more »

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

By aakarshmadhavan, history, 9 days ago, In English,

I have a very interesting problem I feel you will all appreciate!

I have solved with brute force, but it is not fast enough. I am thinking I must use dynamic programming to help and I tried using memoization but still not fast enough.

Here is my code: Code link Java DP + recursion

Please give me sone hints how to make it faster (top down DP) or how to improve my code to get faster. Thank you

Read more »

 
 
 
 
  • Vote: I like it  
  • +1
  • Vote: I do not like it  

By aakarshmadhavan, history, 11 days ago, In English,
Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K.

If there is no non-empty subarray with sum at least K, return -1.

EXAMPLE:
Input: A = [2,-1,2], K = 3
Output: 3
---------
Input: A = [1,2], K = 4
Output: -1
---------
Input: A = [84,-37,32,40,95], K = 167
Output: 3

I have tried 2-pointers/sliding-window but it can't handle negative cases and gives the wrong answer. Can the geniuses of CF help me out on how to approach this problem?

Here is my (non working) code:

public int shortestSubarray(int[] A, int K) {
        int ptr = 0;
        int sum = 0;
        int sol = Integer.MAX_VALUE;
        for(int i = 0; i < A.length; ++i){
            sum += A[i];
            while(sum >= K){
                sol = Math.min(sol, i - ptr + 1);
                sum -= A[ptr++];
            }
            
        }
        return (sol == Integer.MAX_VALUE) ? -1 : sol;
    }

Read more »

 
 
 
 
  • Vote: I like it  
  • +28
  • Vote: I do not like it  

By aakarshmadhavan, history, 2 weeks ago, In English,

478B

Hello! I am completing 100 DivB problem in Ahmed's Ladder and I got stuck on this one. I feel this one has some underlying mathematics concept I am unaware of. Sadly there is no editorial either and understanding from other people's code was very difficult.

Can someone give me a hand in understanding the solution to this problem?

Thank you very much

Read more »

 
 
 
 

By aakarshmadhavan, history, 3 weeks ago, In English,

466C

This is problem 2 from Ahmed Aly's Div-C ladder. I got the O(N^2) solution easily but it did time out so I am thinking of some ways to go for the O(N) solution. I believe it will involve dynamic programming similar to knapsack.

I just need some hints, is this correct?

Thanks

Read more »

 
 
 
 
  • Vote: I like it  
  • +1
  • Vote: I do not like it  

By aakarshmadhavan, history, 3 weeks ago, In English,

I am following Ahmed Aly's Ladder for Div2C problems and I am ... stuck on the first problem :(

489C

I have made a recursive solution very easily but it has timed out. I am thinking of somehow memoizing my solution but I am not sure how to do it.

I thought of memorizing using accumulated sum, but that gives wrong answers for many cases. I am not sure how to memoize from recursive. Here is my code for lowest number for example:

Map<Integer, String> memo = new HashMap<>();
public String lowest(int sum, String cur){
		if(sum > s || cur.length() > m) return "-1";
		if(sum == s && cur.length() == m) {
			map.put(sum, cur);
			return cur;
		}
		if(map.containsKey(sum)) return map.get(sum);

		for(int i = 0; i < 10; ++i){
			if(cur.isEmpty() && i == 0) continue;
			String next = lowest(sum + i, cur + String.valueOf(i));
			if(!next.equals("-1")){
				map.put(cur, next);
				return next;
			}
		}
		if(!map.containsKey(cur)) map.put(cur, "-1");
		return "-1";
	}

Without memo it works, but with it I am failing. Thanks very much

Read more »

 
 
 
 

By aakarshmadhavan, history, 3 weeks ago, In English,

Problem 309 (Div2) C, Kyoya and Colored Balls

I am trying a DP approach and I couldn't think of bottom-up so I am thinking the solution might involve top-down DP approach. This seems like something that can be a variation of knapsack.

Can someone give non-revealing/small hints to pursue this problem? In general, how do you identify subproblems?

Thanks

Read more »

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

By aakarshmadhavan, history, 3 weeks ago, In English,

Hello,

I find myself very bad at greedy-algorithms and greedy-problems. I have found an easy problem online I have not been succesful myself in solving:

Problem

I am not confident in how to get to this problem.

My current idea is to sort the array according to height, and if height is equal then according to k. But I am not sure where to go on from here. Any help is appreciated greatly.

Read more »

 
 
 
 

By aakarshmadhavan, history, 3 weeks ago, In English,
Given an array arr[] consisting of 0’s and 1’s. A flip operation is one in which you turn 1 into 0 and a 0 into 1.You have to do atmost one “Flip” operation on a subarray. Then finally display maximum number of 1 you can have in the array.

I did not know this was a DP problem before I checked the tag. I am kind of confused how to proceed with the problem right now. Any ideas/hints are massively appreciated. So far I thought of some things which arent quite correct such as

  • DP[i] = Max # of 1's in subarray [0,...,i]
  • DP[i] = Max # of 1's in subarray [0,...,i] if you flip at index i

I am thinking second one might be an idea, but I can't find a optimal structure for "recursion."

Thanks

Read more »

 
 
 
 
  • Vote: I like it  
  • +4
  • Vote: I do not like it  

By aakarshmadhavan, history, 3 weeks ago, In English,

I am just trying to make a recursive solution for this but it is failing horribly. Here is the problem:

https://leetcode.com/problems/can-i-win/description/

In the "100 game," two players take turns adding, to a running total, any integer from 1..10. The player who first causes the running total to reach or exceed 100 wins.

What if we change the game so that players cannot re-use integers?

For example, two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100.

Given an integer maxChoosableInteger and another integer desiredTotal, determine if the first player to move can force a win, assuming both players play optimally.

You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300.

Here is my code so far:

class Solution {
    boolean [] used;
    int total = 0;
    int maxChoosableInteger = 0;
    
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        used = new boolean[maxChoosableInteger + 1];
        this.total = desiredTotal;
        this.maxChoosableInteger = maxChoosableInteger;
        int n = helper(true, total);
        System.out.println(n);
        return  n >= total;
    }
    
    public int helper(boolean turn, int sum){
        if(sum < total || sum >= 2*total) return 0;
        int cur = 0;
        if(!turn) cur = Integer.MAX_VALUE;
        for(int i = maxChoosableInteger; i >= 1; --i){
            if(used[i]) continue;
            used[i] = true;
            if(turn) cur = Math.max(cur, i + helper(false, sum + i));
            else cur = Math.min(cur, -i + helper(true, sum - i));
            used[i] = false;
        }
        return cur;
    }
}

It is not working for case maxChooseableInteger=4, desiredTotal=6. If you can help me that would be very much appreciated. I am struggling with these types of "minimax" problems. Thanks in advance.

Read more »

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

By aakarshmadhavan, history, 3 weeks ago, In English,

I found an interesting question on another OJ. I'm very bad at these types of questions (any suggestions to improve are also welcome).

486

For you all here this will be easy cake, I appreciate any help you can provide for me.

I tried 2 pointers-greedy, but I realized that the players will not always take the largest values from each of the left/right pointers of the array. I'm very stuck and can't find a way.

Any ideas/hints/suggestions (not too revealing). I really don't want to look up the solution before getting it myself.

Thanks

Read more »

 
 
 
 
  • Vote: I like it  
  • +1
  • Vote: I do not like it