JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Binary Indexed Trees Find index with given cumulative frequency algorithm
 Find index with given cumulative frequency algorithm | Reply In the article said:MaxVal - maximum value which will have non-zero frequencybitMask - initialy, it is the greatest bit of MaxValBut to properly use this algorithm I had to set: P = maximum value which will have non-zero frequencyMaxVal = min{ 2k such that 2k >= P }bitMask = greatest bit of MaxValto avoid skipping some values while binary searching.Someone else got this?EDIT: typo
 Re: Find index with given cumulative frequency algorithm (response to post by Xyphen) | Reply I suppose that you wanted to writeMaxVal = min{ 2^k such that 2^k >= P }However, you have right. While I was writing the article, I set MaxVal to be in form 2^n, where n is non-negative integer, but didn't mention it - sorry. I wanted to add it later, but it seems that sometimes it is very hard to get response from moderators when it is about articles (i.e. I have send article "Concurrent programming in Java" several times in the last year, but as you see it is not among the articles). Instead setting MaxVal to be in that form, you can add (start body of condition)```if (tIdx <= MaxVal){ ```after```int tIdx = idx + bitMask; ```and close before (just put })```bitMask >>= 1; ```Please, accept my apologize if this kind of mistake did make you (or to anyone other) trouble.EDIT: typo
 Re: Find index with given cumulative frequency algorithm (response to post by boba5551) | Reply boba5551 wrote: I suppose that you wanted to writeMaxVal = min{ 2^k such that 2^k >= P }Yep, you're right.boba5551 wrote: Please, accept my apologize if this kind of mistake did make you (or to anyone other) trouble.Don't worry man.In fact, I just wanted to know if it could be possible to use any kind of trick/s to make this algorithm work using linear space instead of exponential space.I'll test ur fix in a while, thanks.
 Re: Find index with given cumulative frequency algorithm (response to post by Xyphen) | Reply Well, it still use linear space with constant at most 2. But, if you want linear space with constant 1, then it is enough to add that condition.
 Re: Find index with given cumulative frequency algorithm (response to post by boba5551) | Reply It works great.I hadn't thought to fix it in that way.Thanks!.
 Forums Tutorial Discussions Binary Indexed Trees Find index with given cumulative frequency algorithm Previous Thread  |  Next Thread