### hulk_baba's blog

By hulk_baba, history, 3 years ago, 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. By hulk_baba, history, 4 years ago, 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;
}
} #dp,
By hulk_baba, history, 4 years ago, 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 By hulk_baba, history, 4 years ago, 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. By hulk_baba, history, 4 years ago, 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? lca,
By hulk_baba, history, 5 years ago, 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..

By hulk_baba, history, 5 years ago, 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 ..

By hulk_baba, 5 years ago, 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;
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?

By hulk_baba, history, 5 years ago, 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 By hulk_baba, history, 5 years ago, 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 ? #dp,
By hulk_baba, 5 years ago, 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. By hulk_baba, history, 5 years ago, 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.

By hulk_baba, 5 years ago, 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. hash,
By hulk_baba, history, 5 years ago, 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 #dp,
By hulk_baba, history, 5 years ago, 