When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

gepardo's blog

By gepardo, history, 14 months ago, In English

Do you believe this is impossible? It's really not, because some people do it. See yourself:

1775D - Friendly Spiders: 188718250 188731749 188739534

1775F - Laboratory on Pluto: 188742718 188744106 188756319

Writing source code directly in assembly language may make your code faster, as you can write the CPU instructions directly, making some critical optimization faster than the compiler-generated code.

Of course, the statement above about speed is false, and sometimes it's hard to write a faster code than the compiler generates. And, as you can see, the submissions just contain the code generated by the compiler instead of being written manually.

So, why do you think people may want to do this on contests?

Full text and comments »

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

By gepardo, history, 2 years ago, translation, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Full text and comments »

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

By gepardo, history, 3 years ago, In English

Hello everyone :)

We are happy to announce that XXI Open Cup, GP of Belarus will take place on February 14, 2021 at 11:00 MSK.

The authors of the problems are gepardo, kimden, Mediocrity, 244mhq, Wind_Eagle, and PuRpLe_FoReVeR. Also greencis, aleex, RED_INSIDE, programmer228, mrboorger, Chmel_Tolstiy, and gosuto took part in preparing the contest.

This contest was in Petrozavodsk, so if you have been there and have seen the problems, do not solve it now.

Links: Div. 1, Div. 2. You need an Open Cup login to participate.

You can discuss the contest here after it's over.

Good luck everyone and I hope you'll enjoy the problems!

UPD: Editorial

UPD 2: The contest is added to gym now.

Full text and comments »

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

By gepardo, history, 3 years ago, translation, In English

1420A - Cubes Sorting

Hint
Solution
Code in C++ (Wind_Eagle)

1420B - Rock and Lever

Hint
Solution
Code in C++ (Wind_Eagle)

1420C1 - Pokémon Army (easy version)

Hint
Solution
Code in C++ (gepardo)

1420C2 - Pokémon Army (hard version)

Hint
Solution
Code in Java (gepardo)
Code in C++ (Wind_Eagle)

1420D - Rescue Nibel!

Hint
Solution
Code in Java (gepardo)

1420E - Battle Lemmings

Hint 1
Hint 2
Hint 3
Solution
Code in C++ (gepardo)

Full text and comments »

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

By gepardo, history, 5 years ago, In English

Hello, Codeforces!

If you tried to prepare some competitive programming problems, you might parse parameters like this:

#include "testlib.h"
#include <cstdlib>

using namespace std;

int main(int argc, char **argv) {
  registerGen(argc, argv, 1);
  int n = atoi(argv[1]);
  int m = atoi(argv[2]);
  int k = atoi(argv[3]);
  ...

Of course, such way has many disadvantages:

  • You need to pass the exact amount of parameters, you cannot define default values for them.
  • If you have many parameters, it's easy to forget the order.
  • If you pass too few of the them, it will be undefined behavior.

So I developed a library called ParmPars to pass parameters to generators in a more convenient way. You can find it on GitHub. I hope it will help you to generate tests better.

Full text and comments »

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

By gepardo, history, 6 years ago, In English

Hello, Codeforces!

I think many of you know about Mo's algorithm. For those, who don't know, please read this blog.

Here, I consider an alternative (and faster) approach of sorting queries in Mo's algorithm.

Table of contents

 

Full text and comments »

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

By gepardo, history, 6 years ago, In English

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?

Full text and comments »

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

By gepardo, history, 6 years ago, translation, In English

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

Full text and comments »

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

By gepardo, history, 6 years ago, In English

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?

Full text and comments »

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

By gepardo, history, 6 years ago, translation, In English

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:

Codeforces Round 379 (Div. 2) : link

Codeforces Round 404 (Div. 2) : link

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

Full text and comments »

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

By gepardo, history, 7 years ago, translation, In English

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

Alternative solution from Vladik:

C++ code

Alternative solution from netman:

Java code

Full text and comments »

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

By gepardo, history, 7 years ago, translation, In English

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 (dmitriyklebanov) 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. 1

  1. uwi
  2. rajat1603
  3. SaSa
  4. mr.banana
  5. Kaban-5

Div. 2

  1. CommonAnts
  2. Gauss
  3. binsjl
  4. hotwater
  5. mister_dudec

Thanks everyone for participating :)

Full text and comments »

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

By gepardo, 7 years ago, translation, In English

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.

Bugs

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.

Full text and comments »

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

By gepardo, history, 7 years ago, translation, In English

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

Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code

Full text and comments »

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

By gepardo, history, 7 years ago, translation, In English

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 (gepardo) 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

  1. Octotentacle

  2. CisnijAsdPawel

  3. VemMonstro13

  4. fulvioabrahao

  5. Mehrdad_S

Div. 1

  1. sugim48

  2. uwi

  3. khadaev

  4. HellKitsune

  5. Um_nik

Full text and comments »

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