How to think about to write code of finding the longest subarray with sum greater than or equal to k in O(nlogn).

Before contest

Codeforces Round 955 (Div. 2, with prizes from NEAR!)

06:50:14

Register now »

Codeforces Round 955 (Div. 2, with prizes from NEAR!)

06:50:14

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 3845 |

2 | jiangly | 3707 |

3 | Benq | 3630 |

4 | orzdevinwang | 3573 |

5 | Geothermal | 3569 |

5 | cnnfls_csy | 3569 |

7 | jqdai0815 | 3532 |

8 | ecnerwala | 3501 |

9 | gyh20 | 3447 |

10 | Rebelz | 3409 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 171 |

2 | adamant | 163 |

3 | awoo | 162 |

4 | nor | 153 |

5 | maroonrk | 152 |

6 | -is-this-fft- | 151 |

7 | TheScrasse | 150 |

8 | atcoder_official | 145 |

8 | Petr | 145 |

10 | pajenegod | 144 |

How to think about to write code of finding the longest subarray with sum greater than or equal to k in O(nlogn).

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/25/2024 10:44:46 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

I don't understand your question. if the sum needs to be greater or equal to $$$k$$$, can't you just choose all of the elements in the array?

Put all negative integers into an array. Greedily choose all positive integers. Sort negative array by least value. Greedily choose minimum negative integer until you can't anymore.

We will call our array $$$a$$$, for every $$$0 \leq i \leq n - 1$$$ we keep a number $$$ps_i = a_0 + a_1 + \dots + a_i$$$.

For any $$$0 \leq l \leq r \leq n - 1$$$ we can find $$$a_l + a_{l + 1} + \dots + a_r$$$ in $$$O(1)$$$ using the fact that its value is equal to $$$ps_r - ps_{l - 1}$$$ (if $$$l = 0$$$ we dont include $$$ps_{l - 1}$$$)

Using this we write a function $$$check(s)$$$ which will heck all subarrays of size $$$s$$$, if there is at least one with sum greater or equal to $$$k$$$ it returns 1 and otherwise 0. this will work in $$$O(n)$$$.

Now we can just do a binary search on the size of the subbarray. thus the time complexity is $$$O(n \log n)$$$.

codeBinary search doesn't work. You're incorrectly assuming that if there exists no good subarray of length $$$m$$$, there cannot exist a good subarray with length $$$\ge m$$$. This is just not true.

Consider the following example: $$$n = 5$$$, $$$k = 50$$$, $$$a = [10, 10, 10, 10, 10]$$$. There exists a single good subarray $$$a[1:5]$$$ with length $$$5$$$, but your binary search won't find it.

Run resultsI'll give you another example. Let $$$n = 12$$$, $$$k = 60$$$, $$$a = [-10, -10, 10, 10, 10, 10, 10, 10, -10, 10, -10, -10]$$$. There are two good subarrays, $$$a[3:8]$$$ and $$$a[3:10]$$$ with lengths $$$6$$$ and $$$8$$$, but your binary search will "skip over" the one with length $$$8$$$ and only return $$$6$$$.

Run resultsLet's actually prove that the problem can't be solved with binary search (at least in the way you did it). Consider the last example I gave. I'll modify your program to print the result of $$$check(s)$$$ for all possible $$$s$$$.

CodeRun resultsIf you anything about binary search, you can see that the function $$$check(s)$$$ is not binary searchable.