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;
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 >_>...
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 ?I have run this piece of code. and Now Everything's Clear.
Thank you :)
That's very simple to do:
:)
What if dp[i][j][k] = 2 * dp[i - 1][j - 1][k - 1] + 5 ?
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!".
int a[1];
for(int i = 100; i < 1000; i++) cout << a[i] <<" ";
Also will work!
He says about negative indexes and not about unallocated memory for arrays...