Q1. Find the number of ordered positive pairs A,B such that the equation x^2-2Ax+B=0 as integral roots and B lies between L and R both inclusive.

Input Format: The first line conains a single integer T denoting the number of test cases The first line of each test case contains two integers l, r

Output: print number of ordered pairs for each test case

Constraints T<10

l,r < 10^12

Sample Input:

2

1 5

2 10

Output:

4

7

Explanation

For the first test case, the valid pairs are (1,1) (2,3) (2,4) (3,5)

My Approach:

a^2-b should be a perfect square, and a^2-b>=0. Now how to go further?

Hello everyone. Recently I encountered an interesting problem which I believe could be done by greedy strategy but I am not sure how. Can you help me to proceed?

The problem is as follows:

You are given 2n alphabets a_1, a_2, ..., a_{2n} with positive frequencies f_1, f_2, ..., f_{2n} respectively. (We assume that f_1 + f_2 + ... + f_n = 1.)

Alphabets a_1, a_2, ..., a_n are colored blue, and alphabets a_{n+1}, a_{n+2}, ..., a_{2n} are colored red.

A prefix-free code C for {a_1, a_2, ..., a_{2n}} is called valid if and only if every subtree of Trie(C) with at least two leaves has equal number of blue and red alphabets.

Give an algorithm to find a valid prefix-free code of minimum cost.

Thanks for helping me out.

I was doing this Problem on codeforces. It was a dynamic programming question and I am fairly new to dynamic programming.

I wrote a code whose main part is below

n,m,b,mod = li()
a = li()
dp = [[0 for i in range(b+1)] for j in range(m+1)] 
dp[0][0]=1
for i in range(n):
    for j in range(1,m+1):
        for k in range(b+1):
            if k-a[i]>=0:
                dp[j][k]+=dp[j-1][k-a[i]]
ans = 0
for j in range(b+1):
    ans+= dp[m][j]
print(ans%mod)

This was giving the correct output. But when I move the first loop to the end, then it gives the wrong answer.

for j in range(1,m+1):
    for k in range(b+1):
        for i in range(n):
            if k-a[i]>=0:
                dp[j][k]+=dp[j-1][k-a[i]]

The above code is giving incorrect output. Can anybody help me in understanding why does the loop orientation matters in this case.

You are given an array A of N non negative integers. There are K empty slots from 1 to K. You have to arrange these N numbers into K slots( 2*K> =N). Each slot can contain at most two numbers filled into it. After all the integers have been placed into these slots, find the sum of bitwise AND of all the numbers with their respective slot numbers

Task: Determine the maximum possible sum

Note: Some slots may remain empty

Example A = [1,3,10,20,7,1] N = 5 K = 10 answer = 25

I did brute force and some test case passed.

How to do this question?

given an array with n elements, and Q queries consisting of an integer find whether there exists an element in the array such that it's bitwise and is zero

1<=n<10^5 , 1<=q<10^5.

Can anyone tell how to do this question.

find minimum number of integers, (where each such integer>=2) that divide all array elements. For example, if the array is [2,4,6,8,10] then the answer is 1 (because 2 divides all array elements). Another example, if the array is [2,3,4,9] then the answer is 2 (because we need at least 2 different numbers, 2 and 3, that satisfy the conditions).

Constraints: N<=10^3

Can someone help, I am not able to solve this problem.

Question 1 — N boxes are Arrranged in a line. Each box is colored either with white or black. You can select any number of boxes from the starting and put it behind the last box in the same sequence as it was placed initially. you can perform this operation atmost once. For example string s="wbbb" . In one operation you can select "wb" and from the start and put it behind the last box "b".

Note: you cannot select all the n boxes.

You are required to find the minimum number of boxes whose colors must be reversed so that all the boxes in the sequence are of an alternate color, that is any two adjacent boxes are of different colors.

Input :  5
wwwwwbbww
wwwb
bwww
wwww
bbbbb

Output : 
3
1
1
2
2

I was thinking of brute forcing the solution, that is doing operation for each length and then calculating for that configuration. Can anyobody tell the correct approach

So I was doing this problem on leetcode.

I was doing in python. This is my code

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        ans = [];cur = []
        def rec(index):
            if index==len(s):
                ans.append(''.join((cur[:])).strip())
                return 
            for i in range(index,len(s)):
                if s[index:i+1] in wordDict:
                    cur.append(" ")
                    cur.append(s[index:i+1])
                    rec(i+1)
                    cur.pop(-1)
                    cur.pop(-1)
        rec(0)
        return ans

On the for loop,

if s[index:i+1] in wordDict:

This creates a copy of string s from the index till i+1 and hence takes O(n) time. If i use string concatenation instead of this, the time complexity will be O(n^2) as strings are immutable in python . I could'nt use list as keys cannot be mutable in dictonary. So what should I do to make the for loop linear time complexity? Is there any way to make the string concatenation linear in python?