astitva19's blog

By astitva19, history, 2 months ago, In English

I had some issues with understanding Ques A from Edu Round 112, but I found a different way of approaching the problem.

Consider x,y,z to be the Pizzas ordered of slices 6, 8 and 10 respectively.

Thus we require:

$$$6x+8y+10z \leq n$$$

=> $$$ 2 \times (3x+4y+5z) \leq n$$$

We see that any integer k>=3 can be represented by the expression 3x+4y+5z with non negative values of x,y,z (atleast one such triplet x,y,z will always exist) .

(This observation is key to the approach. The proof of this observation is given at the end of this article.)

Thus, any even integer>=6 can be represented by 2*(3x+4y+5z) = 6x+8y+10z . #OBSV1

Now, we know that in order to minimize the time, we would want the number of final slices that we order to be as close to n as possible. In other words, we would want the extra slices we order (that take extra time to make) to be as close to 0 as possible.

If n is even (and >=6) then we can write it in terms of 2*(3x+4y+5z) exactly (#OBSV1); the number of extra slices we order will be 0.

If n is odd (and >6), then we cannot write n as 2*(3x+4y+5z) exactly because this expression will always give an even number. However, we can write n+1 as 2*(3x+4y+5z) exactly, making the number of extra slices we have to order just 1.

The total time taken would be 15x + 20y + 25z = 5*(3x+4y+5z). Thus, if we know the optimal answer for 3x+4y+5z ,we can easily calculate the total time by multiplying this by 5.

Hence, we have an algorithm:

-> If n<6 then we would have to order atleast the 6 slices pizza. Thus the minimum time possible for this case would be 15 mins directly.

-> Else If n is even then divide n by 2 and find the optimal value of 3x+4y+5z, or else if n is odd then divide (n+1) by 2 and find the optimal value of 3x+4y+5z.

-> Multiply the optimal value of 3x+4y+5z by 5 to get the minimum time to get atleast n slices.


Appendix

Proof that any integer k >= 3 can be written in the form of 3x+4y+5z where x>=0, y>=0 and z>=0 :

This proof is trivial for the cases of k=3, k=4, k=5.

Thus consider k>=6.

By the division theorem:

$$$ k = 3 (\lfloor \frac{k}{3} \rfloor) + k\%3 $$$

=> $$$ k = 3(\lfloor \frac{k}{3} \rfloor - 1) + 3 + k\%3 $$$

Now 3 + k%3 can be either 3 or 4 or 5.

In either case, we have represented k as a linear combination of 3 , 4 and 5 i.e. k = 3x+4y+5z.

It can also be seen that in our representation x,y,z will be non negative integers.

Hence proved.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by astitva19 (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks for sharing.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

this problem was based on Chicken McNugget Theorem

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you elaborate on how is this used in the problem?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      from 3,4 we cannot create 3*4-3-4 = 5 , so the setter gave us extra 5 in the form of 10, so now we can create every number .(as they are 6 and 8, only even numbers can be created)

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Okay. Makes sense now. Thanks