sonjoydabnath's blog

Accessing Negative Index of Array Without RTE!
By sonjoydabnath, 9 years ago, In English

While looking for how other people solved the problem I see a solution (1620364) of 182D - Common Divisors by RAD . In this solution He tried to initialize and access a negative index of a Array! I 've always known that it's not possible. Can anybody explain me how he did this or, how negative index working on an Array ?

A significant part of RAD's code: 


void calc_hash(const string &s, int64 *&h) {
    h = new int64[110000] + 1;
    h[-1] = 0; //initiating a negative index with a value of 0!!
    forn(i, s.size())
        h[i] = h[i - 1] * 313 + s[i];
}

.........    ......
.... .           ...
//code snippet from the main function
int ans = 0;
for (int len = min((int)s1.size(), (int)s2.size()); len >= 1; len--) 
    if (s1.size() % len == 0 && s2.size() % len == 0) {
        int64 ha = h1[len - 1];
            for (int i = len - 1; i < (int)s1.size(); i += len)
                if (h1[i] - h1[i - len] * pw[len] != ha) //here i-len sometimes could be negative,  
                    goto bad;                            //but it's Not giving RTE :O
            for (int i = len - 1; i < (int)s2.size(); i += len)
                if (h2[i] - h2[i - len] * pw[len] != ha)
                    goto bad;
            ans++;
            bad:;
    }
cout << ans << endl;
  • Vote: I like it
  • +11
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Ehhhh... Did you see the line above that h[ - 1]?

In C++ tab[5] is changed by compiler to reference to value at address tab + 5 and that is why you can also write 5[tab] and that is why h[ - 1] is reference to value at address h - 1 and since h = newint64[110000] + 1; we get h - 1 = h = newint64[110000] which is perfectly valid.

Personally, I hate 0-based indexing and that example is main reason why — because 1-based indexing allows us to set some guards at position 0. I can't understand how 0-based indexing lovers write their dp where for example dp[i] = 2·dp[i - 1] + 5 holds, but they can't use that formula for i = 0 >_>...

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sorry! tab is not clear to me ? did you mean 1 tab = 4 space ? tab from our key-board ?

    by reading you explanation i think, in C++, we can use [-5,-4,-3,-2,-1,0,1,2,... SIZE-5] as array index ?

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I have run this piece of code. and Now Everything's Clear.

        int ara[100];
    int *h=ara+4;

    ara[0]=10;
    ara[1]=20;
    ara[2]=30;

    cout<<ara[0]<<" "<<h[-4]<<" "<<ara[1]<<" "<<h[-3]<<" "<<ara[2]<<" "<<h[-2]<<"\n";

    Thank you :)

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

    That's very simple to do:

    dp[0] = SOME_BASE_VALUE;
for (int i = 1; i < N; i++)
    dp[i] = 2 * dp[i-1] + 5;

    :)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +21 Vote: I do not like it

      What if dp[i][j][k] = 2 * dp[i - 1][j - 1][k - 1] + 5 ?

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Most formulas are fine if we will put some well defined value for an empty set object like empty sum or empty product or number of coverings of an empty chessboard with some pieces. We can always hardcode dp[0] as value computed as if dp[-1] would be that starting value = take away from a loop one of its n iterations and perform it "by hand", but that's like yelling "Hey, look at me, I'm such an ugly and badly designed code!".

      → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it -12 Vote: I do not like it

int a[1];

for(int i = 100; i < 1000; i++) cout << a[i] <<" ";

Also will work!

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    He says about negative indexes and not about unallocated memory for arrays...

    → Reply