Discussion @ 1658. Sum of Digits @ Timus Online Judge

Fine solution =)

Posted by Teacher30 16 Nov 2008 19:28

I've solved this problem in O(n) time, with O(n) of memory. Where n - length of the answer (in this problem it's not more than 100)

Constants are very big, but solution is really linear =)
Memory: 8^3*9^3 + n*9*150
Time: (8^3*9^3 + n*9*150)*9

Re: Fine solution =)

Posted by svr 16 Nov 2008 22:15

If you are a teacher your work first of all is
to generate tests which crach slow and wrong solutions.

Re: Fine solution =)

Posted by Teacher30 16 Nov 2008 22:43

As teacher I (IMHO) should help people who want to learn smth new.

Btw, "Teacher30" is only my nickname.
My true name is Sergey Kopeliovich.

Which one of yout AC solutions uses this algo?

Posted by Vladimir Yakovlev (USU) 17 Nov 2008 11:16

Re: Which one of yout AC solutions uses this algo?

Posted by Teacher30 17 Nov 2008 14:07

The last.
Last 10-15 submissions are variations of this theme.

Edited by author 17.11.2008 14:10

Re: Fine solution =)

Posted by Slava (ssau) 11 Dec 2008 20:19

I think I understand your method :)

Edited by author 11.12.2008 20:20

if you are Sergey Kopeliovich,

Posted by Rustam 16 Dec 2008 01:32

who is Burunduk1?

Bugoga =)

Posted by Pavel Khaustov [Tomsk PU] 11 Jan 2009 13:42

Really interesting question. Who is Burunduk1? Or you were renumbered few years ago? =)

Re: if you are Sergey Kopeliovich,

Posted by Fyodor Menshikov 11 Jan 2009 15:48

Notice:

Burunduk1 http://acm.timus.ru/author.aspx?id=34699 last AC 14 Sep 2008

Teacher30 http://acm.timus.ru/author.aspx?id=69475 first AC 17 Sep 2008

Edited by author 11.01.2009 15:48

Discussion of Problem 1658. Sum of Digits