Want to Drive Innovation through Crowdsourcing? Learn the 5 Steps Get the eBook ×

Single Round Match 720 Editorials

By aditya In Community Stories

Posted August 30th, 2017

SRM 720 Editorials are now published. Thanks to kapillamba4 and marcose18 for contributing to the editorials. If you wish to discuss the problems or editorials you may do it in the discussion forum here.

SRM 720 Round 1 – Division II, Level OneDistinctGridEasy – by marcose18

We will solve this question with bruteforce. For each row and each column we will check if that row or column contains exactly k distinct elements or not. To check that we can use HashSet (Java) or unordered_set (C++).
Below is the working code in Java explained with appropriate comments.

Java Code

import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;


public class DistinctGridEasy {
   public String checkGrid(int n, int k, int[] grid) {
       int matrix[][] = new int[n][n];
       for (int i = 0; i < n; i++) {          // make actual 2D matrix from given array.
           for (int j = 0; j < n; j++)            
               matrix[i][j] = grid[i * n + j];
       }

       HashSet<Integer> set;

       for (int i = 0; i < n; i++) {
           set = new HashSet<>();
           for (int j = 0; j < n; j++)      //check if ith row contains exactly k elements.
               set.add(matrix[i][j]);

           if (set.size() != k)
               return "Bad";

           set = new HashSet<>();

           for (int j = 0; j < n; j++)     //check if jth column contains exactly k elements
               set.add(matrix[j][i]);
           if (set.size() != k)
               return "Bad";
       }
       return "Good";           /*Finally return Good if each row and column contains      
   }                                         exactly k distinct elements.
                                           */


}

SRM 720 Round 1 – Division II, Level TwoMinProduct – by kapillamba4

We are given multiple copies of digits whose value is between 0 to 9 inclusive.
Using those digits we have to construct 2 numbers A and B such that their product is minimum and for both number A, B leading zeroes are allowed.
Size of number A should be blank1 digits.
Size of number B should be blank2 digits.

Constraints
1 < blank1< 10
1 < blank2= blank1+blank2. Therefore the maximum size of our digits vector will 9+9 = 18 (blank1 + blank2)

Size of our digits vector is now equal to blank1+blank2.

Now for each digit in digits vector we can decide to either put it in A or B. Therefore the total number of possibilities of creating A and B will be 2**(blank1+blank2) which is at max equal to 2**18 = 262144

We can iterate from 0 to 2**(blank1+blank2) using bitmask and for each bit ‘j’ in each number ‘i’ from 0 to 2**(blank1+blank2) we put digits[j] in A if j’th bit is set (is one) else we place it in B if the j’th bit is not set (is zero).

For each number ‘i’, after constructing A and B we check if size of A is blank1 and size of B is blank2, We update our answer with each iteration.

Refer here to know how to iterate over of all subsets of a set using bitmasks.

The time complexity of the above solution is O(size * (2**size) ) where size is length of our digits vector.
(maximum value of size is 18 as per the problem)

C++ Code

#include 
using namespace std;
typedef long long ll;

class MinProduct {
    ll pow2[20];
public:
    ll findMin(vector amount, int blank1, int blank2) {
        string digits;
        int j = 0;
        for(int i = 0; i &lt; blank1+blank2; i++) {
            while(amount[j] == 0) ++j;
            digits.push_back('0'+j);
            amount[j]--;
        }
        
        
        pow2[0] = 1;
        for(ll i = 1; i &lt; 20; i++) {
            pow2[i] = pow2[i-1]*2;
        }

        ll ans = LLONG_MAX;
        for(ll i = 0; i &lt; pow(2, digits.size()); i++) {
            string A, B;
            for(ll j = 0; j &lt; digits.size(); j++) {
                if(i &amp; pow2[j]) {
                    A.push_back(digits[j]);
                } else {
                    B.push_back(digits[j]);
                }
            }

            if(A.size() != blank1 || B.size() != blank2) {
                continue;
            }

            ans = min(ans, stoll(A)*stoll(B));
        }

        return ans;
    }
};

SRM 720 Round 1 – Division I, Level OneSumProduct – by kapillamba4

We are given multiple copies of digits from 0 to 9, an array ‘amount’ denotes the number of occurance of each digit from 0 to 9 inclusive.
We have to add the product of all distinct pairs of numbers A, B constructed using given copies of digits. Here leading zeroes are allowed.

Size of number A should be blank1 digits.
Size of number B should be blank2 digits.
Constraints:
0 < amount[i] <= 100
1 < blank1 <= 100
1 < blank2 <= 100

For each of i’th place in number A and j’th place in number B in Base-10 representation, fix digit value di for number A and digit value dj for number B and then calculate the number of occurrences of distinct pairs (A, B) such that for the pair di is present at i’th place in A and dj is present at j’th place in B.

0 < i < blank1
0 < j < blank2
0 <= di < 10
0 <= dj < 10

Add the result of ((10**i) * di * (10**j) * dj) * (occurrences) to the final ans with each iteration where `occurances` is the number of distinct pairs (A, B) such that di digit occurs at i'th place in A and dj digit occurs at j'th place in B.

Let d[size][x][di][dj] denote the number of ways to fill in ‘size’ places using digits only available from x to 9 inclusive and digits di, dj are fixed.
The `occurances` can be calculated as d[blank1+blank2-2][0][di][dj] after placing di at i’th place and dj at j’th place.
All blank1+blank2-2 places (after fixing di and dj digits) in base-10 representation for A and B are distinct. Therefore choosing `y` places among `size` places is given by nCr(size, y) = size!/(y!*(size-y)!)

Therefore the recursive relation is d[size][x][di][dj] = ∑d[size-y][x+1][di][dj]*nCr(size, y) where 0 <= y <= min(size, amount[i])
d[size][x][di][dj] = 0 if size != 0 and x = 10 (maximum value of a digit in base-10 representation + 1 = 9 + 1 = 10)
d[size][x][di][dj] = 1 if size = 0 and x = 10 (maximum value of a digit in base-10 representation + 1 = 9 + 1 = 10)

Binomial coefficient (nCr) can be calculated in constant time if factorials and modular inverse of factorials of numbers from 0 to blank1+blank2 are calculated and memoized beforehand.

Therefore the time complexity for choosing i, j, di and dj will be O(blank1*blank2*max(di)*max(dj)) and time complexity for calculating the number of distinct pairs (A, B) after using memoization will be around O((blank1+blank2-2)*max(x)*max(di)*max(dj)*min(amount[x], size))

O(blank1*blank2*max(di)*max(dj) + (blank1+blank2-2)*max(x)*max(di)*max(dj)*min(amount[x], size))
where maximum value of di, dj, x can be 10
and maximum value of min(amount[x], size) can be 10

C++ Code

#include 
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
ll d[205][10][10][10];
ll fac[205];
ll invFac[205];

class SumProduct {
public:
    ll power(ll a, ll b) {
        if(a == 0) return 0;
        if(b == 1) return a;
        if(b == 0 || a == 1) return 1;
        if(b % 2) {
            return (power((a*a)%MOD, b/2)*a)%MOD;
        } else {
            return power((a*a)%MOD, b/2);
        }
    }

    ll nCr(ll n, ll r) {
        return (((fac[n]*invFac[r])%MOD)*invFac[n-r])%MOD;
    }

    ll occur(int i, int size, vector &amp;amount, int x, int y) {
        if(size != 0 &amp;&amp; i == amount.size()) return 0;
        if(size == 0 &amp;&amp; i == amount.size()) return 1;
        if(d[size][i][x][y] != -1) return d[size][i][x][y];
        ll ans = 0;
        for(int j = 0; j &lt;= min(amount[i], size); j++) {
           // nCr(size, j) gives number of ways to
           // choose ‘j’ places from ‘size’ places
            ans += (occur(i+1, size-j, amount, x, y)*nCr(size, j))%MOD;
            ans %= MOD;
        }

        return (d[size][i][x][y] = ans);
    }

    ll findSum(vector amount, int blank1, int blank2) {
        for(int i = 0; i &lt; 205; i++) {
            for(int j = 0; j &lt; 10; j++) {
                for(int k = 0; k &lt; 10; k++) {
                    for(int z = 0; z &lt; 10; z++) {
                        d[i][j][k][z] = -1;
                    }
                }
            }
        }

        fac[0] = 1;
        invFac[0] = 1;
        for(ll i = 1; i &lt; 205; i++) {
            fac[i] = (fac[i-1]*i)%MOD;
            invFac[i] = (invFac[i-1]*power(i, MOD-2))%MOD;
        }

        ll ans = 0;
        for(int i = 0; i &lt; blank1; i++) {
            for(int j = 0; j &lt; blank2; j++) {
                for(int di = 0; di &lt; 10; di++) {
                    for(int dj = 0; dj = 0 &amp;&amp; amount[dj] &gt;= 0) {
                            ll a = (di*power(10, i))%MOD;
                            ll b = (dj*power(10, j))%MOD;
                            ll occurance = occur(0, blank1+blank2-2, amount, di, dj);
                            ans += (((a*b)%MOD)*occurance)%MOD;
                            ans %= MOD;
                        }

                        amount[di]++;
                        amount[dj]++;
                    }
                }
            }
        }

        return ans;
    }
};