if com(i) = 0^1^2^…..^i then

com(i) is defined as follows :

int com(int i){ int a[] = {i, 1, i+1, 0}; return a[i%4]; }

and the value of (i)^(i+1)^….^(j) is :

com(j)^com(i-1).

Skip to content
# a property of bitwise xor sum.

# Famous Sequences of Grundy values.

# modified stack & queue for finding (minimum/maximum) in O(1)

# Useful links

if com(i) = 0^1^2^…..^i then

com(i) is defined as follows :

int com(int i){ int a[] = {i, 1, i+1, 0}; return a[i%4]; }

and the value of (i)^(i+1)^….^(j) is :

com(j)^com(i-1).

Advertisements

*Seq id*: A025480.

*Seq definition*: a(2n) = n, a(2n+1) = a(n).

*Seq first terms*: 0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, 0, 8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15, 0, 16, 8, 17, 4, 18, 9, 19, 2, 20, 10, 21, 5, 22, 11, 23, 1, 24, 12, 25, 6, 26, 13, 27, 3, 28, 14, 29, 7, 30, 15, 31, 0, 32, 16, 33, 8, 34, 17, 35, 4, 36, 18, 37, 9, 38, 19, 39, 2, 40, 20, 41, 10

Original article : https://e-maxx.ru/algo/stacks_for_minima.

You can use Yandex translation to translate the page from Russian.

And this link on StackOverflow have a good explanation on how to represent a queue data structure using two stacks.

here is a good implementation to the above mentioned algorithm.

These are some materials that i think it maybe useful for those interested in algorithmic problem solving :

T-414-ÁFLV: A Competitive Programming Course

CS 97SI: Introduction to Programming Contests

will be updated regularly.