Talk:UVa 10591

From Algorithmist
Jump to navigation Jump to search

UVa_10591[edit]

Could someone kindly write up UVa problem 10591 -- Happy Number? Most importantly, are there any gotchas? Sartak 03:11, 26 Mar 2006 (EST)

There's nothing really special about 10591, just remember to store the number and scan through it and see whether it forms a cycle. --Roticv 06:37, 26 Mar 2006 (EST)

Odd. I guess there just must be some corner case that my algorithm misses. Sartak 00:27, 27 Mar 2006 (EST)
What is your algorithm? I haven't solved the problem, but maybe it misses a case like a -> b -> c -> b? --Rrenaud 08:51, 27 Mar 2006 (EST)
I think it is more likekly to miss cases like a -> b -> c -> a or something like that. --Roticv 08:26, 28 Mar 2006 (EST)
The algorithm is: add the first term to a list, calculate the next term, see if this new term is already in the list, if so, quit. If this new term is a 1, quit. Otherwise, add this new term to the list and continue. I'm thinking the problem is an implementation error, not an algorithmic one, because this appears to be a fairly straightforward problem. Here is the unadultered code. Perhaps my array is too small? Sartak 00:22, 29 Mar 2006 (EST)
Your program doesn't print "#" after the word "Case". Also, you can read int's with just scanf("%d", &n); and the longest cycle in this problem can't be longer than . Sweepline 08:17, 29 Mar 2006 (EST)
It's nice that Sweepline caught your bug. In reading your code, I have a couple suggestions. The first is that you shouldn't put large arrays on the stack. Even if it works here, it is quite easy to seg fault by overloading the stack. The second suggestion is algorithmic, you can make your solution a lot faster by precomputing the "happiness" of 0-729, and then you simply iterate the function once (which will bring the numbers into the precomputed range, max original input is 999,999,999 which maps 729), and do a lookup. --Rrenaud 10:43, 29 Mar 2006 (EST)
I didn't precomp, but I didn't clear my cache either. Someone should do the writeup now that it's figured out ;) Larry 14:01, 29 Mar 2006 (EST)
Thanks for the suggestions, fellas. And good eye for spotting that bug, Sweepline. Very silly of me. I should use diff for checking correctness instead of eyeballing it. Sartak 18:54, 29 Mar 2006 (EST)
Thanks for the formatting, though I was going to move this to 10591's Talk page when someone submits that page.. I make stupid formatting mistakes like that all the time.. costed me 4 WA's just the other day.. Larry 12:21, 30 Mar 2006 (EST)