InternetPerson10's blog

By InternetPerson10, history, 10 months ago, In English

There are many problem statements on Codeforces, especially in recent rounds, that use some variation on one of the following lines:

You are given a permutation of length n.

A permutation is an array of length n, consisting of each of the integers from 1 to n in some order.

If we take the dictionary definition of the word "permutation", this doesn't make sense. Strictly speaking, a permutation refers to an arrangement of some objects. Using the term by itself is meaningless, unless we define some set whose elements we can permute.

I'm not saying that we shouldn't be using the word "permutation" in this context. In fact, each of the following would be a semantically valid way to describe such a situation:

  • You are given a permutation of the integers from $$$1$$$ to $$$n$$$.
  • At least how many operations should be performed until the array becomes a permutation of $$$[1, 2, ..., n]$$$?
  • You are given an array of length $$$n$$$, consisting of each of the integers from $$$1$$$ to $$$n$$$ in some order.

The last one doesn't even require the use of the word "permutation"! If we only need to define such an array once, that would be the best option. There's no need to define the term "permutation" anymore.

Even the following would be valid:

  • A permutation of $$$[1, 2, ..., n]$$$ is an array of length $$$n$$$, consisting of each of the integers from $$$1$$$ to $$$n$$$ in some order.

The important part is defining what we are permuting here, and in most problems on Codeforces, mentioning the integers from $$$1$$$ to $$$n$$$ suffices.

I am aware that in competitive programming problems, calling such arrays "permutations" would be understood by a large majority of the community. I'll admit that in my experience, this does make statements easier to understand and solution discussions flow faster, so long as everyone involved knows what it actually refers to. But that last clause is important, and may confuse someone who sees the term in this context for the first time. It definitely ticked me off the first time I saw it, and it irks me that people look at an array of integers and call it a "permutation" without context.

Since when was the term "permutation" used like this? Is this usage prevalent outside the competitive programming community?

Thank you so much for reading.

Full text and comments »

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

By InternetPerson10, history, 2 years ago, In English

It seems AtCoder is going to implement a new system where you choose if your participation in a contest is rated or unrated before you get to see the problems. Here are the full details from the site:

We developed a new system where one can choose Rated or Unrated participation in contests. We will introduce this system from ABC230 on 3rd Dec.

When registering for a rated contest, you can decide whether you want to be Rated or Unrated in advance. You can choose an option before the contest starts or in the first five minutes of the contest. If you choose Rated, your rating will be updated whether or not you open problems or make submissions.

In a rated contest, you can open problems only after you choose Rated or Unrated participation. If you don't choose an option and five minutes have passed after the contest starts, you are considered Unrated. Also, if your rating doesn't fall within the rated range of the contest, you are automatically regarded as Unrated.

We recommend you choose an option in the following way:

Rated: We encourage you to choose this option in general. Even if it's the first time you take part in a contest, we recommend this.

Unrated: If you don't expect your typical performance for some reason but still want to see the problems and solve them, use this option.

Before a contest starts, you can switch Rated/Unrated by first canceling your registration and then registering for the contest again. Note that, after the contest starts, you can't cancel your registration even if it's the first five minutes of the contest, and thus you cannot change the option.

I remember a few blogs being posted a while back, proposing a rule similar to this one to be implemented — I can't find any of them now though. I think the main reason this rule was implemented was so that people who planned on joining, but decided not to due to fear of a negative delta, will be included in rating calculation (please correct me here if I am wrong). There were multiple possible effects discussed, such as

  • People may miss the contest due to reasons beyond their control, giving them a huge loss of rating. I think this is addressed by the five minute grace period rule — people who may expect some problems in their current situation may choose to hold off on registration, and decide within the first five minutes of the contest if they are able to compete. This is enough time to accommodate people slightly late, who will not get a significant disadvantage by the loss of time had they joined the contest under "normal" rules.

  • People who make alt accounts can look at the problems beforehand using one account, and solve using another one. I don't think this will affect the standings much, as I feel five minutes is not enough to make a significant difference.

  • The number of people joining the contest will decrease. I feel like this will happen, due to possible confusion over the new system, and because of the way AtCoder calculates penalties based on the final submission instead of across all submissions, though I'm not too sure.

I'm really interested as to how this will go, and what effects the new change will have on the number of people joining, or how someone's average performance will change (or not change).

What are people's thoughts on this? Should Codeforces implement a similar rule to this also?

Full text and comments »

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