codechef is becoming worst platform for cp as there r a lot of cheaters on this site.
12 Likes
How the fuck are these companies recruiting/shortlisting based on these contests :- 
4 Likes
Are u kidding? The time limit should have been 2 seconds for this problem, not everyone uses for loop dp…
Recursion memoization solution even though correct and having same complexity as many codes that got AC’d, fails only because of such tight constraints. There should be some overhead not so high that a worse complexity solution passes but also not so low either, it is usually seen on codeforces where they give some room in bugaboos having dp tags.
13 Likes
I was also getting TLE for last 2 subtasks and wasted my 1.5 hour thinking what further optimization this question requires!
2 Likes
Can someone please explain how this recursive solution works and what are the dp states in this solution , I don’t usually write iterative so that’s why I want to understand this solution , but having problem especially with the third state
#include <bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC target (“avx2”)
#pragma GCC optimization (“O3”)
#pragma GCC optimization (“unroll-loops”)
/*
*/
const int INF = 1e18;
const int N = 1e5 + 2, K = 101, C = 2;
int cache[N][K][C];
int n, k, res;
vector a(N);
int go(int at, int grp, int take) {
// cerr << at << ’ ’ << grp << ’ ’ << take << ‘\n’;
if (grp == k + 1) {
return 0;
}
if (at == n) {
return -INF;
}
int mem = cache[at][grp][take];
if (mem != -INF) {
return mem;
}
if (take == 1) {
res = a[at] * grp + max({go(at + 1, grp, 1), go(at + 1, grp + 1, 0), go(at + 1, grp + 1, 1)});
} else {
res = max(go(at + 1, grp, 0), go(at + 1, grp, 1));
}
return cache[at][grp][take] = res;
}
void run_case() {
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= k; j++) {
cache[i][j][0] = -INF;
cache[i][j][1] = -INF;
}
}
cout << max(go(0, 1, 0), go(0, 1, 1)) << '\n';
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int T = 1;
cin >> T;
for (int t = 1; t <= T; t++) {
// cout << "Case #" << t << ": ";
run_case();
}
return 0;
}
Check this
my recursive with memorization solution with comments
solution
I hope it would be helpful.
1 Like
so even the subarrays do not have the weight is it the same dp or is there any short answer possible. not having weight I mean instead of multiplying sum with 1,2,3 we will just have sum of sums
As the contest ended I went to check the AC submissions for this problem and I was shocked to see all the top submissions were same . At first I thought to write a blog about this then I realized it’s better to have sleep than wasting time over this .
PS : - Codechef should also run plagiarism check after the contest ends like codeforces .
6 Likes
Can you explain me two things
- what actually is the parameter is started
2.when is started is zero you have writeen this
ll l = f(i, j, 1); // start from current index i;
it says start from current index, so if you start from current index then you should
have taken the value at current index in sum right
i mean wouldn’t this statment would be l = a[i]*j + f(i,j,1);
Also please explain how you though that isstarted parameter will be needed and what it’s actually telling for that state?
Also can you please explain how you though that isstarted parameter will be needed and what it’s actually telling for that state?
isStarted: it will show that we have already started our subarray(=1) or we need to start from here(=0).
why isStarted: let’s understand if not then how we know that for which subarray we are computing or is current subarray ended or need to start new subarray or we skip current element, so for these all we need one variable which isStarted in our case to predict the state for which we are computing.
isStarted==0: means we may start our subarray from here at (i) itself which is equivalent to have already started our subarray at i . f(i, j, 1). or we may start from next f(i+1, j, 0).
isStarted==1: we already have started so we may end our current subarray here at (i) itself which is equivalent to start another subarray from next f(i+1, j+1, 0) or we continue to next element which is f(i+1, j, 1) in both case we included a[i] to current subarray so we need to add it.
it will be equivalent to a[i]*j+f(i+1, j, 1). because we included a[i] here itself so we recur for next to avoid selection of already selected element.
Hope you understood it well, if not reply for further query.
1 Like
Most of them are from chandigarh university.
Return a different large negative value if it’s invalid. when c=1 it will keep returning and computing the same “infinity” and hence gives TLE.
Your AC code
(P.S. don’t blame problem setters before you analyze well)
1 Like
I got the ideal but lost with implementations
I am seriously irritated with soo many immediate submissions of CHESUB question. I got a -119, from being 5 star to 4 star because of too many cheaters above me in div1 ,me getting rank 180s. Now, these people won’t be penalized anyway for a long time. And even when they are penalized, my rating changes in not gonna change. This thing is just sad.
@admin ,
It’s a humble request from my side to do as codeforces does, like removing cheaters after each contest and provide the rating changes, which will make it more fair and reduce the number of cheaters in codechef. This mass copying via youtube/telegram groups has created a huge bad name for codechef and also reduces the value of codechef. Thank you.
7 Likes
This problem is very nice and definitely deserves an appreciation.
But its idea is taken from standard problem of maximum sum subarray and extended it to K subarrays maximum sum. so, many can have same type of solution.
Here is my solution ,It might benefit anyone. CodeChef: Practical coding for everyone
1 Like
I think your logic deserved AC.
Here’s your AC Code : # 47294178.
I just replaced the vector dp with static array dp and it worked. Same thing has happened to me on different OJs (and on this problem, yes again while upsolving), but that’s for old problems where time constraints were too strict.
That happens because vector are dynamic in nature and allocate some extra space than required which cause TLE. I’ve read it somewhere on a cf post and you can find more on it on google.
@nikiitp18 @rising_stark Maybe you guys are getting TLEd due to the same.
I hope someone from the panel can enlighten us on this.
4 Likes