1
$\begingroup$

N students sit in a line, and each of them must be given at least one candy. Teacher wants to distribute the candies in such a way that the product of the number of candies any two adjacent students have, is not greater than M.

Given N and M, we have to find the number of ways Teacher can distribute the candies.

Example : Let N= 2 and M=3 then answer is 5 as Possible sequences are:

{1, 1}, {1, 2}, {1, 3}, {2, 1} and {3, 1}.

How to count these ways for given N and M?

$\endgroup$
  • $\begingroup$ How many candies to distribute? $\endgroup$ – Masacroso Oct 10 '14 at 9:15
  • $\begingroup$ @Masacroso Assume Teacher have infinite candies .We need to count all the ways satisfying this condition.Obviously No two adjacent students can have product of the number of candies greater than M .So answer is going to be finite $\endgroup$ – user119249 Oct 10 '14 at 9:20
  • 1
    $\begingroup$ Are you looking for an explicit formula or a means of calculation? The former is Hard, but the latter is actually relatively straightforwards with a combination of a recurrence formula and memoization. $\endgroup$ – Steven Stadnicki Oct 10 '14 at 22:16
  • 2
    $\begingroup$ A note for anyone who might be considering answering: this is a problem from an ongoing contest, codechef.com/TCFS15P/problems/CANDIS . $\endgroup$ – Steven Stadnicki Oct 10 '14 at 23:05
0
$\begingroup$

Seems a really hard problem... To calculate the valid pairs you need the notion of $\lfloor\sqrt M\rfloor$ that is the central point from where start the definition for valid pairs.

And is important to note too that $|(b-a)a|<|b^2|;\ \forall n\geq a;\ b,a\in\Bbb N$. From here are obvious four things:

1) All pairs of naturals $a\cdot b$ where $a,b\in\{1,...,\lfloor\sqrt M\rfloor\}$ are valid.

2) All pairs $1\cdot b$ where $b\in\{1,...,M\}$ are valid.

3) All pairs $a\cdot b$ where $b=\lfloor\sqrt M\rfloor +c;\ c\in\{1,...,\lfloor\sqrt M\rfloor\}$ and $a\leq \lfloor\sqrt M\rfloor -c;\ c\in\{1,...,\lfloor\sqrt M\rfloor\}$ are valid pairs

4) Could be some pairs $a\cdot b$ where $b=\lfloor\sqrt M\rfloor$ and $a=\lfloor\sqrt M\rfloor +d;\ d\leq \frac{M-\lfloor\sqrt M\rfloor^2}{\lfloor\sqrt M\rfloor}$ are valid pairs.

We can resume all these things on just two:

  • $a\cdot b$ where $a\in\{2,...,\lfloor\sqrt M\rfloor\}=A$, and $b\in\left\{2,...,\left\lfloor\frac{M}{\lfloor\sqrt M\rfloor}\right\rfloor\right\}=B$ are valid pairs,

  • and $1\cdot c$ where $c\in\{1,...,M\}=C$ are valid pairs too.

All possible ordered pairs will be $P=|A|^2+2|C|+2|B-A||A|-1=2\left\lfloor\frac{M}{\lfloor\sqrt M\rfloor}\right\rfloor(\lfloor\sqrt M\rfloor-1)+2M-\lfloor\sqrt M\rfloor^2$

We can see that we have now four kind of numbers: $a\in A$, $b^*\in B-A$, $c^*\in C-B-A-1$ and $1$. Any number $a$ can be surrounded by $a,b^*$ or $1$. Any number $b^*$ can be surrounded by a number $a$ or $1$. And any number $c^*$ just can be surrounded by $1$.

For $N=2$ all possible strings will be $P$. For $N>2$ we can see what happen with validity constructing strings step by step. All strings with $1$ and $a$ are valid so we must see how we can put $b^*$ and $c^*$ numbers that lead to valid strings.

You must notice that this partition on elements $\{1,a,b^*,c^*\}$ is well defined only for $M>3$. For $M\leq 3$ the partition is just $\{1,c\}$.

I will note the number of possible variations of each number as $|a|$ for $a$, $|b^*|$ for $b^*$ and so on. This number is just the cardinality of the set where they take values.

STRINGS WITH ONLY $\{1,a\}$

These kind of numbers can stay in any order together so the strings composed only by $\{1,a\}$ will be

$$f_a=\sum_{k=0}^{N}\binom{N}{k}|a|^k=(|a|+1)^N$$

STRINGS WITH ONLY $\{1,a,b^*\}$

The number $b^*$ cant be consecutive to itself. I will use a trick here: define numbers of chains (and it length) of $b^*$. A chain will be $b^*$ numbers separated by a $1$ or an $a$ that I will note as separators and call them as $s$ example: $b^*,s,b^*,s,b^*,...,b^*$. Any chain start and end on a $b^*$ and it length will be 2 times the number of $b^*$ less $1$, i.e., $b_i=2i-1$. Example $b_2\equiv(b^*,s,b^*)$.

Two different chain will be separated, by definition, by at least to separators, if it only one they will be one chain and not two. So for every chain will subtract to $N$ 2. If I have 3 chains then $N^*=N-2\cdot 3$.

The variations for a string $b_i$ will be $V(b_i)=|b^*|^i(|a|+1)^{i-1}$. The variations for separators between chains is $V(s,k)=(|a|+1)^k$ where $k=|N|-\sum m_i(2i-1)$, where $m_i$ is the multiplicity for each chain of length $2i-1$.

Now I define the function of valid strings $f_b$ for a setup of strings $b_i$ with multiplicity $m_i$:

$$f_b(m_ib_i,m_jb_j,...)=(\prod V(b_i)^{m_i})V(s,k)\frac{((\sum m_i)+|N-N^*|)!}{k!\prod m_i!}$$

The ugly task is the setup of all possible combination of chains by length and multiplicity for a master length of $N$.

STRINGS WITH ONLY $\{1,a,c^*\}$

Similar case that before but this time the separators only can be $1$. So there is a difference on the variations of $V(s,k)$ and $V(c_i)=|c^*|^i$.

STRINGS WITH $\{1,a,b^*,c^*\}$

Similar things that the cases above but this time the separators can change depending what they are separating, being just $1$ when separate chain $c_i$ and being $1$ or $a$ when separate between $b_i$ chains.

For study these combinations we can write the strings as just $3b2c3b2bbc4c$ understanding each number as the number of $b^*$ or $c^*$ of the letter after that represent a chain of this kind. An understanding too that any separator is omitted.

Indeed we can calculate use the same multiplicities $m_i$ and compositions of chains and change from $b^*$ to $c^*$ chains as they were a big group with variations.

I will leave the problem here, the rest is a bit boring and long but not too much difficult that what I answered here.

$\endgroup$
  • $\begingroup$ Can you summarise your results? Also N is at max 1000.So whats your brute solution ?But M can be upto 1000000000 $\endgroup$ – user119249 Oct 10 '14 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.