0

Given: Alice has basket that can contain flowers of sizes $1$ to $A$.
Bob has basket that can contain flowers of sizes $B$ to $C$.
Its given that $B<A<C$.
All flowers of same size should be collected by same person.
It takes 1 minute for Alice and Bob to switch their places.
We have $N$ flowers, size of $i^{th}$ flower is $a[i]$.
To find: The minimum time needed to collect the flowers.
Example:
Let Alice range be $[1, 10]$.
Let Bob range be $[9, 12]$.
Let flowers be $\{10,12,10\}$.
If Alice is collecting the first flower, then they need to switch their places so that Bob can now collect 2nd flower. Now Bob can collect $3^{rd}$ flower of size $10$ but since Alice already picked flower of that size, they again switch places and Alice collects the last flower. Obviously this is not the best option to begin with Alice here, but I introduced it just to make the question clear.

leonbloy
  • 63,430
  • Notice that if you determine ahead of time who is picking what sizes of flowers for flowers whose sizes are between $B$ and $A$, then that will determine when Alice and Bob need to switch. You could brute force every combination of who is picking which size of flower and calculate the minimum times for each which would be on the order of $\mathcal{O}(N\cdot 2^{A-B+1})$. I'm guessing you are looking for something a bit faster though? – benguin Mar 21 '17 at 13:38
  • Yes something better like $O(N*A)$ or $O(N^2)$ –  Mar 21 '17 at 14:30
  • Why is this tagged under "coding theory"? – MathematicianByMistake Mar 21 '17 at 14:38

0 Answers0