Timeline for Minimize the length of two disjoint segments in the string with given property
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 20, 2014 at 13:33 | comment | added | Praveen Dhinwa | @მამუკა ჯიბლაძე, It seems like $\mathbf{O}(n^2)$ might not be improved, I had the following idea, but still it is not much helpful, Binary search over the length, So given a fixed sum of length, can you find two disjoint segments with given length and having number of A's $\geq$ z. I dont have less than $\mathbf{O}(n^2)$ solution for the subproblem that I mentioned. | |
| Mar 19, 2014 at 12:46 | history | edited | Praveen Dhinwa | CC BY-SA 3.0 |
deleted 89 characters in body
|
| Mar 19, 2014 at 10:49 | comment | added | Praveen Dhinwa | ^Federico Poloni, Is it better now? | |
| Mar 19, 2014 at 10:49 | history | edited | Praveen Dhinwa | CC BY-SA 3.0 |
edited title
|
| Mar 19, 2014 at 10:46 | comment | added | Federico Poloni | Could you please add a more descriptive title? "Another Interesting Maths Problem" could easily refer to any question asked here. | |
| Mar 19, 2014 at 10:37 | comment | added | მამუკა ჯიბლაძე | Discarding Bs in the beginning, we have, say, $x_1$ As, $t_1$ Bs, $x_2$ As, $t_2$ Bs and so on. Let $s_1=x_1$, $s_2=x_1+x_2$, $s_3=x_1+x_2+x_3$ etc., so $0=s_0<s_1<s_2<\cdots$ is arbitrary increasing sequence. We then search for $i<j<k<l$ such that $s_j-s_i+s_l-s_k\geqslant z$, with $j-i+l-k$ as small as possible. With this reformulation, I doubt $O(n^2)$ can be improved. | |
| Mar 19, 2014 at 10:15 | history | asked | Praveen Dhinwa | CC BY-SA 3.0 |