ChitreshApte's blog

By ChitreshApte, history, 11 days 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

»
11 days 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}$$$.

  • »
    »
    11 days 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.

    • »
      »
      »
      11 days ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      For each pair x, y you can write $$$n = 2^x 3^y + z$$$. The associated cost is $$$px + qy + rz$$$.

»
11 days ago, # |
Rev. 3   Vote: I like it -9 Vote: I do not like it

I was mistaken I didn't see the contraints

»
11 days 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))
  • »
    »
    11 days 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.

    • »
      »
      »
      11 days 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.

      • »
        »
        »
        »
        11 days 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.

        • »
          »
          »
          »
          »
          11 days 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$$$.

          • »
            »
            »
            »
            »
            »
            11 days 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.

        • »
          »
          »
          »
          »
          11 days ago, # ^ |
            Vote: I like it -10 Vote: I do not like it

          Yeah this solution is horribly wrong. Don't think we can use recursion to solve this problem.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

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

    • »
      »
      »
      11 days ago, # ^ |
      Rev. 3   Vote: I like it -10 Vote: I do not like it

      Yeah you are correct. I didn't think of many test cases and also used a wrong assumption.

»
11 days 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