### gepardo's blog

By gepardo, history, 2 days ago, ,

Hello, Codeforces!

Some time ago I created a blog post about Sqrt-tree. If you didn't read this post, please do it now.

But earlier, we were able just to answer the queries on a static array. Now we will make our structure more "dynamic" and add update queries there.

So, let's begin!

# Update queries

Consider a query that does the assignment ax = val. We need to perform this query fast enough.

## Naive approach

First, let's take a look of what is changed in our tree when a single element changes. Consider a tree node with length l and its arrays: , and . It is easy to see that only elements from and will change (only inside the block with the changed element). will change O(l) elements. Therefore, total update count per node is O(l).

We remember that any element x is present in exactly one tree node at each layer. Root node (layer 0) has length O(n), nodes on layer 1 have length , nodes on layer 2 have length , etc. So the time complexity per update is .

But it's too slow. Can it be done faster?

•
• +93
•

By gepardo, history, 3 months ago, translation, ,

Hello, Codeforces!

When we talk the languages with built-in big integer implementation, usually such languages as Java or Python are mentioned. Now I'll tell you about long arithmetic implementation in Pascal (more precisely, in the Free Pascal Compiler).

The simplest code, which reads two big integers and outputs their sum, looks like this:

Code

gmp unit contains all the classes and operators to work with big integers.

How does it work? This unit contains bindings for GNU Multiprecision Library. The program and the library are linked dynamically, so, to make the program work this library is required to install. Luckily, many Linux distros install libgmp by default and so this trick can be used in the testing systems like ejudge or Yandex.Contest. Testing systems on Windows don't have this library, so this thing won't work.

For convenience the unit implements an object-oriented wrapper for libgmp functions, for which all the operators are overloaded (yes, Free Pascal supports operator overloading!)

What is also remarkable, libgmp has implementation for calculating fast integer square root. So here is a short implementation for problem F for elimination to Moscow Open Olympiad (the website by the link is in Russian and , unfortunately, I cannot find the English version of the statements).

Code

•
• +89
•

By gepardo, history, 3 months ago, ,

Hello, Codeforces!

Some time ago I invented an interesting data structure and I'd like to share it with the community. Maybe, it was known before, and if you knew about it before my blog post, please share the link to the source.

# What can the data structure do?

Given an array a that contains n elements and the operation op that satisfies associative property: (x op y)op z = x op(y op z) is true for every x, y and z.

So, such operations as gcd, min, max, sum, multiplication, and, or, xor, etc. satisfy these conditions.

Also we have some queries l, r. For each query, we need to find al op al + 1 op ... op ar. Let's call such queries q(l, r).

My data structure can process such queries in O(1) time with preprocessing time and memory.

# How it works?

•
• +303
•

By gepardo, history, 5 months ago, translation, ,

Hello, Codeforces!

If would be nice if all the materials of Codeforces contests were publicly available and there was possibility to download the archives. There may be some reasons for it:

• It's easier to hold trainings. There can be different problems on trainings and it can be good to collect them in one contest on one testing system. If the tests are open, it can make holding trainings in this way highly easier.

• More availability. If the site is down or gone offline for some time, contest materials may remain and there will be a possibility to test problems locally.

• More safety for problems. Problem materials will be stored not only on Codeforces. If some problems will be lost on servers for some reason, it will be easier to restore them.

There can be a counterargument against opening the tests that not experienced users will download tests instead of finding bugs themselves. But 1) small tests are already open and 2) the access may be given only for users that have coach mode.

Such idea was proposed earlier, here is a blog post от MikeMirzayanov about this. But, as it appears, progress on this question has stopped.

It will be better if MikeMirzayanov opened the materials. I am waiting for his response to this blog post. But I want to open the materials of my contests without waiting for his decision:

Here is another blog post by Arpa, where you can find the materials of Codeforces Round #383 (Div. 1).

•
• +73
•

By gepardo, history, 13 months ago, translation, ,

This is an editorial for the problems of the today's contest. I tried my best to describe the solutions for the problems as detailed as possible, but if something is not understandable for you, you can write in comments! :)

785A - Anton and Polyhedrons

Hint
Tutorial
C++ code
Java code
Python code

785B - Anton and Classes

Hint
Tutorial
C++ code
Java code
Python code

785C - Anton and Fairy Tale

This problem had weak pretests. It was made intentionally to cause more hacks. And I have warned you about it in the announcement :)

Hint
Tutorial
C++ code
Java code
Python code

785D - Anton and School - 2

Hint
Tutorial
C++ code
Java code

785E - Anton and Permutation

I'm sorry that this problem was not original. I will try my best to prevent this from happening again.

If you have TL or ML in this problem, don't think that the time/memory limits are too strict. The model solution works in 1.2 seconds and consumes 9 MB memory.

Hint
Tutorial
C++ code
Java code

C++ code

Alternative solution from netman:

Java code

•
• +186
•

By gepardo, history, 13 months ago, translation, ,

Hello, Codeforces!

Tomorrow, in March 15, 2017 at 18:05 MSK a regular rated Codeforces round for participants from the second division will take place. As usual, participants from the first division can take part out of competition. It's my second contest and I hope you'll like it more than my previous one.

As usual, there will be five problems on the contest and two hours to solve them. I advice you to read all the problems' statements attentively. Also check all your solutions for correctness even if they passed all the pretests. Verdict Pretests passed doesn't mean that the solution is completely correct! I wish you to enjoy the contest and learn something new solving the problems.

Like in the last time, the problems will be about Anton and his friends.

Great thanks to Alexey Vistyazh (netman) for help in preparing the contest, Vladislav Vishnevsky (Vladik) for testing the round, Dmitry Klebanov (dakdima) for reading the statements carefully, and of course, Mike Mirzayanov (MikeMirzayanov) for the great platforms Codeforces and Polygon.

Scoring distribution is 500 — 1000 — 1500 — 2250 — 2500.

UPD. The contest is over, system testing has already started, the editorial will appear soon.

UPD2. Editorial has arrived.

UPD3. Congratulations to the winners of the contest!

# Div. 2

Thanks everyone for participating :)

•
• +222
•

By gepardo, 13 months ago, translation, ,

Good afternoon! Today I watched submissions from old contests and found a bug on Codeforces: when you try to see a hacked submission, you'll get an error.

24292787

22241174

22235511

To see the error, you must be logged in on the site. If you are not logged in, the error doesn't appear.

In connection with this, I have a question: is there a bugtracker on Codeforces? If there is a bugtracker, it'd be good to give a link to it where anyone can see it. So, bugs that are not fixed, for example, like this or this won't get lost.

UPD: It seems that the bug is fixed.

•
• +35
•

By gepardo, history, 17 months ago, translation, ,

Tutorial for the tasks of the contest. If something isn't clear, you can write in comments :)

Code
Code
Code
Code
Code
Code

•
• +82
•

By gepardo, history, 17 months ago, translation, ,

Hello, Codeforces!

Tomorrow, in November 15, 2016 at 19:35 MSK a regular Codeforces round for participants in the second division will be held. As usual, participants from the first division can take part out of competition.

I (alex256) am the author of the contest. It's my first round and I hope it won't be the last. Great thanks to Gleb Evstropov (GlebsHP) for help in preparing the contest, Andrey Kalendarov (Andreikkaa) for testing the round and Mike Mirzayanov (MikeMirzayanov) for the great platforms Codeforces and Polygon.

As usual, the participants will be given 6 problems and two hours to solve them. I recommend to read ALL the problems. I wish everyone many Accepted and, of course, enjoy solving the problems.

The problems will be about my younger brother Anton. I hope you'll like them :)

The round is rated.

UPD: Though, the round won't be completely usual and there will be 6 problems.

UPD2: The scoring is 500-750-1250-1500-2000-2750.

UPD3: Tutorial is available now.

UPD4: Contest is over, congrats to winners :)

Div. 2

Div. 1