Training - IOI

IOITC Day-1 Part-1

Given a list of integers L = [A1, A2, A3, …, AN]. Where Ai ≥ 0, 0 ≤ i ≤ N. You have to find the shortest contiguous segment in the list which adds up to a given integer K. If there are more than one such segments, print one of them.

For example, If L = [2, 1, 3, 1, 4, 4, 1, 8, 1, 7] and K = 9, The answer would be {6, 7}.

Posted on Jan 23, 2022

IOITC Day-1 Part-2

So, What if the numbers can also be negative?

We can't use sliding window algorithm then. First of all we will compute prefix sum and then sort it with their respective index (sort them as {prefixL[i],i}).Then we will apply binary search on it for every index i to look for element whose index j is greater than index i and whose value is equal to prefixL[i] + K. This will take \(\cal{O}(n \cdot \log(n))\) time.

Posted on Jan 24, 2022

IOITC Day-1 Part-3

Given a grid of integers L = [[A1,1, A1,2, A1,3, ..., A1,M], [A2,1, A2,1, A2,3, ..., A2,M], [A3,1, A3,2, A3,3, ..., A3,M], [..., ..., ..., ..., ...], [AN,1, AN,2, AN,3, ..., AN,M]]. Where Ai,j ≥ 0 , 0 ≤ i ≤ N, 0 ≤ j ≤ M. You have to find least perimeter of rectangle which adds up to a given integer K.

For example, If L = [[1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [1, 0, 1, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 2], [1, 0, 0, 0, 0]] and K = 3 , The answer would be 22, rectangles will be {(0, 0), (2, 2)} and {(2, 3), (4, 4)}.

Posted on Jan 25, 2022