D. World is Mine |EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2) solution

#codeforces #codechef #competitiveprogramming
connect with me on twitter x.com/ogprakashh

[@DineshShukla-bb3zp]

#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

[@og_prakash]

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

[@vibhorkumar9771]

just simple and straight....thanks bro

[@og_prakash]

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

[@attackingzombie4885]

Good Work bro Easy to understand explanation

[@theee_1]

Thanks bro! This was really simply great explanation right there. Keep up the good work!

[@akashsardar495]

Clearly explained 😊

[@NavneetKumar-nt8mc]

Sahi samjhate ho bhaiya, isis tarah hindi me upload karte raho bhaiya thanks

[@utsavaggrawal2697]

thanks a lot

[@VidushJindal]

good explanation brother

[@pushkarraj4640]

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.

[@og_prakash]

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

[@pushkarraj4640]

@@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

[@og_prakash]

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

[@pushkarraj4640]

@@og_prakash thanks a lot 👍

[@r.k6833]

nice explanation bro , thnx a lot

[@SaiChandanMohanty]

how to identify variables in dp?

[@og_prakash]

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

[@SaiChandanMohanty]

@@og_prakash thanks i will keep this in mind

[@divyansh1294]

🥰🥰😘😘

[@og_prakash]

🙏🙏🙏

[@abhinavkumar7801]

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

[@abhinavkumar7801]

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

[@og_prakash]

​​@@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

[@og_prakash]

​@@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

[@abhinavkumar7801]

@@og_prakash oh okey got it. Thank you very much for clearing

[@ashrafulalam4808]

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

[@og_prakash]

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

[@ashrafulalam4808]

@@og_prakash Thanks a lot!!!