You are not logged in. Please login at www.codechef.com to post your questions!

×

How to solve 'F2. Lightsabers (medium)' from Codeforces?

Link to the problem: http://codeforces.com/problemset/problem/958/F2 I thought of doing it, this way: We need to find the smallest length subarray which has each light-saber either greater or equal to the requirement, then minimum deletion will be equal to the sum of extra light-saber of each type.

To implement this I thought of maintaining a prefix-sum array for each of the m light-saber, then using the prefix sum array and binary search we can find the "the smallest length subarray which has which has each light-saber either greater or equal to the requirement. However the time complexity of this solution will be O(M * N * log(N)) which will Time-Out for the given constraint.

What can be an optimal solution?

asked 28 May '18, 00:33

sorb1997's gravatar image

4★sorb1997
1509
accept rate: 10%

edited 28 May '18, 00:35


Your thinking is very clear, but we may wish to think from another perspective, first solve some sub-questions, and consider the final choice of the interval is [1, R1] what is the minimum R1, then consider the final choice of the interval is [2, R2] what is the minimum R2, and so on, This is obvious that Rn >= Rn-1 >= ... >= R2 >= R1, so we can use two-pointers to solve these sub-problems, so the overall time complexity is O(n). sorry for my poor english :)

link

answered 28 May '18, 13:40

freeloop's gravatar image

6★freeloop
3443
accept rate: 47%

Thanks freeloop :)

(28 May '18, 13:56) sorb19974★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,595
×1,038
×682
×98
×53

question asked: 28 May '18, 00:33

question was seen: 100 times

last updated: 28 May '18, 13:56