k1r1t0's blog

By k1r1t0, 7 months ago, In English

Recently I was trying to solve the following problem: 102441E - Очень простая сумма.

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$$$:

Full text and comments »

  • Vote: I like it
  • +231
  • Vote: I do not like it

By k1r1t0, history, 10 months ago, In English
  • Vote: I like it
  • +166
  • Vote: I do not like it

By k1r1t0, history, 12 months ago, In English

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

Full text and comments »

  • Vote: I like it
  • +210
  • Vote: I do not like it

By k1r1t0, history, 12 months ago, In English

Thank you for participating in #25!

104743A - Make All Elements 0 by Yugandhar_Master:

Editorial
Solution

104743B - Array Construction by wuhudsm:

Editorial
Solution

104743C - Prefix MEX Problem by pavlekn:

Editorial
Solution

104743D1 - Prefix XOR Problem(Easy Version) and 104743D2 - Prefix XOR Problem(Hard Version) by pavlekn:

Editorial (Easy Version)
Editorial (Hard Version)
Solution (Easy Version)
Solution (Easy Version)

104743E - Range Modulo Queries by Ashutosh.Singh:

Editorial
Solution

104743F - Yet Another Tree Problem by aryanc403:

Editorial
Solution

Full text and comments »

  • Vote: I like it
  • +39
  • Vote: I do not like it

By k1r1t0, history, 12 months ago, In English

Hello, Codeforces!

We are glad to invite you to TheForces Round #25 (5^2-Forces), which will take place on 29.10.2023 17:35 (Московское время)

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!

You can get more information about theforces rating and prizes in our discord server.

We want to thank:

Previous contests

Congratulations to the winners:

1.Kude

2.siganai

3.YouKn0wWho

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

Full text and comments »

  • Vote: I like it
  • +72
  • Vote: I do not like it

By k1r1t0, history, 13 months ago, In English

104683A - Banis and Cards by Banis

Editorial

104683B - Left or Right Shift by wuhudsm

Editorial

104683C - Yet Another ÷2 or +1 Problem by wuhudsm

Editorial

104683D - Sum and Difference by Banis

Hint 1
Hint 2
Editorial

104683E - L-shaped Dominoes by chromate00

Editorial

104683F1 - Maximum Flow in DIV3?(Easy Version) and 104683F2 - Maximum Flow in DIV3?(Hard Version) by astilate

Hint 1
Hint 2
Hint 3
Editorial

104683G - Useless Trick by amenotiomoi

Editorial

Full text and comments »

  • Vote: I like it
  • +32
  • Vote: I do not like it

By k1r1t0, history, 16 months ago, In English

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

Full text and comments »

  • Vote: I like it
  • +20
  • Vote: I do not like it

By k1r1t0, history, 17 months ago, In English

Hello, Codeforces! We are happy to invite you to TheForces Round #18 (JuneIsApril-Forces), which will take place on 23.06.2023 17:35 (Московское время) (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

Full text and comments »

  • Vote: I like it
  • +47
  • Vote: I do not like it

By k1r1t0, history, 17 months ago, In English
Problem A
Problem B
Problem C
Problem D
Problem E

Full text and comments »

  • Vote: I like it
  • +30
  • Vote: I do not like it

By k1r1t0, history, 22 months ago, In English

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

Full text and comments »

  • Vote: I like it
  • +50
  • Vote: I do not like it