### pranaav's blog

By pranaav, history, 3 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

• +27

 » 3 months ago, # | ← Rev. 4 →   +8 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[2][k+1][n+1]; memset(dp, -1e9, sizeof(dp)); int mod = 1e9 + 7; REP(i,0,n+1){ dp[0][0][i] = 0; } REP(i,1,n+1){ REP(j,1,k+1){ dp[0][j][i] = dp[0][j][i-1]; dp[1][j][i] = dp[1][j][i-1]; if(arr[i] % 2){ dp[1][j][i] += dp[0][j-1][i-1] * arr[i]; dp[0][j][i] += dp[1][j-1][i-1] * arr[i]; } else { dp[1][j][i] += dp[1][j-1][i-1] * arr[i]; dp[0][j][i] += dp[0][j-1][i-1] * arr[i]; } dp[0][j][i] %= mod; dp[1][j][i] %= mod; } if(arr[i] % 2){ dp[1][1][i] += arr[i]; dp[1][1][i] %= mod; } else { dp[0][1][i] += arr[i]; dp[0][1][i] %= mod; } } cout << dp[0][k][n] << "\n"; return 0; } 
•  » » 2 months ago, # ^ |   0 Can you explain the approach/ code
 » 3 months ago, # | ← Rev. 2 →   -6 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][2]={}; int ans=0; /* dp[i][j][0] sum of product of subsets of length 'j' ending at 'i' having odd elements even times dp[i][j][1] 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[2]={}; 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][0]; 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[0][0]=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; } 
•  » » 3 months ago, # ^ |   +7 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.
•  » » » 3 months ago, # ^ |   +1 Yes, it did actually for 3 test cases. Any hint for reducing the constant factor to 9?
•  » » » » 3 months ago, # ^ | ← Rev. 3 →   +1 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[0] = 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] 
•  » » » » » 2 months ago, # ^ | ← Rev. 3 →   -6 @
•  » » » » » 4 weeks ago, # ^ |   0 nice!
•  » » » » 3 months ago, # ^ |   0 My recursive dp solution passed all the test cases when i changed mod operation to subtraction.
•  » » » » » 2 months ago, # ^ |   0 Could you please share the code
•  » » 2 months ago, # ^ |   0 What can be the problems difficutly in terms of cf rating?
 » 3 months ago, # |   +1 Is the 3rd problem of digit dp? What to what major topic does 2nd problem belong to- DP SOS?
•  » » 3 months ago, # ^ |   0 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.
 » 3 months ago, # | ← Rev. 2 →   0 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<
•  » » 3 months ago, # ^ |   +1 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)
•  » » » 3 months ago, # ^ |   0 You are correct. I have edited my comment.
•  » » » » 3 months ago, # ^ |   0 can you explain the logic of your code . I am not able to understand it.
•  » » » » » 3 months ago, # ^ |   0 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.
 » 2 months ago, # |   -14 do i need to code to be a driver?
 » 2 months ago, # |   +1 I guess the constraint in problem 1 was (length of array < 100)
•  » » 2 months ago, # ^ |   0 Also, Those who partially solved for the constraint of length <= 64 got (81/100) points!
 » 2 months ago, # |   +16 Will uber hire me if i can drive well?
•  » » 2 months ago, # ^ |   +12 Only if you are mechanical engineer.
 » 2 months ago, # |   0 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[2][k+1]; // dp[0][i] -> count of odd element is even and size of the subset is i // dp[1][i]-> count is odd elements is odd and size of the subset is i for(int i = 0; i <= k; i++) dp[0][i] = dp[1][i] = 0; // Base case dp[0][0] = 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[1][j-1] and dp[0][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[1][j-1] != 0) dp[0][j] += dp[1][j-1] * arr[i]; if(dp[0][j-1] != 0) dp[1][j] += dp[0][j-1] * arr[i]; }else{ if(dp[0][j-1] != 0) dp[0][j] += dp[0][j-1] * arr[i]; if(dp[1][j-1] != 0) dp[1][j] += dp[1][j-1] * arr[i]; } dp[0][j] %= mod; dp[1][j] %= mod; } } // cout << "Sum of products of subsets of size K with the frequency of odd elements as even is: " << dp[0][k] << endl; cout << dp[0][k] << endl; } return 0; } 
 » 2 months ago, # |   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[0][0] = 1 , dp2[0][0] = 1; for(int i=1; i
 » 2 months ago, # |   0 can you tell me the cutoff?also was this a one hour test?