#Xor Sum Problem

28 messages · Page 1 of 1 (latest)

dense laurel
#

I got a CP problem here that I would like help with


You are given four integers: n, m, s, x.
You need to construct an array of size n such that:
1. All its elements are integers in the range [0, m].
2. The sum of its elements is equal to s.
3. The Bitwise XOR sum of all its elements is equal to x.

Can you do this?

Input:
The first line contains an integer t — the number of test cases (1 <= t <= 10^5).
Then t test cases follow, each containing four integers: n, m, s, x.
(1 <= n <= 10^5)
(0 <= m < 2^30)
(0 <= s <= 10^18)
(0 <= x < 2^30)
It is guaranteed that the sum of n across all test cases does not exceed 3 * 10^5.

Output:
For each test case:
If it is impossible to construct an array that meets the conditions, print -1.
Otherwise, print n integers on a single line — the array that satisfies the conditions.

Sample Input
3
4 4 15 7
4 4 4 4
4 4 15 1

Sample Output
4 4 4 3
4 0 0 0
-1```
neon shardBOT
#

⌛ This post has been reserved for your question.

Hey @dense laurel! Please use /close or the Close Post button above when your problem is solved. Please remember to follow the help guidelines. This post will be automatically marked as dormant after 720 minutes of inactivity.

TIP: Narrow down your issue to simple and precise questions to maximize the chance that others will reply in here.

dense lava
#

I think you could start with one number being equal to x and all other numbers 0

#

then you try to always swap one bit in two numbers at once until the sum equals s

#

Then you "just" have to figure out which bits to swap in which numbers

#

The first priority is making sure that all numbers <=m so you would flip some bits ensuring that

#

once you achieve that, flip some more pairs of bits to get the sum you want without violating the previous constraints

#

and in general: Try starting with the highest/most significant bit and work your way down

#

There would be some edge cases to consider but I think these shouldn't be that complicated

dense laurel
dense lava
dense laurel
#

Can I brute force this?

#

Like keep trying all possible numbers

#

What is a XOR sum anyway. I know XOR, but what do they mean by sum of all elements

dense lava
#

Maybe this can help:

  • To access the n-th bit of an int, you can create a "mask" where that bit is set and all other bits are unset. If we assume that it is the n-th least significant bit starting from 0 (so bit 0 is the least significant bit), you can create a bit mask using something like int mask = 1 << n;
  • When you have an int called number, you can flip the bit of that mask using number ^ mask, set it to 1 using number | mask, set it to 0 using number & ~mask or check whether it is set using (number & mask) != 0
dense lava
#

The problem is about finding a way such that the sum of all numbers is a specific value (s) and that XORing all numbers (a ^ b ^ c) is a specific value (x) (and also ensuring all numbers are between 0 and m, both inclusive)

dense lava
dense laurel
#

I don't think Performance and efficiency matter, they said it. So a simple clean version is better

#

Like start with an array filled with 0s, then keep adding 1 till we get the result. If all elements reached m then print -1

#

Now when I think about it it's heavy

dense lava
#

I don't know how long it will take, feel free to try

dense laurel
#

Yeah I should look for an efficient solution 🥲

neon shardBOT
#

💤 Post marked as dormant

This post has been inactive for over 720 minutes, thus, it has been archived.
If your question was not answered yet, feel free to re-open this post or create a new one.
In case your post is not getting any attention, you can try to use /help ping.
Warning: abusing this will result in moderative actions taken against you.

broken pecan
dense lava
#

my fault, edited