ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1009. K-based Numbers

this is a good algorithm.
Posted by Aharon_Smbatyan(YSU) 20 Jun 2010 04:03
n , k
1. if ( n = 0 ) , then answer = ( 1 ).
2. if ( n = 1 ) , then answer = ( k-1 ).

Edited by author 20.06.2010 04:04
Re: this is a good algorithm.
Posted by f309587969 27 Jul 2010 11:13

Re: this is a good algorithm.
Posted by archimede_syracuse 15 Aug 2010 12:34
n>=2 !!!
Re: this is a good algorithm.
Posted by Andrew Hoffmann aka SKYDOS [Vladimir SU] 15 Aug 2010 12:49
There is good O(1) memory and O(n) algo (n - number length)
info: http://skydos.blogspot.com/2010/07/k.html
Re: this is a good algorithm.
Posted by Artem Khizha [DNU] 16 Aug 2010 03:25
Okay, I'll join to Captains Obvious. You can find an answer with O(1) memory and O(logN) time.
Re: this is a good algorithm.
Posted by Andrew Hoffmann aka SKYDOS [Vladimir SU] 16 Aug 2010 03:32
Can you explain this algo?
Really interesting to know better one.
Thx.
Artem Khizha [DNU] wrote 16 August 2010 03:25
Okay, I'll join to Captains Obvious. You can find an answer with O(1) memory and O(logN) time.
Re: this is a good algorithm.
Posted by Artem Khizha [DNU] 16 Aug 2010 13:32
Sure, you're welcome.
Okay, we're already know, that the answer can be found reccurently: F(N) = (K-1)*(F(K-1)+F(N-2)), where F(0) = 1, F(1) = K-1. We see, that the {F(N)} sequence is very similar to Fibonacci's one and can assume some facts. I see two different approaches to solve the problem.

1) First way is to build characteristic equation, solve it and get an exact formula for F(N). I didn't try this way, because I foresaw some problems with precision and float calculations. If you're interested, you can turn to this article as a manual:
http://www.intuit.ru/department/algorithms/algocombi/8/2.html

2) I assumed, that method with fast matrix exponentiation will work as well as for Fibonacci's numbers.
Just consider a matrix: L(N) = {{F(N+1), F(N)}, {F(N), F(N-1)}}.
Let's try to find such R, that L(N)*R = L(N+1).
If you write down this information, you'll easily see, that R = {{K-1, 1}, {K-1, 0}}. So all you need is to find L(1)*R.pow(N-2).

Hope this information was helpful, I'm not sure it is the best way to describe an approach though. :-)

Edited by author 16.08.2010 13:34
Re: this is a good algorithm.
Posted by Artem Khizha [DNU] 16 Aug 2010 13:39
Actually, I implemented only O(N)-solution before. Today I wrote a code for a fast exponentiation, but (it seems I don't know java well) my time increased in #1013, where BigInteger is needed. Strange. :-)
Re: this is a good algorithm.
Posted by Andrew Hoffmann aka SKYDOS [Vladimir SU] 16 Aug 2010 16:29
Artem Khizha [DNU]
Thx for explanations and idea! I got it!
Really nice approach with matrixes!
Re: this is a good algorithm.
Posted by dima11221122 15 Sep 2010 14:10
#include <iostream>

using namespace std;
unsigned long stepen(unsigned long K,unsigned long N)
{
unsigned long i, result=1;
if (N<0)
return 0;
else
{
i=1;
for(; i<=N; i++)
result*=K;
return result;
}
}

int main()
{
unsigned long N, K, i, result;
cin>>N;
cin>>K;

result=stepen(K, N)-(stepen(K,N-2)+stepen(K, N-1)-1);
cout<<result<<endl;
//system("Pause");
return 0;

}

WA #2. Why?
Re: this is a good algorithm.
Posted by TLaum 23 Sep 2011 17:49
good job!
Re: this is a good algorithm.
Posted by Frankie 26 Nov 2011 06:41
>>dima11221122

Firstly, I came up with something like that and got WA2 too.

N = (k-1)^n + n(k-1)^(n-1) - that formula looks pretty alright; but it isn't.
It assumes there can't be more than one zero in the number, while there obviously can. The actual answer is something like that -
N = (k-1)^n + n * (П(i=1 to min(k,n)) of (k-i)^(n-1))
and i think it's anyways easier to solve that like original poster did.

Edited by author 26.11.2011 06:42
Re: this is a good algorithm.
Posted by daminus 1 Mar 2012 12:15
Thanks! Good algo
Re: this is a good algorithm.
Posted by thefourtheye 29 Mar 2012 02:25
Aharon_Smbatyan(YSU) wrote 20 June 2010 04:03
n , k
1. if ( n = 0 ) , then answer = ( 1 ).
2. if ( n = 1 ) , then answer = ( k-1 ).

Edited by author 20.06.2010 04:04

I am not sure, how the number of zero digit numbers (of course, without two zeros in it) become 1.

Edited by author 29.03.2012 02:38
Hi
Posted by David 23 May 2012 11:28
Can anybody tell me where can i get some info about this topic(k-based numbers), I really don't get from where cames this recurrent formula? Greetings
Re: Hi
Posted by Amir Aupov [MIPT] 8 Aug 2012 19:02
How can we get valid n-digit number? Trivially, we can append each of (k-1) possible digits (k digits except for 0) to the front of each of (n-1)-digit valid numbers.
But we can also form valid number this way: append 0 to the front of (n-2)-digit valid number, and then append (k-1) possible digits, as in the first case.

This gives us F(n) = (k-1)*F(n-1)+(k-1)*F(n-2), where F is the function to yield the amount of valid n-digit numbers.

I'd recommend you to ensure this yields only the valid numbers, think why can't it produce duplicates, and whether other means to construct valid numbers are possible.

Then you follow Artem Khizha's [DNU] recipe and get an AC (=

Edited by author 08.08.2012 19:05
Re: Hi
Posted by Bogatyr 2 Oct 2012 14:32
HI David,
The problem statement language is confusing.   A "k-based number" is a number represented in base "k", that's all.
Re: Hi
Posted by Bogatyr 2 Oct 2012 15:31
>  Amir Aupov [MIPT]

I like your explanation.   I approached the construction of N digit numbers from N-1 digit numbers in the typical way of constructing numbers: multiply N-1 digit number by base, and add in the new digits to the units position.    This has the benefit of being clear and natural, so we can be sure that we're not missing any numbers.   It has the disadvantage that you must track numbers that end in zero separately from those that don't.   But this is still quite simple:
Z(n): # of valid numbers ending in zero
NZ(n): # of valid numbers not ending in zero
Z(2) = k - 1
NZ(2) = (k - 1) * k - (k - 1)   (total number of valid 2-digit numbers, minus those that end in 0)
then,
Z(n) = NZ(n - 1)
NZ(n) = (Z(n-1) + NZ(n-1)) * (k - 1)

Compute Z(n) and NZ(n) iteratively (DP), and then output F(n) at the end
F(n) = Z(n) + NZ(n)