About Me - Introduction

today was a bit odd, woke up at 6 again, meds are too strong, knocked me out last night, woke up again at night watched Warriors 2011, wonderful movie, i didnt expect so much emotional depth in a movie about fighting, it really respected the intellect of the audience, didnt give away every minute detail felt like i was picking pieces of characters and it was wonderful experience, the fight scenes were lowkey crazy had me on my toes(i was sleeping so had me on my back :D)
day started with a bit of tomfoolery and instaposting, but we are not going to break the routine. Opened codeforces locked tf in. one problem which was pretty beautiful but the implementation isnt, but yet we are going to talk about the beauty of the problem: Palindrome Basis
This is modified problem on Integer partioning : example: 3= 2+1=1+1+1=3,{breaking a number into sum of positive integers} Integer partioning is overlap of famous coin problem(look it up) ,but in this prob the twist is that you have to break the number into sum of positive palindromes //Driver Code Starts #include
#include
using namespace std;
//Driver Code Ends
int count(vector &coins, int sum) {
int n = coins.size();
// dp[i] will be storing the number of solutions for
// value i.
vector dp(sum + 1);
dp[0] = 1;
// Pick all coins one by one and update the table[]
// values after the index greater than or equal to the
// value of the picked coin
for (int i = 0; i < n; i++)
for (int j = coins[i]; j <= sum; j++)
dp[j] += dp[j - coins[i]];
return dp[sum];
}
in simple language suppose you have been given a coins of denomination {1,2,3} and you have to make a sum of 4 via coins, so the DP idea is to find the number of ways to make sum j using a coin of value x, look at how many ways you could already make {j-x} because if you can make {j-x} then adding one coin of value x gives {j-x}+{x}=j. which is basically dp[j]= dp[j]+dp[j-x]. this problem is direct implication of this exact coin problem but instead of denominations you have to first make a vector of all the possible palindromes{}. there were so many ways you could have gone wrong even though the answer was simple asf. you couldve gone towards matrix multiplication, problem "parquet", partition matrix etc.
also refer : DP.Partition.

Another good problem i came across: Factorials and Powers of Two in this you have to figure out the minimum distinct k powerful numbers where powerful number is described as 2^d or d!.heres the code:


ll original = n;
ll ans = __builtin_popcountll(n);

for (ll mask = 0; mask < (1LL << 15); mask++) {
    ll sum = 0;
    ll cnt = 0;

    for (ll i = 0; i < 15; i++) {
        if (mask & (1LL << i)) {
            sum += fact[i];
            cnt++;
        }
    }

    if (sum <= original) {
        ans = min(ans, cnt + (ll)__builtin_popcountll(original - sum));
    }
}

in this we are basically using bit manipulation to figure out all the possible subsets of fact that sum up to less than or equal to original, total iteration stays less than 500k(safe).

follow my everyday blogs, youre going to witness my life ramming and unfolding infront of your eyes!!