Karan2116's blog

Round 334 Div 2 Editorial for first two problems

By Karan2116, history, 9 years ago, In English

Problem 1

In this problem we simply use the formula that is given in the problem however it may lead to floating point error.Hence we use the formula sum=sum+max(300*x,(1000-4*m[i])*x-50000*w[i]) and divide the final answer by 1000.
Complexity : O(1)
Code : Problem A

Problem 2

In this problem,we first reverse sort the list of sizes and then allocate the k largest sizes to k blocks then we fill the leftover n-k sizes to those k blocks such that largest of n-k pairs with smallest of k boxes and second largest with second smallest and so on.
Complexity : O(nlog(n))

Code : Problem B

  • Vote: I like it
  • -19
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

You don't need to sort the list in problem 2. The list is already sorted (ascending though). This gives a complexity of O(n).

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

Any problems with author's editorial? If you wrote another solutions for this problem it would be nice, but your solutions and author solutions are the same. I don't see any reason, why you wrote this blog.

→ Reply