Обсуждение @ 1658. Сумма цифр @ Timus Online Judge

Fine solution =)

Послано Teacher30 16 ноя 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 =)

Послано svr 16 ноя 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 =)

Послано Teacher30 16 ноя 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?

Послано Vladimir Yakovlev (USU) 17 ноя 2008 11:16

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

Послано Teacher30 17 ноя 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 =)

Послано Slava (ssau) 11 дек 2008 20:19

I think I understand your method :)

Edited by author 11.12.2008 20:20

if you are Sergey Kopeliovich,

Послано Rustam 16 дек 2008 01:32

who is Burunduk1?

Bugoga =)

Послано Pavel Khaustov [Tomsk PU] 11 янв 2009 13:42

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

Re: if you are Sergey Kopeliovich,

Послано Fyodor Menshikov 11 янв 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

Обсуждение задачи 1658. Сумма цифр