July 10, 2017 Single Round Match 717 Editorials

SRM 717 Editorials are now published. We are still awaiting the submission to the Div I Hard Problem. Thanks to Srimaan1316 and Shizhouxing for contributing to the SRM 717 Editorials. If you wish to discuss the problems or editorials you may do it in the discussion forum here.
Want to write an editorial? And get featured on the Topcoder blog? We still have some editorials challenges open – Contribute to SRM Editorials.
 
 
SRM 717 Round 1 – Division II, Level One – NiceTable – by Shizhouxing
Assume the table has n rows and m columns.
Solution I
If we set a value for x[0], since x[0] xor y[0] = t[0][0], y[0] should be (x[0] xor t[0][0]). Then for i (1 <= i < n), since x[i] xor y[0] = t[i][0], x[i] should be (y[0] xor t[i][0]). Similarly, for j (1 <= j < m), since x[0] xor y[j] = t[0][j], y[j] should be (x[0] xor t[0][j]).
So we can deduce values of x[1]…x[n-1],y[0]…y[m-1] only from x[0]. Then, we just check whether for each i, j (0 <= i < n, 0 <= j < m), x[i] xor y[j] = t[i][j]. If this is true, the table is nice, otherwise the table is not nice.
Solution II
Since n and m are both very small (n, m <= 5), we can just do brute force. We try all possible values for x[0]…x[n-1], y[0]..y[m-1], and check whether they conform to the given table. The complexity for this algorithm is O(2^(n+m)*nm).
C++ Code
Here is an implementation of both solutions: Solution I is given as the main method isNice(), while Solution II is given as the method bf().

#include <bits/stdc++.h>
using namespace std;
int n, m, x[100], y[100];
class NiceTable
{
public:
    string bf(vector<string> t) {
        for (int i = 0; i < 1 << n; ++i)
            for (int j = 0; j < 1 << m; ++j) {
                for (int k = 0; k < n; ++k) x[k] = bool((1 << k) & i);
                for (int k = 0; k < m; ++k) y[k] = bool((1 << k) & j);
                int ok = true;
                for (int ii = 0; ii < n; ++ii)
                    for (int jj = 0; jj < m; ++jj)
                        if ((x[ii] ^ y[jj]) != t[ii][jj] - '0')
                            ok = false;
                if (ok) return "Nice";
            }
        return "Not nice";        
    }
    string isNice(vector <string> t)
    {
        n = t.size();
        m = t[0].size();
        
        x[0] = 0;
        y[0] = t[0][0] - '0';
        for (int i = 1; i < n; ++i) x[i] = (t[i][0] - '0') ^ y[0];
        for (int i = 1; i < m; ++i) y[i] = (t[0][i] - '0') ^ x[0];
        
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                if (t[i][j] - '0' != (x[i] ^ y[j]))
                    return "Not nice";
        
        return "Nice";
    }
};

 
 
SRM 717 Round 1 – Division II, Level Two – LexmanReplace – by Srimaan1316
In this problem, you are given 2 strings: s and t. You have to replace some characters of the string s using the characters of string t, such that you obtain the lexicographically largest string. Note that you are not allowed to increase the length of the string s. Also note that in some cases, it is best to leave the string s as is, since that is the optimal answer.
This problem can be solved using a greedy approach. The idea is as follows. For better understanding, let us rename the string s as source and string t as allow_chars.
Sort the characters of allow_chars in the non-increasing order. For example, if the string is “egabn” then after sorting it becomes “ngeba”.
Let next = 0.
For each character in the source string from left to right:
Compare it with the next-th character of allow_chars.
If the character of source is the greater one or equal, do not change anything.
Else, replace that character with the leftmost character of allow_chars, then increase next by one.
The time needed to solve this problem is the time taken to traverse source. Let srclen be the length of source, then the time complexity of the above solution is O(srclen).
Though it was mentioned above that allow_chars is to be sorted in the non-increasing order and initialise next to 0 and then perform comparisons, for ease of implementation, I sorted the string in the non-decreasing order. So, instead of next being zero, it is now len-1.
Pseudocode:

sort allow_chars in non-decreasing order;
len := length(allow_chars)
len--;
srclen := length(source)
for(int i = 0; i < srclen; i++) if (len >= 0 && source[i] < allow_chars[len])
        add allow_chars[len] to the answer and decrement len;
    else
        add source[i] to the answer;
return answer;

C++ code:

class LexmaxReplace
{
    public:
    string get(string s, string t)
    {
        int len=t.length();
        sort(t.begin(),t.end());
        int length=s.length();
        string ans="";
        len--;
        for(int i=0;i<length;i++)
        {
            if(s[i]<t[len]&&len>=0)
            {
                ans+=t[len];
                len--;
            }
            else
            {
                ans+=s[i];
            }
        }
        return ans;
    }
};

 
 
SRM 717 Round 1 – Division II, Level Three – DerangementsDiv2 – by Srimaan1316
In a gist, we need to find the number of derangements of the set {1…m} modulo 1000000007. We can solve this using inclusion-exclusion principle.
Prerequisites:

1. -To understand more about derangements, check out this Wikipedia link.
2. -For even more ease of understanding of derangements check out this YouTube video.
3. -Learn about inclusion-exclusion principle here.
4. -Check this comment to know how formula for derangements can be derived using inclusion-exclusion principle.

 
Let A be the set of all permutations of the set {1…n+m}.
Let Ti be the set of permutations in which the element i is still in its original position.
Let Dm be the required answer.
Then,
 (Why only m and not n+m? Because we need to find the number of derangements of only the first m numbers.)

Therefore,

We can simplify the above equation into:

Now that we have the formula ready, we come to the implementation part. Looking at the above formula, it can be understood that we need to compute the factorial of a given number and binomial coefficients C(m,i) where C(m,i) = m! / ((m-i)! * i!). We can make use of the concept of Pascal triangle. Check out this to know more about Pascal triangle.
Also, rather than computing factorials multiple number of times, we precompute it once and store them in an array.
Please refer my code below to understand the implementation better.
C++ code

C++ code
#include<bits/stdc++.h>
#define endl '\n'
#define mod 1000000007
using namespace std;
class DerangementsDiv2
{
    int fact[104];
    int pascal[103][103];
    public:int count(int n, int m)
    {
        //Initialising the values of 0! and 1!
        fact[0]=1;
        fact[1]=1;
        // Calculating the factorial values upto 100.
        for(int i=2;i<104;i++)
        fact[i]=(fact[i-1]*(long long)i)%mod;
        //Computing the Binomial Coefficients using Pascal Triangle.
        for(int i=0;i<103;i++)
        {
            pascal[i][0]=1;
            for(int j=1;j<=i;j++)
            pascal[i][j]=(pascal[i-1][j]+pascal[i-1][j-1])%mod;
        }
        int answer=fact[n+m];
        for(int i=1;i<=m;i++)
        {
        int val=pascal[m][i];
        if(i&1)
    answer=(answer-((long long)val*fact[m+n-i] %mod)+mod)%mod;
        else
answer=(answer+((long long)val*fact[m+n-i]%mod))%mod;
        }
        return answer;
    }
};

Note
Check out this to know more about performing modulo operation on negative numbers.
 
 
 
SRM 717 Round 1 – Division I, Level One – ScoresSequence – by Shizhouxing
It is said that the answer can always be uniquely determined. We can first construct a graph that satisfies the given score.
From the scores sequence, we can deduce the in-degree and out-degree of each vertex. Now, we can construct the graph using a greedy algorithm. We consider vertices in the descending order of their out-degrees. For each vertex u, let d be its out-degree. We should choose d other vertices v[1], v[2], …, v[d], and add edges (u,v[1]), (u,v[2]), …, (u,v[d]).
We can choose those d vertices in the following way: each time, choose a vertex that has the largest remaining in-degree; i.e., its original in-degree minus the number of edges which end at that vertex. For two vertices with same remaining in-degrees, we’ll prefer the one with smaller out-degree. You can easily validate that the solution can’t be better if we don’t construct the graph in this way.
Finally, we can use Floyd-Warshall algorithm to count the number of pairs of vertices (u,v) such that v is reachable from u, in O(n^3) time.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = ~0U >> 1;
const ll INF = ~0ULL >> 1;
int G[200][200], in[200], out[200];
int n;
class ScoresSequence
{
public:
    int count(vector <int> s)
    {
        n = s.size();
        sort(s.begin(), s.end(), greater<int>());
        for (int i = 0; i < n; ++i) {
            in[i] = n - 1 - s[i];
            out[i] = s[i];
            for (int j = 0; j < n; ++j)
                G[i][j] = false;
            G[i][i] = true;
        }
        for (int i = 0; i < n; ++i) {
            while (out[i]--) {
                int j = -1;
                for (int k = 0; k < n; ++k) if (i != k && !G[i][k] && (j == -1 || in[k] >= in[j]))
                        j = k;
                G[i][j] = true;
                in[j]--;
            }
        }
        for (int k = 0; k < n; ++k)
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    G[i][j] |= G[i][k] & G[k][j];
        int cnt = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (G[i][j]) ++cnt;
        return cnt;
    }
};

 
 
SRM 717 Round 1 – Division I, Level Two – DerangementsStrikeBack – by Shizhouxing
Obviously, B[0] = 1 and B[1] = n. Now, let’s compute B[i] from B[0], B[1], …, B[i-1] using dynamic programming.
Let p(i) = j (1<=j<=n+i, j ≠ i). We have:
If j < i, consider the remaining subproblem:
If p(j) = i, now we can simply “remove” positions i and j from the problem to form a subproblem. We now need to arrange the remaining n+i-2 values where first i-2 values can’t be fixed points. The number of ways is B[i-2].
If p(j) ≠ i, that means for a valid permutation p(1), p(2), …, p(i-1), p(i+1), …, p(n+i), we have p(k) ≠ k (1<=k<=i-1, k ≠ j) and p(j) ≠ i. This is equivalent to the permutation p(1), p(2), …, p(i-1), p(i+1), …p(n+i) such that p(k) ≠ k (1<=k<=i-1). The number of permutations is B[i-1]. For both cases, there are i-1 such j’s, so the total number of permutations is (i-1)(B[i-2]+B[i-1]) If j > i, the remaining subproblem now is to count number of permutations p(1), p(2), …, p(i-1), p(i+1), …, p(n+i) such that p(k) ≠ k (1<=k<=i-1). The number of permutations is B[i-1]. Since there are n such j’s, the total number of permutations is n*B[i-1].
Therefore, B[i] = (i-1) (B[i-2] + B[i-1]) + n*B[i-1] = (i-1) B[i-2] + (n+i-1) B[i-1]. So, we can simply compute B[1], …, B[m] in O(m) complexity.
Finally, B[1] xor B[2] xor … xor B[m] is the answer that should be returned.

#include <bits/stdc++.h>
using namespace std;
const int mo = 1000000007;
int ans, B[200000];
class DerangementsStrikeBack
{
public:
    int count(int n, int m)
    {
        B[0] = 1;
        B[1] = n;
        for (int i = 2; i <= m; ++i)
            B[i] = ((long long)(i - 1) * B[i - 2] + (long long)(n + i - 1) * B[i - 1]) % mo;
        int ans = 0;
        for (int i = 1; i <= m; ++i)
            ans ^= B[i];
        return ans;
    }
};