-is-this-fft-'s blog

By -is-this-fft-, history, 6 years ago, In English

Sometimes we see problems where a seemingly naive algorithm — for example simple brute force — is actually the correct solution. Mostly, I mean problems where, due to some clever observations, the complexity of the brute force algorithm is greatly reduced.

For example, in a recent contest we had 1168B - Good Triple. You can notice that any string of length at least 9 contains a "good triple", which means a brute force is sufficient here and runs in O(n).

Or 1028F - Make Symmetrical where you can notice that on any given circle, there are not too many lattice points.

Randomized input is also a good source of these. In 896C - Willem, Chtholly and Seniorious you can observe that after a bit of time, most adjacent elements of the array are equal and write something seemingly naive based on that.

What are some other examples of problems where a stupid brute force is actually the correct solution?

Full text and comments »

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

By -is-this-fft-, history, 6 years ago, In English

The Baltic Olympiad in Informatics will be held in Tartu, Estonia from April 27 to May 2. Both days of the contest will feature an online mirror contest. We invite you to take part.

Both online mirrors will start one hour after the corresponding onsite contests. Both contests last 5 hours.

Solutions will be accepted in the following programming languages: C++, Java and Python. We have separate time limits for C++/Java and Python. Tasks have IOI-style batched partial scoring. Problem statements will be available in English and a multitude of languages spoken in the participating countries.

Some links:

Let's discuss problems here after the contests!

Full text and comments »

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

By -is-this-fft-, history, 6 years ago, In English

Can someone else staying at this hotel please tell me how to turn off that light:

This is urgent, I need some sleep before the finals.

Full text and comments »

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

By -is-this-fft-, history, 6 years ago, In English

The Open Competition is an annual week-long competition for Estonian high school students which serves as the first contest of the season. This year, we are welcoming international participants as well. The contest started on 15 October, 10:00 EEST and lasts a week, ending at 22 October, 00:00 EEST.

The contest consists of 7 problems with scoring distribution 20-30-40-50-60-60-60. The problems will have partial scoring. The first five problems are "classical" problems of increasing difficulty, while the last two slots are reserved for output-only, interactive, out of scope, approximation, optimization — just in general "weird" problems. The problemset should be interesting for most Div. 2 participants.

Problem statements will be available in Estonian, English and Russian. However, to register, you will need to navigate through a bit of Estonian.

Please note that you might not appear on the scoreboard immediately after registering.

Full text and comments »

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

By -is-this-fft-, history, 7 years ago, In English

#define rep(i, l, r) for ((i) = (l); (i) < (r); (i)++)

Things like that are pretty common. Why do so many of you need to do things like this? What is wrong with a good old for-loop? Is it that slow to write one explicitly?

Full text and comments »

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

By -is-this-fft-, history, 7 years ago, In English

I tried to add a problem prepared in Polygon to a mashup contest. Instead of the problem however, the statement shows this wonderful piece of art:

What is going on?

Full text and comments »

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

By -is-this-fft-, history, 7 years ago, In English

To my (untrained) eye, it seems that Codeforces servers are unable to handle the traffic that comes with a regular Codeforces round. If this is indeed so, a possible solution to alleviate the server load would be to simply limit the number of participants in any given contest: only allowing a fixed number of people to register for the contest — first come, first serve. A limited-access contest is better than "no" contest at all.

Should Codeforces do this? Discuss.

(of course if the issues originate elsewhere then don't mind this)

Full text and comments »

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

By -is-this-fft-, history, 7 years ago, In English

Title says it all. What are some of your favourite problems in competitive programming?

Full text and comments »

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

By -is-this-fft-, history, 8 years ago, In English

I was hoping to see discussion on the problems, but the announcement seems to have disappeared.

EDIT: Back up!

Full text and comments »

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

By -is-this-fft-, history, 9 years ago, In English

I often, not that often, but still often see things like this while hacking:

#define MIN(a,b) (a) < (b) ? (a) : (b)
#define MAX(a,b) (a) > (b) ? (a) : (b)
#define ABS(a) (a) > 0 ? (a) : -(a)

While these are not as common as other (dubious) preprocessor macros, I still see these being used fairly commonly. There are, in my opinion, several downsides to using these -- if the inputs were functions, one of them gets executed twice.

So I want to ask, is there any advantage to using these over std::min(a, b) and others?

Full text and comments »

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