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.

Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

# | User | Rating |
---|---|---|

1 | Radewoosh | 3443 |

2 | tourist | 3372 |

3 | OO0OOO00O0OOO0O0…O | 3264 |

4 | ksun48 | 3176 |

5 | scott_wu | 3168 |

6 | CongLingDanPaiSh…5 | 3157 |

7 | Benq | 3154 |

8 | Petr | 3139 |

9 | Um_nik | 3138 |

10 | LHiC | 3118 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 195 |

2 | Errichto | 176 |

3 | rng_58 | 158 |

4 | Ashishgup | 157 |

5 | neal | 156 |

6 | tourist | 154 |

7 | Petr | 151 |

8 | PikMike | 150 |

9 | Um_nik | 149 |

10 | kostka | 147 |

10 | Swistakk | 147 |

10 | Vovuh | 147 |

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.

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.

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

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

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 :(

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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/11/2018 17:51:15 (d3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|