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 1611. Decimation

What is complexity of your algo?
Posted by Vedernikoff Sergey 3 Apr 2008 01:44
During the OpenCup I've accepted the problem with complexity O(N*K^2), but here, on timus, only optimizations helped me to beat timelimit with this algo. At the same time, some people have AC-times 0.015 or something like that. Is it possible to solve the problem with more efficient algo?
Re: What is complexity of your algo?
Posted by KIRILL(ArcSTUpid coder:) 3 Apr 2008 02:53
O(N*K)
my implementation is not so fast because of recursion
Re: What is complexity of your algo?
Posted by Denis Koshman 4 Aug 2008 12:33
O(N*K). Are you sure it's still O(N*K) with recursion?
Re: What is complexity of your algo?
Posted by svr 19 Oct 2008 14:47
I could adopt only O(N*K*10) in DP
Re: What is complexity of your algo?
Posted by 198808xc 21 Oct 2010 23:18
I got confused.
My program is very short and the complexity is O(N*K). I didn't find anything hard when solving this.
I think you must have made it harder in thought.

BTW, not O(N*K*M), but O(N*K). M is the modulo(10 here).

Edited by author 21.10.2010 23:19

Edited by author 21.10.2010 23:19