Блог пользователя dholakpur_wala_raju

Автор dholakpur_wala_raju, история, 2 года назад, По-английски

A genuine question to all problem setters: why do most of the questions have $$$1$$$-based indexing and not $$$0$$$-based indexing (for instance, permutations, $$$[l,r]$$$ range queries, graph nodes are mostly $$$1$$$ to $$$n$$$ instead of $$$0$$$ to $$$n-1$$$. In my humble opinion, having $$$0$$$-based indexing just helps in writing a much cleaner code i.e. a slightly simplified implementation, like I can create an array of length $$$n$$$ instead of $$$n+1$$$, since computer uses $$$0$$$-based indexing and hence $$$1$$$-based indexing adds an unnecessary offset of $$$1$$$. This offset is most likely not the intention of the problem setter to judge the contestant on his/her problem-solving skills. However, I will mention that $$$1$$$-based indexing looks cleaner to human eyes but with respect to programming perspective, I really don't see any point other than missing it and getting an unnecessary WA.

  • Проголосовать: нравится
  • +73
  • Проголосовать: не нравится

»
2 года назад, скрыть # |
 
Проголосовать: нравится +42 Проголосовать: не нравится

I think it is easy to visualize when you are using 1 based index. if there are 5 element in an array we think it from 1 to 5 not from 0 to 4

»
2 года назад, скрыть # |
 
Проголосовать: нравится +37 Проголосовать: не нравится

1-based indexing is important because it helps create content for live commentators.

»
2 года назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

We all know that 1-based indexing is better but still use 0-based indexing

»
2 года назад, скрыть # |
 
Проголосовать: нравится +79 Проголосовать: не нравится

You pointed well the advantages 0-indexing and 1-indexing have (computer preference vs human readability).

In my opinion, 1-indexing is better in statements here on Codeforces because rather than making it difficult for a beginner to make the mental switch from 1 to 0 indexing that early on, we should just let the stronger contestants make sure to avoid having faulty implementations because of such an insignificant change. In addition, it would be weird to have Div2A-C use 1-indexing and then Div2D+ use 0-indexing.

However there are instances where it's explicitly better to use one or the other but this already comes with a bit of experience (for example, there is no point in using 2x memory and time with 1-indexed bitmasks just like there is no point in using 0-indexed prefix sums because of having to write unnecessary if statements to avoid dealing with line/column -1).

»
2 года назад, скрыть # |
 
Проголосовать: нравится -30 Проголосовать: не нравится

How about $$$-1$$$ indexing? I.e. first element has index $$$-1$$$, second is $$$0$$$, and so on. THe last element will have index $$$n - 2$$$ or $$$-2$$$ in python. Sounds cool, isn't it?

»
2 года назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

I think our brains are more familiar to 1-based indexing (it's easy to visualize) so people use them in statements. Additionally, it allows a spare element ($$$[0]$$$) that might help with cleaner implementations in some particular tasks (prefix sums and BITs for example) so people use them in their codes as well.

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Yeah most problem statements are usually given with 1-based indexing which is sorta annoying sometime. I have written a class inherited from vector for dealing with this issue.

template <typename Tp> class vect1 : public vector<Tp> {
public:
  using vector<Tp>::vector;
  Tp& operator[](size_t idx) {
    return this->at(idx - 1);
  }
};

It just makes things slightly less confusing in a lot of cases and makes the code more readable also.

It doesn't work with bool btw.

Usage
»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

If the numbers in a permutation or the nodes in a graph are from 1 to n, you can decrease each value by 1. 0-based indexing lets us have both choices.

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

building prefix sum is easier...