I have two problems on permutations which I can´t solve now becuase my knowledge about permutations and the necessary tricks is very poor.
1st:
Find an algorithm that for given natural N (N<=1000), K and given permutation of N elements will find the Kth composition of this permutation in time...
I think that the estimation established by n/8 ln n < PI(n) < 6n/ln n is correct (which results form the work of Chebyshev, he also prooved that there are better constants than 1/8 and 6 in the estimations like a previous and I really believe in it) and is is also coppied from one manual (I am...
The field shouldn´t be monotonic necessarilly, but it seems that any using of binary search could reduce sufficiently the number of steps. I will have a look on your hints, thanks.
Ok... if I proceed according to Eratosthenes (so I start in 2 and below each multiple of 2 i make some sign and do this whith each prime p_k <= n without any simplification, finally the number of signs at i-th position will be the number of all divisors of i). This algorithm has the effecienty...
Modify the Eratosthenes Sieve to count the number of all divisors of the given number. Find an algorithm which for given number N <= 10000 will create a field of N numbers such that the value of the i-th element of the field is the number of all divisors of the number i for each i <= N, but the...
Let A be a field of N integers and A[0] = A[N+1] = infinity. Element A[i] is called a local minimum if A[I-1] >= A[i] <= A[I+1]. Find an alogrithm that will find some local minimum in a time asymptotically better then O(n). Hint: Consider that in each field deffined as before there must exist at...
Let A be a field of N integers and A[0] = A[N+1] = infinity. Element A[I] is called a local minimum if A[I-1] >= A[I] <= A[I+1]. Find an alogrithm that will find some local minimum in a time asymptotically better then O(n). Hint: Consider that in each field deffined as before there must exist at...