Codeforces Round 2717 | Problem B | AGAGA XOOORRR
Разница между en1 и en2, 2 символ(ов) изменены
I would recommend reading the problem first.↵
Now that you have read it.↵
When we calculate the XOR of adjacent elements array eventually boils down to size 1.↵
But we need to stop at array length '2' because then only elements being equal makes sense.(Given in the problem.)↵

NOTE:↵
XOR of two elements which are equal is '0'.↵
XOR of an element with '0' is the element itself.↵

Now suppose we are reducing the array by calculating XORs.↵
Case 1: when the two elements are equal : ↵
 Example : a b c d e e↵
At certain point(Greater than 3) if two adjacent elements are equal, then we obtain '0' as XOR.(e XOR e = 0)↵
We have : a b c d 0↵
Now when we XOR : a b c d ↵

So we transformed array from a b c d e e -> a b c d ↵


Case 2 : when they are not equal : ↵
a b c d e f -> a b c d g (g= e XOR f)↵

In both the cases we reduced the array size by 1 or 2.↵

Suppose we reduce the array size to 4.↵
If its case 1 then we get an array of size 2. We stop here.↵
If its case 2 then we get an array of size 3. Now if its case 1 we would get 1 element, which is not feasible. Otherwise if its case 2 we would get 2 elements.↵


At the end we are left with 2 or 3 set of elements, which are obtained from XORing adjacent elements.↵
So we could find 2 partitions of array, XORing these two partitions we get '0' then its a YES.↵
Or we could find three partitions of array, XORing these three parts we get '0', then its a YES else NO.↵

Case 1: TWO PARTS — ↵
If we are left with 2 elements, then both the elements(element1 and element2) should be equal. If they are equal then element1 XOR element2 is 0.↵
Element1 was obtained from some adjacent elements XOR.↵
Element2 was obtained from some adjacent elements XOR.↵
Therefore, if Element1 XOR Element2 is zero. The XOR of whole array must have been 0 to get this.↵


Case 2 : THREE PARTS:↵

You could use two nested loops for two pointers which would split the array into three parts.↵

Use prefix array to calculate XORs from 1 to i- index and store it.↵

a  b c d  e f g ↵

XOR of{c,d} = XOR of(a,b,c,d) XOR XOR of(a,b).↵
Why so?↵
a^b^c^d^a^b = c^d [As x^x = 0 && 0 ^ x = x]↵


Using this calculate the XOR of three parts of every possible partition. If you find the XOR of these parts equal for a partition print YES else NO.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский amireripmav786 2021-04-22 17:01:38 2
en1 Английский amireripmav786 2021-04-22 17:00:58 2345 Initial revision (published)