Hey, I know the contest was postponed, but I was trying to solve this question:↵
↵
Question:↵
↵
↵
~~~~~↵
Consider the integer sequence A[], where the elements are first N natural numbers in order.↵
↵
You are now given two integers, L and S. Determine whether there exists a subarray with length L and sum S after removing at most one element from A.↵
↵
A subarray of an array is a non-empty sequence obtained by removing zero or more elements from the front of the array, and zero or more elements from the back of the array.↵
1 <= N <= 10^9↵
1 <= L <= N - 1↵
~~~~~↵
↵
↵
↵
I came up with something like this:↵
↵
<spoiler summary="My Code">↵
↵
~~~~~↵
↵
def solve(n, l, s):↵
lo = 1↵
hi = n↵
↵
def helper(i):↵
one = i * (i+1) >> 1↵
two = 0↵
if i - l > 0:↵
two = (i-l)*(i-l+1) >> 1↵
return one - two↵
for _ in range(100):↵
mid = ((hi - lo) >> 1) + lo↵
val = helper(mid)↵
if abs(s - val) < 2:↵
if lo == 1:↵
if s - val >= 0:↵
return "YES"↵
elif mid == n:↵
if s - val <= 0:↵
return "YES"↵
else:↵
return "YES"↵
if s > val:↵
lo = mid + 1↵
elif s < val:↵
hi = mid - 1↵
return "NO"↵
↵
↵
for _ in range(int(input())):↵
n, l, s = map(int, input().split())↵
↵
print(solve(n, l, s))↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
↵
↵
Test Cases with the answers:↵
↵
~~~~~↵
3↵
5 3 11 # YES↵
5 3 5 # NO↵
5 3 6 # YES↵
~~~~~↵
↵
My code seems to pass the initial test cases, but I'd like to know if this will work for all cases. Please let me know if this is correct.↵
↵
<spoiler summary="Updated Code">↵
↵
~~~~~↵
def solve(n, l, s):↵
lo = l↵
hi = n↵
↵
def helper(i):↵
one# Author : iron_nicko↵
from collections import Counter, defaultdict, deque↵
from bisect import bisect_left, bisect_right↵
from functools import cache↵
from itertools import accumulate↵
from heapq import heapify, heappush, heappop↵
↵
↵
def range_sum(l, r):↵
l -= 1↵
x =il * (i+l + 1) >> 1↵
two = 0↵
if i - l > 0:↵
two = (i-l)*(i-l+1) >> 1↵
return one - twoy = r * (r + 1) >> 1↵
return y - x↵
↵
def check(N, L, S, deletion=0):↵
L += deletion↵
for _ in range(100):↵
if hi < lo: break↵
mid = ((hi - lo) >> 1) + lo↵
val = helper(midl, r = 1, N - L + 1↵
while l <= r:↵
mid = (l + r) >> 1↵
subarray_sum = range_sum(mid, mid + L - 1)↵
dif abs(s - val) < 2:↵
if lo == l:↵
f = subarray_sum - S↵
if not deletion:↵
if s - val >ubarray_sum == 0S:↵
return "YES"True↵
elifmid == n:↵
subarray_sum < S:↵
if s - va l <= 0:↵
return "YES"↵
mid + 1↵
else:↵
r = mid - 1↵
else:↵
return "YES"↵
if s > val:↵
loif diff < mid:↵
l = mid + 1↵
elif mid <= diff <= mid + L - 1:↵
elif s < val:↵
return True↵
else:↵
hir = mid - 1↵
return"NO"False↵
↵
↵
for _ in range(int(input())def solve():↵
nN, lL, sS = map(int, input().split())↵
↵
print(solve(n"NYOE S"[check(N, L, S, 1) or check(N, lL, s)S) :: 2].rstrip())↵
↵
for _ in range(int(input())):↵
solve()↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
Question:↵
↵
↵
~~~~~↵
Consider the integer sequence A[], where the elements are first N natural numbers in order.↵
↵
You are now given two integers, L and S. Determine whether there exists a subarray with length L and sum S after removing at most one element from A.↵
↵
A subarray of an array is a non-empty sequence obtained by removing zero or more elements from the front of the array, and zero or more elements from the back of the array.↵
1 <= N <= 10^9↵
1 <= L <= N - 1↵
~~~~~↵
↵
↵
↵
I came up with something like this:↵
↵
<spoiler summary="My Code">↵
↵
~~~~~↵
↵
def solve(n, l, s):↵
lo = 1↵
hi = n↵
↵
def helper(i):↵
one = i * (i+1) >> 1↵
two = 0↵
if i - l > 0:↵
two = (i-l)*(i-l+1) >> 1↵
return one - two↵
for _ in range(100):↵
mid = ((hi - lo) >> 1) + lo↵
val = helper(mid)↵
if abs(s - val) < 2:↵
if lo == 1:↵
if s - val >= 0:↵
return "YES"↵
elif mid == n:↵
if s - val <= 0:↵
return "YES"↵
else:↵
return "YES"↵
if s > val:↵
lo = mid + 1↵
elif s < val:↵
hi = mid - 1↵
return "NO"↵
↵
↵
for _ in range(int(input())):↵
n, l, s = map(int, input().split())↵
↵
print(solve(n, l, s))↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
↵
↵
Test Cases with the answers:↵
↵
~~~~~↵
3↵
5 3 11 # YES↵
5 3 5 # NO↵
5 3 6 # YES↵
~~~~~↵
↵
My code seems to pass the initial test cases, but I'd like to know if this will work for all cases. Please let me know if this is correct.↵
↵
<spoiler summary="Updated Code">↵
↵
~~~~~↵
lo = l↵
hi = n↵
↵
def helper(i):↵
one
from collections import Counter, defaultdict, deque↵
from bisect import bisect_left, bisect_right↵
from functools import cache↵
from itertools import accumulate↵
from heapq import heapify, heappush, heappop↵
↵
↵
def range_sum(l, r):↵
l -= 1↵
x =
if i - l > 0:↵
two = (i-l)*(i-l+1) >> 1↵
return one - two
return y - x↵
↵
def check(N, L, S, deletion=0):↵
L += deletion↵
if hi < lo: break↵
mid = ((hi - lo) >> 1) + lo↵
val = helper(mid
while l <= r:↵
mid = (l + r) >> 1↵
subarray_sum = range_sum(mid, mid + L - 1)↵
dif
if lo == l:↵
if not deletion:↵
if s
elif
return "YES"↵
else:↵
r = mid - 1↵
else:↵
if s > val:↵
lo
l = mid + 1↵
elif mid <= diff <= mid + L - 1:↵
else:↵
return
↵
↵
↵
for _ in range(int(input())):↵
solve()↵
~~~~~↵
↵
↵
</spoiler>↵
↵
