ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1708. Sum of Digits 2

OMG! I've solve this
Posted by DK [Samara SAU 1: X2008] 3 May 2009 18:49
Re: OMG! I've solve this
Posted by Al.Cash 3 May 2009 21:27
Have you examined only forbidden sets (which can be replaced with the smaller set of digits, whose sum and sum of squares are equal to the initial), that contain not more than one maximal digit?

I can't prove any restrictions on such sets yet, so the answer would be very helpful.
Re: OMG! I've solve this
Posted by DK [Samara SAU 1: X2008] 4 May 2009 01:20
I've just use folowing ideas:
A. Calculating lots of samples that are minimal (with length <= X = 55). There is not more than about 50m of them.
B. If there is a long enough (length >= Y = 13 (?) ) sequence of equal chars, there is '*' possible. E.g. "12222222222222" transforms to "12*"
C. There is no more than 2 '*' in any pattern
D. There is no patterns with "1*", except "1*2*"
E. No patterns likes "11*"

So, I've not used some specific ideas or facts.

This solution makes you right answer, but works too slow.

Then, I've precalculated all the difference from solution with X = 23, Y = 8 (I'm not sure in constants ) and right solution.
With lots of specific optimization, it is AC.
My first AC solution used 63K of source, 4.85 s. and 63M of memory
Good luck!
Re: OMG! I've solve this
Posted by OpenGL 9 May 2009 01:46
2Al.Cash: I think you are wrong. For example 12355->4444.
Re: OMG! I've solve this
Posted by shako 29 Jun 2009 15:58
OpenGL wrote 9 May 2009 01:46
2Al.Cash: I think you are wrong. For example 12355->4444.

Edited by author 29.06.2009 15:59