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

0-based indexing vs 1-based indexing
Автор dholakpur_wala_raju, история, 11 месяцев назад, По-английски

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
  • Проголосовать: не нравится

»
11 месяцев назад, # |
  Проголосовать: нравится +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

→ Ответить
  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    → Ответить
»
11 месяцев назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

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

→ Ответить
»
11 месяцев назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

→ Ответить
»
11 месяцев назад, # |
  Проголосовать: нравится +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).

→ Ответить
»
11 месяцев назад, # |
  Проголосовать: нравится -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?

→ Ответить
»
11 месяцев назад, # |
← 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.

→ Ответить
»
11 месяцев назад, # |
  Проголосовать: нравится 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
→ Ответить
  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Is this serious?

    → Ответить
  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      11 месяцев назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
»
11 месяцев назад, # |
  Проголосовать: нравится 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.

→ Ответить
»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

building prefix sum is easier...

→ Ответить