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} \lt m$$$, and $$$a_1 + a_n \lt 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 :
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$$$.
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.
I think number of valid different permutations should be = (m*(m+1)*(m+2)*...*(m+n-1))/(n*(n-1))
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$$$.
no no no
You don't calculate newtons binomial like that :)
you dont divide by n!, you multiply by inversions of every number between [2 ... n], so
inv(2) * inv(3) * ... * inv(n) (of course keeping everything in check using modulo)
Ok, thanks.
or it would rather be smarter to preprocess the inversions for the factorials at the same loop you do the factorials
why would that be smarter
'cause it's always faster to multiply only $$$1$$$ integer instead of $$$n$$$ of them
I think I'm missing something, either way you have to multiply each one of them
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.
This is good but you can count inversions in linear time instead of nlogn
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.
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
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.
This problem is a blatant copy of 1580F - Problems for Codeforces. It's also very difficult and the previous commenters' answers are wrong.
Damn! Companies are asking $$$3300$$$ rated problem in an intern hiring test where hardly a coder would have ~$$$2100$$$ rating on Codeforces.
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
OMG, it is a 3300 rated problem. Why do companies ask this difficult of a problem ?
At least they bothered to change up the statements...