JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Possible bug in template code | Reply
In template code to find cumFre, calculation of tIdx may exceed array size. Hence, I think this should be better.

Discover this while doing this problem
http://acm.timus.ru/problem.aspx?space=1&num=1521
int findG(int cumFre){
	int idx = 0;
	while ((bitMask != 0) && (idxx < n)){
		int tIdx = idx + bitMask;
		if ((tIdx <= n) && (cumFre >= tree[tIdx]) ){
		        // if current cumulative frequency is equal to cumFre,
		        // we are still looking for higher index (if exists)
			idx = tIdx;
			cumFre -= tree[tIdx];
		}
		bitMask >>= 1;
	}
	if (cumFre != 0)
		return -1;
	else
		return idx;
}
Re: Possible bug in template code (response to post by tungnk1993) | Reply
A smaller change to fix the bounds check in findG is:
while ((bitMask != 0) && ((idx + bitMask) <= MaxVal)) {
RSS