10909 - Lucky Number

[top]

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

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

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

[Observer]

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!

[mf]

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.

In my Accepted program I only need the first 80000 lucky numbers.

Oh thanks. Nice idea!

[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 !

[Sedefcho]

Thanks, I'll have that in mind when I come back to this problem.

[little joey]

Strange, does anyone also hear an echo, echo, echo, ....

[Sedefcho]

No, noone does does does

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

[wook]

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.

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

[ImLazy]

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.

[mf]

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

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