User_NULL's blog

[1600 rated ] why this problem is tagged as greedy ?
By User_NULL, history, 20 months ago, In English

Is there any greedy approach for finding minimum operations required for making a_i to b_i ?

https://mirror.codeforces.com/contest/1633/problem/D

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

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

This is weird! I think this is because we can know how many operations are needed to get from $$$1$$$ to $$$b_i$$$ greedily.

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

    can you share your greedy approach ?

    i've been trying but not able to come up with any!!

    → Reply
    • »
      »
      »
      20 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      We can always choose $$$x = 1$$$ so that when performing $$$a_i = a_i + \lfloor{\frac{a_i}x\rfloor}$$$ is the same as $$$ a_i = 2a_i$$$.

      Let $$$b_i$$$ is the minimum number of the above operation to get from $$$1$$$ to $$$i$$$. Sense $$$i <= 10^3$$$ so we need at most $$$\lceil \log_2{10^3} \rceil$$$ operations, $$$b_i \le 10$$$.

      Update:

      Ops! forget about it, in the last operation we can't increase by all values in the range $$$[1, a_i)$$$. Only some of them are available.

      The editorial provided a DP approach for it, check it out.

      → Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It tagged greedy because it's a knapsack problem.

By the way, thanks for sharing a great problem to solve.

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

    But the problem can't be solved greedily. The greedy approach only works with the fractional knapsack (as far as I know).

    → Reply
»
20 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Tags are sometimes wrong.

→ Reply