coderdhanraj's blog

By coderdhanraj, 2 years ago, In English

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.

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think number of valid different permutations should be = (m*(m+1)*(m+2)*...*(m+n-1))/(n*(n-1))

»
2 years ago, # |
Rev. 10   Vote: I like it 0 Vote: I do not like it

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$$$.

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

    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)

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

      Ok, thanks.

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

      or it would rather be smarter to preprocess the inversions for the factorials at the same loop you do the factorials

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

        why would that be smarter

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

          'cause it's always faster to multiply only $$$1$$$ integer instead of $$$n$$$ of them

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

            I think I'm missing something, either way you have to multiply each one of them

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 12   Vote: I like it 0 Vote: I do not like it

      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
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This is good but you can count inversions in linear time instead of nlogn

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
          Rev. 4   Vote: I like it 0 Vote: I do not like it

          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.

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

            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

            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
              Rev. 2   Vote: I like it +3 Vote: I do not like it

              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.

»
2 years ago, # |
  Vote: I like it +38 Vote: I do not like it

This problem is a blatant copy of 1580F - Problems for Codeforces. It's also very difficult and the previous commenters' answers are wrong.

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    Damn! Companies are asking $$$3300$$$ rated problem in an intern hiring test where hardly a coder would have ~$$$2100$$$ rating on Codeforces.

  • »
    »
    2 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    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

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

    OMG, it is a 3300 rated problem. Why do companies ask this difficult of a problem ?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    At least they bothered to change up the statements...

    ah yes, the problems are very different