|
|
back to boardShow all messages Hide all messagesplease give me some hints how to solve the problem fast i.e. O(n*ln(n)) or O(n*sqrt(n)). Create Sqrt(N) buckets: In bucket k store amount of start in such range: [(k-1)*Sqrt(32000); k*Sqrt(32000)) When placing a star find bucket were it is situated O(Sqrt(N)) Add all buckets wich are lefter O(Sqrt(N)) In current bucket range check all stars. O(1) Because Sqrt(32000)=O(1) Update bucket! O(1) I used next: b[i] - number of start with x <= i. P.S. Bucket may be any size. For speed I chose bucket size 128. So I fastly can find bucket num: x shr 7. If something explained badly, ask. Good luck! > Create Sqrt(N) buckets: > In bucket k store amount of start in such range: > [(k-1)*Sqrt(32000); k*Sqrt(32000)) > When placing a star find bucket were it is situated O(Sqrt(N)) > Add all buckets wich are lefter O(Sqrt(N)) > In current bucket range check all stars. O(1) Because Sqrt(32000)=O (1) > Update bucket! O(1) > > I used next: > b[i] - number of start with x <= i. > > P.S. Bucket may be any size. For speed I chose bucket size 128. So I > fastly can find bucket num: x shr 7. > > If something explained badly, ask. > > Good luck! thanks a lot for your help. (sory about previous message) but can you explain in detail what do you put in buckets : a range of star in sorted list, or a list of star which X coordinate is in some range ? why sqrt(N) - amount of buckets ? in placing id a star do you mean calculation of its level ? > but can you explain in detail what do you put in buckets : > a range of star in sorted list, or a list of star which X coordinate > is in some range ? Picture: ^y | * <- we currently process this star | * * * | * * | 100 200 300 | | | | x +---------------------------> \_____/\______/\______/\___ bucket0 bucket1 bucket2 etc. 2 2 1 (!) We store in bucket amount of stars with x coordinate in range; To make it faster to analyze I used next statement: "two integers X and Y per line separated by a space, 0<=X,Y<=32000". Let b[i] = bucket i. b is array of integer; Let p[k] = Number of stars wich x coord is k Let Size = size of bucket. We select this value as we want. It is easy to see that we will have (32000 + 1)/Size + 1 buckets. The read and solve pseudo code: 1. b[i] = 0 for each i = 0, 1, .... (MaxX+1) div size + 1 p[i] = 0 for each i = 0, 1, 2, ... , 32000 2. We read star with coords (x; y) 3. CurLevel = 0 4. CurBucket = x div Size; 5. for i = 0 to CurBucket-1 do CurLevel = CurLevel + b[i]; Explanation: Because in bucket i (<CurBucket) we have number of stars with smaller x than current star we avoided running whole coordinates array. 6. But there still can be start with smaller x and wich are in same bucket! for i := (x div Size) * Size to x do Inc(CurLevel, p[i]); Left bound is leftest element in bucket. Right bound is coordinate. 7. Print CurLevel. 8. We need to upgrade buckets. Inc(b[CurBucket]); <--- New star in bucket ! Inc(p[x]); <--- New star on x ! 9. Anything left? About size of buckets. If we use too small bucket size we will do a lot of job on p.5. If we use too big bucket size we will do a lot of job on p.6. So we have to find such Size that next expression is minimal: 32000/Size + Size >= 2 * Sqrt(32000/Size * Size) = (теорема Коші, як по англійськи не знаю :( ) = 2 * Sqrt(32000) ~ 358. To make this expression as small as possible it must be: 32000/Size = Size => Size = Sqrt(32000) To be as strict as possible this solution is O(N) because number of buckets is constant :). Але рука не піднімається назвати його лінійним!. The O(N * Sqrt(N)) mark is taken from problem 1090 "In the army now". Number of buckets there is Sqrt(N). If you read this 2 problems you might see that they are very similar, execpt soldiers cant have same height. Level of star is number of jumps made by soldier :). дуже дякую ) thanks a lot. but how be in following situation : Picture: ^y | * * | * * * <- we currently process this star | * * | 100 200 300 | | | | x +---------------------------> \_____/\______/\______/\___ bucket0 bucket1 bucket2 etc. 2 2 1 (!) we insert star in bucket #2, calculating level of it = b[0]+b[1]+p[200..x] while there is star in bucket #1 which Y coord > Y coord of current star.? thanks for your help. i got AC in 0.7 sec. maybe because i used another partition in buckets not on x ranges, but on star ranges, and the constant of my algo is bigger than your one. i tried also to solve this problem using sorted binary tree. ( insertation & finding the star level aproximately log2(n) ), but i got TLE (maybe there is a test with all stars with equal X?). sorry about offtopic, but do you take part in ACM Ukrainian Regional Contest on 2-5 March ? thanks for your help. i got AC in 0.7 sec. maybe because i used another partition in buckets not on x ranges, but on star ranges, and the constant of my algo is bigger than your one. i tried also to solve this problem using sorted binary tree. ( insertation & finding the star level aproximately log2(n) ), but i got TLE (maybe there is a test with all stars with equal X?). sorry about offtopic, but do you take part in ACM Ukrainian Regional Contest on 2-5 March ? ACM Ukrainian Regional, what is this. Is it NetOI? I am in 9-th form. I take part in Ukrainian Respublican Olimpiad (UOI). How old are you? ACM Ukrainian Regional is 1/8 of final ACM world students command olympiad. Ukraine is devided on 4 regions. One of them is Kiev region. it covers several districts. Are from Kiev ? (in this case maybe you could take part in Kiev Regional olympiad (not included in rating), i am one of its organizers and participant as well:) i am a student of NAU on 3-d course my mail : xdex@ukrpost.net send me ur src. I used partitioning by x with bucket size 128. This made selecting bucket slightly faster: x shr 7 = x div 128. Hi! I solved this problem, but I have some trouble with 1090, which as you said, is simillar. I can't realize why I get WA. I posted my code at 1090's webboard... If you could look over my code or give me some test cases I would be grateful. My e-mail is vlad_io1@yahoo.com Any balanced trees! Not RB! RB is hard to implement in contest! |
|
|