dholakpur_wala_raju's blog

0-based indexing vs 1-based indexing
By dholakpur_wala_raju, history, 11 months ago, In English

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.

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

»
11 months ago, # |
  Vote: I like it +42 Vote: I do not like it

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

→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yeah I agree, when I think of sequences and stuff it makes sense to start counting from 1 rather than 0, as it makes more sense to say first rather than 0th.

    → Reply
»
11 months ago, # |
  Vote: I like it +37 Vote: I do not like it

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

→ Reply
»
11 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
11 months ago, # |
  Vote: I like it +79 Vote: I do not like it

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).

→ Reply
»
11 months ago, # |
  Vote: I like it -30 Vote: I do not like it

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?

→ Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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
→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is this serious?

    → Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Is the usage of at intended? It leads to bounds checking for every access, which is quite wasteful in a competitive programming context. You might want (*this)[idx - 1] instead.

    → Reply
    • »
      »
      »
      11 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks, I did not know about the bound checking thing, but it seems to be a good idea.

      Perhaps it might be a better idea to use some #ifdef stuffs and use at only for local execution and use []operator otherwise. That might help with debugging as well as fasten execution while judging.

      Edit :

      I was just trying with (*this)[idx - 1] and got the following error.

      b4.cpp:29:30: warning: all paths through this function will call itself [-Winfinite-recursion]
  Tp& operator[](size_t idx) {
                             ^
b4.cpp:59:10: note: in instantiation of member function 'vect1<long long>::operator[]' requested here
    ump[a[i]] = i;
         ^
1 warning generated.

      So it can cause an infinite recursion. Now I remember why I used at in the first place.

      → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

building prefix sum is easier...

→ Reply