By DrSwad, history, 5 months ago, ,

## Inspiration

I'm very excited about this blog, as it took me quite a lot of effort and scavenging through the internet to completely grasp the concept of this technique(That's probably because I have almost zero knowledge in Linear Algebra or I'm just plain dumb). So I feel like I genuinely conquered a challenge, and I really want to share it with someone. But there's no way my CP friends circle will believe it, they'll think I'm just trying to show off :P

So here I am, sharing it on CF. I also created a personal blog, so that if I ever feel like sharing something again(not only about CP), I can write a blog there. I also added this same post there, you can read it there if you prefer dark theme. I'll be pleased to hear any thoughts on the blog or if I can improve it in some way ^_^

## Introduction

Since it concerns Linear Algebra, there needs to be a lot of formal stuff going on in the background. But, I'm too much inconfident on this subject to dare go much deep. So, whenever possible, I'll try to explain everything in intuitive and plain English words. Also, this blog might take a while to be read through completely, as there are quite a few observations to grasp, and the example problems aren't that easy either. So please be patient and try to go through it all, in several sits if needed. I believe it'll be worth the time. In any case, I've written the solutions, codes, and provided links to their editorials(if available). I'll provide more details in the solutions tomorrow and put more comments in the codes, since I'm really tired from writing this blog all day.

Now, the problems that can be solved using this technique are actually not much hard to identify. The most common scenario involves: you'll be given an array of numbers, and then the problem asks for an answer by considering all the xor-sums of the numbers in all possible subsets of the array. This technique can also be used in some online-query problems: the problem can provide queries of first type instructing you to insert numbers in the array(_without removal_, I don't know how to solve with deletion of elements) and in-between those queries, asking for answers in separate queries of second type.

The whole technique can be divided into two main parts, some problems can even be solved by using only the first part(Don't worry if you don't understand them completely now, I explain them in details right below): 1. Represent each given number in it's binary form and consider it as a vector in the $\mathbb{Z}_2^d$ vector space, where $d$ is the maximum possible number of bits. Then, xor of some of these numbers is equivalent to addition of the corresponding vectors in the vector space. 2. Somehow, relate the answer to the queries of second type with the basis of the vectors found in Part 1.

PS: Does anyone know any name for this technique? I'm feeling awkward referring to it as 'technique' this many times :P If it's not named yet, how about we name it something?

## Part 1: Relating XOR with Vector Addition in $\mathbb{Z}_2^d$

Let me explain the idea in plain English first, then we'll see what the $\mathbb{Z}_2^d$ and vector space means. I'm sure most of you have already made this observation by yourselves at some point.

Suppose, we're xor-ing the two numbers $2$ and $3.$ Let's do it below:

$\begin{equation*}\begin{array}{r} (10)_2\\ \underline{\oplus\;(11)_2}\\ (01)_2 \end{array}\end{equation*}$

Now, for each corresponding pair of bits in the two numbers, compare the result of their xor with the result of their sum taken modulo $2$:

Bit no. First number Second number $\oplus$ Sum Sum taken $\pmod 2$
$1$st bit $0$ $1$ $1$ $1$ $1$
$2$nd bit $1$ $1$ $0$ $2$ $0$

Notice the similarity between columns $4$ and $6$? So, we can see that taking xor between two numbers is essentially the same as, for each bit positions separately, taking the sum of the two corresponding bits in the two numbers modulo $2.$

Now, consider a cartesian plane with integer coordinates, where the coordinate values can only be $0$ or $1.$ If any of the coordinates, exceeds $1,$ or goes below $0,$ we simply take it's value modulo $2.$

This way, there can only be $4$ points in this plane: $(0, 0), (0, 1), (1, 0), (1, 1).$ Writing any other pair of coordinates will refer to one of them in the end, for example, point $(3, 2)$ is the same point as point $(1, 0)$ since $3 \equiv 1$ and $2 \equiv 0$ modulo $2.$

In view of this plane, we can represent the number $2 = (10)_2$ as the point $(0, 1),$ by setting the first bit of $2$ as the $x$ coordinate and the second bit as the $y$ coordinate in our plane. Refer to this point as $P(0, 1).$ Then, the position vector of $2$ will be $\overrightarrow{OP}$ where $O(0, 0)$ is the origin. Similarly, the position vector of $3$ will be $\overrightarrow{OQ}$ where $Q = (1, 1).$

An interesting thing happens here, if we add the two position vectors, the corresponding coordinates get added modulo $2,$ which actually gives us the position vector of the xor of these two position vectors. For example, adding vectors $\overrightarrow{OP}$ and $\overrightarrow{OQ}$ we get $\overrightarrow{OR}$ where $R(1, 0)$ turns out to be the point corresponding the xor of $2$ and $3.$

This is all there is to it. Transforming xor operations to bitwise addition modulo $2$ and, in some cases, vector addition in this way can be helpful in some problems. Let's see one such problem. Before that, let me explain in short what vector space and $\mathbb{Z}_2^b$ meant earlier. I apologize to any Linear Algebra fans, since I don't want to write formal definitions here to make things look harder than it is. I'll explain the idea of these terms the way I find them in my mind, kindly pardon me for any mistakes and correct me if I'm wrong.

$\underline{\text{Vector Space}}$: Just a collection of vectors.

$\underline{\mathbb{Z_2}}$: $\mathbb{Z_m}$ is the set of remainders upon division by $m.$ So, $\mathbb{Z_2}$ is simply the set $\{0, 1\},$ since these are the only remainders possible when taken modulo $2.$

$\underline{\mathbb{Z_2^d}}$: A $d-$dimensional vector space consisting of all the different position vectors that consists of $d$ coordinates, all coordinates being elements of $\mathbb{Z_2}.$ For example, earlier our custom cartesian plane was a two-dimensional one. So, it was $\mathbb{Z_2^2}.$ $\mathbb{Z_2^3}$ would be a small $3d-$plane with only $2^3 = 8$ points, all coordinates taken modulo $2.$

So, what we've seen is that the xor-operation is equivalent to vector addition in a $\mathbb{Z}_2^d$ vector space. See how unnecessarily intimidating this simple idea sounds when written in formal math!

Anyways, the problem:

### Problem 1 (Division 2 — C)

Find the number of non-empty subsets, modulo $10^9 + 7,$ of a given set of size $1 \le n \le 10^5$ with range of elements $1 \le a_i \le 70,$ such that the product of it's elements is a square number.

If you'd like to solve the problem first, then kindly pause and try it before reading on further.

Solution

Since the number of different possible masks were just $70$ in the previous problem, we had been able to use dynamic programming for checking all possible xors. But what if the constraint was much bigger, say $10^5.$ That is when we can use Part $2$ of this technique, which, in some cases, works even when the queries are online.

## Part 2: Bringing in Vector Basis

We need a couple of definitions now to move forward. All the vectors mentioned in what follows, exclude null vectors. I sincerely apologize for being so informal with these definitions.

$\underline{\text{Independent Vectors:}}$ A set of vectors $\vec{v_1}, \vec{v_2}, \ldots, \vec{v_n}$ is called independent, if none of them can be written as the sum of a linear combination of the rest.

$\underline{\text{Basis of a Vector Space:}}$ A set of vectors is called a basis of a vector space, if all of the element vectors of that space can be written uniquely as the sum of a linear combination of elements of that basis.

A few important properties of independent vectors and vector basis that we will need later on(I find these pretty intuitive, so I didn't bother with reading any formal proofs. Let me know in the comments if you need any help):

1. For a set of independent vectors, we can change any of these vectors by adding to it any linear combination of all of them, and the vectors will still stay independent. What's more fascinating is that, the set of vectors in the space representable by some linear combination of this independent set stays exactly the same after the change.

2. Notice that, in case of $\mathbb{Z}_2^d$ vector space, the coefficients in the linear combination of vectors must also lie in $\mathbb{Z}_2.$ Which means that, an element vector can either stay or not stay in a linear combination, there's no in-between.

3. The basis is actually the smallest sized set such that all other vectors in the vector space are representable by a linear combination of just the element vectors of that set.

4. The basis vectors are independent.

5. For any set with smaller number of independent vectors than the basis, not all of the vectors in the space will be representable.

6. And there cannot possibly be larger number of independent vectors than basis in a set. If $d$ is the size of the basis of a vector space, then the moment you have $d$ independent vectors in a set, it becomes a basis. You cannot add another vector into it, since that new vector is actually representable using the basis.

7. For a $d-$dimensional vector space, it's basis can have at most $d$ vector elements.

With just these few properties, we can experience some awesome solutions to a few hard problems. But first, we need to see how we can efficiently find the basis of a vector space of $n$ vectors, where each vector is an element of $\mathbb{Z}_2^d.$ The algorithm is quite awesome <3 And it works in $O(n \cdot d).$

### The Algorithm:

This algorithm extensively uses properties $1, 2, 3$ and $4,$ and also the rest in the background. All the vectors here belong to $\mathbb{Z}_2^d,$ so they are representable by a bitmask of length $d.$
Suppose at each step, we're taking an input vector $\vec{v_i}$ and we already have a basis of the previously taken vectors $\vec{v_1}, \vec{v_2}, \ldots, \vec{v_{i - 1}},$ and now we need to update the basis such that it can also represent the new vector $\vec{v_i}.$
In order to do that, we first need to check whether $\vec{v_i}$ is representable using our current basis or not.
If it is, then this basis is still enough and we don't need to do anything. But if it's not, then we just add this vector $vec{v_i}$ to the set of basis.
So the only difficuly that remains is, to efficiently check whether the new vector is representable by the basis or not. In order to facilitate this purpose, we use property $1$ to slightly modify any new vectors before inserting it in the basis, being careful not to break down the basis. This way, we can have more control over the form of our basis vectors. So here's the plan:
Let, $f(\vec{v})$ be the first position in the vector's binary representation, where the bit is set. We make sure that all the basis vectors each have a different $f$ value.
Here's how we do it. Initially, there are no vectors in the basis, so we're fine, there are no $f$ values to collide with each other. Now, suppose we're at the $i$'th step, and we're checking if vector $\vec{v_i}$ is representable by the basis or not. Since, all of our basis have a different $f$ value, take the one with the least $f$ value among them, let's call this basis vector $\vec{b_1}.$
If $f(\vec{v_i}) < f(\vec{b_1})$ then no matter how we take the linear combination, by property $2,$ no linear combination of the basis vectors' can have $1$ at position $f(\vec{v_i}).$ So, $\vec{v_i}$ will be a new basis vector, and since it's $f$ value is already different from the rest of the basis vectors, we can insert it into the set as it is and keep a record of it's $f$ value.
But, if $f(\vec{v_i}) == f(\vec{b_1}),$ then we must subtract $\vec{b_1}$ from $\vec{v_i}$ if we want to represent $\vec{v_i}$ as a linear combination of the basis vectors, since no other basis vector has bit $1$ at position $f(\vec{v_i}) = f(\vec{b_1}).$ So, we subtract $\vec{b_1}$ from $\vec{v_i}$ and move on to $\vec{b_2}.$
Note that, by changing the value of $\vec{v_i}$ we're not causing any problem according to property $1.$ $\vec{v_i}$ and $\vec{v_i} - \vec{b_1}$ is of same use to us. If in some later step we find out $\vec{v_i}$ is actually not representable by the current basis, we can still just insert it's changed value in the basis, since the set of vectors in the space representable by this new basis would've been the same if we inserted the original $\vec{v_i}$ instead.
If, after iterating through all the basis vector $\vec{b}$'s and subtracting them from $\vec{v_i}$ if needed, we still find out that $\vec{v_i}$ is not null vector, it means that the new changed $\vec{v_i}$ has a larger value of $f$ than all other basis vectors. So we have to insert it into the basis and keep a record of it's $f$ value.

Here's the implementation, the vectors being represented by bitmasks of length $d$:

int basis[d]; // basis[i] keeps the mask of the vector whose f value is i

int sz; // Current size of the basis

for (int i = 0; i < d; i++) {
if ((mask & 1 << i) == 0) continue; // continue if i != f(mask)

if (!basis[i]) { // If there is no basis vector with the i'th bit set, then insert this vector into the basis
++sz;

return;
}

mask ^= basis[i]; // Otherwise subtract the basis vector from this vector
}
}


Let's view some problems now:

### Problem 2a

Given a set $S$ of size $1 \le n \le 10^5$ with elements $0 \le a_i \lt 2^{20}.$ Find the number of distinct integers that can be represented using xor over the set of the given elements.

Solution

### Problem 2b

We have a graph of $2^{k}$ nodes numbered from $0$ to $2^{k} - 1,$ $1 \le k \le 30.$ Also, we're given $1 \le M \le 10^5$ integers $x_1, x_2, \ldots, x_M$ within the range $0 \le x_i \le 2^{k} - 1.$ In the graph, two vertices $u$ and $v$ are connected with an edge iff $u \oplus v = x_i$ for some $i.$ Find the number of connected components in the graph.
Link to the editorial and reference code

### Problem 3

Given a set $S$ of size $1 \le n \le 10^5$ with elements $0 \le a_i \lt 2^{20}.$ What is the maximum possible xor of the elements of some subset of $S?$

Solution

### Problem 4 (1st Hunger Games — S)

We have an empty set $S$ and we are to do $1 \le n \le 10^6$ queries on it. Let, $X$ denote the set of all possible xor-sums of elements from a subset of $S.$ There are two types of queries.
Type $1$: Insert an element $1 \le k \le 10^9$ to the set(If it's already in the set, do nothing)
Type $2$: Given $k,$ print the $k$'th hightest number from $X.$ It's guaranteed that $k \le \mid X \mid.$ Link to the source

Solution

### Problem 5 (Division 2 — F)

You're given an array $0 \le a_i \lt 2^{20}$ of length $1 \le n \le 10^5.$ You have to answer $1 \le q \le 10^5$ queries.
In each query you'll be given two integers $1 \le l \le n$ and $0 \le x \lt 2^{20}.$ Find the number of subsequences of the first $l$ elements of this array, modulo $10^9 + 7,$ such that their bitwise-xor sum is $x.$

Solution

### Problem 6 (Education Round — G)

You are given an array $0 \le a_i \le 10^9$ of $1 \le n \le 2 \cdot 10^5$ integers. You have to find the maximum number of segments this array can be partitioned into, such that -
1. Each element is contained in exactly one segment
2. Each segment contains at least one element
3. There doesn't exist a non-empty subset of segments such that bitwise-xor of the numbers from them is equal to $0$
Print $-1$ if no suitable partition exists.

Solution

## Conclusion

This is my first take on writing tutorial blogs on CF. I hope it'll be of use to the community.

I apologize for my terrible Linear Algebra knowledge. I would write this blog without using any of it if I could. I don't want to spread any misinformation. So please let me know in comments if you find any mistakes/wrong usage of notations.

I plan to write on Hungarian Algorithm next. There's just so many prerequisites to this algorithm. It'll be an enjoyable challenge to write about. I'd be glad if you can provide me some resource links in the comments to learn it from, though I already have quite a few.

## References:

• +424

By DrSwad, 15 months ago, ,

Hello Codeforces!

Since many of our users participate in MathMash contests after viewing the contest announcement in Codeforces, I thought I should also put this news here.

We're working on an update for the site. The design is ready. Now for the coding part, since I know how the site works under the hood I have to do most of it and organising the weekly contests alongside is making it really hard to do fast progress in the development. Preparing the problems, verifying their answers, setting up everything in the server, watching over the contest and finally writing the editorials take up 2 days at the least each week. It's also hard to keep focus in work with these regular intermissions. So I talked with the admins and we decided that it's better to give the contests a few weeks break and release the new site as soon as possible. We planned a lot of new features like monthly tournaments, reward system(where you get to exchange virtual points for real presents) and more. So I believe the wait is going to be totally worth it.

Meanwhile, to cover for the contests, we have added the "Problem of the day" section. We will update this page with a new problem everyday of varying difficulties and topics. Solving these problems will gain you reward points which you'll be able to use in the new site. A higher streak(the number of successive days you've managed to solve the problem of that day) will also give you higher reward points.

I hope you'd like this new section and have fun solving these daily challenges.

• +54

By DrSwad, 15 months ago, ,

Hello Codeforces!

I'm glad to announce that we will be having Round 37 of MathMash today at 17: 00 UTC. The round has been prepared by Snpushpita and DrSwad.

The round will consist of 8 problems, to be solved within 2 hours.

Points distribution for the problems are decided as 500-1000-1250-1500-2000-2500-2750-3000

We're inviting you all to join us in the contest. Hopefully we'll have a fun and successful round.

A few details about the contest:

• In order to participate in the contest, you need to register first. Kindly follow this link to do so. Registration deadline has been removed from the contests. So now, you can register at any time before the contest ends.

• I know this announcement is being placed in a coding website, but unfortunately using computer programs for MathMash contests is not allowed. We are trying to reward users' math skills with high ratings as there are not many sites that do this yet. We also try our best to set up the problems in such a way that any trivial brute force approach isn't supposed to work (for the mediocre/difficult problems).

• Time-penalty is applicable for the contest: Each problem is given an appropriate number of points, which will be visible when the round starts. Participants will gain that many points — the time penalty after successfully submitting to a particular problem. The later the problem submission occurs, the more points being deducted due to time penalty.

• The round is rated; which means that if you participate in the contest, your rating will be updated at the end of the round based on your rank in it. But you won't be considered as participating in the round if you don't submit any answer at all, even if you're registered for the contest.

• +24

By DrSwad, 15 months ago, ,

Hello Codeforces!

I'm glad to announce that we will be having Round 36 of MathMash today at 17: 00 UTC. The round has been prepared by Snpushpita and DrSwad.

The round will consist of 8 problems, to be solved within 2 hours.

Points distribution for the problems are decided as 500-750-1250-1500-1750-2250-2500-2500

We're inviting you all to join us in the contest. Hopefully we'll have a fun and successful round.

A few details about the contest:

• In order to participate in the contest, you need to register first. Kindly follow this link to do so. Registration deadline has been removed from the contests. So now, you can register at any time before the contest ends.

• I know this announcement is being placed in a coding website, but unfortunately using computer programs for MathMash contests is not allowed. We are trying to reward users' math skills with high ratings as there are not many sites that do this yet. We also try our best to set up the problems in such a way that any trivial brute force approach isn't supposed to work (for the mediocre/difficult problems).

• Time-penalty is applicable for the contest: Each problem is given an appropriate number of points, which will be visible when the round starts. Participants will gain that many points — the time penalty after successfully submitting to a particular problem. The later the problem submission occurs, the more points being deducted due to time penalty.

• The round is rated; which means that if you participate in the contest, your rating will be updated at the end of the round based on your rank in it. But you won't be considered as participating in the round if you don't submit any answer at all, even if you're registered for the contest.

• +33

By DrSwad, 16 months ago, ,

Hello Codeforces!

I'm glad to announce that we will be having Round 35 of MathMash today at 17: 00 UTC. The round has been prepared by Snpushpita and DrSwad.

The round will consist of 8 problems, to be solved within 2 hours.

Points distribution for the problems are decided as 500-750-1250-1500-2000-2250-2500-2750

We're inviting you all to join us in the contest. Hopefully we'll have a fun and successful round.

A few details about the contest:

• In order to participate in the contest, you need to register first. Kindly follow this link to do so. Registration deadline has been removed from the contests. So now, you can register at any time before the contest ends.

• I know this announcement is being placed in a coding website, but unfortunately using computer programs for MathMash contests is not allowed. We are trying to reward users' math skills with high ratings as there are not many sites that do this yet. We also try our best to set up the problems in such a way that any trivial brute force approach isn't supposed to work (for the mediocre/difficult problems).

• Time-penalty is applicable for the contest: Each problem is given an appropriate number of points, which will be visible when the round starts. Participants will gain that many points — the time penalty after successfully submitting to a particular problem. The later the problem submission occurs, the more points being deducted due to time penalty.

• The round is rated; which means that if you participate in the contest, your rating will be updated at the end of the round based on your rank in it. But you won't be considered as participating in the round if you don't submit any answer at all, even if you're registered for the contest.

• +22

By DrSwad, 16 months ago, ,

Hello Codeforces!

I'm glad to announce that we will be having Round 34 of MathMash today at 17: 00 UTC. The round has been prepared by Snpushpita and DrSwad.

The round will consist of 8 problems, to be solved within 2 hours.

Points distribution for the problems are decided as 500-750-1250-1500-2000-2500-2750-2750

We're inviting you all to join us in the contest. Hopefully we'll have a fun and successful round.

A few details about the contest:

• In order to participate in the contest, you need to register first. Kindly follow this link to do so. Registration deadline has been removed from the contests. So now, you can register at any time before the contest ends.

• I know this announcement is being placed in a coding website, but unfortunately using computer programs for MathMash contests is not allowed. We are trying to reward users' math skills with high ratings as there are not many sites that do this yet. We also try our best to set up the problems in such a way that any trivial brute force approach isn't supposed to work (for the mediocre/difficult problems).

• Time-penalty is applicable for the contest: Each problem is given an appropriate number of points, which will be visible when the round starts. Participants will gain that many points — the time penalty after successfully submitting to a particular problem. The later the problem submission occurs, the more points being deducted due to time penalty.

• The round is rated; which means that if you participate in the contest, your rating will be updated at the end of the round based on your rank in it. But you won't be considered as participating in the round if you don't submit any answer at all, even if you're registered for the contest.

• +19

By DrSwad, 16 months ago, ,

Hello Codeforces!

I'm glad to announce that we will be having Round 33 of MathMash today at 17: 00 UTC. The round has been prepared by Snpushpita and DrSwad.

The round will consist of 8 problems, to be solved within 2 hours.

Points distribution for the problems are decided as 500-750-1000-1500-2000-2750-3000-3000

We're inviting you all to join us in the contest. Hopefully we'll have a fun and successful round.

A few details about the contest:

• In order to participate in the contest, you need to register first. Kindly follow this link to do so. Registration deadline has been removed from the contests. So now, you can register at any time before the contest ends.

• I know this announcement is being placed in a coding website, but unfortunately using computer programs for MathMash contests is not allowed. We are trying to reward users' math skills with high ratings as there are not many sites that do this yet. We also try our best to set up the problems in such a way that any trivial brute force approach isn't supposed to work (for the mediocre/difficult problems).

• Time-penalty is applicable for the contest: Each problem is given an appropriate number of points, which will be visible when the round starts. Participants will gain that many points — the time penalty after successfully submitting to a particular problem. The later the problem submission occurs, the more points being deducted due to time penalty.

• The round is rated; which means that if you participate in the contest, your rating will be updated at the end of the round based on your rank in it. But you won't be considered as participating in the round if you don't submit any answer at all, even if you're registered for the contest.

• -4

By DrSwad, 16 months ago, ,

Hello Codeforces!

I'm glad to announce that we will be having Round 32 of MathMash today at 17: 00 UTC. The round has been prepared by Snpushpita and DrSwad.

The round will consist of 8 problems, to be solved within 2 hours.

Points distribution for the problems are decided as 500-750-1000-1750-2000-2500-3000-3000

We're inviting you all to join us in the contest. Hopefully we'll have a fun and successful round.

A few details about the contest:

• In order to participate in the contest, you need to register first. Kindly follow this link to do so. Registration deadline has been removed from the contests. So now, you can register at any time before the contest ends.

• I know this announcement is being placed in a coding website, but unfortunately using computer programs for MathMash contests is not allowed. We are trying to reward users' math skills with high ratings as there are not many sites that do this yet. We also try our best to set up the problems in such a way that any trivial brute force approach isn't supposed to work (for the mediocre/difficult problems).

• Time-penalty is applicable for the contest: Each problem is given an appropriate number of points, which will be visible when the round starts. Participants will gain that many points — the time penalty after successfully submitting to a particular problem. The later the problem submission occurs, the more points being deducted due to time penalty.

• The round is rated; which means that if you participate in the contest, your rating will be updated at the end of the round based on your rank in it. But you won't be considered as participating in the round if you don't submit any answer at all, even if you're registered for the contest.

• +20

By DrSwad, 16 months ago, ,

Hello Codeforces!

It's been long since I last had the fun of any serious programming(being all night awake with loud music on headphones and lots of snacks infront) due to admission studies. I'm missing it a lot. So after the exams are done I wish to improve MathMash a lot and also start a pet project of some sort. First thing that came to my mind is to build a small cute OJ. I'm aware that we have plenty of OJs already and they are more than enough helpful. So this project won't be of much use to anyone. But it'll be fun to design and build an entire OJ from scratch and also learn lots of new stuff along the way.

So I did a light research yesterday about what I might need to learn to build it. The first obvious thing needed is of course a way to execute submitted codes. I tried to go with the easiest option first: Using some third-party service/api so that I can give them the code and receive the output. But there doesn't seem to be any free option of this kind. Ideone used to provide a free api I guess, but now they use Sphere-Engine. And I found out Sphere-Engine costs roughly \$100+/month for their service. That's way too high for a non-profit pet project.

Another known option to me is to save the submitted code in a temp file in the server, execute it, and then return the result. But I read somewhere that it's not as easy as it sounds, as there are a lot of security concerns to be dealt with. And I don't have any knowledge about how to safely run a possibly malicious code.

I can also do something like what vjudge does, execute the problem in the respective sites and then scrape the submissions page to fetch the result. But it's kind of an unstable solution, as I'll have to update the whole process of scraping whenever the respective site updates their site structure.

I'm sure a lot of you have created an OJ or did some research on how to do so in the past. Can you kindly show me any idea on how to solve this problem? It'll be really helpful. Thanks in advance!

• +48

By DrSwad, 17 months ago, ,

Hello Codeforces!

I'm glad to announce that we will be having Round 31 of MathMash today at 17: 00 UTC. The round has been prepared by rah4927 and DrSwad.

The round will consist of 8 problems, to be solved within 2 hours.

Points distribution for the problems are decided as 500-750-1250-1500-2000-2000-2500-2750

We're inviting you all to join us in the contest. Hopefully we'll have a fun and successful round.

A few details about the contest:

• In order to participate in the contest, you need to register first. Kindly follow this link to do so. Registration deadline has been removed from the contests. So now, you can register at any time before the contest ends.

• I know this announcement is being placed in a coding website, but unfortunately using computer programs for MathMash contests is not allowed. We are trying to reward users' math skills with high ratings as there are not many sites that do this yet. We also try our best to set up the problems in such a way that any trivial brute force approach isn't supposed to work (for the mediocre/difficult problems).

• Time-penalty is applicable for the contest: Each problem is given an appropriate number of points, which will be visible when the round starts. Participants will gain that many points — the time penalty after successfully submitting to a particular problem. The later the problem submission occurs, the more points being deducted due to time penalty.

• The round is rated; which means that if you participate in the contest, your rating will be updated at the end of the round based on your rank in it. But you won't be considered as participating in the round if you don't submit any answer at all, even if you're registered for the contest.

• +17

By DrSwad, 17 months ago, ,

Hello Codeforces!

I'm glad to announce that we will be having Round 30 of MathMash today at 17: 00 UTC. The round has been prepared by Snpushpita and DrSwad.

The round will consist of 8 problems, to be solved within 2 hours.

Points distribution for the problems are decided as 500-750-1000-1500-2000-2000-3000-3000

We're inviting you all to join us in the contest. Hopefully we'll have a fun and successful round.

A few details about the contest:

• In order to participate in the contest, you need to register first. Kindly follow this link to do so. Registration deadline has been removed from the contests. So now, you can register at any time before the contest ends.

• I know this announcement is being placed in a coding website, but unfortunately using computer programs for MathMash contests is not allowed. We are trying to reward users' math skills with high ratings as there are not many sites that do this yet. We also try our best to set up the problems in such a way that any trivial brute force approach isn't supposed to work (for the mediocre/difficult problems).

• Time-penalty is applicable for the contest: Each problem is given an appropriate number of points, which will be visible when the round starts. Participants will gain that many points — the time penalty after successfully submitting to a particular problem. The later the problem submission occurs, the more points being deducted due to time penalty.

• The round is rated; which means that if you participate in the contest, your rating will be updated at the end of the round based on your rank in it. But you won't be considered as participating in the round if you don't submit any answer at all, even if you're registered for the contest.

• +8

By DrSwad, 17 months ago, ,

Hello Codeforces!

I'm glad to announce that we will be having Round 29 of MathMash today at 17: 00 UTC. The round has been prepared by Snpushpita and DrSwad.

The round will consist of 8 problems, to be solved within 2 hours.

Points distribution for the problems are decided as 500-750-1250-1500-2000-2250-3000-3000

We're inviting you all to join us in the contest. Hopefully we'll have a fun and successful round.

A few details about the contest:

• In order to participate in the contest, you need to register first. Kindly follow this link to do so. Registration deadline has been removed from the contests. So now, you can register at any time before the contest ends.

• I know this announcement is being placed in a coding website, but unfortunately using computer programs for MathMash contests is not allowed. We are trying to reward users' math skills with high ratings as there are not many sites that do this yet. We also try our best to set up the problems in such a way that any trivial brute force approach isn't supposed to work (for the mediocre/difficult problems).

• Time-penalty is applicable for the contest: Each problem is given an appropriate number of points, which will be visible when the round starts. Participants will gain that many points — the time penalty after successfully submitting to a particular problem. The later the problem submission occurs, the more points being deducted due to time penalty.

• The round is rated; which means that if you participate in the contest, your rating will be updated at the end of the round based on your rank in it. But you won't be considered as participating in the round if you don't submit any answer at all, even if you're registered for the contest.

• +23

By DrSwad, 17 months ago, ,

Hello Codeforces!

I'm glad to announce that we will be having Round 28 of MathMash today at 17: 00 UTC. The round has been prepared by Snpushpita and DrSwad.

The round will consist of 8 problems, to be solved within 2 hours.

Points distribution for the problems are decided as 500-750-1250-1250-1750-2000-2500-3000

We're inviting you all to join us in the contest. Hopefully we'll have a fun and successful round.

A few details about the contest:

• In order to participate in the contest, you need to register first. Kindly follow this link to do so. Registration deadline has been removed from the contests. So now, you can register at any time before the contest ends.

• I know this announcement is being placed in a coding website, but unfortunately using computer programs for MathMash contests is not allowed. We are trying to reward users' math skills with high ratings as there are not many sites that do this yet. We also try our best to set up the problems in such a way that any trivial brute force approach isn't supposed to work (for the mediocre/difficult problems).

• Time-penalty is applicable for the contest: Each problem is given an appropriate number of points, which will be visible when the round starts. Participants will gain that many points — the time penalty after successfully submitting to a particular problem. The later the problem submission occurs, the more points being deducted due to time penalty.

• The round is rated; which means that if you participate in the contest, your rating will be updated at the end of the round based on your rank in it. But you won't be considered as participating in the round if you don't submit any answer at all, even if you're registered for the contest.

• +9

By DrSwad, 18 months ago, ,

Hello Codeforces!

I'm glad to announce that we will be having Round 27 of MathMash today at 17: 00 UTC. The round has been prepared by Snpushpita and DrSwad.

The round will consist of 8 problems, to be solved within 2 hours.

Points distribution for the problems are decided as 500-750-1250-1750-2000-2250-2750-2750

We're inviting you all to join us in the contest. Hopefully we'll have a fun and successful round.

A few details about the contest:

• In order to participate in the contest, you need to register first. Kindly follow this link to do so. Registration deadline has been removed from the contests. So now, you can register at any time before the contest ends.

• I know this announcement is being placed in a coding website, but unfortunately using computer programs for MathMash contests is not allowed. We are trying to reward users' math skills with high ratings as there are not many sites that do this yet. We also try our best to set up the problems in such a way that any trivial brute force approach isn't supposed to work (for the mediocre/difficult problems).

• Time-penalty is applicable for the contest: Each problem is given an appropriate number of points, which will be visible when the round starts. Participants will gain that many points — the time penalty after successfully submitting to a particular problem. The later the problem submission occurs, the more points being deducted due to time penalty.

• The round is rated; which means that if you participate in the contest, your rating will be updated at the end of the round based on your rank in it. But you won't be considered as participating in the round if you don't submit any answer at all, even if you're registered for the contest.

• +10

By DrSwad, 18 months ago, ,

Hello Codeforces!

I'm glad to announce that we will be having Round 26 of MathMash today at 17: 00 UTC. The round has been prepared by Snpushpita and DrSwad.

The round will consist of 8 problems, to be solved within 2 hours.

Points distribution for the problems are decided as 500-750-1000-1500-2000-2500-3000-3500

We're inviting you all to join us in the contest. Hopefully we'll have a fun and successful round.

PS: We're redesigning and implementing a bunch of new features to MathMash. But none of my friends are much good at Illustration. So we would be really grateful to anyone with Illustration skills who would kindly be willing to collaborate with us. All of the team members are aspiring college students preparing for university admissions, so we can't really pay money in return for the works. But if you like our project and would like to be a part of it, you're most welcome to join us. Kindly PM me if you're interested.

A few details about the contest:

• In order to participate in the contest, you need to register first. Kindly follow this link to do so. Registration deadline has been removed from the contests. So now, you can register at any time before the contest ends.

• I know this announcement is being placed in a coding website, but unfortunately using computer programs for MathMash contests is not allowed. We are trying to reward users' math skills with high ratings as there are not many sites that do this yet. We also try our best to set up the problems in such a way that any trivial brute force approach isn't supposed to work (for the mediocre/difficult problems).

• Time-penalty is applicable for the contest: Each problem is given an appropriate number of points, which will be visible when the round starts. Participants will gain that many points — the time penalty after successfully submitting to a particular problem. The later the problem submission occurs, the more points being deducted due to time penalty.

• The round is rated; which means that if you participate in the contest, your rating will be updated at the end of the round based on your rank in it. But you won't be considered as participating in the round if you don't submit any answer at all, even if you're registered for the contest.

• +5

By DrSwad, 18 months ago, ,

Hello Codeforces!

I'm glad to announce that we will be having Round 25 of MathMash today at 17: 00 UTC. The round has been prepared by Snpushpita and DrSwad.

The round will consist of 8 problems, to be solved within 2 hours.

Points distribution for the problems will be added soon.

We're inviting you all to join us in the contest. Hopefully we'll have a fun and successful round.

A few details about the contest:

• In order to participate in the contest, you need to register first. Kindly follow this link to do so. Registration deadline has been removed from the contests. So now, you can register at any time before the contest ends.

• I know this announcement is being placed in a coding website, but unfortunately using computer programs for MathMash contests is not allowed. We are trying to reward users' math skills with high ratings as there are not many sites that do this yet. We also try our best to set up the problems in such a way that any trivial brute force approach isn't supposed to work (for the mediocre/difficult problems).

• Time-penalty is applicable for the contest: Each problem is given an appropriate number of points, which will be visible when the round starts. Participants will gain that many points — the time penalty after successfully submitting to a particular problem. The later the problem submission occurs, the more points being deducted due to time penalty.

• The round is rated; which means that if you participate in the contest, your rating will be updated at the end of the round based on your rank in it. But you won't be considered as participating in the round if you don't submit any answer at all, even if you're registered for the contest.

• +18

By DrSwad, 18 months ago, ,

Hello Codeforces!

I'm glad to announce that we will be having Round 24 of MathMash tomorrow at 17: 00 UTC. The round has been prepared by Snpushpita and DrSwad.

The round will consist of 8 problems, to be solved within 2 hours.

Points distribution for the problems are decided as 500-750-1000-1500-2000-2500-3000-3500

We're inviting you all to join us in the contest. Hopefully we'll have a fun and successful round.

A few details about the contest:

• In order to participate in the contest, you need to register first. Kindly follow this link to do so. Registration deadline has been removed from the contests. So now, you can register at any time before the contest ends.

• I know this announcement is being placed in a coding website, but unfortunately using computer programs for MathMash contests is not allowed. We are trying to reward users' math skills with high ratings as there are not many sites that do this yet. We also try our best to set up the problems in such a way that any trivial brute force approach isn't supposed to work (for the mediocre/difficult problems).

• Time-penalty is applicable for the contest: Each problem is given an appropriate number of points, which will be visible when the round starts. Participants will gain that many points — the time penalty after successfully submitting to a particular problem. The later the problem submission occurs, the more points being deducted due to time penalty.

• The round is rated; which means that if you participate in the contest, your rating will be updated at the end of the round based on your rank in it. But you won't be considered as participating in the round if you don't submit any answer at all, even if you're registered for the contest.

• +27

By DrSwad, 18 months ago, ,

Hello Codeforces!

I'm glad to announce that we will be having Round 23 of MathMash today at 16: 00 UTC. The round has been prepared by Snpushpita, DrSwad and neutron-byte.

The round will consist of 8 problems, to be solved within 2 hours.

Points distribution for the problems are decided as 500-750-1000-1250-1750-2250-3000-3500

We're inviting you all to join us in the contest. Hopefully we'll have a fun and successful round.

PS: We tried our best to avoid the quarter finals. Let me know if I should update the schedule. I'm hoping that the first match doesn't go to the Extra Time.

A few details about the contest:

• In order to participate in the contest, you need to register first. Kindly follow this link to do so. Registration deadline has been removed from the contests. So now, you can register at any time before the contest ends.

• I know this announcement is being placed in a coding website, but unfortunately using computer programs for MathMash contests is not allowed. We are trying to reward users' math skills with high ratings as there are not many sites that do this yet. We also try our best to set up the problems in such a way that any trivial brute force approach isn't supposed to work (for the mediocre/difficult problems).

• Time-penalty is applicable for the contest: Each problem is given an appropriate number of points, which will be visible when the round starts. Participants will gain that many points — the time penalty after successfully submitting to a particular problem. The later the problem submission occurs, the more points being deducted due to time penalty.

• The round is rated; which means that if you participate in the contest, your rating will be updated at the end of the round based on your rank in it. But you won't be considered as participating in the round if you don't submit any answer at all, even if you're registered for the contest.

• +20

By DrSwad, 19 months ago, ,

Hello Codeforces!

I'm glad to announce that we will be having Round 22 of MathMash today at 17: 00 UTC. The round has been prepared by NicolasCassia, DrSwad and Snpushpita.

The round will consist of 10 problems, to be solved within 2 hours.

Points distribution for the problems are decided as 500, 500, 750, 1250, 1300, 1500, 2000, 2500, 3000, 3500

We're inviting you all to join us in the contest. Hopefully we'll have a fun and successful round.

A few details about the contest:

• In order to participate in the contest, you need to register first. Kindly follow this link to do so. Registration deadline has been removed from the contests. So now, you can register at any time before the contest ends.

• I know this announcement is being placed in a coding website, but unfortunately using computer programs for MathMash contests is not allowed. We are trying to reward users' math skills with high ratings as there are not many sites that do this yet. We also try our best to set up the problems in such a way that any trivial brute force approach isn't supposed to work (for the mediocre/difficult problems).

• Time-penalty is applicable for the contest: Each problem is given an appropriate number of points, which will be visible when the round starts. Participants will gain that many points — the time penalty after successfully submitting to a particular problem. The later the problem submission occurs, the more points being deducted due to time penalty.

• The round is rated; which means that if you participate in the contest, your rating will be updated at the end of the round based on your rank in it. But you won't be considered as participating in the round if you don't submit any answer at all, even if you're registered for the contest.

• +20

By DrSwad, 19 months ago, ,

Hello Codeforces!

I'm glad to announce that we will be having Round 21 of MathMash today at 17: 00 UTC. The round has been prepared by Snpushpita, Joydip, thanicsamin, rah4920 and DrSwad.

The round will consist of 10 problems, to be solved within 2 hours.

Points distribution for the problems are decided as 500-750-1250-1500-1750-2000-2250-2500-2500-2750

We're inviting you all to join us in the contest. Hopefully we'll have a fun and successful round.

A few details about the contest:

• In order to participate in the contest, you need to register first. Kindly follow this link to do so. Registration deadline has been removed from the contests. So now, you can register at any time before the contest ends.

• I know this announcement is being placed in a coding website, but unfortunately using computer programs for MathMash contests is not allowed. We are trying to reward users' math skills with high ratings as there are not many sites that do this yet. We also try our best to set up the problems in such a way that any trivial brute force approach isn't supposed to work (for the mediocre/difficult problems).

• Time-penalty is applicable for the contest: Each problem is given an appropriate number of points, which will be visible when the round starts. Participants will gain that many points — the time penalty after successfully submitting to a particular problem. The later the problem submission occurs, the more points being deducted due to time penalty.

• The round is rated; which means that if you participate in the contest, your rating will be updated at the end of the round based on your rank in it. But you won't be considered as participating in the round if you don't submit any answer at all, even if you're registered for the contest.

• +10

By DrSwad, 19 months ago, ,

Hello Codeforces!

I'm glad to announce that we will be having Round 20 of MathMash today at 17: 00 UTC. The round has been prepared by Snpushpita, Joydip, thanicsamin, rah4920 and DrSwad.

The round will consist of 10 problems, to be solved within 2 hours.

Points distribution for the problems will be added soon.

We're inviting you all to join us in the contest. Hopefully we'll have a fun and successful round.

A few details about the contest:

• In order to participate in the contest, you need to register first. Kindly follow this link to do so. Registration deadline has been removed from the contests. So now, you can register at any time before the contest ends.

• I know this announcement is being placed in a coding website, but unfortunately using computer programs for MathMash contests is not allowed. We are trying to reward users' math skills with high ratings as there are not many sites that do this yet. We also try our best to set up the problems in such a way that any trivial brute force approach isn't supposed to work (for the mediocre/difficult problems).

• Time-penalty is applicable for the contest: Each problem is given an appropriate number of points, which will be visible when the round starts. Participants will gain that many points — the time penalty after successfully submitting to a particular problem. The later the problem submission occurs, the more points being deducted due to time penalty.

• The round is rated; which means that if you participate in the contest, your rating will be updated at the end of the round based on your rank in it. But you won't be considered as participating in the round if you don't submit any answer at all, even if you're registered for the contest.

• +23

By DrSwad, 19 months ago, ,

Hello Codeforces!

I'm glad to announce that we will be having Round 19 of MathMash today at 17: 15 UTC. The round has been prepared by Snpushpita, Joydip, thanicsamin, rah4920 and DrSwad.

The round will consist of 8 problems, as usual, to be solved within 2 hours.

Points distribution for the problems are decided as 750-750-1250-1500-1750-2500-2500-3000

We're inviting you all to join us in the contest. Hopefully we'll have a fun and successful round.

Update: The round has been postponed by 15 minutes as it appears that the Google Code Jam Distributed Round ends exactly at 17: 00 UTC.

A few details about the contest:

• In order to participate in the contest, you need to register first. Kindly follow this link to do so. Registration deadline has been removed from the contests. So now, you can register at any time before the contest ends.

• I know this announcement is being placed in a coding website, but unfortunately using computer programs for MathMash contests is not allowed. We are trying to reward users' math skills with high ratings as there are not many sites that do this yet. We also try our best to set up the problems in such a way that any trivial brute force approach isn't supposed to work (for the mediocre/difficult problems).

• Time-penalty is applicable for the contest: Each problem is given an appropriate number of points, which will be visible when the round starts. Participants will gain that many points — the time penalty after successfully submitting to a particular problem. The later the problem submission occurs, the more points being deducted due to time penalty.

• The round is rated; which means that if you participate in the contest, your rating will be updated at the end of the round based on your rank in it. But you won't be considered as participating in the round if you don't submit any answer at all, even if you're registered for the contest.

• +27

By DrSwad, 20 months ago, ,

Hello Codeforces!

I'm glad to announce that we will be having Round 18 of MathMash today at 17: 00 UTC. The round has been prepared by Golovanov399. Many thanks to him for his amazing efforts and hard works preparing everything for the round.

The round will consist of 10 problems, to be solved within 2 hours.

Points distribution for the problems are decided as 500-500-750-1000-1500-2000-2500-2500-3000-3000

We're inviting you all to join us in the contest. Hopefully we'll have a fun and successful round.

A few details about the contest:

• In order to participate in the contest, you need to register first. Kindly follow this link to do so. Registration deadline has been removed from the contests. So now, you can register at any time before the contest ends.

• I know this announcement is being placed in a coding website, but unfortunately using computer programs for MathMash contests is not allowed. We are trying to reward users' math skills with high ratings as there are not many sites that do this yet. We also try our best to set up the problems in such a way that any trivial brute force approach isn't supposed to work (for the mediocre/difficult problems).

• Time-penalty is applicable for the contest: Each problem is given an appropriate number of points, which will be visible when the round starts. Participants will gain that many points — the time penalty after successfully submitting to a particular problem. The later the problem submission occurs, the more points being deducted due to time penalty.

• The round is rated; which means that if you participate in the contest, your rating will be updated at the end of the round based on your rank in it. But you won't be considered as participating in the round if you don't submit any answer at all, even if you're registered for the contest.

• +31

By DrSwad, 20 months ago, ,

Hello Codeforces!

I'm glad to announce that we will be having Round 17 of MathMash tomorrow at 17: 00 UTC. The round has been prepared by Snpushpita, Joydip, thanicsamin, rah4920 and DrSwad.

The round will consist of 8 problems, as usual, to be solved within 2 hours.

Points distribution for the problems are decided as 500-1000-1250-1500-1750-2000-2500-3000

We're inviting you all to join us in the contest. Hopefully we'll have a fun and successful round.

A few details about the contest:

• In order to participate in the contest, you need to register first. Kindly follow this link to do so. Registration deadline has been removed from the contests. So now, you can register at any time before the contest ends.

• I know this announcement is being placed in a coding website, but unfortunately using computer programs for MathMash contests is not allowed. We are trying to reward users' math skills with high ratings as there are not many sites that do this yet. We also try our best to set up the problems in such a way that any trivial brute force approach isn't supposed to work (for the mediocre/difficult problems).

• Time-penalty is applicable for the contest: Each problem is given an appropriate number of points, which will be visible when the round starts. Participants will gain that many points — the time penalty after successfully submitting to a particular problem. The later the problem submission occurs, the more points being deducted due to time penalty.

• The round is rated; which means that if you participate in the contest, your rating will be updated at the end of the round based on your rank in it. But you won't be considered as participating in the round if you don't submit any answer at all, even if you're registered for the contest.

• +24

By DrSwad, 20 months ago, ,

Hello Codeforces!

I'm glad to announce that we will be having Round 16 of MathMash tomorrow at 17: 00 UTC. The round has been prepared by Snpushpita, Joydip, thanicsamin, rah4920 and DrSwad.

The round will consist of 8 problems, as usual, to be solved within 2 hours.

Points distribution for the problems are decided as 500-750-1250-1500-2000-2000-2500-3000

We're inviting you all to join us in the contest. Hopefully we'll have a fun and successful round.

A few details about the contest:

• In order to participate in the contest, you need to register first. Kindly follow this link to do so. Registration ends at 10 minutes after the start of the contest.

• I know this announcement is being placed in a coding website, but unfortunately using computer programs for MathMash contests is not allowed. We are trying to reward users' math skills with high ratings as there are not many sites that do this yet. We also try our best to set up the problems in such a way that any trivial brute force approach isn't supposed to work (for the mediocre/difficult problems).

• Time-penalty is applicable for the contest: Each problem is given an appropriate number of points, which will be visible when the round starts. Participants will gain that many points — the time penalty after successfully submitting to a particular problem. The later the problem submission occurs, the more points being deducted due to time penalty.

• The round is rated; which means that if you participate in the contest, your rating will be updated at the end of the round based on your rank in it. But you won't be considered as participating in the round if you don't submit any answer at all, even if you're registered for the contest.