Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

2020's blog

By 2020, history, 4 weeks ago, In English,

There's a scientist named Brook who is interested in budding of cells. He has one container which initially contains only a single cell. Now Brook wants n number of cells in his container. So he can change the number of cells in container in 3 different ways -:

Double the number of cells present in the container.

Increase the number of cells in the container by 1.

Decrease the number of cells in the container by 1.

Now, all the above operations have different costs associated with them x,y,z respectively for above operations. Help brook in finding the minimum cost to generate n cells in the container starting from one cell Constraints 1<=n<=10^5 1<=x<=y<=z<=10^5

Output Format Output an integer denoting the minimum cost incurred to create n cells

Sample Input 5 2 1 3 Sample Output 4 i have been trying hard but cant get around what can work for this question

Tags #dp
 
 
 
 
  • Vote: I like it
  • +16
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

Think of it as a shortest paths problem on a graph. To guarantee correctness, create a graph with 2e5 vertices.

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

    Does the number of nodes are 2 times the n?

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

This is a classic example of making a node for each number, where each node has an outdegree of 3.

The more interesting version of this problem has n up to 10^18, so you can’t do that naively.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I am pretty sure you can make some greedy observations, assuming x=y=z for the hard version

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

      if $$$x = y = z$$$
      then we just need to calculate the first power of $$$2$$$ smaller or equal to $$$n$$$
      and the first power of $$$2$$$ greater or equal to $$$n$$$
      $$$a = 2^m \le n$$$ $$$,$$$ $$$m$$$ is maximum possible
      $$$b = 2^t \ge n$$$ $$$,$$$ $$$t$$$ is minimum possible

      $$$ans = x \times min(m + (n - a) , t + (b - n));$$$

      but can it be solved when there are no restrictions on $$$(x , y , z)$$$ ?

      $$$UPD$$$ incorrect solution

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +22 Vote: I do not like it

        Your solution is incorrect. It can be proven that the answer is less than $$$2 \cdot log(n)$$$ for $$$x = y = z = 1$$$ (using only additions and doubling), and your solution is of order $$$O(n)$$$.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it +4 Vote: I do not like it

          yeah you're right it's incorrect, I didn't consider some additions and then doubling.
          but for time complexity it's $$$O(log (n))$$$ because I'm just considering powers of two and if $$$n = 10^{18}$$$ it will be $$$O(60)$$$, because $$$2^{60}$$$ is greater than $$$10^{18}$$$
          code.
          correct me if I'm wrong.

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it +9 Vote: I do not like it

            I was referring to the solution complexity (how big your solution is), not the time complexity of the algorithm. You are right, the solution runs in $$$O(log(n))$$$, but your answer is of order $$$O(n)$$$.

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
                Vote: I like it +4 Vote: I do not like it

              yeah the answer is in order of $$$O(n)$$$.
              thanks for discussing the issue of my solution, I'll try better next time :D.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    How to solve the problem with constraints upto 10^18?

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

    I was just thinking if it's possible to do this kind of question using dp somehow like can we create state and state transition for this type of question I found a solution but not able to prove that this works

    [user:agtxdy][user:agtxdy] if i is even dp[i]= min(dp[i/2]+x,dp[i-1]+y} ;

    if i is odd dp[i]=min(dp[i-1]+y,dp[i+1/2]+x+z} ;agtxdy

  • »
    »
    4 weeks ago, # ^ |
    Rev. 10   Vote: I like it +23 Vote: I do not like it

    It can be proven that the number of doubling operations should be relatively small (less than $$$2 + log_{2}(n * max(y, z))$$$). Let's iterate over this number of operations, and call it $$$a$$$.

    Without any additions/subtractions, the final number would be $$$2^a$$$. Now, any addition or subtraction can add/subtract any power of two of form $$$2^b$$$, where $$$b \leq a$$$, depending on where it is placed. Also, at most one addition/subtraction of $$$2^b$$$ with $$$b < a$$$ makes sense. In fact, we can argue that $$$n$$$ will be formed by satisfying the equation $$$n = 2^a * k + b$$$, where $$$|b| < 2^a$$$. It can be seen that only a handful of values for $$$k$$$ make sense in a scenario like this (2 at most).

    Let's add cost $$$n\text{ div }2^a * y$$$ to our current case, and set $$$n' = n\text{ mod }2^a$$$. Now we're left with an easier problem, writing $$$n'$$$ as a sum of powers of $$$2$$$, with sign either $$$+1$$$ or $$$-1$$$ (note the fact that the upper bound on the power of $$$2$$$ has disappeared, this is ultra important). It's important that you convince yourself that we're allowed to do thnt.

    This problem can be solved using dp in complexity $$$O(a)$$$.

    Total complexity is $$$O(log^2(n * (x + y + z)))$$$

    Source code: https://pastebin.com/84Fcm9SP

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you give me the link of this problem for practicing?