I'm trying to come up with a recursive solution for this problem but I haven't been able to so far. Any advice/pointers here?

I tried 0-1 knapsack style but there is an issue with backtracking the array.

Often times I am stuck on problems that I am doing here and on other online judges. I am wondering how others here seek help in those cases and who they ask. I have tried asking with Blog but it doesnt seem like a good method.

What are you all doing for help and where are you going and who are you asking?

Thanks

I am struggling very badly for recursive + cache/memoize solution. I read some solutions online and the idea is to start with the last balloon and work up. Here is the code for the solution:

class Solution {
    int [][] cache;
    public int maxCoins(int[] nums) {
        cache = new int[nums.length + 5][nums.length + 5];
        for(int [] arr : cache)
            Arrays.fill(arr, -1);
        return helper(nums, 0, nums.length - 1);
    }
    
    public int helper(int [] nums, int left, int right){
        if(right < left) 
            return 0;
        if(cache[left][right] != -1) 
            return cache[left][right];
        for(int i = left; i <= right; ++i){
            cache[left][right] = Math.max(cache[left][right], nums[i]*getVal(nums, left - 1)*getVal(nums, right + 1) + helper(nums, left, i - 1) + helper(nums, i + 1, right));  /////HELP ME HERE!
        }
        return cache[left][right];
    }
    
    public int getVal(int [] nums, int index){
        if(index < 0 || index >= nums.length) return 1;
        return nums[index];
    }
}

I am having the confusion in the Math.max line. What is it nums[i]*getVal(nums, left - 1)*getVal(nums, right + 1)?

I understand the nums[i] part, but I do not understand the right + 1 or the left - 1. Can someone please help explain it? I would appreciate it very much.

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

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?

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

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

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?

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

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

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.

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?

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?

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

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!

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

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

I just need some very basic hints.

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

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

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

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

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

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

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

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:

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.