|
|
| Show all threads Hide all threads Show all messages Hide all messages | | What count of pattern for n=36? | OpenGL | 1708. Sum of Digits 2 | 23 Oct 2016 18:56 | 5 |
Edited by author 17.06.2009 19:29 I also get 47062 and use 1500+ms 85000K in codeforces custom test, how to optimize memory?
YES Accepted memory is too hard...
Edited by author 23.10.2016 18:54
Edited by author 23.10.2016 18:54 I hope admin can decrease the Time limit to 1s, to encourage me continue to optimise time. | | Why answer not 1*2*3* ??? | Valentin (Perm SU) | 1708. Sum of Digits 2 | 24 Oct 2011 13:47 | 2 | I understand, because 1113 gets to 1*2*3* | | What output for n=5? | Valentin (Perm SU) | 1708. Sum of Digits 2 | 24 Oct 2011 13:44 | 3 | 1*2*
112*3*
12*3*
1223*4*
123*4*
13*4*
2*3*
223*4*
23*4*
3*4*
Seems to be correct :)
Big thanks, I get this output too :) | | OMG! I've solve this | DK [Samara SAU 1: X2008] | 1708. Sum of Digits 2 | 29 Jun 2009 15:58 | 5 | 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. 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! 2Al.Cash: I think you are wrong. For example 12355->4444. 2Al.Cash: I think you are wrong. For example 12355->4444. Edited by author 29.06.2009 15:59 | | To admins | DK [Samara SAU 1: X2008] | 1708. Sum of Digits 2 | 29 Apr 2009 15:52 | 2 | To admins DK [Samara SAU 1: X2008] 29 Apr 2009 08:04 Why the answer
1*2*
112*3*
12*3*
2*33*
is forbidden for test case 1?
The last pattern is not equal from "2*3*".
Does the phrase "the patterns should not contain unnecessary elements" mean that if I can remove a letter from pattern without making list incorrect, I must do so?
Yes Vladimir Yakovlev (USU) 29 Apr 2009 15:52 | | What does it mean? | OpenGL | 1708. Sum of Digits 2 | 8 Apr 2009 17:34 | 1 | It is allowed that the empty string matches several patterns. ??? |
|
|
|
