2
$\begingroup$

Problem: There are infinite number of spoons and forks at your disposal. You have to keep a total of n spoons and forks on a table in a row. As soon as you keep a fork, you will have to keep forks alternately. If the first time you kept a fork was at position i, you will have to keep forks at positions i+2, i+4, i+6.. and so on. How many arrangements are possible? Since the answer could be very large, print it modulo 109+7.

Constraints: 1 $\leqslant$ n $\leqslant$ 109

Time Limit: $1$ sec

Sample Input 1: $3$

Output 1: $6$ (SSS, SSF, SFS, SFF, FSF, FFF)

Sample Input 2: $5$

Output 2: $14$

The way I solved it (inefficient):

Keep n spoons first. Start from the end and replace each spoon with a fork. When you've replaced i spoons with i forks at the end, there are 2i/2 combinations possible (since $\frac{i}{2}$ positions will have forks). So basically it's a summation of powers of 2.

Going by my method, the answer will be: Summation of the first $n+1$ terms of the following series

1 1 2 2 4 4 8 8 16 16 32 32 ...

My submission is getting the verdict Time Limit Exceeded. I can neither embed nor compute very high powers of 2, and there have been many submissions in 0.0 seconds! It must be very easy though I can't think of anything else.

What is a better method to solve this question?


[EDIT]: If the first time you keep a fork is at position $i$, you will have to keep forks at positions $i+2, i+4 ...$ and so on. This happens only ONCE.

For example, A(4) = 10. By the answers below, it is 9 (which is wrong). The 10th arrangement will be FFFS.

$\endgroup$
4
  • $\begingroup$ Curious as to where you came across this problem. Not Project Euler, is it? $\endgroup$ Sep 5, 2012 at 1:58
  • $\begingroup$ @Gerry I couldn't find it there. $\endgroup$ Sep 5, 2012 at 2:39
  • $\begingroup$ @Rick, me neither - it just smells like a PE problem. Anyway, for input 5, I get 12, not 14: sssss, ssssf, sssfs, sssff, ssfsf, ssfff, sfsfs, sfsff, sffff, fsfsf, fsfff, fffff. What am I missing? $\endgroup$ Sep 5, 2012 at 2:51
  • $\begingroup$ You're right. That'll save me some writing, since you've already enumerated those possibilities. $\endgroup$ Sep 5, 2012 at 2:58

2 Answers 2

6
$\begingroup$

It can also be completely analyzed without recursion.

Skip to the bottom for the solution to the updated problem.

You can start with any numbers of spoons. Once you have two forks in a row, you must continue with forks. Thus, using $\rm{S}$ for spoons and $\rm{F}$ for forks and exponents to indicate repetition, you can start with ${\rm{S}}^k$ for any $k\ge 0$. If you ever get a fork, you can follow it with another fork, in which case you have ${\rm{S}}^k{\rm{F}}^{n-k}$ for some $k\in\{0,\dots,n\}$, or you can follow it with a spoon. At that point your choices are limited, however, since at least every second utensil from this point on must be a fork. In fact, it’s not hard to see that all you can do is alternate forks and spoons until you decide to place two forks in a row (if you ever do). In short, the only possible configurations are those of the form

$${\rm{S}}^k({\rm{FS}})^\ell{\rm{F}}^m\;,$$

where $k,\ell,m\ge 0$ and $k+2\ell+m=n$.

Fix $k$ with $0\le k\le n$. Then $2\ell+m=n-k$. Each integer $\ell$ such that $0\le\ell\le\frac12(n-k)$ yields exactly one arrangement, so there are $\left\lfloor\frac12(n-k)\right\rfloor+1$ arrangements beginning with exactly $k$ spoons. This gives a total of

$$\begin{align*} \sum_{k=0}^n\left(\left\lfloor\frac12(n-k)\right\rfloor+1\right)&=n+1+\sum_{k=0}^n\left\lfloor\frac12(n-k)\right\rfloor\\\\ &=n+1+\sum_{k=0}^n\left\lfloor\frac{k}2\right\rfloor\\\\ &=n+1+\begin{cases} 2\sum_{k=0}^{(n-1)/2}k,&\text{if }n\text{ is odd}\\\\ 2\sum_{k=0}^{n/2}k-\frac{n}2,&\text{if }n\text{ is even} \end{cases}\\\\ &=n+1+\begin{cases} \frac{n^2-1}4,&\text{if }n\text{ is odd}\\\\ \frac{n^2}4,&\text{if }n\text{ is even} \end{cases}\\\\ &=\left(\frac{n}2+1\right)^2-\frac14[n\text{ is odd}]\\\\ &=\left\lfloor\left(\frac{n}2+1\right)^2\right\rfloor\;, \end{align*}$$

arrangements of $n$ spoons and forks, where $[n\text{ is odd}]$ is an Iverson bracket.

Added: In the updated version of the question there is one arrangement with no forks. Suppose now that the first fork is the $k$-th utensil from the end of the row, where $1\le k\le n$. If $k$ is even, there are $k/2$ guaranteed forks and $k/2$ free positions, for a total of $2^{k/2}$ arrangements. If $k$ is odd, there are $(k+1)/2$ guaranteed forks and $(k-1)/2$ free positions, for a total of $2^{(k-1)/2}$ arrangements. The grand total number of arrangements is therefore

$$\begin{align*} 1+\sum_{k=1}^n2^{\lfloor k/2\rfloor}&=\sum_{k=0}^n2^{\lfloor k/2\rfloor}\\\\ &=2\sum_{k=0}^{\lfloor n/2\rfloor}2^k-2^{n/2}[n\text{ is even}]\\\\ &=2\left(2^{\lfloor n/2\rfloor+1}-1\right)-2^{n/2}[n\text{ is even}]\\\\ &=\begin{cases} 2^{(n+3)/2}-2,&\text{if }n\text{ is odd}\\\\ 3\cdot2^{n/2}-2,&\text{if }n\text{ is even}\;. \end{cases} \end{align*}$$

$\endgroup$
2
  • $\begingroup$ We haven't understood the question correctly. There's an update to the question. Check it out.. $\endgroup$ Sep 5, 2012 at 20:24
  • $\begingroup$ I solved this logically, though yours is pretty mathematical. :-) $\endgroup$ Sep 5, 2012 at 21:47
5
$\begingroup$

The first step in any programming competition is to look at the constraints of the problem. Since the parameter, $n$, can be as large as $10^9$ you clearly don't want to waste your time with any program involving loops or recursion and any auxiliary numbers your solution involves almost certainly have to be small (at worst quadratic in the parameter). In other words, there'd better be a closed form solution for this problem involving at most a few expressions that are no worse than quadratic in $n$. Fortunately, there is, but you'll have to wait a bit to see it.

In the tradition of almost all programming challenges, I'll obfuscate things as much as possible, trying to find wording that I (and only I) consider cloyingly cute and nerdy. Imagine, then, a mathematically-inclined butler laying out the silverware according to your specifications (it has to be the butler, obviously, since he's the only household staff member permitted to touch the very expensive silver). The first thing he learned in his training was "serve from the left" (and take away from the right, but that won't come into play now), and that's what we'll do: build strings of "S"s and "F"s, starting at the left, and we'll count the number of possible arrangements, given the rules you laid out.

There are two things to notice: first, starting with an "S" doesn't constrain us in any way, so if we let $A(n)$ count the number of arrangements of $n$ utensils, we'll have immediately that $$ A(n) = A(n-1) + \text{some other stuff} $$ where the $A(n-1)$ term counts the number of strings starting with "S" (followed by $n-1$ characters) and the "other stuff" counts the number of strings (of length $n$) starting with "F". The second thing to observe is that if we ever build a substring of the form "...FF", any remaining characters must be "F"s.

Starting, then, with the empty string and adding characters to the right, we'll have the following possibilities at the start: enter image description here

Working from the top down we see that there are two possible length-$1$ strings, "S" and "F", four possible length-$2$ strings and 6 possible length-$3$ strings. Using the first observation above, we can ignore the left subtree, starting with "S", since that's already taken care of by our recursion.

Now look at the right subtree, enumerating those strings that start with "F". At each level going down we'll have the counts $1$ (for the "F"), $2$ (for "FS" and "FF"), $2$ (for "FSF" and "FFF"), and a bit of thought will convince you that the sequence of the number of possible strings starting with "F" is $\langle 1, 2, 2, 3, 3, 4, 4, 5, 5, \dots\rangle$. That's just the "some other stuff" in the displayed equation above and it's easy to see that it's simply $\lfloor(n+2)/2\rfloor$, where the braces, as usual, delimit the floor function. In other words, we now have a recurrence for the number of arrangements: $A(1)=2$ and for $n>1$, $$ A(n) = A(n-1) + \left\lfloor\frac{n+2}{2}\right\rfloor $$ Expanding this, we see with the tiniest bit of algebra that $$ A(n) = 1+\sum_{k=2}^{n+2}\left\lfloor\frac{k}{2}\right\rfloor $$ That's good enough for every situation except a programming competition where $n$ may be very large. However, the sum is clearly going to be at most quadratic, so we look for a quadratic closed form for $A(n)$. One final trick comes into play here: because of the division by $2$, we'll have two different forms, depending upon whether $n$ is even or odd. To cut to the chase, it's easy enough to do some polynomial interpolation (twice) and come, at long last to $$ A(n) = \frac{1}{4}n^2 + n + \begin{cases} 1 & \text{if $n$ is even}\\ 3/4 & \text{if $n$ is odd}\end{cases} $$

$\endgroup$
10
  • $\begingroup$ That was a great answer! Thanks. $\endgroup$ Sep 5, 2012 at 11:41
  • $\begingroup$ you said that you could ignore the left subtree. How did you handle that? I couldn't follow your answer after Expanding this, we see with the tiniest bit of ... $\endgroup$ Sep 5, 2012 at 11:42
  • $\begingroup$ okay I got all of it. Can you just explain the polynomial interpolation part? I've never heard of it before. $\endgroup$ Sep 5, 2012 at 16:06
  • $\begingroup$ Unfortunately, the solution I coded is now getting the verdict Wrong Answer. There is something wrong with your solution. $\endgroup$ Sep 5, 2012 at 19:18
  • $\begingroup$ @Rushil For polynomial interpolation, a good place to start is to check out Wikipedia. In this case, you want to find a polynomial $p(x)=Ax^2+Bx+C$ that fits your data. We already know, for example, that $p(2)=4$ so $4A+2B+C=4$. We also know that $p(4)=9$ so $16A+4B+C=9$, and we can also find $p(6)=16$ so $36A+6B+C=16$. Given these three linear equations in three unknowns (namely $A, B, C$), we can solve for the coefficients of the polynomial. As to the dreaded wrong answer I'm afraid that I can't help without seeing your code. I'm sure, though, that Brian's and my answers are correct. $\endgroup$ Sep 5, 2012 at 19:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .