### coderdhanraj's blog

By coderdhanraj, 23 months ago,

Hey Everyone,

Recently, I had my Salesforces Coding Test and I got 3 problems in which I solved 2 problems fully and solved the following problem partially with $O(n * m * m)$ using DP. Can anyone tell me the $O(n)$ approach for this problem?

## Problem : Bob and Problems

Bob and Alice are preparing $n$ problems for Hackerrank. [n-problem together can be considered as 1 problem-set]

The hardness level of the problem $i$ will be an integer $a_i$, where $a_i \ge 0.$

The hardness of the problems in a given problem-set must satisfy $a_i + a_{i + 1} < m$, and $a_1 + a_n < m$, where $m$ is a fixed integer.

Bob wants to know how many different problem-set are possible. And since this number can be huge, he wants Alice to find it under modulo $998244353$.

Note :

1. Two problem-sets of difficulty $a$ and $b$ are different only if there is an integer $j$ ($1 \le i \le n$) satisfying $a_i \neq a_j$.

2. You can choose $a_i$ as any integer greater than or equal to $0$, as long as it satisfies the constraints on line-3.

#### Constrains :

$2 \le n \le 10^5$, $1 \le m \le 10^9$

#### Sample Test Case :

Input : 3 2

Output : 4

Explanation :

The valid different problem-sets are [0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 0].

[1, 0, 1] is invalid since $a_1 + a_n \ge m$ here.

• +9

 » 23 months ago, # |   0 I think number of valid different permutations should be = (m*(m+1)*(m+2)*...*(m+n-1))/(n*(n-1))
 » 23 months ago, # | ← Rev. 10 →   0 I proved the correctness of the following formula for $n = 2$ and $3$. $f(n,m) = \binom{m+n-1}{n}$. You may try to prove it by induction for larger values of $n$. It is possible to compute $f(n,m)$ in $O(n)$ time-complexity using $n-1$ multiplication operations of integer numbers between $m$ and $m+n-1$ inclusive, and dividing the result by $n!$ modulo $998244353$.
•  » » 23 months ago, # ^ |   0 no no noYou don't calculate newtons binomial like that :)you dont divide by n!, you multiply by inversions of every number between [2 ... n], soinv(2) * inv(3) * ... * inv(n) (of course keeping everything in check using modulo)
•  » » » 23 months ago, # ^ |   0 Ok, thanks.
•  » » » 23 months ago, # ^ |   0 or it would rather be smarter to preprocess the inversions for the factorials at the same loop you do the factorials
•  » » » » 23 months ago, # ^ |   0 why would that be smarter
•  » » » » » 23 months ago, # ^ |   0 'cause it's always faster to multiply only $1$ integer instead of $n$ of them
•  » » » » » » 23 months ago, # ^ |   0 I think I'm missing something, either way you have to multiply each one of them
•  » » » 23 months ago, # ^ | ← Rev. 12 →   0 I usually use the two loops in the constructor of the following modular combinatorics class template to compute the required inverse of $n!$ using the modular inversion only one time. modular combinatorics class template#include using namespace std; template class modular_combinatorics { static constexpr int size = max+1; vector fact, ifact; public: int mul(int x, int y) const { return 1ll*x*y%mod; } int add(int x, int y) const { return (x+y)%mod; } int sub(int x, int y) const { return (x-y+mod)%mod; } int pow(int x, int y) const { int z = 1; for (; y > 0; x = mul(x,x), y >>= 1) if (y&1) z = mul(z,x); return z; } int inv(int x) const { return pow(x,mod-2); } int div(int x, int y) const { return mul(x,inv(y)); } int mac(int x, int y) const { return add(x,mul(y,x)); } int nPk(int n, int k) const { return mul(ifact[n-k],fact[n]); } int nCk(int n, int k) const { return mul(ifact[k],nPk(n,k)); } modular_combinatorics() : fact(size,1), ifact(size,1) { for (int x = 2; x < size; ++x) fact[x] = mul(fact[x-1],x); ifact[max] = inv(fact[max]); for (int x = max; x > 2; --x) ifact[x-1] = mul(ifact[x],x); } }; const modular_combinatorics<100000,998244353> mc; int main() { return 0; } 
•  » » » » 23 months ago, # ^ |   0 This is good but you can count inversions in linear time instead of nlogn
•  » » » » » 23 months ago, # ^ | ← Rev. 4 →   0 Which part of the code has $n \log(n)$ time-complexity?Computing the inverse factorials still has linear time-complexity! I am not sure what you mean by counting inversions.
•  » » » » » » 23 months ago, # ^ |   0 you're right, nice I didn't understand the code (didn't have time to in the morning).however what I usually do is calculate all inversions independently — this can also be done in linear time
•  » » » » » » » 23 months ago, # ^ | ← Rev. 2 →   +3 I see. If you are computing the inversions independently using pow(factorial[x],mod-2), then the proportionality factor should be slightly larger than using mul(inv_factorial[x],x), even though both approaches are linear time-complexity, as the modular power function should do on the average more than one modular multiplication operation.
 » 23 months ago, # |   +38 This problem is a blatant copy of 1580F - Problems for Codeforces. It's also very difficult and the previous commenters' answers are wrong.
•  » » 23 months ago, # ^ | ← Rev. 2 →   +2 Damn! Companies are asking $3300$ rated problem in an intern hiring test where hardly a coder would have ~$2100$ rating on Codeforces.
•  » » 23 months ago, # ^ | ← Rev. 4 →   0 Thanks for the helpful comment. I did not claim that the expression $f(n,m)$ is valid for all $n$.The following implementation proved that the formula is incorrect for the second sample test in the Codeforces problem statement: $n = 5$ and $m = 9$.brute-force
•  » » 23 months ago, # ^ |   0 OMG, it is a 3300 rated problem. Why do companies ask this difficult of a problem ?
•  » » 23 months ago, # ^ |   +3 At least they bothered to change up the statements... ah yes, the problems are very different Bob and Alice instead of XYMXYM and CQXYM Hackerrank instead of Codeforces