#include #include using namespace std; typedef long long int lli; typedef pair p; #define all(x) (x).begin(), (x).end() #define allr(x) (x).rbegin(), (x).rend() #define sz(a) ((int)a.size()) #define rep(i, a, n) for (lld i = (a); i = (n); --i) #define fastIO ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); cout.precision(numeric_limits::max_digits10); // std::ios::sync_with_stdio(false); // Ab : ) vector dp(5005, vector(5005, -1)); // dp[0][0] = max cake can be eatten by bob vector c; // cake freq // alice opt_ play - eat min_taste // bob opt_ play - eat if he can prevent it eaten by alice int solve(int i, int x){ // idx_count, (alice - bob) = no. cake bob can eat if(i == sz(c)) return 0; // end of dp if(dp[i][x] != -1) return dp[i][x]; // already exists // bob able to eat (no. cake bob can eat - no. of cake at the idx) -> max(i-bob eats cake or ii-bob don't eat cake) if(x - c[i] >= 0) return dp[i][x] = max(c[i] + solve(i+1, x - c[i]), solve(i+1, x+1)); else return dp[i][x] = solve(i+1, x+1); // bob can't able to eat cake } int main() { fastIO; int tt; cin >> tt; while (tt--) { int n; cin >> n; vector a(n); // tast_i // greedy won't work here because bob can't choose specificaly which cake he can eat // actually he don't know the future of alice // bob has options to eat a particular eat Yes/No - DP map mp; // map to store freq of cake repI(i, 0 , n-1) { cin >> a[i]; mp[a[i]]++; } for(auto it: mp) c.push_back(it.second); int ans = solve(0, 0); cout
actually few mistakes #include #include using namespace std; typedef long long int lli; typedef pair p; #define all(x) (x).begin(), (x).end() #define allr(x) (x).rbegin(), (x).rend() #define sz(a) ((int)a.size()) #define rep(i, a, n) for (lld i = (a); i = (n); --i) #define fastIO ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); cout.precision(numeric_limits::max_digits10); // std::ios::sync_with_stdio(false); // Ab : ) vector dp(5005, vector(5005, -1)); // dp[0][0] = max cake can be eatten by bob vector c; // cake freq // alice opt_ play - eat min_taste // bob opt_ play - eat if he can prevent it eaten by alice int solve(int i, int x){ // idx_count, (alice - bob) = no. cake bob can eat if(i == sz(c)) return 0; // end of dp if(dp[i][x] != -1) return dp[i][x]; // already exists // bob able to eat (no. cake bob can eat - no. of cake at the idx) -> max(i-bob eats cake or ii-bob don't eat cake) if(x - c[i] >= 0) return dp[i][x] = max(1 + solve(i+1, x - c[i]), solve(i+1, x+1)); else return dp[i][x] = solve(i+1, x+1); // bob can't able to eat cake } int main() { fastIO; int tt; cin >> tt; while (tt--) { int n; cin >> n; vector a(n); // tast_i // greedy won't work here because bob can't choose specificaly which cake he can eat // actually he don't know the future of alice // bob has options to eat a particular eat Yes/No - DP for(int i=0;i a[i]; mp[a[i]]++; } for(auto it: mp) c.push_back(it.second); int ans = solve(0, 0); cout
1. alice wanna maximize the no of cakes and Bob wanna minimise it 2. Alice won't eat same cake twice 3. If bob don't want alice to eat cakes with value 3 then he will eat all cake with value 3 4. In example 1112233355788. Alice would plan to eat cakes in order 1 then 2 then 3 5 7 8 4. So let's suppose Bob want to eat all cakes with value 3 It will take him 3 moves But till now alice will have got 3 move so he eat cakes with value 1 2 3 so eating 3 not possible for Bob 5.so for each value we know if bob can eat all cakes with that value (eg all cakes with value 5) 6. So now problem turns into either pick or not Coin combination problem Hope you got it
@@abhinavkumar7801 no bro almost all the times recursive solution passes the codeforces testcases Sirf prefix sum optimisation wagerah k time p iterative dp jada acha hota hai Also check the pinned comment uske reply section m accepted recursive dp solution hai
@@abhinavkumar7801 Aapne har test case m dp ko initialise kra hai wo v dp of 5001 *5001 ko Toh let's suppose 100 test case hai Then sirf initialise krne m hi tle aa jayega That's why problem me sum of n of all test case doesn't exceed 5000 Aisa rhta hai Toh actually aapko dp ko initialise itna hi Krna hai jitna dp states ka need hai Matlab sirf dp (n*n) ko hi initialise kro -1 se
When good moves are 3 why 5 is pick not pick logic at 5 whose frequency is 2 , reason behind not picking 5?? If the problem was to find maximum tastiness Alice can achieve then dp is intuitive but here we have to find the number of cakes dp isn't intuitive.
1. alice wanna maximize the no of cakes and Bob wanna minimise it 2. Alice won't eat same cake twice 3. If bob don't want alice to eat cakes with value 3 then he will eat all cake with value 3 4. In example 1112233355788. Alice would plan to eat cakes in order 1 then 2 then 3 5 7 8 4. So let's suppose Bob want to eat all cakes with value 3 It will take him 3 moves But till now alice will have got 3 move so he eat cakes with value 1 2 3 so eating 3 not possible for Bob 5.so for each value we know if bob can eat all cakes with that value (eg all cakes with value 5) 6. So now problem turns into either pick or not Coin combination problem Hope you got it
@@og_prakash all explanation I understood by only question is why Bob would have two choices to pick and not pick 5? The cnt of unique cakes eaten by Alice won't change
Actually you are right if you take the example taken in problem but I was just trying to explain that you have choice to either pick cakes with value 5 and use your 2 moves here or use your move on some other cake Ok so let's take this example 1112233355789 In this example bob will not pick 5 but I was just trying to explain that bob has choice to invest 2 move to pick all cakes with value 5 or he use these moves to eat some other cake So in this case it's better for Bob to eat cakes with value 7 8 9 rather than eating 5 So it's dp problem that you have choice to pick or don't pick If he picks cake with value 5 he will need to use 2 moves here or if he don't choose cake with value 5 then he can use it on some other cake
write recursive relation and let suppose you have 3 variable in that recursive relation now you try to find out if you can reduce no of variables How to reduce variables? Let's suppose we have 3 variables (a,b,c) and c can be derived by a and b ( like c=a+b or c=n-a-b) then we say dp will have 2 variables a and b
#include
#include
using namespace std;
typedef long long int lli;
typedef pair p;
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define sz(a) ((int)a.size())
#define rep(i, a, n) for (lld i = (a); i = (n); --i)
#define fastIO ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); cout.precision(numeric_limits::max_digits10);
// std::ios::sync_with_stdio(false); // Ab : )
vector dp(5005, vector(5005, -1)); // dp[0][0] = max cake can be eatten by bob
vector c; // cake freq
// alice opt_ play - eat min_taste
// bob opt_ play - eat if he can prevent it eaten by alice
int solve(int i, int x){ // idx_count, (alice - bob) = no. cake bob can eat
if(i == sz(c)) return 0; // end of dp
if(dp[i][x] != -1) return dp[i][x]; // already exists
// bob able to eat (no. cake bob can eat - no. of cake at the idx) -> max(i-bob eats cake or ii-bob don't eat cake)
if(x - c[i] >= 0) return dp[i][x] = max(c[i] + solve(i+1, x - c[i]), solve(i+1, x+1));
else return dp[i][x] = solve(i+1, x+1); // bob can't able to eat cake
}
int main() {
fastIO;
int tt; cin >> tt;
while (tt--) {
int n; cin >> n;
vector a(n); // tast_i
// greedy won't work here because bob can't choose specificaly which cake he can eat
// actually he don't know the future of alice
// bob has options to eat a particular eat Yes/No - DP
map mp; // map to store freq of cake
repI(i, 0 , n-1) { cin >> a[i]; mp[a[i]]++; }
for(auto it: mp) c.push_back(it.second);
int ans = solve(0, 0);
cout
actually few mistakes
#include
#include
using namespace std;
typedef long long int lli;
typedef pair p;
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define sz(a) ((int)a.size())
#define rep(i, a, n) for (lld i = (a); i = (n); --i)
#define fastIO ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); cout.precision(numeric_limits::max_digits10);
// std::ios::sync_with_stdio(false); // Ab : )
vector dp(5005, vector(5005, -1)); // dp[0][0] = max cake can be eatten by bob
vector c; // cake freq
// alice opt_ play - eat min_taste
// bob opt_ play - eat if he can prevent it eaten by alice
int solve(int i, int x){ // idx_count, (alice - bob) = no. cake bob can eat
if(i == sz(c)) return 0; // end of dp
if(dp[i][x] != -1) return dp[i][x]; // already exists
// bob able to eat (no. cake bob can eat - no. of cake at the idx) -> max(i-bob eats cake or ii-bob don't eat cake)
if(x - c[i] >= 0) return dp[i][x] = max(1 + solve(i+1, x - c[i]), solve(i+1, x+1));
else return dp[i][x] = solve(i+1, x+1); // bob can't able to eat cake
}
int main() {
fastIO;
int tt; cin >> tt;
while (tt--) {
int n; cin >> n;
vector a(n); // tast_i
// greedy won't work here because bob can't choose specificaly which cake he can eat
// actually he don't know the future of alice
// bob has options to eat a particular eat Yes/No - DP
for(int i=0;i a[i]; mp[a[i]]++; }
for(auto it: mp) c.push_back(it.second);
int ans = solve(0, 0);
cout
1. alice wanna maximize the no of cakes and Bob wanna minimise it
2. Alice won't eat same cake twice
3. If bob don't want alice to eat cakes with value 3 then he will eat all cake with value 3
4. In example 1112233355788. Alice would plan to eat cakes in order 1 then 2 then 3 5 7 8
4. So let's suppose Bob want to eat all cakes with value 3
It will take him 3 moves
But till now alice will have got 3 move so he eat cakes with value 1 2 3 so eating 3 not possible for Bob
5.so for each value we know if bob can eat all cakes with that value (eg all cakes with value 5)
6. So now problem turns into either pick or not
Coin combination problem
Hope you got it
just simple and straight....thanks bro
Clearly explained 😊
Good Work bro
Easy to understand explanation
thanks a lot
Thanks bro! This was really simply great explanation right there. Keep up the good work!
Sahi samjhate ho bhaiya, isis tarah hindi me upload karte raho bhaiya thanks
Hi
I am getting tle after implementing the solution. Can you help me please?
#include
using namespace std;
#define INF INT_MAX
#define ll long long
#include
int dp[5001][5001];
void print(vector& diff)
{
for(auto it: diff)
cout t;
while(t--)
{
int n; cin >> n;
vector a(n);
for(int i=0; i> a[i];
cout
Recursive and Memoization solution does not pass on codeforces. So we have to make it iterative.
The iterative solution is below:
#include
using namespace std;
#define fastIO ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cout.precision(numeric_limits::max_digits10);
#define INF INT_MAX
#define ll long long
#include
int fun(int size, vector& nums)
{
if(size == 1) return 1;
map mp;
vector freqVec;
for(auto elem: nums) mp[elem]++;
for(auto it: mp)
freqVec.push_back(it.second);
int n = freqVec.size();
vector prev(n+1, 0);
for(int i=n-1; i>=0; i--)
{
vector curr(n+1);
for(int movesLeft=0; movesLeft= 0)
curr[movesLeft] = max(1 + prev[isPossible], prev[movesLeft+1]);
else
curr[movesLeft] = prev[movesLeft+1];
}
prev = curr;
}
int ans = prev[0];
return n - ans;
}
int main() {
int t; cin >> t;
while(t--)
{
int n; cin >> n;
vector a(n);
for(int i=0; i> a[i];
cout
@@abhinavkumar7801 no bro almost all the times recursive solution passes the codeforces testcases
Sirf prefix sum optimisation wagerah k time p iterative dp jada acha hota hai
Also check the pinned comment uske reply section m accepted recursive dp solution hai
@@abhinavkumar7801 Aapne har test case m dp ko initialise kra hai wo v dp of 5001 *5001 ko
Toh let's suppose 100 test case hai
Then sirf initialise krne m hi tle aa jayega
That's why problem me
sum of n of all test case doesn't exceed 5000 Aisa rhta hai
Toh actually aapko dp ko initialise itna hi Krna hai jitna dp states ka need hai
Matlab sirf dp (n*n) ko hi initialise kro -1 se
@@og_prakash oh okey got it.
Thank you very much for clearing
When good moves are 3 why 5 is pick not pick logic at 5 whose frequency is 2 , reason behind not picking 5?? If the problem was to find maximum tastiness Alice can achieve then dp is intuitive but here we have to find the number of cakes dp isn't intuitive.
1. alice wanna maximize the no of cakes and Bob wanna minimise it
2. Alice won't eat same cake twice
3. If bob don't want alice to eat cakes with value 3 then he will eat all cake with value 3
4. In example 1112233355788. Alice would plan to eat cakes in order 1 then 2 then 3 5 7 8
4. So let's suppose Bob want to eat all cakes with value 3
It will take him 3 moves
But till now alice will have got 3 move so he eat cakes with value 1 2 3 so eating 3 not possible for Bob
5.so for each value we know if bob can eat all cakes with that value (eg all cakes with value 5)
6. So now problem turns into either pick or not
Coin combination problem
Hope you got it
@@og_prakash all explanation I understood by only question is why Bob would have two choices to pick and not pick 5? The cnt of unique cakes eaten by Alice won't change
Actually you are right if you take the example taken in problem but I was just trying to explain that you have choice to either pick cakes with value 5 and use your 2 moves here or use your move on some other cake
Ok so let's take this example
1112233355789
In this example bob will not pick 5 but
I was just trying to explain that bob has choice to invest 2 move to pick all cakes with value 5 or he use these moves to eat some other cake
So in this case it's better for Bob to eat cakes with value 7 8 9 rather than eating 5
So it's dp problem that you have choice to pick or don't pick
If he picks cake with value 5 he will need to use 2 moves here or if he don't choose cake with value 5 then he can use it on some other cake
@@og_prakash thanks a lot 👍
nice explanation bro , thnx a lot
good explanation brother
🥰🥰😘😘
🙏🙏🙏
how to identify variables in dp?
write recursive relation and let suppose you have 3 variable in that recursive relation now you try to find out if you can reduce no of variables
How to reduce variables?
Let's suppose we have 3 variables (a,b,c) and c can be derived by a and b ( like c=a+b or c=n-a-b) then we say dp will have 2 variables a and b
@@og_prakash thanks i will keep this in mind
I'm getting tle on test 2 in my following code:
ll dp[5001][5001];
ll calc(ll idx, ll gm, vector&v){
if(idx==v.size()) return 0;
if(dp[idx][gm]!=-1) return dp[idx][gm];
ll sc=gm-v[idx];
if(sc> n;
vectorv;
mapm;
for(ll i=0;i> x;
m[x]++;
}
for(auto x:m){
v.push_back(x.second);
}
memset(dp,-1,sizeof dp);
cout
For each test case you are initialising dp of 5001*5001
So just n size tak kr lo where n is size of vector v
@@og_prakash Thanks a lot!!!