Auto comment: topic has been updated by viralm (previous revision, new revision, compare).

Auto comment: topic has been updated by viralm (previous revision, new revision, compare).

Thanks mgcd.

It is probably because this website is for mobile phones. I think you should scroll down and click on switch to Desktop Version. :)

In the 7th section, how are those paths included in the answer where we use vertices v < first(mask). This means, if our bit representation of mask is 1101000, and we want to count no. of paths starting at first(mask)=3(3rd bit, 0-based indexing from right to left) and ending at vertex v=5(0-based indexing from right to left), how will paths like the one starting from vertex 3 to vertex 5 with vertex 0 on the way(and similar) be counted if we use the dp meaning given in section 7?

Can you explain your code?

Sorry. You are right.

Your code gets into an infinite loop when lo==hi.

Here is my approach to solving D. 1.Let's first store a vector {l,r} in another vector for all queries. Let's denote this vector of vectors as v. 2.Now sort this vector.Now we have a vector containing l,r pairs sorted by l. 3.Now here is the analysis — The answer to our question is a range such that its 2 endpoints belong to the set of points obtained from queries. Whenever we get a query of form l,r, we include l and r in this set of points. Lets call this set pts. So our 2 end points belong to pts. 4. Now we plan to iterate over the pts set(stored in a vector). We also make a set<vector> called st. Now as we iterate over pts, we keep in our set only those ranges from v such that their l <= pts[i]. We put the sanges into st in the form {r,l}, so that the ranges in set are sorted by r. 5. We plan to use 2 pointer technique here. For each i over pts we increase j (which is also iterator over pts) and remove all ranges from st whose r<pts[j] till the size of st > k. 6.The answer is max of all pts[j] -pts[i]. 7. There are definately a lot of details left to be explained but are not very difficult to figure out. This is just the basic idea. 8. If you feel something wrong with this approach, feel free to tell me.

In order to use kmp, we need to keep track of the LCS found upto a particular state. How do you suggest to do that? Should I store the LCS itself in another array[][][] ?

Anyone?

Auto comment: topic has been updated by viralm (previous revision, new revision, compare).

I think you can take the negative of all edge weights and apply the Bellman–Ford Algorithm. Your final answer will be the negative of the answer given by Bellman–Ford Algorithm. This works because, Bellman–Ford Algorithm is used to calculate the shortest path from source node to every other node. Now, if you negate all edge weights, then the abs(length of shortest path) = length of longest path. You can read more about Bellman–Ford Algorithm here — http://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/

I know. Just wanted to give an alternative approach. :P

In above solution, I have assumed that 2 or more subsequences having the same sum are counted more than once.

// Dynamic Programming based solution for Problem 2.
#include<bits/stdc++.h> 
#define ll long long int
#define ld long double
#define pb push_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(false)
#define MAX 400000
using namespace std;
int ar[1009];
int dpl[1000000]; // for dp[i-1][]
int dph[1000000]; // for dp[i][]
int h[1000000];
int main()
{
	//ios;
	// dp[i][sum] denotes the number of subsequences ending at index i and having sum = sum.
	// recurrence relation for dp:  dp[i][sum]=dp[i-1][sum-ar[i]]+dp[i-1][sum+ar[i-1]-ar[i]]
	// Space optimization: clearly, dp[i][] depends only on dp[i-1][], and hence, we don't need to make entire 2D dp[i][sum], just 2 dp arrays: dpl[] and dph[]
	// Note that always, sum<MAX. The proof is simple. Sum is maximum when n=log2(10000) (got by solving for n: 2^n=10000). Thus, for n==log2(10000), if all ar[i]==20000, then sum<= n*20000, taking n=20 (> log2(10000)), sum<400000. If n==1000, then sum<= 2*max(ar),
	// because nC2>10000.
	// h[j] stores min(number of subsequences having sum=j,10000).
	int n,q;
	scanf("%d",&n);
	int i,j;
	for(i=0;i<n;i++) scanf("%d",&ar[i]);
	dpl[ar[0]]=1; // base case
	h[ar[0]]++;
	for(i=1;i<n;i++)
	{
		for(j=0;j<=MAX;j++)
		{
			if(j-ar[i]>=0)dph[j]=min(10001,dpl[j-ar[i]]+dpl[j+ar[i-1]-ar[i]]);
			else dph[j]=0;
		}
		for(j=0;j<=MAX;j++) 
		{
			dpl[j]=dph[j];
			h[j]=min(10001,h[j]+dph[j]);
		}
	}
	vector<int> v; // stores the smallest min(2^n,10000) subsequence sums.
	v.pb(0); // for null subsequence
	int idx=0;
	while(v.size()<10009&&idx<=MAX)
	{
		for(i=0;i<h[idx]&&v.size()<10009;i++) v.pb(idx);
		idx++;
	}
	//for(i=0;i<v.size();i++) printf("%d ",v[i]); printf("\n");
	// Answer Queries.
	scanf("%d",&q);
	while(q--)
	{
		int x;
		scanf("%d",&x);
		printf("%d\n",v[x-1]);
	}
	return 0;
}

My code for Problem C, small — http://ideone.com/bxHN0y

I think you need to use dynamic programming, for problem C.

Can be done in logn time using Fenwick tree or BIT. I assume that some preprocessing is allowed. As far as I know, femwick tree is not part of STL.

I think it is not possible in this way because it might be the case that as you move from the root towards the leaves, allowing the root node to have a mismatch might lead to the best possible answer.

Auto comment: topic has been updated by viralm (previous revision, new revision, compare).

OK