While solving a problem I thought of another problem which could have easily been asked in the earlier problem and is as follows: Consider an array of a group of people of size n. One wants to invite the maximum number of people given to m constraints that a group X and a group Y cannot be invited together.

Example:- Group No. 1 2 3 4 5 6 Size of group 3 4 7 2 8 10

Suppose m=3 and X=1, Y=6. X=2, Y=4. X=1, Y=5. I don't know the answer but it can be calculated for small cases like these but I thought a lot about formulating it as a dynamic programming problem but couldn't reach anywhere. Any help is appreciated.

Hello I was asked this problem in an interview

Given a string(S) consisting of only open & closed brackets, you need to tell the no. of ways to assign each bracket as ‘X’ or ‘Y’ such that when you traverse the string from left to right, the 2 strings formed by each ‘X’ and ‘Y’ are both balanced.

Example:

Input String : (())
1)  XYXY
    XX : ()
    YY : ()
2)  XXXX
3)  YYYY
Output - 6
Explantion-{XXXX,YYYY,XYYX,YXXY,XYXY,YXYX}

I was able to come up with O(N^3) solution but the interviewer wanted an O(N^2) solution. I considered three states in my DP, current index, number of X seen, number of Y seen. Please see my code. If somebody can please share better solutions O(N^2) or even better than O(N^2). Thank you.

string s ; 
int Count[N][N][N] ; 
int NumberOfStrings(int curr , int Xc, int Yc  ){
    if(curr==s.size())
        return  1 ;
  
    int count = 0 ;
    int s1,s2;
    
    if(s[curr] == '('){                
        s1 = NumberOfStrings(curr+1 , Xc+1 , Yc) ;
        s2 = NumberOfStrings(curr+1 , Xc , Yc+1) ; 
        Count[Xc][Yc][curr] = s2+s1;
        return s1+s2;
    }
    
    if(dp[Xc][Yc][curr])
        return dp[Xc][Yc][curr]  ;
   
    else{
        if(Xc >= 1 ){
            s1 = NumberOfStrings(curr+1, Xc-1 , Yc) ;
        }
        if(Yc >= 1){
            s2 = NumberOfStrings(curr+1, Xc, Yc-1 ) ; 
        }
        
       Count[Xc][Yc][curr] = s1+s2;
       
       return s1+s2;
    }
} 

Please go through this problem FPOLICE.I wrote a recursive solution intending to somehow convert it into an iterative one. But my recursive solution gives wrong answer. I applied a simple approach explore a vertex 'idx' and calculate minimum risk and money associated with that 'idx' and 'T'(time) and if some vertex is already visited on that path mark it so I do not have to visit it again. I have written some comments too. Can anybody please help to figure out why this code gives the Wrong answer. Code link here

Hello. I was trying to implement priority queue by myself, though I have used priority_queue from C++ STL many times. I was getting TLE for a very simple problem but when I used STL it got accepted. I believe time complexity of my priority queue for insert and pop() operation is O(log N) and overall complexity of solution is O(NlogN). please see the submission here.

Hello, all. I was studying properties of the ancestors in the tree and solved a problem of finding the kth ancestor of any node in O(logK) time by pre-computing 2^jth parent of every node in O(NlogN) time. I am curious to know how can I apply this knowledge to find LCA of 2 given nodes efficiently?

Please see the image for assignment problem :- I have idea of that this will be solved by divide and conquer but can't figure out the exact way. Please suggest me some algorithm to do this. A proof is really welcome.. idea of that this will be solved by divide and conquer but can't figure out the exact way. Please suggest me some algorithm to do this. A proof is really welcome..

I was trying to solve problem from SRM 698. I can't think of any approach for this problem. Firstly I thought, lets iterate through 0 to n .. and see if I delete i character from string will I get S = T + T ..but after some time I realised it's difficult to keep track which characters to be deleted and so on.. Recently in Educational Round at Codeforces I got another problem.. I keep getting these types of problems all the time but never solved them . How do I develope an approach for all these types of problems and problems where they delete, insert and do all kind of operations like this problem.. Also I could not find editorials for that match.. if you find please share the link ..

1. Please go through the problem BOOKS1 Spoj. I figured out the following things and reached a state where I require your help:-
2. I applied binary search over interval [max_element , sum_of_all_elements].
3. then I calculate x = [lo + hi]/2 ;
4. I check if I can partition the array in less than or equal to m parts such that no parts' sum is greater than x;
5. If I successfully completed this task I reduce hi to x and carry on;
6. The problem I face is there can be a case where I might not need exact k partitions (less than k might do) and output format such that first scriber's work is least

int main(){
	int n;
	cin>>n;
	while(n--){
		int m,k;
		cin>>m>>k;
		int a[501];
		int s=0;
		rep(i,m){ 
			cin>>a[i];
			s+=a[i];
		}
		int lo = *max_element(a,a+m);
		int hi = s;
		int it=100;
		int req;
		while(lo <= hi and it--){
			int mid = lo + (hi-lo)/2;
			int sum=0;
			req=1;
			for(int i=0;i<m;i++){
				if(sum + a[i] <= mid){
					sum += a[i];
					trace1(sum);
				}
				else{
					++req;
					sum = a[i];
					v.pb(i);
				}
			}
			if(req<=k){
				hi=mid;
			}
	
			else{
				lo= mid+1;
				
			}
		}
	//	cout<<"loop terminated";
		
		
	}
}

can you suggest me how can proceed further from here?

Hello CF community! I have previously asked my doubts regarding the specific problem on my blog but turns out I was getting downvoted. So, I thought there must be something I was doing wrong. I am writing this to know how to ask one's doubt regarding specific problems and their approaches? Are there some guidelines or other threads where I should ask my doubts? Any help is appreciated. Thank you

I am trying to solve SAMER08D — DNA Sequences . I know how to solve LCS but can't figure out how to think of states in this problem. I tried reading approaches for the solution of this problem on google but I only got codes. However, that didn't help as I did not get a feel what code was trying to do. Can you please help me with this ?

Please go through this problem (some may have difficulty accessing it). I tried to solve this problem by doing the following: 1. Since the answer is bound to come in 60 steps. If I calculate the minimum moves to reach the answer then I am done. 2. so I thought First try, anew = a+b and ask for solution (anew,b,n-anew), and then try bnew = a+b and ask for solution of (a,bnew,n-bnew) . Then I will store the solution whichever gives me minimum steps; 3.Since three elements are forming the state of DP memoizing becomes messy and difficult to construct the actual solution. 4. I tried hard to implement but could not pass even simple test case 5. I also found it difficult to write base cases for recursion.

I wish to know how you approach such DP problems? If there are other solutions to the problem, I would be happy to know their approaches too. Please help me with this.

Please go through this problem 716B. My idea is : 1. if length of string in less than 26 , print "-1" and return ; 2. calculate frequency of first 26 characters and then see how many characters are left out and how many '?' are available . 3. If left out == cnt['?'] it is possible. 4. If not go for next 26. 4. I tried it but failed on 18th test case here? Could you help me with my implementation. Or if you have more elegant implementation please suggest me.

Please go through the problem. I was impressed by this solution which is what editorial also suggested editorial. I got how to compute 2's power and what needs to be added to get the power of 2 but can't understand how they are calculating the count of such pairs? Please explain with context to what editorial and solution are trying to do.

Please look at problem here. I figured out how to do it: 1. I will check among all possible quasibinary numbers which provides me least numbers of such numbers whose sum is equal to n(the given number) 2. I memoize the solution. Basic DP stuff. 3. In all my tests I got correct answer for number of numbers but I can't construct the solution i.e actual numbers which form the solution. Can you help me with this.

I have submitted my solution here

Hello all. I was solving one problem which boils down to finding 2 numbers (precisely their indices) in an array which are at least some distance k apart such that their sum is maximum. How can i solve this problem in O(n).

eg indice 1 2 3 4 5 6 7 8 9 10 arr[i] 4 18 18 20 11 17 17 14 14 17

given k = 3; answer is : 4(20) , 7(17).