I have read the solution for this problem but still have doubts about how the solution works.

Why doesnt dp[i][j] depend upon dp[i-1][j] and dp[i][j-1]

why does dp[i][j] only depend on dp[i-1][j-1]

Solution link: https://leetcode.com/problems/count-substrings-that-differ-by-one-character/discuss/1523218/C%2B%2B-DP-(Detailed-Explanation-with-Examples)

contest https://codeforces.me/contest/380/problem/C Algorithm gym https://codeforces.me/blog/entry/15890

For each node (for example x), we keep three integers : 1.t[x] = Answer for it's interval. 2. o[x] = The number of

Unable to parse markup [type=CF_MATHJAX]

So, as you know, first of all we need a build function which would be this : (as above) (C++ and [l, r) is inclusive-outclusive )

void build(int id = 1,int l = 0,int r = n){
    if(r - l < 2){
        if(s[l] == '(')
            o[id] = 1;
        else
            c[id] = 1;
        return ;
    }
    int mid = (l+r)/2;
    build(2 * id,l,mid);
    build(2 * id + 1,mid,r);
    int tmp = min(o[2 * id],c[2 * id + 1]);
    t[id] = t[2 * id] + t[2 * id + 1] + tmp;
    o[id] = o[2 * id] + o[2 * id + 1] - tmp;
    c[id] = c[2 * id] + c[2 * id + 1] - tmp;
}

For queries, return value of the function should be 3 values : t, o, c which is the values I said above for the intersection of the node's interval and the query's interval (we consider query's interval is [x, y) ), so in C++ code, return value is a pair<int,pair<int,int> > (pair<t, pair<o,c> >) :

typedef pair<int,int>pii;
typedef pair<int,pii>   node;
node segment(int x,int y,int id = 1,int l = 0,int r = n){
    if(l >= y || x >= r)   return node(0,pii(0,0));
    if(x <= l && r <= y)
        return node(t[id],pii(o[id],c[id]));
    int mid = (l+r)/2;
    node a = segment(x,y,2 * id,l,mid), b = segment(x,y,2 * id + 1,mid,r);
    int T, temp, O, C;
    temp = min(a.y.x , b.y.y); //why
    T = a.x + b.x + temp;      //repeat
    O = a.y.x + b.y.x - temp;  //these steps
        C = a.y.y + b.y.y - temp; //wasnt it alreasy performed while building the segment
    return node(T,pii(O,C));    
}

why are the last steps of both functions repeating, T,O,C was already updated during build, if it is updated again during segment then it should be wrong?

// Union-Find Disjoint Sets Library written in OOP manner, using both path compression and union by rank heuristics
class UnionFind {                                              // OOP style
private:
  vi p, rank, setSize;                       // remember: vi is vector<int>
  int numSets;
public:
  UnionFind(int N) {
    setSize.assign(N, 1); 
    numSets = N; 
    rank.assign(N, 0);
    p.assign(N, 0); for (int i = 0; i < N; i++) p[i] = i; }
  
  int findSet(int i) { return (p[i] == i) ? i : (p[i] = findSet(p[i])); }
  
  bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }
  
  void unionSet(int i, int j) { 
    if (!isSameSet(i, j)) { 
      numSets--; 
      int x = findSet(i), y = findSet(j);
      // rank is used to keep the tree short
      if (rank[x] > rank[y]) { 
        p[y] = x; 
        setSize[x] += setSize[y]; }
      else { 
        p[x] = y; 
        setSize[y] += setSize[x];
        if (rank[x] == rank[y]) 
          rank[y]++; }}}

  int numDisjointSets() { return numSets; }
  int sizeOfSet(int i) { return setSize[findSet(i)]; }
};

What I could infer: find funtion gives the key of a particular set. we are setting p[i]=find(p[i]), this will set the key of the set as parent of every element of the set.

Doubt: Some elements will still have p[i]=nk where nk is an element of the set which is not the key. If this is the case ,then why perform this assignment (p[i]=find(p[i]))

change(rs) gives the coins required for remaining value

1. change(0) = 0 // we need 0 coins to produce 0 cents
2. change(< 0) = ∞ // in practice, we can return a large positive value
3. change(value) = 1 + min(change(value — coinValue[i])) ∀ i ∈ [0..n-1]

I wrote this but its not working (gives a large integer value !)

#define INT_MA 999999
int memo[1000],v[1000];
int coin(int rs)
{
	if(rs == 0)
		return 0;
	if(rs<0)
		return INT_MA;
	if(memo[rs] != INT_MA)
		return memo[rs];
	int &a = memo[rs];
	for(int i=0;i<n;i++)
	{
		a=min(a,coin(rs-v[i]));
	}
	if(a!=INT_MA)
	a=a+1;
	return a;
}
int main()
{
int n,val;
cin>>n>>val;

for(int i=0;i<n;i++)
cin>>v[i];

memset(memo,INT_MA,sizeof memo);
cout<<coin(val);
}

If rules of creating BST is as follows:

The left sub-tree contains only nodes with values less than or equal to the parent node; the right sub-tree contains only nodes with values greater than the parent node.

If a node has level i, then the subtree rooted at that node should have exactly number of distinct values in the subtree. Note that it is the number of distinct values in the subtree and not the number of nodes in the subtree.

If a is the smallest value in the tree and b is the largest value, then all values from a to b must come atleast once in the tree.

I read the editorial https://www.hackerearth.com/practice/data-structures/trees/binary-search-tree/practice-problems/algorithm/monk-and-bst/editorial/

It says that we can observe that, in subtree with N nodes, (N-1)/2 nodes will occur twice and 1 node will occur exactly once, which will be of maximum value, and tree will be of form: img

Can someone explain why is this so, or better yet point me to some resource which will help me understand this.

Problem_link

Given a big amount N and the array of denominations S. Assuming infinite supply of each of S = {S1,S2….Sm} denominations, find the number of ways to make change for N cents.

Input Format: First line contains an integer T denoting the total number of test cases. For every test case, there are three lines. First line will contain an integer 'M' denoting the size of array. The second line contains M space-separated integers A1, A2, …, Am denoting the elements of the array. The third line contains an integer 'N' denoting the cents.

Constraints: 1 <= T <= 10 1 <= n <= 100 1 <= S[i] <= 1000 1 <= N <= 1000000 Output Format: Print number of possible ways to make change for N cents in a new line. Since answers can be large, print answer % (1000000000 + 7).

Sample Input: 2 3 1 2 3 4 4 2 5 3 6 10 Sample Output: 4 5 Explanation: For N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.

I am getting WA for t-1 test cases ,though I think the code is fine ?!

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[1000006];

int main()
{

ll t;
cin>>t;

while(t--)
{
	
	ll n;
	cin>>n;

	int v[100];
	for(int i=0 ; i<n ; i++)
		cin>>v[i];
	
	ll s; 
	cin>>s;

	for(int i=0;i<=s;i++)
		dp[i]=0;
	
	dp[0]=1;
	
	for(int i=0 ;i<n ;i++)
	{
		for(int j=v[i];j<=s;j++)
			{
		
				dp[j] = (dp[j]%1000000007 + dp[j-v[i]]%1000000007) % 1000000007;
			
			}
	}
	
	cout<<(dp[s])<<"\n";
}

}

Fixed modulo T0 and T1 are AC But getting run time error for the rest T-2 test cases

Hey I found this implementation on a codeforces blog. What do you think about it , is this the most easy and reliable implementation according to you (for solving the problems)? I am asking because there's so much confusing stuff about loop invariants and I just want something which always works for sure!

l, r = -1, n
while r-l > 1:
    m = (l+r)//2
    if F(a[m]):
        l = m
    else:
        r = m

You can easily prove that l = k and r = k + 1 by the end of the while loop. In this case no worries about whether to increase m by 1 or not.

Question: Given a set of "n" non-negative integers, and a value "sum", determine if there is a subset of the given set with sum equal to given sum.

Input Format: 1st Line: n sum 2nd Line: a1 a2……an (Array Values)

Constraints: 1<= n <= 5000 1<= sum <= 10^7 1<= Ai <=10^5

Output Format: Yes, if sum exist No, it sum does not exist

I wanted to use this https://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/ solution But creating an array dp[5000+1][10e7+1] is not possible. So what can be done?

#include<bits/stdc++.h>
using namespace std;
#define S 100001
#define ll int

ll arr[S];
ll ans;

void merge(int l ,int h , ll (&arr)[S])
{
	ll mid=l+(h-l)/2;
	long long ar[S];
	int i=l;
	int j=mid+1;
	int k=0;

	while(i<=mid && j<=h)
	{
		if (arr[i]>arr[j])
		{
			ans+=(mid-i+1);
			ar[k++]=arr[j++];
		}
		else
			ar[k++]=arr[i++];
	}

	while(i<=mid)
		ar[k++]=arr[i++];
		
	while (j<=h)
		ar[k++]=arr[j++];

	for (int i = 0; i < k; ++i)
		arr[l++]=ar[i];
	
}

void merge_sort(int l , int h , ll (&arr)[S])
{

if(l>=h)
	return ;

ll m=l+(h-l)/2;

merge_sort(l,m,arr);
merge_sort(m+1,h,arr);
merge(l,h,arr);
}

int main()
{
int t;
cin>>t;

while(t--)
{
ans=0;
int n;
cin>>n;

for(int j=0;j<n;j++) 
{
	/**************************************comment 1********
	/int tp;
	/cin>>tp;
	/arr[j]=tp;
	**********************************************************/

	///////////////////////replace following line with comment 1 and you'll get WA
	cin>>arr[j];
}

merge_sort(0,n-1,arr);
cout<<ans<<endl;

}
}

Why do I get WA on replacing?