[algogeeks] Re: How to solve this problem efficiently?
I guess it is binary search tree. Try this and you will get what you want. On Sep 26, 5:12 am, mukesh agrawal [EMAIL PROTECTED] wrote: What is binary index tree ? I googled it finding irrelevent information ... help needed .. On 9/25/07, Mohammad Naser Zandy [EMAIL PROTECTED] wrote: I am agree with Sticker, I comes to write exactly what Sticker wrote. ;) It's O(N^2 / 2) that is 1+2+3+4+5+...+N. On 9/25/07, Sticker [EMAIL PROTECTED] wrote: I saw your ideas. Some of them are correct some are not. Here is what I am thinking. From the question we know that 1 ≤ M ≤ 100 and 1 ≤ N ≤ 4000. So notice that M N. Using a linked list to store M, you have to travel it from either end, so at least M/2 travels each time, still larger than N. So what if we keep M stored in an array(a simplest array int[], called booArray) and do touch it. Rather we dynamically store N? I use a linked list borLList to store all the borrowed books' original position in booArray. Once we come across a borrowed index, we go through borLList, each time a position smaller than the borrowed index, we increase the borrowed index by one until we come across a position has a position larger than it, then we insert this borrowed index to the current position. Do another one and so on. Example: 5 26 1 42 15 3 2 3 4 The booArray is 26, 1, 42, 15, 3, stored in booArray[1] to booArray[5]. borLList is empty now. 3 is the first borrowed index, we insert it into borLList and return booArray[3]. The next borrowed index is 4, since the first element in borLList is 3, which is smaller than 4, we increase this borrowed index by one, now it is 5, since no larger element exists in borLList, we insert 5 into borLList and return booArray[5]. Now the borLList is 3-5. As we can see, practically far less than 4000 times is required for each borrowed index, which is definitely better than the double link list solution (which is (S/2 -1) * (S/2 - 2) * (S/2 -3) * ... 1 as given by jliang. I definitely do not agree the method to reorder the borrowed indexes. This will give wrong answer. The order is important for this problem. I do not know how to use binary search tree to solve this problem, it will be great if solution can be described here. On Sep 23, 12:17 pm, Jun [EMAIL PROTECTED] wrote: I already know how to solve it. Binary Index Tree is good approach to solve this problem. Thanks very body involved in this discussion! On Sep 22, 6:31 am, KK [EMAIL PROTECTED] wrote: On Sep 5, 11:07 am, jliang [EMAIL PROTECTED] wrote: how about a doubled linked list where you can remove item at any index. the removing is O(1). you can also keep track of the current removing from a doubled linked list is O(1)? How? size S so if you are borrowing book at index greater than S/2, you traverse the list from the end, if index S/2, you traverse from the beginning. every time a book is removed, S becomes 1 smaller, so the traversal time is something like (S/2 -1) * (S/2 - 2) * (S/2 -3) * ... 1 you can also put them in a binary tree, so every operation is O(lgN) putting the original array in binary tree takes O(M lgM) time, and you will lose the original indices. So it's of no use. so the total will be O(lgN M) I dont think so. correct me if I am wrong. -- Mukesh Agrawal Final Year UG CSE IIT KGP --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Programing problem
Hi, if ( commnad sequence is bad ) whether to include it area calculation or not?? On 10/5/07, piruk [EMAIL PROTECTED] wrote: Hi. How to solve this task? Areameter is a turtle-like self-propelled vehicle controlled by sequences of commands transmitted over a radio channel. Initially the vehicle is oriented in some fixed direction, let's say to the North. Commands instruct Areameter how far to move in the current direction and where to turn after the move. Allowed turns are +90 or -90 degrees relative to the current direction. By positive turn we mean turning to the right (clockwise). A command sequence is good if it brings the vehicle to the starting point and starting orientation after tracing a closed non self- intersecting path. On coming back to the starting point Areameter should emits the area (number of square units) of the territory walked around. Write a program to perform Areameter's task of calculating the area from the sequence of received commands. Input The standard input stream contains a sequence of test cases specified as follows: The first line contains a positive integer n, number of test cases. A test case is simply one good command sequence spread over one or more lines. Each command sequence consists of alternating move and turn commands. Move command is represented by a positive integer; turn command is represented by single character '+' or '-'. End of command sequence is coded by giving 0 for move command. Commands are separated by at least one white-space character. You can assume the input is well-formed and contains only good command sequences. There are no a priori constraints on the sequence length. The values of moves and the resulting area are all within integer representation. Output For each test case the program should output one text line containing a number: the area in square units. Example Input 3 3 + 3 + 3 + 3 + 0 2 + 2 + 3 - 3 - 1 + 2 + 3 + 3 + 1 - 3 + 2 - 1 + 0 2 + 2 - 1 - 1 + 1 + 3 + 3 + 2 - 2 - 4 - 4 + 2 + 2 + 1 - 1 - 2 + 1 + 1 - 1 + 7 + 2 - 1 + 0 Output 9 16 27 -- PRADEEP MACHARLA Ph:08040141194 --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Programing problem
On 10/7/07, macharla pradeep [EMAIL PROTECTED] wrote: Hi, if ( commnad sequence is bad ) whether to include it area calculation or not?? It is mentioned that command sequence is never bad. On 10/5/07, piruk [EMAIL PROTECTED] wrote: Hi. How to solve this task? Areameter is a turtle-like self-propelled vehicle controlled by sequences of commands transmitted over a radio channel. Initially the vehicle is oriented in some fixed direction, let's say to the North. Commands instruct Areameter how far to move in the current direction and where to turn after the move. Allowed turns are +90 or -90 degrees relative to the current direction. By positive turn we mean turning to the right (clockwise). A command sequence is good if it brings the vehicle to the starting point and starting orientation after tracing a closed non self- intersecting path. On coming back to the starting point Areameter should emits the area (number of square units) of the territory walked around. Write a program to perform Areameter's task of calculating the area from the sequence of received commands. Input The standard input stream contains a sequence of test cases specified as follows: The first line contains a positive integer n, number of test cases. A test case is simply one good command sequence spread over one or more lines. Each command sequence consists of alternating move and turn commands. Move command is represented by a positive integer; turn command is represented by single character '+' or '-'. End of command sequence is coded by giving 0 for move command. Commands are separated by at least one white-space character. You can assume the input is well-formed and contains only good command sequences. There are no a priori constraints on the sequence length. The values of moves and the resulting area are all within integer representation. Output For each test case the program should output one text line containing a number: the area in square units. Example Input 3 3 + 3 + 3 + 3 + 0 2 + 2 + 3 - 3 - 1 + 2 + 3 + 3 + 1 - 3 + 2 - 1 + 0 2 + 2 - 1 - 1 + 1 + 3 + 3 + 2 - 2 - 4 - 4 + 2 + 2 + 1 - 1 - 2 + 1 + 1 - 1 + 7 + 2 - 1 + 0 Output 9 16 27 -- PRADEEP MACHARLA Ph:08040141194 -- Ciao, Ajinkya --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
