You are not logged in. Please login at www.codechef.com to post your questions!

×

FOMBRO - Editorial

PROBLEM LINK:

Practice
Contest

Author: Devendra Agarwal
Tester: Anudeep Nekkanti
Editorialist: Amit Pandey

DIFFICULTY:

Simple.

PREREQUISITES:

Dynamic programming and basic mathematics.

PROBLEM:

You are given a function f which is defined as: $$f(N) = 1^N 2^{N-1}.....N^1$$ Find $$\frac {f(N)}{f(r)f(N-r)} \mod M$$

QUICK EXPLANATION:

Let $r = \min(r,N-r)$. There will be three cases: $x \le r$, $r < x \le N-r$ and $N-r < x \le N$. Calculate power of $x$ in each of the case and multiply them taking modulo $M$.

EXPLANATION:

The give problem can be solved using simple dynamic programming approach.

Let $r = \min(r,N-r)$ and call $ F(N,r) = \frac {f(N)}{f(r)f(N-r)} $.

Case 1$(x \le r)$:

Power of $x$ in $f(N)$= $N -x+1$.
Power of $x$ in $f(r)$= $r-x+1$.
Power of $x$ in $f(N-r)$= $(N-r)-x+1$.
Hence, Power of $x(\le r)$ in $F(N,r)$= $(N-x+1) - (r-x+1) - ((N-r)-x+1) = x-1$.

Case 2$(r < x \le N-r)$:

Power of $x$ in $f(N)$= $N-x+1$.
Power of $x$ in $f(r)$= $0$. as $(x > r)$
Power of $x$ in $f(N-r)$= $(N-r)-x+1$.
Hence, Power of $x$ in $F(N,r)$= $(N-x+1) - ((N-r)-x+1) = r $.

Case 3$(N-r < x \le N)$:

Power of $x$ in $f(N)$= $N-x+1$.
There will not be any term corresponding to denominator. Hence, Power of $x$ in $F(N,r)$= $(N-x+1)$.

As, there can be large number of queries. We need to do some pre-processing to give results. As, results to first and third case doesn't depend on the value of $r$, we can pre-process them and store.

    //Case I : For the given value of r, fordp[r] will store multiplication 
      of all x corresponding to the first case.
    for(int i=1;i<=N/2;i++) 
         fordp[i] = (fordp[i-1]*binpow(i,i-1,M))%M;

In case 2, it can be noticed that power of $x$ depends on $r$ and the distance of $r$ and $N-r$ from $N/2$ will be the same. So, we can store multiplication of terms which are equi-distance from center in an array. So, that we can get value of $Midr = \prod_{r+1}^{N-r} x$ in constant time.

     //Case 2 : You can get Midr in O(1) time.
     if(N&1)
          betdp[N/2] = N/2 +1; 
     else
          betdp[N/2]=1;
     for(ll i=N/2-1;i>=1;i--)
      betdp[i] = ((ll)((betdp[i+1]*(i+1))%M)*(ll)(N-i))%M;

Case 3 will not depend on the value of $r$, so we can do it similar to case 1.

    //Case III
     for(ll i=1;i<=N/2;i++) 
           backdp[i]= (backdp[i-1]*binpow(N-i+1,i,M))%M;

Finally you can calculate the output easily. See Setter's code for the detailed implementation.

Second case i.e. calculating $\prod_{r+1}^{N-r} x % M$ can also be done using the segment tree. In the segment tree, a node will store the multiplication of both of the children mod $M$. Refer this wonderful tutorials for the more details on segment tree. See tester's code for the implementation of this approach.

Solutions:

Setter's solution can be found here.
Tester's solution can be found here.

asked 10 Feb '15, 00:35

amitpandeykgp's gravatar image

4★amitpandeykgp
25911522
accept rate: 0%

edited 11 Feb '16, 19:13

admin's gravatar image

0★admin ♦♦
19.8k350498541


I've solved with another approach, no segment tree is needed, just math.
We can see, that F(n) = n! * (n-1)! * ... * 2! Lets rmin = min(r, n - r) and rmax = max(r, n - r)
So, answer is (n! * (n - 1)! * ... * 2!) / ((rmin! * (rmin - 1)! * ... * 2!) * (rmax! * (rmax - 1)! * ... *2!))
Let's make it simpler by removing f(rmax):
(n! * (n - 1)! * ... * (n - rmax + 1)!) / (rmin! * (rmin - 1)! * ... * 2!)
Now we can see that number of the terms in the denominator + 1 equal number of terms in the numerator, so we can separately divide: (n-1)! / rmin!, (n-2)! / (rmin-1)!, ... , (n-rmax+1)! / 2!
Let's see what we have: (n-1) * (n-2)^k1 * (n-3)^k2 * ... * 5^k2 * 4^k1 * 3
ki depends on rmin. when rmin == 2, all ki == 1
when rmin == 3, all ki == 2
when rmin == 4, k1 == 2, ki == 3 for each i>2
and so on.
Let's denote this product X(rmin), so the final answer will be n! * X(rmin) % m.
For each n and m we precalculate X(i) [2 <= i <= n/2] with complexity O(n).
Final answer we get for O(1).
Do not forget to process corner cases separately, when n < 5 or r == n - 1.
Total complexity: O(N). Solution

link

answered 16 Feb '15, 06:52

rotozoom's gravatar image

3★rotozoom
412
accept rate: 0%

edited 16 Feb '15, 06:54

this was EXACTLY my approach!! easy to implement, which helped me to quickly solve 3 questions :D here's my code, its a little simpler: http://www.codechef.com/viewsolution/6283536

(19 Feb '15, 12:26) gvaibhav217★

@rotozoom I also tried the same approach during contest, but got stuck on the step where you have mentioned

Let's see what we have: (n-1) * (n-2)^k1 * (n-3)^k2 * ... * 5^k2 * 4^k1 * 3

I am still unable to understand how this step came. Could you please elaborate a bit more?

(22 Feb '15, 23:41) chandan7212★

Access to the source codes denied on the links given.

link

answered 16 Feb '15, 00:15

sahil2305dua's gravatar image

3★sahil2305dua
112
accept rate: 0%

Will be updated in few minutes.

(16 Feb '15, 00:20) amitpandeykgp4★

could someone give me list of problems with similar idea which is used in tester's code? thanks in advance!

link

answered 16 Feb '15, 01:39

k0stia's gravatar image

4★k0stia
416
accept rate: 0%

Are you interested in segment tree?

(16 Feb '15, 13:07) amitpandeykgp4★

I used segment tree for case 2 ... does it take time really more than given limit or its just because of JAVA that it showed TLE

link

answered 17 Feb '15, 04:16

shubham011's gravatar image

5★shubham011
1783718
accept rate: 0%

I don't think so, check other's code soe might have got accepted.

(17 Feb '15, 15:45) amitpandeykgp4★

@gvaibhav21 awesome solution.

link

answered 19 Feb '15, 23:12

nivin's gravatar image

4★nivin
1113
accept rate: 0%

The answer directly started with case 1(x<=r). could someone tell me what value is "x" holding here? Also i really didn't understood the math behind this question.

link

answered 21 Feb '15, 17:50

sjnonweb's gravatar image

2★sjnonweb
1
accept rate: 0%

For example if N=5,r=2

F(5,2)=(5!4!3!2!)/((3!2!)(2!))=((5!*4!)/2!)=

5^14^23^22^1 = [(5^1) * (4)^2 ] [(3)^2] *[ (2^1) ]

                   ^              ^         ^
                   |              |         |
                  Case 3        Case 2     Case 1

Here x is the the base i.e {5,4,3,2}.

(21 Feb '15, 23:42) rahul_nexus2★

Can someone please explain case 2. The if else statement and the for loop statements. I do not understand the math behind it.

link

answered 23 Feb '15, 00:15

prateekjjw001's gravatar image

4★prateekjjw001
462
accept rate: 10%

It is basically about whether N is even of odd, and we are taking the multiplication for the range [N/2-x,N/2+x], So In case of N is odd, we have to initialize product by N/2+1.

(23 Feb '15, 10:55) amitpandeykgp4★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,212
×1,191
×139
×109
×4

question asked: 10 Feb '15, 00:35

question was seen: 3,283 times

last updated: 11 Feb '16, 19:13