A Lexicographical Order problem

general
1

Hi everyone,
I’m trying to solve this problem. I know it’s a kind of dynamic programming problem, but I still don’t get the way to do it. Please help me! I really appreciate your time! Thank you in advance!

Given a list. Each element in this list is a sequence of N numbers in lexicographical order such that:

  • The i_th number can have a value up to 2 * i.

  • For all j > i, the j_th number is always greater than the i_th number.

Find the x_th element in that list.

Example:
N = 2, we have the following list:

1 2

1 3

1 4

2 3

2 4

The 4th element is 2 3

2
  • Each Element is N digit wide.
  • N=2 -> Max No=24 as for the first digit i=1 We can have values from 1 to 1x2=2 and for i=2 We can have values from 1 to 2x2=4.And Number at second position should be always greater than its previous position. So values like 11,21,22 are not part of the list
  • Generate list according to this rule and find the X th number.
1 Like
3

It can be slow, depends what is MAXN…

What is the length od such list for N = 100 ?

4

The idea (without details) is this.

You can ask how many elements in list start with 1, let say a1.

if ( a1 == x_th ) return { 1, 2, 6, 8, ... }
else if ( a1 < x_th ) ask again "how many alements start with (1 2)/(1 3)/(1 4)" and so on
else ask "how many elements start with (2 3)/(2 4)"

For such question you will use DP.

howMany( int first, int count )
    if ( count == 2 ) return 2*N-first;
    else // count > 2
        sum = 0
        for i in first + 1 .. (N - count + 1) * 2
            sum += howMany( i, count - 1 )

(yes I used recursion for clarity)

1 Like
5

provide a link to the problem, please

6

-The trick is you don’t need to find length or the last element of such a list. U just need to calculate up to X th element.
-I solved this problem using a 1D array of length N.
-Make an analogy of this problem with a click counter.and see the transition states of it for N=3 and you’ll get your answer.
-For example.1 4 6 -> CLICK ->2 3 4.
-When the i th element becomes equal to 2xi. we start incrementing its previous elements such that none of them exceed 2xi constraint.
-When we get a successful increment, We make all the elements following it arr[i]=arr[i-1]+1.
-I hope this helps.

1 Like
7

@belista - Have a look at my second answer. Hope it should solve all your doubts about this problem

8

But you do, what if the question is find the 100.000.000.000th element for N = 100?

9

I don’t think that would be a test case. Still I checked my code and it does find N=100 and X=100,000,000 solution in about 2.8 sec.

10

I’m 100% sure that @anton_lunyov would say: “If I’m the problem setter than there will 1 <= X <= 10^18 and time limit will be 1s.”.

Btw: you know you tested 1000x smaller number, right? If I have time I’ll implement my solution and post the time here with link.

11

Thnx for the feedback. Ill try to improve my code too. Pls provide the link to the problem so I can test my code. M new to the codechef gig :slight_smile:

12

I’m so sorry, the page of this problem is in my language (VNese). I don’t think you two can understand it, but I still post it here anyway:

(betlista was right, the time limit is 1s for n <= 250)

Actually, I already figured out how to solve it by using DP.

Let’s say F[i, j] is the number of elements (for each element, consider the position from i to n) where the i_th number equals j.

—> F[i, j] = sum(F[i + 1, j + 1 … 2 * (i + 1)])

By optimizing, we can find F[i, j] in O(N^ 2).

For example:
N = 3, and we’ll have a list:

  1. 1 2 3

  2. 1 2 4

  3. 1 2 5

  4. 1 2 6

  5. 1 3 4

  6. 1 3 5

  7. 1 3 6

  8. 1 4 5

  9. 1 4 6

  10. 2 3 4

  11. 2 3 5

  12. 2 3 6

  13. 2 4 5

  14. 2 4 6

And this is my F[i, j] array:

F[3, 3] = 1,
F[3, 4] = 1,
F[3, 5] = 1,
F[3, 6] = 1

F[2, 2] = 4,
F[2, 3] = 3,
F[2, 4] = 2

F[1, 1] = 9,
F[1, 2] = 5

Using that F[i, j] table, we can find the desired element in O(N^ 2). And remember to be careful for very big integers that we can’t store in the primitive data types in our programs.

1 Like
13

Thanks for the link, google translates that languege quit well (as far as I can see)
http://translate.google.sk/translate?hl=sk&sl=auto&tl=en&u=http%3A%2F%2Fvn.spoj.com%2Fproblems%2FCHUOIHAT%2F :wink:

I didn’t get your description of F, as I understood your description F[3, 4] = 3, { 1 2 4, 1 3 4, 2 3 4 }.

14

no no no, look at the formula again, and you can see that I consider the positions from i to N. Therefore, F[3, 4] = 1: the number of elements, considering from 3rd (which is i) to 3rd (N) positions, the 3rd number (i) = 4 (j)

15

So the length of those elements is only one: 3 or 4 or 5 or 6. We didn’t care about the numbers in front of those yet. Now we just worry about the possible appearances of “the last column” without anything before them.