Today we will discuss a common problem. The problem is, you are given a string S, you have to find the longest palindromic substring in S. For example, S = abcbsd, here our desired answer is bcb with length 3. Solution: This problem can be solved in many ways. One of them is DP solution and another is Expand Around Center. DP: DP solution is a very straight cut solution. We go through all the substrings of the main string S and check each substring is palindrome or not and find the longest substring if it is palindrome. Here we do DP in the palindrome checking part. Here is the Code. Complexity O(n^2) . #include<bits/stdc++.h> using namespace std ; string s ; int dp [ 1005 ] [ 1005 ] ; ///dp[l][r] means is substring s[l...r] is a palindrome or not int isPalindrome ( int left, int right ) { if ( left >= right ) return 1 ; if ( dp [ left ] [ right ] ! = - 1 ) return dp [ left ] [ right ] ; int result = 0 ; if ( s ...
Problem Post #01 Given a positive integer N, determine whether you can make N by summing up some non-negative multiple of A and some non-negative multiple of B where A and are relatively prime numbers. ( একটা ধনাত্বক পূর্নসংখ্যা N দেয়া আছে । তোমাকে বলতে হবে N কে A এবং B এর গুনিতক এর যোগফল আকারে প্রকাশ করা যায় কিনা । অর্থাৎ N = xA + yB আকারে প্রকাশ করা যায় কিনা যেখানে x এবং y রিলেটিভ প্রাইম সংখ্যা । ) Solutions: The Chicken McNugget Theorem (or Postage Stamp Problem or Frobenius Coin Problem) states that for any two relatively prime positive integers A, B, the greatest integer that cannot be written in the form xA + yB for nonnegative integers x, y is AB - A - B. ( এই থিওরি মতে যেকোন দুইটা রিলেটিভ পজিটিভ প্রাইম সংখ্যা A এবং B এর জন্য সবচেয়ে বড় যে সংখ্যাটা xA + yB ফর্ম এ লেখা যাবে না সেটা হলো A*B - A - B অর্থাৎ A*B - A - B এর থেকে বড় সকল সংখ্যা xA + yB আকারে প্রকাশ করা যাবে ) A consequence of the theorem is that there are exactly positive i...
Comments
Post a Comment