hulk_baba's blog

By hulk_baba, history, 3 years ago, In English

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.

Read more »

 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

By hulk_baba, history, 4 years ago, In English

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; } }

Read more »

 
 
 
 
  • Vote: I like it
  • -5
  • Vote: I do not like it

By hulk_baba, history, 4 years ago, In English

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

Read more »

 
 
 
 
  • Vote: I like it
  • -21
  • Vote: I do not like it

By hulk_baba, history, 4 years ago, In English

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.

Read more »

 
 
 
 
  • Vote: I like it
  • -8
  • Vote: I do not like it

By hulk_baba, history, 4 years ago, In English

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?

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By hulk_baba, history, 5 years ago, In English

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..

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

By hulk_baba, history, 5 years ago, In English

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 ..

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Read more »

 
 
 
 
  • Vote: I like it
  • -17
  • Vote: I do not like it

By hulk_baba, history, 5 years ago, In English

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

Read more »

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

By hulk_baba, history, 5 years ago, In English

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 ?

Read more »

 
 
 
 
  • Vote: I like it
  • -5
  • Vote: I do not like it

By hulk_baba, 5 years ago, In English

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.

Read more »

Tags #dp
 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

By hulk_baba, history, 5 years ago, In English

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.

Read more »

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

By hulk_baba, 5 years ago, In English

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.

Read more »

 
 
 
 
  • Vote: I like it
  • +13
  • Vote: I do not like it

By hulk_baba, history, 5 years ago, In English

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

Read more »

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

By hulk_baba, history, 5 years ago, In English

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).

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it