Uber coding round - Codeforces

Блог пользователя moonrise07

Uber coding round

Автор moonrise07, история, 5 лет назад, По-английски

You have to convert base 2 number into base 6 constraint : length of array <1000
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;
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

#interview, # dp, #knapsack

moonrise07
5 лет назад
26

Комментарии (20)

Показать архивные | Написать комментарий?

samay_var

5 лет назад, скрыть # |

← Rev. 4 →

For question 2 consider this solution

#include <bits/stdc++.h>
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;	
}

→ Ответить

aryan57

5 лет назад, скрыть # |

← Rev. 2 →

-6

problem 2 in O(2*n*k)

/**
 *    author:  Aryan Agarwal
 *    created: 01.08.2021 00:20:23 IST
**/
#include <bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
    int M=1e9+7;

    int n,k;
    cin>>n>>k;
    vector<int> 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<<ans<<"\n";
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int _t = 1;
    // cin>>_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 <bits/stdc++.h>
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<vector<int>> dp(n+1,vector<int>(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<<ans<<"\n";
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int _t = 1;
    // cin>>_t;
    while(_t--)solve();
    return 0;
}

→ Ответить

TheLovelyLion

5 лет назад, скрыть # ^ |

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.

→ Ответить

zass

5 лет назад, скрыть # ^ |

Yes, it did actually for 3 test cases. Any hint for reducing the constant factor to 9?

→ Ответить

TheLovelyLion

5 лет назад, скрыть # ^ |

← 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<int> dp(max);
dp[0] = 1;
for i in range(n):
    vector<int> 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]

→ Ответить

contests_only__

5 лет назад, скрыть # ^ |

← Rev. 3 →

-6

→ Ответить

professo

5 лет назад, скрыть # ^ |

nice!

→ Ответить

tanmay.raj.29

5 лет назад, скрыть # ^ |

My recursive dp solution passed all the test cases when i changed mod operation to subtraction.

→ Ответить

Impostor_Syndrome

5 лет назад, скрыть # |

Is the 3rd problem of digit dp? What to what major topic does 2nd problem belong to- DP SOS?

→ Ответить

TheLovelyLion

5 лет назад, скрыть # ^ |

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.

→ Ответить

pretending

5 лет назад, скрыть # |

← 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<int> Solve(vector<bool> 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<int> ans(temp.size(), 0);
    for(int i=0; i<temp.size(); ++i)
    ans[i]=temp[i]-'0';
    return ans;
}
 
int main() {
	vector<bool> v={1, 1, 1, 1, 1, 1, 1};
	auto k = Solve(v);
	for(auto i:k)
	cout<<i<<" ";
	return 0;
}

→ Ответить

DL-POWER

5 лет назад, скрыть # ^ |

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)

→ Ответить

pretending

5 лет назад, скрыть # ^ |

You are correct. I have edited my comment.

→ Ответить

jerseyguy

5 лет назад, скрыть # ^ |

can you explain the logic of your code . I am not able to understand it.

→ Ответить

KunKaneki

5 лет назад, скрыть # ^ |

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.

→ Ответить

__SchrodingersCat__

5 лет назад, скрыть # |

I guess the constraint in problem 1 was (length of array < 100)

→ Ответить

__SchrodingersCat__

5 лет назад, скрыть # ^ |

Also, Those who partially solved for the constraint of length <= 64 got (81/100) points!

→ Ответить

Reconciliation

5 лет назад, скрыть # |

+16

Will uber hire me if i can drive well?

→ Ответить

mahachutiya_coder

5 лет назад, скрыть # ^ |

+12

Only if you are mechanical engineer.

→ Ответить

sangram03

5 лет назад, скрыть # |

Consider this for 2nd problem,

Code

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

#define fio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define endl '\n'
#define vi vector<int>
#define ll long long int
#define fo(i,begin,end) for(int i = begin;i<end;i++)
#define MOD 1000000007
// #define MOD 998244353

#define pb push_back
ll add(ll x,ll y){ll res = x+y;return (res>=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<odd.size(); i++){
		dp1[i][0] = 1;
		for(int j=1; j<=i && j<odd.size(); j++){
			dp1[i][j] = add ( dp1[i-1][j] , mul (dp1[i-1][j-1] , odd[i] ));
    	}
	}
	for(int i=1; i<even.size(); i++){
		dp2[i][0] = 1;
		for(int j=1; j<=i && j<even.size(); j++){
			dp2[i][j] = add ( dp2[i-1][j] , mul (dp2[i-1][j-1] , even[i] ));
    	}
	}
	fo(i , 0 , odd.size()){
		if(i%2 == 0 && (k - i) < even.size()){
			int ans1 = dp1[odd.size()-1][i];
			int ans2 = dp2[even.size()-1][(k - i)];
			ans = add(ans , mul(ans1 , ans2));
		}
	}
	cout << ans << endl;
	cerr << "\ntime taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
	return 0;
}

→ Ответить