To protect people from evil, 
a long and tall wall was constructed a few years ago. 
But just a wall is not safe, there should also be soldiers on it, 
always keeping vigil. 
The wall is very long and connects the left and the right towers. 
There are exactly N spots (numbered 1 to N) on the wall for soldiers. 
The K^{th} spot is K miles far from the left tower and (N+1-K) miles from the right tower.

Given a permutation of spots P of {1, 2, ..., N}, soldiers occupy the N spots in that order. 
The P[i]^{th} spot is occupied before the P[i+1]^{th} spot. 
When a soldier occupies a spot, he is connected to his nearest soldier already placed to his left. 
If there is no soldier to his left, he is connected to the left tower. The same is the case with right side. 
A connection between two spots requires a wire of length equal to the distance between the two.

The realm has already purchased a wire of M miles long from Nokia, 
possibly the wire will be cut into smaller length wires. 
As we can observe, the total length of the used wire depends on the permutation of the spots P. Help the realm in minimizing the length of the unused wire. If there is not enough wire, output -1.

------ Input ------ 

First line contains an integer T (number of test cases, 1 ≤ T ≤ 10 ). Each of the next T lines contains two integers N M, as explained in the problem statement (1 ≤ N ≤ 30 , 1 ≤ M ≤ 1000).

------ Output ------ 

For each test case, output the minimum length of the unused wire, or -1 if the the wire is not sufficient.

----- Sample Input 1 ------ 
4
3 8
3 9
2 4
5 25
----- Sample Output 1 ------ 
0
0
-1
5
----- explanation 1 ------ 
In the 1st case, for example, the permutation P = {2, 1, 3} will use the exact 8 miles wires in total.
In the 2nd case, for example, the permutation P = {1, 3, 2} will use the exact 9 miles wires in total.
To understand the first two cases, you can see the following figures:
In the 3rd case, the minimum length of wire required is 5, for any of the permutations {1,2} or {2,1}, so length 4 is not sufficient.
In the 4th case, for the permutation {1, 2, 3, 4, 5} we need the maximum length of the wire = 20. So minimum possible unused wire length = 25 - 20 = 5.

Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Divide and conquer

Mathematics

Complete search
Skill types: Bit manipulation

Complete search

Starter code:

Solutions:
min = [0 for i in range(32)]
max = [0 for i in range(32)]
for i in range(1, 32):
	min[i] = i + 1 + min[(i - 1) // 2] + min[i - (i - 1) // 2 - 1]
	max[i] = i + 1 + max[i - 1]
for i in range(int(input())):
	(n, m) = map(int, input().split())
	if m < min[n]:
		print(-1)
	elif m <= max[n]:
		print(0)
	else:
		print(m - max[n])


import sys
import time
input_lines = [line.strip() for line in sys.stdin.readlines() if line.strip()]
T = int(input_lines[0])

def problem(n):
	if n == 0:
		return 0
	elif n == 1:
		return 2
	else:
		length = n + 1
		length += problem(int(n / 2))
		length += problem(n - int(n / 2) - 1)
		return length
t = 0
while t < T:
	(N, M) = [int(x) for x in input_lines[t + 1].split()]
	max_length = int(N * (N + 3) / 2)
	min_length = problem(N)
	if M > max_length:
		print(M - max_length)
	elif M >= min_length:
		print(0)
	else:
		print(-1)
	t += 1


def min_length(k):
	if k == 0:
		return 0
	if k == 1:
		return 2
	else:
		return k + 1 + min_length((k - 1) // 2) + min_length(k - 1 - (k - 1) // 2)
t = int(input())
for i in range(t):
	(n, m) = [int(x) for x in input().split()]
	if m < min_length(n):
		print(-1)
	elif m > n * (n + 3) / 2:
		print(m - n * (n + 3) // 2)
	else:
		print(0)


def min_length(x):
	if x == 0:
		return 0
	if x == 1:
		return 2
	else:
		return x + 1 + min_length((x - 1) // 2) + min_length(x - 1 - (x - 1) // 2)

def slove():
	(n, m) = map(int, input().split())
	if m < min_length(n):
		print(-1)
	elif m > n * (n + 3) / 2:
		print(m - n * (n + 3) // 2)
	else:
		print(0)
t = int(input())
for _ in range(t):
	slove()


lmn = [2, 5, 8, 12, 16, 20, 24, 29, 34, 39, 44, 49, 54, 59, 64, 70, 76, 82, 88, 94, 100, 106, 112, 118, 124, 130, 136, 142, 148, 154, 160, 167, 174, 181, 188, 195, 202, 209, 216, 223]
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	mx = (n + 1) * (n + 2) // 2 - 1
	mn = lmn[n - 1]
	if m > mx:
		print(m - mx)
	elif m < mn:
		print(-1)
	else:
		print(0)


from math import *
from collections import *
from functools import *

def rvi():
	return [*map(int, input().split())]

def maxL(n):
	if n == 1:
		return 0
	elif n == 2:
		return 2
	else:
		return 2 * maxL(n // 2) + n if n % 2 == 0 else n + maxL(n // 2) + maxL(n // 2 + 1)
for _ in range(int(input())):
	(n, m) = rvi()
	max_l = ((n + 1) * (n + 1) + n + 1) // 2 - 1
	min_l = maxL(n + 1)
	if m < min_l:
		print(-1)
	else:
		print(max(0, m - max_l))


def snek(k):
	if k == 0:
		return 0
	if k == 1:
		return 2
	else:
		return k + 1 + snek((k - 1) // 2) + snek(k - 1 - (k - 1) // 2)
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	if m < snek(n):
		print(-1)
	elif m > n * (n + 3) / 2:
		print(m - n * (n + 3) // 2)
	else:
		print(0)


T = input()
T = int(T)

def recur(N):
	N = int(N)
	if N == 3:
		return 8
	if N == 2:
		return 5
	if N == 1:
		return 2
	elif N != 1:
		p = N // 2
		if N % 2 == 0:
			return recur(N // 2) + recur(N // 2 - 1) + N + 1
		elif N % 2 == 1:
			return 2 * recur(N // 2) + N + 1

def permut(N):
	N = int(N)
	return (N + 2) * (N + 1) / 2 - 1
for i in range(0, T):
	(s, l) = list(map(int, input().split()))
	j = int(l - recur(s))
	minim = int(l - permut(s))
	if j < 0:
		print(-1)
	if j == 0:
		print(j)
	if j > 0:
		if minim < 0:
			print(0)
		else:
			print(minim)


def get_min_length(f, p, l):
	if f == l - 1:
		return 0
	return get_min_length(f, (f + p) // 2, p) + (l - f) + get_min_length(p, (p + l) // 2, l)

def get_max_length(f, p, l):
	if f == l - 1:
		return 0
	return l - f + get_max_length(p, p + 1, l)

def func():
	(n, m) = map(int, input().split(' '))
	maxm = get_max_length(0, 1, n + 1)
	minm = get_min_length(0, (n + 1) // 2, n + 1)
	if minm <= m <= maxm:
		ans = 0
	elif m > maxm:
		ans = m - maxm
	else:
		ans = -1
	print(ans)
t = int(input())
while t:
	func()
	t -= 1


import math
t = int(input())
while t > 0:
	t -= 1
	(n, m) = map(int, input().split())
	spMax = (n + 1) * (n + 2) // 2 - 1
	spMin = math.ceil((n + 1) * math.log(n + 1, 2))
	if m > spMax:
		print(m - spMax)
	elif m < spMin:
		print(-1)
	else:
		print(0)


def min_s(x):
	if x == 0:
		return 0
	elif x == 1:
		return 2
	elif x % 2 == 0:
		return x + 1 + min_s(x // 2 - 1) + min_s(x // 2)
	else:
		return x + 1 + 2 * min_s(x // 2)

def max_s(y):
	return y * (y + 3) // 2
for i in range(int(input())):
	(n, m) = map(int, input().split())
	j = int(m - min_s(n))
	k = int(m - max_s(n))
	if j < 0:
		print(-1)
	elif k > 0:
		print(k)
	else:
		print(0)


def minRange(l, r):
	if r - l <= 1:
		return 0
	mid = (l + r) // 2
	return r - l + minRange(l, mid) + minRange(mid, r)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	max1 = n * (n + 3) // 2
	min1 = minRange(0, n + 1)
	if m > max1:
		print(m - max1)
		continue
	elif m < min1:
		print(-1)
	else:
		print(0)


mem = {0: 0, 1: 2}

def get_min_req_len(n):
	if n in mem:
		return mem[n]
	ans = n + 1
	if n % 2:
		ans += 2 * get_min_req_len(n // 2)
	else:
		ans += get_min_req_len(n // 2) + get_min_req_len(n // 2 - 1)
	mem[n] = ans
	return ans
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	max_ans = (n + 1) * (n + 2) // 2 - 1
	min_ans = get_min_req_len(n)
	if min_ans <= m <= max_ans:
		print(0)
	elif m < min_ans:
		print(-1)
	else:
		print(m - max_ans)


min = {1: 2, 2: 5}
for i in range(3, 32):
	x1 = (i - 1) // 2
	x2 = x1 + (i - 1) % 2
	min[i] = i + 1 + min[x1] + min[x2]
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	y = (n + 1) * (n + 2) // 2 - 1
	if m < min[n]:
		print('-1')
	elif m > y:
		print(m - y)
	else:
		print('0')


import math
t = int(input())
while t > 0:
	t -= 1
	(n, m) = map(int, input().split())
	sMax = (n + 1) * (n + 2) // 2 - 1
	sMin = math.ceil((n + 1) * math.log(n + 1, 2))
	if m > sMax:
		print(m - sMax)
	elif m < sMin:
		print(-1)
	else:
		print(0)


import math

def recur(a):
	mid = int(math.ceil(len(a) / 2))
	if len(a) == 1:
		return 2
	if len(a) == 0:
		return 0
	return len(a) + 1 + recur(a[:mid - 1]) + recur(a[mid:])
t = int(input())
l = 0
while l < t:
	(n, m) = map(int, input().split(' '))
	max = int((n + 2) * (n + 1) / 2) - 1
	a1 = m - max
	if a1 >= 0:
		print(a1)
	else:
		arr = [int(i) for i in range(n)]
		min = recur(arr)
		a2 = m - min
		if a2 < 0:
			print(-1)
		else:
			print(0)
	l += 1


import math
T = int(input())
for tc in range(T):
	(N, M) = map(int, input().split())
	A = int(math.log(N, 2))
	SI = 0
	for i in range(A + 1):
		if i < A:
			SI = SI + (i + 2) * (2 ** (i + 1) - 2 ** i)
		else:
			SI = SI + (i + 2) * (N - 2 ** i + 1)
	if M >= (N + 3) * N / 2:
		D = M - (N + 3) * N / 2
	elif M >= SI:
		D = 0
	else:
		D = -1
	print(int(D))


def minLength(l, r):
	m = int(l + (r - l) / 2)
	if m <= 0 or r - l == 1:
		return 0
	return r - l + minLength(l, m) + minLength(m, r)

def nokia(n, m):
	max_len = (3 * n + n * n) / 2
	min_len = minLength(0, n + 1)
	if m < min_len:
		return -1
	if m >= max_len:
		return m - max_len
	if m < max_len and m >= min_len:
		return 0
t = int(input())
for i in range(t):
	line = input()
	(n, m) = line.split(' ')
	n = int(n)
	m = int(m)
	print(int(nokia(n, m)))


import math

def find_minimum_length_required(left, right):
	if right - left <= 1:
		return 0
	else:
		mid = math.ceil(left + (right - left) / 2)
		return right - left + find_minimum_length_required(left, mid) + find_minimum_length_required(mid, right)

def find_maximum_length_required(left, right):
	if right == left:
		return 0
	else:
		return right - left + 1 + find_maximum_length_required(left + 1, right)
testcases = int(input())
for i in range(testcases):
	(n, m) = map(int, input().split())
	minimum_length_required = find_minimum_length_required(0, n + 1)
	maximum_length_required = find_maximum_length_required(0, n)
	if m < minimum_length_required:
		print(-1)
	elif minimum_length_required <= m <= maximum_length_required:
		print(0)
	else:
		print(m - maximum_length_required)


def helperConnecting(l, r):
	if r - l <= 1:
		return 0
	mid = (l + r) // 2
	return r - l + helperConnecting(l, mid) + helperConnecting(mid, r)
T = int(input())
while T > 0:
	T -= 1
	(N, M) = [int(x) for x in input().split(' ')]
	max1 = int(N * (N + 3) / 2)
	min1 = helperConnecting(0, N + 1)
	if M > max1:
		print(M - max1)
	elif M >= min1:
		print(0)
	else:
		print(-1)


k = int(input())
minimum = [0, 0, 2, 5]
maximum = [0, 0, 2, 5]
n = 4
while n < 40:
	min_values = []
	max_values = []
	for i in range(1, n // 2 + 1):
		min_values.append(minimum[i] + minimum[n - i])
		max_values.append(maximum[i] + maximum[n - i])
	minimum.append(n + min(min_values))
	maximum.append(n + max(max_values))
	n += 1
for i in range(k):
	(a, b) = map(int, input().split())
	if b < minimum[a + 1]:
		print(-1)
	elif b < maximum[a + 1]:
		print(0)
	else:
		print(b - maximum[a + 1])


a = []
for i in range(1001):
	a.append(0)
ans = []
ans.append([0])
ans.append([2])
for i in range(2, 31):
	for j in range(1001):
		a[j] = 0
	for j in range(i):
		for i0 in range(len(ans[j])):
			for i1 in range(len(ans[i - j - 1])):
				a[ans[j][i0] + ans[i - j - 1][i1] + i + 1] = 1
	ans.append([])
	for j in range(1001):
		if a[j] > 0:
			ans[i].append(j)
T = int(input())
for tc in range(T):
	(N, M) = map(int, input().split())
	x = -1
	for i in range(len(ans[N])):
		if ans[N][i] <= M:
			x = M - ans[N][i]
	print(x)


def mini_len(l):
	if l == 0:
		return 0
	if l == 1:
		return 2
	else:
		return l + 1 + mini_len((l - 1) // 2) + mini_len(l - 1 - (l - 1) // 2)

def maxi_len(l):
	return l * (l + 3) // 2
T = int(input())
for i in range(T):
	(n, m) = map(int, input().split())
	if m < mini_len(n):
		print(-1)
	elif m > maxi_len(n):
		print(m - maxi_len(n))
	else:
		print(0)


import sys, math
mn = [0 for i in range(50 + 1)]
mx = [0 for i in range(50 + 1)]
for i in range(1, 51):
	k = i // 2
	mn[i] = mn[k] + mn[i - k - 1] + i + 1
	mx[i] = mx[i - 1] + i + 1
for _ in range(int(input())):
	(n, m) = [int(c) for c in input().split()]
	if m < mn[n]:
		print(-1)
	elif m <= mx[n]:
		print(0)
	else:
		print(m - mx[n])


import sys
sys.setrecursionlimit(10 ** 7)

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def get_int():
	return int(sys.stdin.readline().strip())

def get_list_strings():
	return list(map(str, sys.stdin.readline().strip().split()))

def findLeast(N, store):
	if N in store:
		return store[N]
	if N == 1:
		return 2
	if N == 2:
		return 5
	mid = (N + 1) // 2
	ans = N + 1
	ans += findLeast(mid - 1, store) + findLeast(N - mid, store)
	store[N] = ans
	return ans

def solve(N, M):
	up = (N + 1) * (N + 2) // 2
	up -= 1
	if M >= up:
		ans = M - up
		sys.stdout.write(str(ans) + '\n')
		return
	low = findLeast(N, {})
	if M < low:
		sys.stdout.write(str(-1) + '\n')
		return
	sys.stdout.write(str(0) + '\n')
	return
T = get_int()
while T:
	(N, M) = get_ints()
	solve(N, M)
	T -= 1


t = int(input())
for k in range(t):
	(n, m) = map(int, input().split())
	dpM = [[0 for i in range(n + 2)] for j in range(n + 2)]
	dpm = [[10 ** 9 for i in range(n + 2)] for j in range(n + 2)]
	for kro in range(1, n + 2):
		for one in range(0, n + 2 - kro):
			if kro == 1:
				dpM[one][one + 1] = 0
				dpm[one][one + 1] = 0
			else:
				for k in range(one + 1, one + kro):
					dpM[one][one + kro] = max(dpM[one][one + kro], kro + dpM[one][k] + dpM[k][one + kro])
					dpm[one][one + kro] = min(dpm[one][one + kro], kro + dpm[one][k] + dpm[k][one + kro])
	if dpM[0][n + 1] <= m:
		print(m - dpM[0][n + 1])
	elif dpm[0][n + 1] <= m:
		print(0)
	else:
		print(-1)


t = int(input())
mindp = [i + 2 for i in range(30)]
maxdp = [i + 2 for i in range(30)]
maxdp[0] = 2
for j in range(1, 30):
	maxdp[j] = maxdp[j - 1] + maxdp[j]
mindp[0] = 2
mindp[1] = 5
for k in range(2, 30):
	p = (k + 1) // 2
	if k % 2 != 0:
		ans = mindp[p - 1] + mindp[k - p - 1]
	else:
		ans = 2 * mindp[p - 1]
	mindp[k] = mindp[k] + ans
for _ in range(t):
	(n, m) = map(int, input().split())
	if mindp[n - 1] > m:
		print(-1)
	elif maxdp[n - 1] > m:
		print(0)
	else:
		print(m - maxdp[n - 1])