C++ Day 37

 

Here’s C++ Day 37 with lots of rich, structured content so your daily practice stays meaningful.
This includes:
✔ Concepts
✔ Problems
✔ Code templates
✔ Mini-projects
✔ Debug tasks
✔ Interview-style challenges

---

🚀 C++ Day 37 – Advanced Mixed Practice (Deep Dive Edition)

---

1️⃣ Concept of the Day — “Bitmasking + DP + Greedy Hybrids”

Many advanced contest problems combine bit operations, DP, and greedy pruning.

👉 Key Points

• Use bitmasks to represent subsets.

• Use greedy heuristics to prune DP states.

• Use __builtin_popcountll() for fast operations.

• Precompute masks for speed.

⭐ Example Pattern

for (int mask = 0; mask < (1<<n); mask++) {
    int bits = __builtin_popcount(mask);
    dp[mask] = ...;
}

---

2️⃣ Quick Practice Problems (with difficulty)

Try to solve these after studying the concept:

(A) Easy — "Count Bits in Ranges"

Given a range [l, r], count total number of 1-bits in all numbers.

---

(B) Medium — "Smallest Missing Bitmask Value"

Given array of integers (≤ 1e6), find the smallest value not representable as bitwise-AND of some subarray.

---

(C) Hard — “Maximize Score with K Picks + Bitmask States”

You have n coins with a[i] values and can choose exactly k coins.
Score = sum( chosen ) AND xor( chosen ).
Maximize score.
Constraint: n ≤ 1e5.

(Hint: use greedy + pruning on top bits)

---

3️⃣ Debugging Task (You must fix it)

This code tries to compute LIS but gives wrong output:

vector<int> lis;
for (int i = 0; i < n; i++) {
    auto it = lower_bound(lis.begin(), lis.end(), arr[i], greater<int>());
    if (it == lis.end()) lis.push_back(arr[i]);
    else *it = arr[i];
}
cout << lis.size();

❌ What’s wrong?

• Compares incorrectly for LDS/LIS

• Should use:

  • lower_bound for LIS

  • upper_bound for some variants

• OR use reverse comparator properly

Fix it as part of day 37.

---

4️⃣ Short Topic – “Prefix Tricks for DP”

Useful in problems with large ranges:

Trick	Use
Prefix max	For DP like knapsack variants
Prefix AND	To track decreasing AND intervals
Prefix XOR	For fast queries

Example:

vector<int> px(n+1);
for(int i=1;i<=n;i++) px[i] = px[i-1] ^ arr[i];

---

5️⃣ Mini Project – “Meet-in-the-middle subset apps”

Problem:
Given n ≤ 40, find the number of subsets with sum ≤ W.

Plan:

• Split array in two halves.

• Generate all subset sums.

• Sort one half.

• For each sum in first half, binary search in second.

Skeleton:

void gen(vector<int>& arr, vector<long long>& out) {
    int n = arr.size();
    for(int mask=0; mask < (1<<n); mask++) {
        long long sum = 0;
        for(int i=0;i<n;i++) if(mask&(1<<i)) sum += arr[i];
        out.push_back(sum);
    }
}

Finish it as exercise.

---

6️⃣ Interview Problem — “Minimum Removal Cost to Make Array Good”

Array is good if a[i] ≤ i.
Each removal costs a[i].
Find minimum cost.

Hint: Greedy + priority queue.

---

7️⃣ Competitive Problem — “Maximum Path Sum in Tree with State”

You get a tree with value on nodes.
You choose a path, but you can skip at most one value on the path (set one node’s value = 0).

Solve using:

• DFS + DP states

• State 0 = no skip used

• State 1 = skip used

---

8️⃣ Code Template (Day 37 Standard)

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(x) x.begin(), x.end()

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Day 37 Starter Template

    int n;
    cin >> n;
    vector<int> arr(n);
    for(int &x : arr) cin >> x;

    // Write your code here

    return 0;
}