moonrise07's blog

Uber coding round
By moonrise07, history, 3 years ago, In English

  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
  • Vote: I like it
  • +27
  • Vote: I do not like it

Comments Comments (20)
| Write comment?
»
3 years ago, # |
← Rev. 4   Vote: I like it +8 Vote: I do not like it

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;	
}
→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it
problem 2 in O(2*n*k)
problem 3 in O(81*n*n)
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 3   Vote: I like it +1 Vote: I do not like it

        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]
        → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
Problem 1 in O(n*n)
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are correct. I have edited my comment.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like 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.

          → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Will uber hire me if i can drive well?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Consider this for 2nd problem,

Code
→ Reply