### pranaav's blog

By pranaav, history, 2 months ago, 1. You have to convert base 2 number into base 6 constraint : length of array <1000

2. You have to find sum of product of cool subset : cool subset is having number of odd element even total size of subset is k constraint size of array <1000;

3. you have to find number of numbers of exact digit n whose digit sum is compact number. compact number is the number which is made by the given x, y for ex if x and y are 2 and 3 respectively then 22, 33, 23, 32 are compact numbers. x<=9 y<=9 n<=1000 # dp, Comments (26)
 » 2 months ago, # | ← Rev. 4 →   For question 2 consider this solution #include using namespace std; #define ld long double #define ll long long #define REP(i, a, b) for (ll i = a; i < b; i++) #define REPI(i, a, b) for (ll i = b - 1; i >= a; i--) #define i_os ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define INF (ll)1e18 + 100 #define endl "\n" int main() { i_os; ll n, k; cin >> n >> k; ll arr[n+1]; REP(i,1,n+1){ cin >> arr[i]; } ll dp[k+1][n+1]; memset(dp, -1e9, sizeof(dp)); int mod = 1e9 + 7; REP(i,0,n+1){ dp[i] = 0; } REP(i,1,n+1){ REP(j,1,k+1){ dp[j][i] = dp[j][i-1]; dp[j][i] = dp[j][i-1]; if(arr[i] % 2){ dp[j][i] += dp[j-1][i-1] * arr[i]; dp[j][i] += dp[j-1][i-1] * arr[i]; } else { dp[j][i] += dp[j-1][i-1] * arr[i]; dp[j][i] += dp[j-1][i-1] * arr[i]; } dp[j][i] %= mod; dp[j][i] %= mod; } if(arr[i] % 2){ dp[i] += arr[i]; dp[i] %= mod; } else { dp[i] += arr[i]; dp[i] %= mod; } } cout << dp[k][n] << "\n"; return 0; } 
•  » » Can you explain the approach/ code
 » 2 months ago, # | ← Rev. 2 →   problem 2 in O(2*n*k)/** * author: Aryan Agarwal * created: 01.08.2021 00:20:23 IST **/ #include using namespace std; #define int long long void solve() { int M=1e9+7; int n,k; cin>>n>>k; vector a(n+1); for(int i=1;i<=n;i++)cin>>a[i]; int dp[n+1][k+1]={}; int ans=0; /* dp[i][j] sum of product of subsets of length 'j' ending at 'i' having odd elements even times dp[i][j] sum of product of subsets of length 'j' ending at 'i' having odd elements odd times */ for(int j=1;j<=k;j++) { int pre={}; for(int i=1;i<=n;i++) { if(j==1){ dp[i][j][a[i]%2]=a[i]; continue; } for(int bit : {0,1}) { dp[i][j][bit] += a[i]*pre[(a[i]%2)^bit]; dp[i][j][bit] %= M; pre[bit]+=dp[i][j-1][bit]; pre[bit]%=M; } if(j==k){ ans+=dp[i][j]; ans%=M; } } } cout<>_t; while(_t--)solve(); return 0; }  problem 3 in O(81*n*n)/** * author: Aryan Agarwal * created: 31.07.2021 23:36:16 IST **/ #include using namespace std; #define int long long bool is_compact(int x,int y,int n) { while(n) { if(n%10!=x && n%10!=y) { return false; } n/=10; } return true; } void solve() { int M=1e9+7; int x,y,n; cin>>x>>y>>n; vector> dp(n+1,vector(9*n+1)); dp=1; for(int i=1;i<=n;i++) { for(int d=(i==n?1:0);d<=9;d++) { for(int j=d;j<=9*n;j++) { dp[i][j]+=dp[i-1][j-d]; dp[i][j]%=M; } } } int ans=0; for(int j=1;j<=9*n;j++) { if(is_compact(x,y,j)) { ans+=dp[n][j]; ans%=M; } } cout<>_t; while(_t--)solve(); return 0; } 
•  » » 3rd one will give TLE(for a few cases). Try to do it in $O(n^2)$ and constant factor of $9$ and not $81$. The time limit was strict.
•  » » » Yes, it did actually for 3 test cases. Any hint for reducing the constant factor to 9?
•  » » » » 2 months ago, # ^ | ← Rev. 3 →   Let us convert it to another problem: Given $n$, $dp[i]$ represents number of values that contain at most $n$ digits and their sum is $i$.pseudo-code: max = 9*n + 5; vector dp(max); dp = 1; for i in range(n): vector p = dp; // make p to represent prefix sums for j in range(max): dp[j] = p[j] if j-10 >=0: dp[j] -= p[j-10] 
•  » » » » » 7 weeks ago, # ^ | ← Rev. 3 →   @
•  » » » » » nice!
•  » » » » My recursive dp solution passed all the test cases when i changed mod operation to subtraction.
•  » » » » » Could you please share the code
•  » » What can be the problems difficutly in terms of cf rating?
 » Is the 3rd problem of digit dp? What to what major topic does 2nd problem belong to- DP SOS?
•  » » It can be considered as digit dp, but can be reduced down to simpler combinatorics dp if you try to observe the states in digit dp.
 » 2 months ago, # | ← Rev. 2 →   Problem 1 in O(n*n)#include "bits/stdc++.h" using namespace std; string add(string num1, string num2) { string res = ""; int c = 0; for(int i = num1.size() - 1,j = num2.size() - 1;i >= 0 || j >= 0 ;i--,j--) { const int val = (i < 0 ? 0 : num1[i] - '0') + (j < 0 ? 0 : num2[j] - '0') + c; c = val/6; res.push_back('0' + val%6); } if(c > 0) { res.push_back('0' + 1); } reverse(res.begin(),res.end()); return res; } vector Solve(vector v) { string temp="0", power="1"; for(int i=v.size()-1; i>=0; --i) { if(v[i]) temp=add(temp, power); power=add(power, power); } vector ans(temp.size(), 0); for(int i=0; i v={1, 1, 1, 1, 1, 1, 1}; auto k = Solve(v); for(auto i:k) cout<
•  » » it's O(N*N) not O(N), each time you do an add operation that takes length of string in for loop which make the add function O(N) and you call this function N times, so it make complexity O(N*N)
•  » » » You are correct. I have edited my comment.
•  » » » » can you explain the logic of your code . I am not able to understand it.
•  » » » » » So the power vector represents 2^i for ith iteration in loop.Now if that number is set it is to be added to the answer uptil there . He wrote addition of 2 string in base 6 in the add function . The C in that function represents carry . Hope you understand now.
 » do i need to code to be a driver?
 » I guess the constraint in problem 1 was (length of array < 100)
•  » » Also, Those who partially solved for the constraint of length <= 64 got (81/100) points!
 » Will uber hire me if i can drive well?
•  » » Only if you are mechanical engineer.
 » Solution for Problem 2 with proper comments for each step. It is a DP problem very similar to the standard subset sum problem. In this problem, we need to find the subsets of size K such the frequency of the odd elements inside the subset is even. After finding such subsets we need to take the product of all the elements of an individual subset and then sum all the products obtained in the previous step.Code for the above-mentioned approach in C++ #include using namespace std; #define int long long int #define fast \ ios_base::sync_with_stdio(false); \ cin.tie(NULL); #define endl "\n" bool isOdd(int num){ if(num%2) return true; return false; } signed main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif // ONLINE_JUDGE fast int tt = 1; cin >> tt; int mod = 1e9 + 7; for(int loop = 1; loop <= tt; loop++) { int n, k; cin >> n >> k; // Subset size should be k int arr[n]; for (int i = 0; i < n; i++) cin >> arr[i]; int dp[k+1]; // dp[i] -> count of odd element is even and size of the subset is i // dp[i]-> count is odd elements is odd and size of the subset is i for(int i = 0; i <= k; i++) dp[i] = dp[i] = 0; // Base case dp = 1; // count of odd elements is even(i.e. equal to zero) and set size is 0 for(int i = 0; i < n; i++){ // i denotes the array element for(int j = k; j >= 1; j--){ // j denotes the subset size // Note it is important to check dp[j-1] and dp[j-1] whether they are non zero or not. Because we can form a subset of size j only when a subset of size j - 1 already exists which is denoted if there is a non zero value if(isOdd(arr[i])){ if(dp[j-1] != 0) dp[j] += dp[j-1] * arr[i]; if(dp[j-1] != 0) dp[j] += dp[j-1] * arr[i]; }else{ if(dp[j-1] != 0) dp[j] += dp[j-1] * arr[i]; if(dp[j-1] != 0) dp[j] += dp[j-1] * arr[i]; } dp[j] %= mod; dp[j] %= mod; } } // cout << "Sum of products of subsets of size K with the frequency of odd elements as even is: " << dp[k] << endl; cout << dp[k] << endl; } return 0; } 
 » Consider this for 2nd problem, Code#include using namespace std; #define fio ios_base::sync_with_stdio(false); cin.tie(NULL) #define endl '\n' #define vi vector #define ll long long int #define fo(i,begin,end) for(int i = begin;i=MOD? res-MOD:res);} ll mul(ll x,ll y){ll res = x*y;return (res>=MOD? res%MOD:res);} ll sub(ll x,ll y){ll res = x-y;return (res<0?res+MOD:res);} int main() { fio; int n , k; cin >> n >> k; vi arr(n + 1); vi odd = {0}, even = {0}; fo(i,1 , n + 1){ cin >> arr[i]; if(arr[i]%2) odd.pb(arr[i]); else even.pb(arr[i]); } vector < vector < int > > dp1( odd.size() , vector < int > (odd.size() , 0)); vector < vector < int > > dp2( even.size() , vector < int > (even.size() , 0)); int ans=0; dp1 = 1 , dp2 = 1; for(int i=1; i
 » can you tell me the cutoff?also was this a one hour test?