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

×

SEALCM - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sergey Nagin
Tester: Shiplu Hawlader
Editorialist: Lalit Kundu

DIFFICULTY:

MEDIUM-HARD

PRE-REQUISITES:

Solving Dynamic Programming with Matrix Expo

PROBLEM:

In this problem Sereja is interested in number of arrays A[1], A[2], ..., A[N] (1 ≤ A[i] ≤ M, A[i] - integer) such that least common multiple (LCM) of all its elements is divisible by number D.

Please, find sum of answers to the problem with D = L, D = L+1, ..., D = R. As answer could be large, please output it modulo (109 + 7).

TECHNIQUE:

I will suggest to specifically read the whole post given in pre-requisite if you are not aware about this technique.

Let there be K states, s1,s2...sK.
For each state si where i = 1 to K recurrence is defined as:
f(n,si) = sum {j=1 to K} c{i,j} f(n-1,sj).
We define a transition matrix M where M[i][j]=c{i,j}.
Let's consider M{N-1}. Sum of all elements in row i will give us f(N,si) assuming f(0,i)=0 forall i.

EXPLANATION:

Let's solve for a single D first. Let's say D has prime factors p1a1, p2a2 ... pKaK, where all pi are unique.
We form a simple dp of dp[n,mask], which denotes the answer for N=n and D=product [pia_i], if i'th bit is set in mask. So, mask is a K bit number.
A simple recurrence would be:

&ret = dp[n,mask]
primes[] //prime factors of D.
count[] //count[i] denotes count of i'th prime in D
ret=0
for i = 0 to size(primes)-1:
    for j = 1 to M:
        //if j is kept at n'th index
        //and keeping it satisfies the i'th set bit condition
        //ie. count of primes[i] in j is greater than or equal to count[i]
        if count_prime(primes[i] in j) >= count[i]
            //set the i'th bit, add to current ret
            ret += dp[n-1, mask|(1<<i)]

So, we can clearly see that our dp[n,x] is dependent on dp[n-1,y], where x and y are two different masks/states. We can use matrix exponentiation here because in one state in our dp, answer for n is dependent on answer for n-1 and the transition among other states is not dependent on n.

So, we form the transition matrix, where we set at transit[i][j], the number of ways to reach mask j from mask i . Sum of all elements in (2K-1)'th (all bits of D are set) row of N-1'th power of this transition matrix, will give us the answer, in accordance with the technique explained above. Try to prove how this works.

So, complexity for single D is O(log N * (2K*3)). Note matrix multiplication of sizes P*P takes O(P3). And, maximum K is until 235711*13... is smaller than 1000(since D<1000). So, max K is 4. Total complexity for single D is O(log N * 212).

Doing it for 1000 such values of D will take O(log N * 222) worst case. Note it will be really lower than that because of variation in K.

SOLUTIONS:

Setter's solution
Tester's solution

This question is marked "community wiki".

asked 12 Jan '15, 15:08

darkshadows's gravatar image

5★darkshadows ♦
3.0k91161186
accept rate: 12%

edited 12 Jan '15, 16:06


16

This problem can be solved easily with inclusion exclusion principal too . http://www.codechef.com/viewsolution/5846988 Heres my solution . First factorize all the numbers in the form d = p * q * r * s where p,q,r and s are powers of prime numbers . Do this for all numbers from L to R . Then apply inclusion exclusion . See the code for more understanding

link

answered 12 Jan '15, 16:00

rajat1603's gravatar image

7★rajat1603
936112
accept rate: 4%

exactly what i did..

(12 Jan '15, 16:55) fauzdar656★

The constraints were low enough to use IEP for at max '4' elements.

(12 Jan '15, 19:45) animesh_f ♦6★

Inclusion Exclusion. Helped by a pen and lots of paper. Time Complexity is O(log(n)*2^15). That's almost 250 times faster than required. Made me wonder for a long time if I was missing something.

http://www.codechef.com/viewsolution/5867632

link

answered 13 Jan '15, 00:43

gkcs's gravatar image

4★gkcs
2.5k11025
accept rate: 9%

edited 13 Jan '15, 08:29

Another Inclusion Exclusion guy here. Having used python, I did not have to hard-code for different number of factors.

from itertools import combinations FTFW xD

http://www.codechef.com/viewsolution/5835895

link

answered 13 Jan '15, 09:28

grebnesieh's gravatar image

6★grebnesieh
707211
accept rate: 16%

Any idea someone how to use the fact, that N, M <= 10? Brute force worked fine for test cases, but I didn't try for 10^10...

link

answered 13 Jan '15, 17:44

betlista's gravatar image

3★betlista ♦♦
16.8k49115224
accept rate: 11%

edited 13 Jan '15, 17:45

1

To explore N, M <= 10 we can use a simple dynamic programming algorithm.

First, note that the maximum LCM of an array with numbers 1..10 is 2520 (5 * 7 * 8 * 9). So our search state will be how many arrays are there with X numbers and lcm L. This yields 10*2520 states and we need to check all numbers 1..N and all lcms 1..2520.

My code: http://www.codechef.com/viewsolution/5751475

(13 Jan '15, 23:38) mogers5★

Thanks ;-)

(13 Jan '15, 23:49) betlista ♦♦3★

Hi

I can't open neither setter's solution nor tester solution, can you please check this links.

Thanks.

link

answered 21 Jan '15, 00:05

pachon_1992's gravatar image

2★pachon_1992
1112
accept rate: 0%

can anyone explain the editorial for newbies like me so that we can progress further, im not getting anything in the editorial as i dont know anything about bit masks.

link
This answer is marked "community wiki".

answered 27 May '15, 17:39

raghu_317's gravatar image

5★raghu_317
19815
accept rate: 0%

The solution links of setter and tester are not working. Can you please check that?

link

answered 21 Jan '15, 14:28

loch_ish's gravatar image

2★loch_ish
26
accept rate: 25%

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:

×11,987
×1,292
×828
×202
×166
×10

question asked: 12 Jan '15, 15:08

question was seen: 7,145 times

last updated: 27 May '15, 17:39