pranaav's blog

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

»
2 months 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;	
}

»
2 months 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)
  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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?

      • »
        »
        »
        »
        2 months 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]
      • »
        »
        »
        »
        2 months 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.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What can be the problems difficutly in terms of cf rating?

»
2 months 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?

  • »
    »
    2 months 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.

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
Problem 1 in O(n*n)
  • »
    »
    2 months 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)

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are correct. I have edited my comment.

      • »
        »
        »
        »
        2 months 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.

        • »
          »
          »
          »
          »
          2 months 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.

»
7 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

do i need to code to be a driver?

»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    7 weeks 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!

»
6 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Will uber hire me if i can drive well?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 <bits/stdc++.h>
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;
}
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Consider this for 2nd problem,

Code
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can you tell me the cutoff?

also was this a one hour test?