ChitreshApte's blog

How to solve this problem
By ChitreshApte, history, 3 years ago, In English

We start with 0 and we have to reach n

We can perform 3 operations:

  1. Multiply the current number by 2 (cost p)

  2. Multiply the current number by 3 (cost q)

  3. Increase/Decrease the current number by 1 (cost r)

Find the min-cost to reach from 0 to n 

Constraints:
10 testcases
1 <= n <= 10^18
1 <= p,q,r <= 10^9

Example:

n,p,q,r = 11,1,2,8

Answer : 20

Order: +1, *3, *2, *2, -1 = 8 + 2 + 1 + 1 + 8 = 20

  • Vote: I like it
  • +17
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Maybe generate all natural x and y such that $$$2^x 3^y \leq n$$$. There exist only $$$O(log^2(n))$$$ such pairs. Get the minimum cost seeing the solution generated by each pair.

UPD: Not always the optimal strategy. By seeing the editorial provided in the comments below, it seems we should start backwards and either decrease until zero or decrease until find a multiple of 2 or 3 of the form $$$k \ floor(\frac{n}{k})$$$ or $$$k \ ceil(\frac{n}{k})$$$. So the solution is always of the form $$$\sum c_i + \sum 2^{a_j} 3^{b_j}$$$.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The first step makes sense. How to implement the second as we can have many possibilities.

    → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it -9 Vote: I do not like it

I was mistaken I didn't see the contraints

→ Reply
»
3 years ago, # |
  Vote: I like it -26 Vote: I do not like it

I guess you can simply use recursion. Just keeping check of the usage of +1/-1 will not give TLE. Something like this:

def cost(curr):
    if curr == 0:
        return 0 
    if curr%2!=0 and curr%3!=0:
        return cost(curr - 1) + r
    ans1,ans2 = 10**18,10**18
    if curr%2==0:
        ans1 = cost(curr//2) + p 
    if curr%3==0:
        ans2 = cost(curr//3) + q
    return min(ans1,ans2)
    
    
n = 10**18
p = 1
q = 2 
r = 8 
print(min(cost(n),cost(n+1)+r))
→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    Intput -

    2 100 100 1

    Correct output - 2

    Your output — 101

    I can think of one improvement in your code $$$cost(n/2)+min(p,(n/2)*r)$$$ similarly for 3 case.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -19 Vote: I do not like it 
      def cost(curr):
    if curr == 0:
        return 0 
    if curr%2!=0 and curr%3!=0:
        return cost(curr - 1) + r
    ans1,ans2 = 10**18,10**18
    if curr%2==0:
        ans1 = min( cost(curr//2) + p , cost(curr//2) + r*curr//2 )
    if curr%3==0:
        ans2 = min( cost(curr//3) + q , cost(curr//3) + 2*r*curr//3 )
    return min(ans1,ans2)
    
    
n = 102
p = 100
q = 100
r = 1
print(min(cost(n),cost(n+1)+r))

      Yeah I think this will work. Didn't consider the case when r < p,q. Also I suppose memoization can help improve the efficiency.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Now your code reports 20 for this testcase:

        n = 61
p = 2
q = 1000000
r = 1

        While a lower cost 15 is possible by running 61 to 0 via doing +1 +1 +1 /2 /2 /2 /2 -1 -1 -1 -1 operations.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +19 Vote: I do not like it

          In fact it can be done with cost 14: $$$0 \to 1 \to 2 \to 3 \to 4 \to 8 \to 16 \to 32 \to 31 \to 62 \to 61$$$.

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            You are right. But being pedantic, I didn't claim that 15 was the minimal possible cost. Just that the last rakeshpanda's solution wasn't good enough and I successfully "hacked" it.

            → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Your code never uses the "decrease by 1" operation?

    → Reply
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

This problem was asked in previous Atcoder round. i am sharing the link below

Problem Link : Pay to Win

Editorial : this

→ Reply