can anyone suggest approach to solve this problem?
given a string S. you have to find maximum product of length of two non overlapping palindromic sequence.
here, non overlapping means only indexes are non overlap.
s = “abcab”
ans = 3*2 = 6
two palindromic sequence are “aca” and “bb”
s = nriatdoiarn
ans = 5*5 = 25
two palindromic sequences are “nitin” and ( “radar” or “raoar”)
s = “abcdef”
ans = 1*1 = 1
please share your solution.
Easy Version link : https://stackoverflow.com/questions/53663721/find-the-maximum-product-of-two-non-overlapping-palindromic-subsequences
Given an array A[1…N] of positive integers, you have to sort it in ascending order in the following manner : In every operation, select any 2 non-overlapping sub-arrays of equal length and swap them. i.e, select two sub-arrays A[i…(i+k-1)] and A[j…(j+k-1)] such that i+k-1 < j and swap A[i] with A[j], A[i+1] with A[j+1] … and A[i+k-1] with A[j+k-1].
6 7 8 1 2 3
Only one operation is needed as after swapping (6 7 8) and (1 2 3 ) sub arrays
we can get 1 2 3 6 7 8 , that is sorted.
How can we figure out minimum number of swaps in most effective way ? and what is minimum time complexity ?
hackereath link :
This is the time of Christmas and Santa wants to distribute gifts to M children. He has N number of boxes, and each box contains some chocolates. Now, Santa wants to distribute N boxes to M children keeping in mind that distribution should be as fair as possible. To fairly distribute the gift boxes, Santa wants to minimize the maximum number of choclates gifted to a child.
Formally, given M number of children and N boxes, where each box contains some amount of chocolates. The task is to minimize the maximum number of chocolate gifted to a child.
In another word, you have to divide array into M subset such that maximum sum of subset is minimized.
First line of input contains number of testcases T. For each testcase, there will be three lines of input. First line contains N number of gift boxes, next line contains choclates in each of the N boxes. Last line contains number of children.
For each testcase, print the minimum number of maximum chocolate a child get.
1 <= T <= 100
1 <= N, M <= 10^6
1 <= A[i] <= 10^8
12 34 67 200
Testcase 1: Minimum 200 chocolates will be given to a child which gets the maximum number of chocolate.
Another Corner Case : n = 5 and M=3
array is : [ 3 4 5 5 8]
answer is : 9
how to solve? i didn’t figure out.
how to solve this problem?
how to apply centroid decomposition in this problem? or any other approach to solve this problem?