Codeforces Round 890 | Problem C: To Make Max | Binary Search, Constructive Algorithms

[@i_am_wiz]

Nice explanation. Try to post editorials from C onwards, they are really helpful

[@kunalsutar3946]

You were the last person to look upto. If even your explaination wasn't helping I would have left the problem entirely. It took me nearly 2 hours to figure out the whole thing but thank god I sticked with it. Excellent explaination !

[@shivamkushwaha1029]

This was very helpful and your explanation made it easy to understand. Good Job buddy !

[@harshtank7075]

Legendary explanation

[@vibhupandey9522]

what an amazing question this was

[@wizard-gg6et]

I watched the tutorial on codeforces but it was hard for me and I watched many editorials on TH-cam but also they were hard but yours was good for me thanks a lot ❤

[@kishorjha5028]

thanks sir perfect explanation better than cf editorial

[@pabitrakb5291]

Niceee

[@AbhinavVerma2602]

Please make Editorial of Problem E1 of the same Round.

[@kamikazewarrior9800]

very nice explanation better than the editorial

[@Mdenterprises8]

whats wrong in my code its cses dp question - projects recusrsive solution is giving right answer but as soon as im memoizing it its giving wrong answers
#define ll long long
#include
using namespace std;
ll solve(ll ind, ll prev, vector& nums, ll n, vector& dp) {
if (ind == n) return 0;
if (dp[ind][prev] != -1) return dp[ind][prev];

ll notTake = solve(ind + 1, prev, nums, n, dp);
ll take = INT_MIN;
if (prev == -1 || nums[ind][0] > nums[prev][1]) {
take = nums[ind][2] + solve(ind + 1, ind, nums, n, dp);
}

return dp[ind][prev] = max(notTake, take);
}
int main() {
ll n;
cin >> n;
vector nums(n);
for (int i = 0; i < n; i++) {
ll a, b, c;
cin >> a >> b >> c;
nums[i].push_back(a);
nums[i].push_back(b);
nums[i].push_back(c);
}
vector dp(n, vector(n, -1));
cout

[@MahirJain-z3b]

I tried this using dp. but for some reason it doesnt work. Tho the recursive logic is correct. I am somehow not able to memoize it. Can someone please help :
#include
#include
#include
typedef long long ll;
ll a[300009];
using namespace std;
int mod = 1e9 + 7;
int solve(vector &arr, int i, int k, vector &dp) {
if (i == 0 || k == 0) {
int x = *max_element(arr.begin(), arr.end());
if (k > 0 && arr[1] >= arr[0]) {
return max(x, arr[0] + min(arr[1] - arr[0] + 1, k));
}
return x;
}
if (dp[i][k] != -1) {
return dp[i][k];
}
int a = INT_MIN, b = INT_MIN;
if (arr[i] > t;
while (t--) {
int n, k;
cin >> n >> k;
vector arr;
for (int i = 0; i < n; i++) {
int a;
cin >> a;
arr.emplace_back(a);
}
vector dp(n, vector(k + 1, -1));
cout

[@i_am_wiz]

You are incrementing arr[i] only once…the optimal number of increments might be greater than one
So you need to run a loop from 0 till k applying all possible number of operations at the ith index.
But that will result in K transitions per state which will result in TLE, the answer will be optimal though

[@satyampatidar5848]

a[i]++
// Function call
Solve(a,b….)
a[i]-
this type of pattern only works if you going through all the possibilities (non dp)
try to understand why and how

[@MahirJain-z3b]

@@i_am_wizoh right, thanks got it