[My New Problem] XOR partition
Difference between en2 and en3, changed 32 character(s)


<spoiler summary="Statement">↵
You are given an array $a_1,a_2,\ldots,a_n \; (1 \le n \le 10^5,0 \le a_i \le 10^9)$ and two integers $k,x$, determine if it is possible to divide the array into exactly $k$ segments $[l_1,r_1],[l_2,r_2],\ldots,[l_k,r_k] \; (l_1 = 1,r_k = n,l_{i+1} = r_i + 1)$ such that $\forall i \in [1,k], \oplus_{j=l_i}^{r_i} a_j \le x$.↵
</spoiler>↵

<spoiler summary="Hint 1">↵
Greedy.↵
</spoiler>↵

<spoiler summary="Hint 2">↵
Consider the first segment. Let $p$ be the mininum position such that $\oplus_{j=1}^p a_j \le x$, is the partition $[l_1,r_1] = [1,p]$ optimal?↵

<spoiler summary="Answer">↵
Yes. You could easily prove that.↵
</spoiler>↵

</spoiler>↵

<spoiler summary="Hint 3">↵
Have you found some cases that the solution in Hint 2 dosen't work?↵

Try to reverse the array.↵
</spoiler>↵

<spoiler summary="Solution">↵
Read the hints first.↵

For each segment, we want it to be as short as possible. Thus, we can just iterate $r$ from $l$ to $n$, when the XOR sum of $a[l,r]$ is not greater than $x$, divide here. If we get exactly $k$ segments, output `Yes`, otherwise the answer is `No`.↵

There's a small case: sometimes you need to reverse the array and calculate again, think about why.↵
</spoiler>↵

**UPD** Thanks to [user:nonrice,2024-06-06]
 and [user:sammyuri,2024-06-06], I fix the solution.↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English GDCass1ni 2024-06-06 16:26:57 32
en2 English GDCass1ni 2024-06-06 16:25:32 310
en1 English GDCass1ni 2024-06-06 16:00:03 1037 Initial revision (published)