## 10909 - Lucky Number

**Moderator:** Board moderators

### 10909 - Lucky Number

can anyone please describe this problems efficient way to solve...I am facing TLE.

top

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.

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.

Last edited by mf on Fri Sep 23, 2005 8:58 pm, edited 1 time in total.

Hi,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 ??

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!

**7th Contest of Newbies**

**Date**: December 31st, 2011 (Saturday)

**Time**: 12:00 - 16:00 (UTC)

**URL**: http://uva.onlinejudge.org

My program spends just 1.3 seconds generating them. Here's my algorithm.juki wrote:It takes too many seconds to generate all lucky numbers which are less than 2,000,000.

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.
```

Oh thanks. Nice idea!Observer wrote:In my Accepted program I only need the first 80000 lucky numbers.

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
```

- little joey
- Guru
**Posts:**1080**Joined:**Thu Dec 19, 2002 7:37 pm

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.

Sorry For My Poor English..

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.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.

I stay home. Don't call me out.

If the root has zero or one child, you can remove it directly by manipulation the pointers.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 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
```

Oh, I see. Thanks.

I used to do like this:
You see, if A has subtree, the height will increase.

Now I will do what you say. Thanks.

I used to do like this:

Code: Select all

```
B F
/ \ / \
A F E G
/ \ /
E G --> C
/ / \
C A D
\
D
```

Now I will do what you say. Thanks.

I stay home. Don't call me out.