Page 1 of 2
10909 - Lucky Number
Posted: Thu Sep 22, 2005 11:39 am
by top
can anyone please describe this problems efficient way to solve...I am facing TLE.
Posted: Thu Sep 22, 2005 12:28 pm
by mf
You can use a binary search tree to generate the list of luckies.
The tree should be able to remove an element and return k-th smallest element in O(log n) time.
Once you have this list, you can solve each test case by bruteforcing L1, starting from L1=floor(N/2) and going down to 1.
Also note, that no odd number can be represented as a sum of luckies.
Posted: Fri Sep 23, 2005 6:48 pm
by juki
It takes too many seconds to generate all lucky numbers which are less than 2,000,000.
Does it need to include all lucky numbers generated already in a source code ??
But they are also too many to do that.
I really have no idea to solve this problem.
Please help me.
Posted: Fri Sep 23, 2005 7:54 pm
by Observer
juki wrote:It takes too many seconds to generate all lucky numbers which are less than 2,000,000. Does it need to include all lucky numbers generated already in a source code ??
Hi,
In my Accepted program I only need the first 80000 lucky numbers.
At first I tried to use an array, which ran fast in my machine (takes only ~3 seconds) but got TLE here. Then I tried something like what mf suggested (well actually I didn't use a proper binary search tree in my program), and got Accepted in ~2 sec.
Have fun!
Posted: Fri Sep 23, 2005 8:31 pm
by mf
juki wrote:It takes too many seconds to generate all lucky numbers which are less than 2,000,000.
My program spends just 1.3 seconds generating them. Here's my algorithm.
Code: Select all
Let T be a data structure, which holds a list of numbers and supports the operations:
T.find(k) - returns (k+1)-st smallest number in T
T.remove(k) - removes (k+1)-st smallest number
initialize T with the set {1,3,5,...,1999999}.
for (k = 1; T.find(k) <= T.size; k++)
for (i = j = T.find(k) - 1; i < T.size; i += j)
T.remove(i);
Now T holds all lucky numbers less than 2000000.
You can implement T as a simple BST, just make sure that during initialization you create a perfectly balanced tree, and when you remove a node, the height of the tree doesn't increase. Then you'll get a guaranteed O(n log n) time without the trouble of implementing a balanced tree.
Observer wrote:In my Accepted program I only need the first 80000 lucky numbers.
Oh thanks. Nice idea!
Posted: Wed Oct 05, 2005 11:42 am
by Sedefcho
Guys,
I want to first make sure my program is logically correct and
then optimize it with some fast data structure as you suggest.
So can anyone tell me:
1. How many luckies are there in total below 2 000 000 ?
My program says there are 136412 luckies in total. Is that right ?
2. Are these the first 50 luckies:
Code: Select all
1 3 7 9 13 15 21 25 31 33 37 43 49 51 63 67 69 73 75 79 87
93 99 105 111 115 127 129 133 135 141 151 159 163 169 171 189 193 195 201 205 211
219 223 231 235 237 241 259 261
3. Are these the last 50 luckies below
2 000 000 ( this list shoud be read backwards ) :
Code: Select all
1999983 1999977 1999969 1999959 1999917 1999915 1999905 1999879 1999861 1999857
1999825 1999819 1999815 1999813 1999725 1999719 1999689 1999675 1999671 1999641
1999623 1999621 1999609 1999587 1999569 1999557 1999543 1999537 1999525 1999515
1999507 1999501 1999483 1999477 1999453 1999447 1999423 1999413 1999411 1999405
1999381 1999357 1999353 1999351 1999347 1999339 1999335 1999315 1999263 1999255
Thanks in advance !
Posted: Wed Oct 05, 2005 2:40 pm
by Sedefcho
Thanks, I'll have that in mind when I come back to this problem.
Posted: Wed Oct 05, 2005 2:43 pm
by little joey
Strange, does anyone also hear an echo, echo, echo, ....
Posted: Wed Oct 05, 2005 2:55 pm
by Sedefcho
No, noone does does does
Posted: Thu Oct 06, 2005 8:33 am
by ImLazy
Dear MF, I don't understand how to use a Binary Search Tree to find the (k)th smallest number. Can you describe it more detialdely? Thanks.
Posted: Thu Oct 06, 2005 9:35 am
by wook
ImLazy wrote:Dear MF, I don't understand how to use a Binary Search Tree to find the (k)th smallest number. Can you describe it more detialdely? Thanks.
Let cn[v] : the number of nodes, in the binary tree whose root is v.
(e.g. if v is a terminal node, cn[v] = 1)
then,
cn[v] = cn[ left[v] ] + 1 + cn[ right[v] ], (define cn[NIL] = 0)
so you can make a recursive search in BST, just like finding an element in BST.
Posted: Thu Oct 06, 2005 4:35 pm
by ImLazy
Oh, I see. I can set two variables in each node representing how many nodes are there in its left subtree and right subtree. Thanks.
Posted: Fri Oct 07, 2005 1:55 pm
by ImLazy
mf wrote:just make sure that during initialization you create a perfectly balanced tree, and when you remove a node, the height of the tree doesn't increase.
How can I prevent the tree's height increasing when I remove nodes? If I remove the root node of the tree, I think, the height of the tree will be doubled.
Posted: Fri Oct 07, 2005 2:58 pm
by mf
ImLazy wrote:How can I prevent the tree's height increasing when I remove nodes? If I remove the root node of the tree, I think, the height of the tree will be doubled.
If the root has zero or one child, you can remove it directly by manipulation the pointers.
If the root has two children, you can do the following:
1. Find the smallest element in the root's right subtree. I'll call this element X.
2. Assign X's key and any additional data to the root.
3. Remove X. (notice that X cannot have two children, else it wouldn't be the smallest in step 1.)
For example, consider the picture below. You want to remove B. The smallest element in B's right subtree is C (to find it just start from F, and go left as long as it's possible.) Relabel the root as C, and remove the original C.
Code: Select all
B C
/ \ / \
A F A F
/ \ / \
E G --> E G
/ /
C D
\
D
Posted: Fri Oct 07, 2005 5:12 pm
by ImLazy
Oh, I see. Thanks.
I used to do like this:
Code: Select all
B F
/ \ / \
A F E G
/ \ /
E G --> C
/ / \
C A D
\
D
You see, if A has subtree, the height will increase.
Now I will do what you say. Thanks.