### k1r1t0's blog

By k1r1t0, 4 months ago,

Recently I was trying to solve the following problem: 102441E - Very Simple Sum.

In process of solving it, I realised that I need to use xor convolution and just copied FWHT code somewhere from the internet. My solution passed, but I wanted to know how does it work, so started searching info on FWHT and xor convolution.

After some time of going through endless blogs talking about weird matrices and other difficult stuff, I decided to reinvent everything on my own, as I always do. Here I will describe a simple algorithmic way to look at xor convolution, I hope that it doesn't contain any crucial mistakes and will be useful for you.

## The Algorithm

Let the size of the arrays be $2^n$, we want to calculate

$C_i = \sum_{j\oplus k=i}{A_j\cdot B_k}$

for all $0\le i\le 2^n - 1$.

If we look at halves of the arrays separately, first half consists of indices with $n$-th bit set to zero, and the second consists of indices with $n$-th bit set to one, so the sum becomes

$C0_i = \sum_{j\oplus k=i}{A0_j\cdot B0_k+A1_j\cdot B1_k}$
$C1_i = \sum_{j\oplus k=i}{A0_j\cdot B1_k+A1_j\cdot B0_k}$

where $X0$ is the first half of $X$ and $X1$ is the second.

Let's take a look at the xor convolution of $A0+A1$ and $B0+B1$:

• +231

By k1r1t0, history, 8 months ago,

Finally

• +166

By k1r1t0, history, 9 months ago,

Here I will describe a way to maintain deque that will allow us to find the smallest element in deque at any time. Maybe this technique is well-known, but I couldn’t find any info about it, so decided to post it there.

### Minimum Stack and Minimum Queue

First, we want to maintain stack with the ability to find its smallest element whenever we want. Let's store minimums on the corresponding prefix of stack along with elements. This way we can easily push/pop elements and find minimum in $O(1)$.

Minimum Queue can be maintained using two Minimum Stacks: one stack will store some elements from beginning, and the other from the end. We will push elements to the second stack and pop them from the first. If the first stack becomes empty, then we move all elements from the second stack into the first. It will work in $O(N)$ amortized.

### Minimum Deque

Actually, we can maintain Minimum Deque the same way we maintain Minimum Queue, but it will be too slow. The problem is the number of moved elements: in the worst case we will move all elements every operation by removing first and last element alternately. So instead of moving all elements let's move only a half of them at a time. Turns out it works in $O(N)$!

But how to prove it? Let $k_i$ be the number of elements deque contained right before $i_{th}$ operation, the algorithm above obviously works in $O(N + \sum k_i)$. Also $k_i = \frac{k_{i-1}}{2} + q_i$, where $q_i$ is the number of elements added between operations $i-1$ and $i$. We can see that $q_i$ contributes $q_i$ to $k_i$, $\frac{q_i}{2}$ to $k_{i+1}$, $\frac{q_i}{4}$ to $k_{i+2}$ and so on. It follows that $q_i$ contributes $O(q_i)$ to $O(\sum k_i)$. $\sum q_i$ is obviously $\leq N$, so $O(\sum k_i) = O(N)$. That's why the algorithm above is $O(N)$ amortized.

Implementation
• +210

By k1r1t0, history, 10 months ago,

Thank you for participating in #25!

Editorial
Solution
Editorial
Solution
Editorial
Solution
Editorial (Easy Version)
Editorial (Hard Version)
Solution (Easy Version)
Solution (Easy Version)
Editorial
Solution
Editorial
Solution
• +39

By k1r1t0, history, 10 months ago,

Hello, Codeforces!

We are glad to invite you to TheForces Round #25 (5^2-Forces), which will take place on Oct/29/2023 17:35 (Moscow time)

You will be given 6 problems and 2 hours to solve them.

The round is TheForces rated! After the round you can find your rating changes here.

Prizes: the participant in the $i$th place will receive $2^{3-i}$ dollars $(1 \leq i \leq 3)$ as a prize. In addition, we will randomly select $\lfloor \frac{p}{30} \rfloor$ lucky participants and give each of them $1$ dollar as a prize, where $p$ is the number of participants. Please actively participate!

We want to thank:

Previous contests

Congratulations to the winners:

1.Kude

2.siganai

And $3$ lucky participants(we only count people who have submitted at least once):

(Pls DM wuhudsm in CF or Discord for your prize :) )

Editorial published

• +72

By k1r1t0, history, 10 months ago,
Editorial
Editorial
Editorial
Hint 1
Hint 2
Editorial
Editorial
Hint 1
Hint 2
Hint 3
Editorial
Editorial
• +32

By k1r1t0, history, 14 months ago,

Thanks you for participating in TheForces Round #18! Here is editorial:

104443A - TheForces

Editorial

104443B - Smaller than 100

Editorial

104443C - Morco-Feely Palindromes

Editorial

104443D - Missing Characters

Editorial

104443E - Cringemeter

Editorial

104443F - Rt Dg

Editorial

104443G - Qpert pg yep

Editorial

104443H - Random Generator

Editorial
• +20

By k1r1t0, history, 14 months ago,

Hello, Codeforces! We are happy to invite you to TheForces Round #18 (JuneIsApril-Forces), which will take place on Jun/23/2023 17:35 (Moscow time) (which is unusual)

What is TheForces Round?

Problems of this round will have the April Fools style, Registration is open now!!

You will have 120 minutes to solve 8 problems.

Discord Server (1000+ people)

Contests' archive

Editorial is out

• +47

By k1r1t0, history, 14 months ago,
Problem A
Problem B
Problem C
Problem D
Problem E
• +30

By k1r1t0, history, 19 months ago,

Thanks you for participating in TheForces Round #4! Here is the editorial:

Problem A
Problem B
Problem C
Problem D
Problem E
Problem F
Problem G
• +50