Skip to main content
MathOverflow

Return to Question

deleted 89 characters in body
Source Link
Praveen Dhinwa
Praveen Dhinwa
  • 363
  • 2
  • 8

You are given a strngstring s of size n, consisting of characters A and B only. Ram wantsYou have to take out two disjoint segments out of its and he will count the number of As inside those segments, let us call this quantity x andfind minimum sum of size of the two disjoint segments y. You have to find minimum yof the string s such that there exists two disjoint segments which have their x quantitynumber of A's in them are >= z.

Input: string s, n, x and z are given in the input. Output: minimum sum of size of two disjoint segments with given property

Currently I have a solution of complexity $\mathbf{O}(n^2)$, Can anybody give a better solution than this?

Or can somebody prove that it is somehow related to 3 SUM problem?

You are given a strng s of size n, consisting of characters A and B only. Ram wants to take out two disjoint segments out of its and he will count the number of As inside those segments, let us call this quantity x and sum of size of the two segments y. You have to find minimum y such that there exists two disjoint segments which have their x quantity >= z.

string s, n, x and z are given in the input.

Currently I have a solution of complexity $\mathbf{O}(n^2)$, Can anybody give a better solution than this?

Or can somebody prove that it is somehow related to 3 SUM problem?

You are given a string s of size n, consisting of characters A and B only. You have to find minimum sum of size of the two disjoint segments of the string s such that number of A's in them are >= z.

Input: string s, n, z are given in the input. Output: minimum sum of size of two disjoint segments with given property

Currently I have a solution of complexity $\mathbf{O}(n^2)$, Can anybody give a better solution than this?

Or can somebody prove that it is somehow related to 3 SUM problem?

edited title
Link
Praveen Dhinwa
Praveen Dhinwa
  • 363
  • 2
  • 8

Another Interesting Maths Problem Minimize the length of two disjoint segments in the string with given property

Source Link
Praveen Dhinwa
Praveen Dhinwa
  • 363
  • 2
  • 8

Another Interesting Maths Problem

You are given a strng s of size n, consisting of characters A and B only. Ram wants to take out two disjoint segments out of its and he will count the number of As inside those segments, let us call this quantity x and sum of size of the two segments y. You have to find minimum y such that there exists two disjoint segments which have their x quantity >= z.

string s, n, x and z are given in the input.

Currently I have a solution of complexity $\mathbf{O}(n^2)$, Can anybody give a better solution than this?

Or can somebody prove that it is somehow related to 3 SUM problem?