I need Help to optimize a Dp Code !!
Difference between en1 and en2, changed 2 character(s)
Today, I learned Digit DP for the first time, so I tried to solve different kinds of Digit DP problems. While doing that, I came upon [This](https://codeforces.net/problemset/problem/2039/C1) question. I know this is not a Digit Dp question, and there is a much better approach to this question. However, I wrote a solution using the concepts I learned and got **TLE on Test Case 45**. Can Someone help me optimize this further?↵

Here is the code :↵


~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
using namespace std;↵
using namespace __gnu_pbds;↵
template<class T> using oset = tree< T , null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update >; ↵
// *st.find_by_order(i) --> element at ith position↵
// st.order_of_key(x) --> no. of ele less than x↵
//For multiset change less to less_equal and for reverse order change less to greater↵
#define int long long ↵
#define endl '\n'↵
#define all(x) (x).begin(), (x).end()↵
template<typename T> // cin >> vector<T>↵
istream& operator>>(istream &istream, vector<T> &v){for(auto &it : v)cin >> it;return istream;}↵
template<typename T> // cout << vector<T>↵
ostream& operator<<(ostream &ostream, const vector<T> &c){for(auto &it : c)cout << it << " ";return ostream;}↵

// int dp[19][2];↵
map<tuple<int, bool, string>, int> memo;↵

int f(int idx , bool bound , string ans , int x , string &s) {↵
    if(idx == (int)s.size()) {↵
        int y = stoll(ans);↵
        if(y == 0 or (x == y)) return 0;↵
        int div = x ^ y;↵
        return (x % div == 0) or (y % div == 0);↵
    }↵
    auto state = make_tuple(idx, bound, ans);↵
    if (memo.find(state) != memo.end()) return memo[state];↵
    // if(dp[idx][bound] != -1) return dp[idx][bound];↵
    int res = 0;↵
    int maxDigit = 9;↵
    if(bound) maxDigit = s[idx] - '0';↵
    for(int i = 0 ; i <= maxDigit ; i++) {↵
        res += f(idx + 1 , bound & (i == maxDigit) , ans + to_string(i) , x , s)   ;↵
    }↵
    // return dp[idx][bound] = res;↵
    return memo[state] = res;↵
}↵

signed main()↵
{↵
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);↵
    int testCase; cin >> testCase;↵
    while(testCase--) {↵
        memo.clear();↵
        int x , m;↵
        cin >> x >> m;↵
        string s = to_string(m);↵
        string ans = "";↵
        // memset(dp , -1 , sizeof(dp));↵
        cout << f(0 , true , ans , x , s) << endl;↵
        memo.clear();↵
    }↵
    return 0;↵
}↵
~~~~~↵




Any help is highly appreciated, my friend!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Cakee 2024-12-09 23:45:19 2 Tiny change: 'Test Case 4**. Can So' -> 'Test Case 5**. Can So'
en1 English Cakee 2024-12-09 23:44:17 2581 Initial revision (published)