xzyxzy's blog

A way to solve 808E by ternary searching
By xzyxzy, history, 8 years ago, In English

I'm sorry to ask a foolish problem about my submission.So I share a way to solve 808E by ternary searching.

As we can see,W[i] = 1, 2, 3. We sort the Souvenirs which have the same W[i] by their C[i]. Then we know we will just choose a prefix for each W[i].

If we get X Souvenirs that W[i] = 3,we remain (m - 3X) to get Souvenirs that W[i] = 1, 2. Let's define F[i][x] the prefix sum of Souvenirs that W[i] = x. If we get Y Souvenirs that W[i] = 2,our cost is F[X][3] + F[Y][2] + F[m - 3X - 2Y][1] (m-3X-2Y>=0).

We can try every X and use ternary searching to find the best Y.The complexity is O(nlogn).

My submission:http://codeforces.net/contest/808/submission/27174539

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

»
8 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

But we know that as X increases,the optimal Y is decreasing,so you can use two-pointers to solve it.

And if you use radix sort,you can get an algorithm which complexity is O(n).

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

    That's right!Thanks for your better solution.

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

    打开CF回忆往事看到了熟悉的头像 这不会是ff吧 难道我在两年前就被ff回复过了？

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

I'm trying to learn how to prove when a function (like this one) is strictly increasing-then-decreasing (or viceversa) so to apply ternary search. How can i formally show this function holds this property ??? Other problems are welcome too

→ Reply