dalex's blog

By dalex, 11 months ago, In English

Recently one my friend got a TL verdict in some problem, and another my friend tried to help him to overcome it. Then I joined, got shocked by the results they got and we together stabilized the approach they came to.

By "deep recursion" we will mean a recursion with depth >= 100000. If it's less than 1000, this approach doesn't work at all, if it's between 1000 and 100000, most likely the speedup won't be so high so that will be decisive.

Let's consider this simple DFS function (it just counts the number of vertices):

private int dfs(int x, int p, List<Integer>[] g) {
    int result = 1;
    for (int y : g[x]) {
        if (y == p) {
            continue;
        }
        result += dfs(y, x, g);
    }
    return result;
}

generate a chain tree with 500000 vertices:

int n = 500000;
List<Integer>[] g = new List[n];
for (int i = 0; i < n; i++) {
    g[i] = new ArrayList<>();
}
for (int i = 1; i < n; i++) {
    int p = i - 1;
    g[i].add(p);
    g[p].add(i);
}

and run it:

long t1 = System.nanoTime();
int result = dfs(0, -1, g);
long t2 = System.nanoTime();
System.out.println("time = " + (t2 - t1) / 1.0e9 + " sec, result = " + result);

On my computer it runs 1.8 sec. Too slow for such a simple function, isn't it?

Let's speedup it. First, add two dummy parameters curDepth and maxDepth to DFS:

private int dfs(int x, int p, List<Integer>[] g, int curDepth, int maxDepth) {
    if (curDepth > maxDepth) {
        return 0;
    }
    int result = 1;
    for (int y : g[x]) {
        if (y == p) {
            continue;
        }
        result += dfs(y, x, g, curDepth + 1, maxDepth);
    }
    return result;
}

and then... OMG WTF

long t1 = System.nanoTime();
for (int i = 0; i < 100000; i++) {
    dfs(0, -1, g, 0, 0); // JIT please
}
int result = dfs(0, -1, g, 0, Integer.MAX_VALUE);
long t2 = System.nanoTime();
System.out.println("time = " + (t2 - t1) / 1.0e9 + " sec, result = " + result);

Now it works for 0.1 sec :)

When some method in Java is called too frequently, JIT optimizes it. It gets recompiled in runtime and on every new call the recompiled version will be called. However, the method cannot be recompiled while it is being executed. See this StackOverflow thread for more info. Maybe some Java expert can add something?

So in the first example, we enter into not optimized version of DFS and use it all the time. In the second example we do a lot of very short DFS calls, it for sure gets optimized, and finally we use optimized version to solve the actual problem.

Make sure the warming up does many calls but doesn't do many operations. In this example it's wise to do these fake DFS calls from a leaf and stop after the first recursive call.

Make sure all branches in your recursive function are actually run. It would be wrong to call dfs(0, -1, g, 0, -1) because the execution finishes quickly on if (curDepth > maxDepth), and the remaining code with iteration over adjacency list is not run and therefore is not optimized.

It doesn't work very well on Codeforces:

But it works just fine on Ideone:

and also works on:

  • Atcoder
  • CSES
  • Yandex.Contest in Java 8 compiler
  • ...

Maybe it's Windows/Linux or 32-bit/64-bit or OpenJDK/Oracle JDK differences, I haven't tested it yet.

Once more, it works only when recursion has depth >= 100000, and only on specific sites. But maybe it will help someone, and it is funny anyway.

Read more »

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

By dalex, history, 12 months ago, In English

Problem or Question?

Question is a short phrase, requiring a short answer. Examples of questions:

  • What's your name?
  • Where are you from?
  • What drinks do you prefer?

Some say interview questions are problems, but that's not correct, most of the interview questions are either short and require short answer...

  • How to compile a C++ source file?
  • What is the complexity of mergesort?
  • How add a file to a Docker image?

... or the interviewer may want to hear how you design a system with microservices and so on, which is can't be called a problem too.

Problem is something complicated but strict. You need to solve a problem a get a solution.

Problems exist not only in competitive programming, but also in math or physics competitions, in chess.

Examples of problems:

Why does one particular nation misuse the word "question"?

  • Their native language seems to have the same word for these concepts, and they don't care English does have different words.
  • Many of them get into competitive programming because of jobs, they got used to this "interview question" phrase, and as in their country technical interview is closely connected with competitive programming problems, they replace problems with questions.

What to do with contests?

I think the default word is to take part or to participate. My language allows the words play or write, they both make sense because contest is like a game, you compete (another good word) against other players, and you write code on contests.

The word give is wrong. When you say "give", you mean you no longer have something, and someone else receives this something from you. How are contests connected with it? No data.

People from the known country say they use the word "give" as they use it in the phrase "give an exam", which is wrong too and is surely related to their native language. You can pass or fail an exam or you can take an exam (note that "take" is literally the opposite word for "give")

Conclusion

I'm not a native speaker. But when someone says I'm wrong at something, I try to remember it and not to repeat the same mistake in the future. The most numerous nation on Codeforces don't. It is disrespectful.

Please don't use Indian English. It is ugly and contradictory.

Read more »

 
 
 
 
  • Vote: I like it
  • -137
  • Vote: I do not like it

By dalex, 17 months ago, In English

Hello everyone,

As you may know, ICPC movement has officially died in my university. It was a streak of 14 NEERCs in a row, with 3 WFs, but now it's over and it doesn't seem to recover in near future. Let's celebrate this event with Samara Farewell Contest, and don't forget to press F!

It is a collection of not-so-easy (still easy for nutellas) problems authored by dalex and craus throughout our ICPC career and then problemsetting career. Find the enter links on Opencup site on Sunday, January 3, 2021, 11:00 MSK.

We can discuss the problems here after the contest ends. I will also upload it to Codeforces Gyms, but a bit later.

Links:

Read more »

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

By dalex, 23 months ago, translation, In English

Hi all,

This year in our programming competition in Samara (link) there was also an experimental contest with a marathon problem. You could face these problems at Marathon 24, Deadline 24, Google Hash Code, and recently at ICPC Challenge. It turned out Codeforces supports these problems, and this post is a tutorial how to prepare them. If MikeMirzayanov don't mention it, I'll do it.

Contest link: 2020, XIII Samara Regional Intercollegiate Programming Contest (marathon problem)
The duration of the onsite contest was 4 hours, so you can participate virtually and compare your results with onsite results:

Best onsite scores

So, how to prepare such problems and contests? Actually it is very easy. These are the differences from the standard problems:

  • the problem should have only one test that should be uploaded somewhere in advance (for example, to gist.github.com). Then give participants the download link.
  • use function void quitp(double points, const std::string &message = "") or template<typename F> void quitp(F points, const char *format, ...) in checker.
  • don't output anything to stderr in checker (to be precise, don't output too much to stderr), for unknown reason it breaks the checker and it starts to always return 0 points. I don't know why this happens, but that's it.
  • change the contest type to IOI in the contest settings (by default it's ICPC).
  • it is impossible to set Text language in the contest settings, but luckily there is a magic language PHP, which works exactly like Text for such problems and just redirects the program code (your output) to stdout. You have to be sure that any possible output for the test fits into source limit.

Read more »

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

By dalex, 2 years ago, translation, In English
 
 
 
 
  • Vote: I like it
  • +51
  • Vote: I do not like it

By dalex, 3 years ago, translation, In English

Please put to main page. So we won't see blogs like https://codeforces.com/blog/entry/70236 in the nearest future.

In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.
In C++, comparator should return false if its arguments are equal.

Hope you remember it and will never make such a stupid mistake!

Read more »

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

By dalex, 3 years ago, translation, In English
 
 
 
 
  • Vote: I like it
  • +170
  • Vote: I do not like it

By dalex, history, 3 years ago, In English

Hi,

I was allowed to upload two contests from Petrozavodsk camps, Yandex Cups 2018 and 2019, into Codeforces Gyms:

These contests are mostly authored by Zlobober and ifsmirnov, with the help of some other people. Yandex Cup 2018 has more easier problems and less hard problems.

The 2018 one is also known as Grand Prix of Khamovniki (discussion on CF), the 2019 one was never published before.

Enjoy!

Read more »

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

By dalex, history, 3 years ago, In English
 
 
 
 
  • Vote: I like it
  • +44
  • Vote: I do not like it

By dalex, 4 years ago, In English

Hello!
I want to solve different contests to learn a new language (Kotlin), but I have a busy shedule (and cannot write regular contests in suitable time), so the only way for me is to train using virtual contests.
There is a great variety of contests on Codeforces (thanks to Mike!) and consequently it is not easy to decide which contests to solve.
I love random, but I have a better idea. Let's make the list of not anime-themed contests! But I need your help (in comments) to find them all...

Read more »

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

By dalex, 4 years ago, translation, In English
 
 
 
 
  • Vote: I like it
  • +88
  • Vote: I do not like it

By dalex, 4 years ago, In English

Qualification Round has ended, but no blog on Codeforces yet. What happened to my Codeforces?

Main page: https://hashcode.withgoogle.com/

Judge system: https://hashcodejudge.withgoogle.com/

Our points: 10 / 176877 / 15824126 / 11808094 / 21465945, total score 49275052, 55th place.

How did you solve all the subtasks? I'm most interested in C and D.

Read more »

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

By dalex, 5 years ago, translation, In English

Some weeks ago I read a Quora answer by I_love_Tanya_Romanova (link). The 4th paragraph attracted me, here is it's short content:

There are jokes about these typical problem statements: “Little Rohit got an array as a birthday present”. I’m also not getting why these trashy statements should be writtten instead of formal model of the task. It is awesome to have fictional statement when it makes sense, or when it comes from real life; it is at least funny to have stuff like problems I mentioned above. And I know that some of the platforms I mentioned are requiring problems with fictional statements and say that formal models are bad. Well, OK, “Parents asked little Chandan to perform following operations…”. May I go to some other site and solve normal problems, please? That’s a matter of taste — but for me this kind of statements is something that makes strong negative impression, and I think I’m not the only one.

I also don't like statements where characters were added just because there were no characters originally. You read such statement and think: "Why do they added this Alice with her birthday present? It has nothing to do with the problem".

I think there must be some rules that authors should use when they write a problem statement:

  1. If the problem comes from real life or from some situation that may appear in real life / fiction book / computer game — use the original statement. Those who will solve this problem will be clearly understand what's going on.
  2. If the problem originally had the formal statement (e.g. you have an array and you have to answer some queries, you have an array and you have to find a subarray with maximal xor / and / or, and so on): use formal statement.
  3. Never introduce a setting if the problem originally had formal statement.

Read more »

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

By dalex, history, 5 years ago, In English

I've just met a comment with a link to a problem statement. There was such text in the statement:

Soon the professor realized that reconstructing Anatoly’s code and the test tree from his output was not a simple task and that the result might be ambiguous. You will have to help her find all possible reconstructions of Anatoly’s code.

Don't you see something weird here? I think it should be:

Soon the professor realized that reconstructing Anatoly’s code and the test tree from his output was not a simple task and that the result might be ambiguous. You will have to help him find all possible reconstructions of Anatoly’s code.

or:

Soon the professor realized that reconstructing Anatoly’s code and the test tree from his output was not a simple task and that the result might be ambiguous. You will have to help them find all possible reconstructions of Anatoly’s code.

I know that people either use the gender that is more common for a person, e.g. he for drivers and she for nurses, or just use they (my English teacher said they is correct). I've wandered across Wikipedia (here is one of the links: https://en.wikipedia.org/wiki/English_personal_pronouns#Use_of_he.2C_she_and_it), but haven't found anything about preferrable usage of female pronouns.

However, I've read really a lot of English statements, and everywhere the female pronouns are used! For children and professors, for drivers and miners, for rabbits and foxes, for everything and everyone. Why?

Read more »

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

By dalex, 5 years ago, translation, In English

Hello everyone,

Some days ago there was an annual programming contest in Samara University, and yet again we copy it into Codeforces Gyms. The gym contest takes place on Saturday, 8 April, at 9:30 MSK. Site clist.by says that there are no intersections with something important that day.

Second time in a row it is a personal contest. So we ask everyone to participate solo. It must be very interesting for yellow and lower guys, and, who knows, maybe for reds too. You can start virtual participation at any time.

And as usual,

Read more »

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

By dalex, 6 years ago, translation, In English
 
 
 
 
  • Vote: I like it
  • +147
  • Vote: I do not like it

By dalex, 6 years ago, translation, In English

Hello everyone,

Some days ago we had an annual programming contest in Samara, and yet again we copy it into Codeforces Gyms. The gym contest takes place on Sunday, 17 April, at 11:00 MSK. Site clist.by says that there are no intersections with something important that day.

Previously, it was a team contest, but this year we decided to make it personal. So we ask everyone to participate solo. This is how the results will be the most adequate.

And as usual,

Read more »

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

By dalex, 7 years ago, translation, In English

Hi all!

On September 13, a qualification contest for ACM ICPC was held in Samara SAU. We always put our contests to Codeforces Gyms, so this Saturday, November 14, 11.00 MSK everyone will be able to enjoy it.

The contest will be held at Codeforces Gyms, it will be unrated and will last for 5 hours. The problems were prepared by craus and Shlakoblock.

And here is the full list of our previous contests:

Read more »

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

By dalex, history, 7 years ago, In English

What's going on here? This contest was held two years ago. Just look at its id: it is 100187. Someone has managed to change its start date (and also to make it invisible for everyone but the author, which is fixed now), but how is it possible? Any permission settings? What if I go and reschedule all the contests in the gym? What if I hide them all? It must be a bug, admins, look into it, please.

P.S. Don't participate if you remember the problems.

UPD. Looks like gym vandals continue their work:

Read more »

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