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$$$.
Greedy.
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?
Yes. You could easily prove that.
Have you found some cases that the solution in Hint 2 dosen't work?
Try to reverse the array.
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.
UPD: The time complexity is $$$\mathcal O(n)$$$, which is fast enough.
What would your solution do in this case:
$$$a = [101_2, 10101_2]$$$, $$$k=1$$$, $$$x=10000_2$$$
If I understand correctly the solution would see $$$101_2$$$ at $$$a_1$$$, and since it is smaller than $$$x$$$ it would create a partition there. But obviously this is the wrong way since it leaves $$$a_2$$$ part of no segment at all and thus your solution would claim
NO. Whereas the correct way would be to include both $$$a_1$$$ and $$$a_2$$$ in the same segment, which means the answerYES.Response to "UPD":
From my experience (since I commonly have this thought too) when a solution is wrong, figuring "reverse the array" usually doesn't fix anything. Indeed, it's easy to show a case that exemplifies it for the updated solution:
$$$a = [1_2, 10000_2, 1_2]$$$, $$$k=2$$$, $$$x=10001_2$$$
The array is symmetrical so we can ignore the step about reversing. Here, the provided solution creates length $$$1$$$ segments at $$$[1, 1]$$$ and $$$[2, 2]$$$, ignoring $$$a_3$$$. As $$$a_3$$$ is left over, it incorrectly claims the answer is
NO.A DP solution to this problem is quite simple, perhaps you can improve it from there.
What about $$$a = [1, 4, 2], k = 2, x = 5$$$. It is clearly possible if you divide into sections $$$[1, 4]$$$ and $$$[2]$$$ which have xor-sum $$$5$$$ and $$$2$$$ respectively. But the greedy algorithm would divide after $$$1$$$ and the remaining numbers $$$4, 2$$$ do not have an xor-sum $$$\le 5$$$, and so it would incorrectly output
No.Bro in the case the length of array is only $$$3$$$, how could you get the segment $$$[1,4]$$$? I can't understand at all xD
I meant the segment with the numbers $$$1$$$ and $$$4$$$ in it, sorry. In terms of array indices the solution is $$$[1, 2]$$$ and $$$[3, 3]$$$.
Auto comment: topic has been updated by GDCass1ni (previous revision, new revision, compare).
Auto comment: topic has been updated by GDCass1ni (previous revision, new revision, compare).
You say you fixed the solution, but now what about $$$a = [3, 6, 1, 1, 6, 3], k = 4, x = 5$$$? This is also clearly possible by splitting into sections with indices $$$[1, 2], [3, 3], [4, 4], [5, 6]$$$ with respective xor-sums $$$5, 1, 1, 5$$$, so the answer is
Yes. The greedy algorithm on the other hand would split after $$$3$$$, then not split until the second $$$6$$$, meaning it can find a maximum of $$$3$$$ sections, and incorrectly outputNo. Since this test case is symmetrical, reversing the array and calculating again won't help.In your hints and solutions, you wrote things like "You could easily prove that." and "think about why.". There's probably a good reason most contest editorials don't contain such statements, instead having actual rigorous proofs. Do you have one for this problem?
My solution is to spilt the segments as short as possible, so it will spilt after $$$2$$$ and work on this test case xD.
And I really think that the proof is very easy :)
If it splits the segments as short as possible, it will split after index 1, because the segment containing just 3 has an xor-sum less than or equal to 5. I don't know why you are saying it will split after index 2, because at that point the current xor-sum will be 6 (as it has already split after index 1 and started a new segment), so it cannot split at that index. Unless I've misunderstood your solution, in which case please explain exactly how it would split the array in this test case.
You are right, I will fix my solution later, thanks.