10909 - Lucky Number

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

top
New poster
Posts: 1
Joined: Thu Sep 22, 2005 11:36 am
Contact:

10909 - Lucky Number

Post by top » Thu Sep 22, 2005 11:39 am

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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Thu Sep 22, 2005 12:28 pm

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.
Last edited by mf on Fri Sep 23, 2005 8:58 pm, edited 1 time in total.

juki
New poster
Posts: 2
Joined: Sat Oct 18, 2003 10:55 am

Post by juki » Fri Sep 23, 2005 6:48 pm

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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Fri Sep 23, 2005 7:54 pm

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! :D
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Fri Sep 23, 2005 8:31 pm

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!

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Wed Oct 05, 2005 11:42 am

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 !

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Wed Oct 05, 2005 2:40 pm

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Oct 05, 2005 2:43 pm

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

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Wed Oct 05, 2005 2:55 pm

No, noone does does does :wink:

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Thu Oct 06, 2005 8:33 am

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.
I stay home. Don't call me out.

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

Post by wook » Thu Oct 06, 2005 9:35 am

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

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Thu Oct 06, 2005 4:35 pm

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.
I stay home. Don't call me out.

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Fri Oct 07, 2005 1:55 pm

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.
I stay home. Don't call me out.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Fri Oct 07, 2005 2:58 pm

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


User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Fri Oct 07, 2005 5:12 pm

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.
I stay home. Don't call me out.

Post Reply

Return to “Volume 109 (10900-10999)”