Given two sequences $a$ and $b$, find largest $x$ such that in $a$ there is substring $A$ and substring $B$ in $b$ meeting those conditions:

  1. length of both $A$ and $B$ is equal to $x$;
  2. sum of elements in $A$ has the same parity as sum of elements in $B$.

Lengths of $a$ and $b$ are up to $5\times10^5$, so simple $O(n^2)$ solution won't do.

Example:
$a = [0, 1, 2, 3, 4, 5]$
$b = [3, 1, 3, 6]$
Answer: 3 (one of the possible solutions is $A = [2, 3, 4], B = [3, 1, 3]$).

I've thought about it for hours and can't find a solution. How to do this in linear or linearithmic time complexity?

I'm quite sure the problem can be simplified to for index $i$, storing only sum of elements up to $i$ modulo $2$. However, it doesn't help me much.

(The problem comes from a rather-old Israeli book תכנות תחרותי: סביב אתגרים ('Competetitive programming') by Mordechai Ben-Ari. The book isn't well known and I couldn't find any solution in Hebrew, so I translated the problem into English for a better chance of getting answer.)

Any help will be appreciated.

New contributor
ךאמיל is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • Thanks @TopSekret! I just deleted my comment that contains a clue. I can only hope that I have not gone too far in my comment. This site is a fishing pond for various contest participants. It looks like I have to be even more vigilant. I can be certain that Yuval's answer below is not the algorithm intended by the Polish IT olympics and I suspect that the acceptance of that answer is only a decoy of OP's true intention. (Of course, I cannot have any further evidence hereof.) – Apass.Jack Nov 9 at 18:27
  • You do realize @TopSekret 's question here is the same question as this after trivial transformation of the problem? – ךאמיל Nov 9 at 18:51
  • For each index $i$, store parity of sum between $0$ and $i$; then what you do have to do? Find common longest subsequences of same length and same both ends! (This is the "What if all numbers belong to a small closed range (like the max value is 3 or they are bits)?"--we then have exactly bits.) – ךאמיל Nov 9 at 19:03
  • We don't have any ball in your game. Not restoring any comments against their authors' will, but definitely deleting the conversation that has nothing to do with the question. Please use Computer Science Chat if you want to, well, chat. – Raphael 7 hours ago
up vote 2 down vote accepted

Here is an $O(n\log^2 n)$ solution.

The first step is to reduce to an easier problem:

Given $x_1,\ldots,x_n \in \{0,1\}$, determine, for all $0 \leq i \leq n$ and $b \in \{0,1\}$, whether there is a contiguous subarray of length $i$ whose sum is equal to $b$ modulo 2.

Applying this to both $A$ and $B$, we can solve the original problem in $O(n)$.

The basic idea is to use divide and conquer. Given an array $x_1,\ldots,x_n$, divide it into two arrays $x_1,\ldots,x_m$ and $x_{m+1},\ldots,x_n$ of roughly equal size. Every contiguous subarray of $x_1,\ldots,x_n$ of length $i$ with parity $b$ has one of the following forms:

  1. Contiguous subarray of $x_1,\ldots,x_m$ of length $i$ with parity $b$.
  2. Contiguous subarray of $x_{m+1},\ldots,x_n$ of length $i$ with parity $b$.
  3. The concatenation of a subarray $x_{m-i_1+1},\ldots,x_m$ of parity $b_1$ with a subarray $x_{m+1},\ldots,x_{m+i_2}$ of parity $b_2$, where $i_1+i_2 = i$ and $b_1+b_2 \equiv b \pmod{2}$.

We can determine whether subarrays of the first two forms exist, for all $i$ and $b$, by running the procedure recursively on the two halves. The interesting part is the third form. We start by determining the parity of all arrays of the form $x_{m-i_1+1},\ldots,x_m$ and of the form $x_{m+1},\ldots,x_{m+i_2}$ for all $i_1,i_2$, which takes time $O(n)$. Let $L_{b_1}$ be the set of $i_1$ such that $x_{m-i_1+1},\ldots,x_m$ has parity $b_1$, and define $R_{b_2}$ analogously. Using FFT (exercise), for each $b_1,b_2$ we can determine in $O(n\log n)$ the set $X_{b_1b_2}$ of $i$ such that there exist $i_1 \in L_{b_1}$ and $i_2 \in R_{b_2}$ summing to $i$. Given the sets $X_{b_1b_2}$ for all $b_1,b_2$, we can determine whether subarrays of the third form exist, for all $i$ and $b$.

In total, denoting the running time of our algorithm by $T(n)$, we get the recurrence $$ T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + O(n\log n), $$ whose solution is $T(n) = O(n\log^2 n)$.

  • It looks like there is an $O(n)$ algorithm, although $O(n\log^2n)$ with not huge constant multiplier might be enough for competitive programming. – Apass.Jack Nov 9 at 7:23
  • Yes, that's not too surprising. – Yuval Filmus Nov 9 at 8:20
  • @YuvalFilmus I understand everything but I can't imagine how to find the set $X_{b_1b_2}$ using FFT. If I understand correctly, it's as if we have two sets of numbers, let's call them $P$ and $Q$, and we want every possible sum of one number from $P$ and one from $Q$ (with the additional restriction that such sum will never exceed $n$). How to do that? – ךאמיל Nov 9 at 13:58
  • @Apass.Jack What is that algorithm? If you don't want to write everything, could you just give an overview? (If it's $O(n)$ then it doesn't require FFT and maybe I have a chance of understanding it 😃) – ךאמיל Nov 9 at 14:05
  • 1
    Hint: FFT can be used to multiply polynomials. – Yuval Filmus Nov 9 at 15:15

Your Answer

ךאמיל is a new contributor. Be nice, and check out our Code of Conduct.
 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.