Help with a problem asked in a recent CodingNinjas test

Блог пользователя t0rto1se

Автор t0rto1se, история, 4 года назад, По-английски

Problem Name — "Group Photo"

There are $$$N$$$ people, each with a unique height. The height of the $$$i^{th}$$$ person is $$$i (1 \leq i \leq N)$$$. The $$$i^{th}$$$ person will smile in the photo if at least $$$A[i]$$$ people in the photo are shorter than him and at most $$$B[i]$$$ people in the photo are taller than him.

Find the largest group such that everyone will smile in the photo of this group. A group is a collection of randomly selected people from the given $$$N$$$ people.

Constraints:

$$$1 \leq N \leq 10^5$$$
$$$0 \leq A[i], B[i] \leq N$$$

Example Test Case

My O(N^2) approach

I cannot come up with a better solution for this. Any help would be greatly appreciated, thanks!

external contest, question

t0rto1se
4 года назад
10

Комментарии (9)

Показать архивные | Написать комментарий?

18o3

4 года назад, скрыть # |

Binary Search on the number of people. Also this is a Codeforces problem.

→ Ответить

Snapper_001

4 года назад, скрыть # ^ |

i got idea of binary search but didn't get to know how i made the function

→ Ответить

Snapper_001

4 года назад, скрыть # ^ |

Can you give the link or you can tell the approach . thanks in advance

→ Ответить

18o3

4 года назад, скрыть # ^ |

Found the problem

→ Ответить

Snapper_001

4 года назад, скрыть # ^ |

Thanks brother

→ Ответить

FrozenKandy

4 года назад, скрыть # |

← Rev. 2 →

Hint

Solution

Code

def check(num):
	count = 0
	for i in range(n):
		if count >= a[i] and num - count <= b[i]:
			count += 1

	return count >= num

def findLargestGroup():
	r = n
	l = 0
	ans = 0

	while l <= r:
		mid = (l + r) // 2
		if check(mid):
			l = mid + 1
			ans = mid
		else:
			r = mid - 1

	return ans


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	print(findLargestGroup())

→ Ответить