hoco's blog

spoj _ nested dolls
By hoco, 13 years ago, In English

hi everybody, about this problem + if any body solved it, plz share his code.

My algorithm is to use LIS and see how many distinct "Increasing sequences" there is. but I think it's hard to code. does any body have any easier algorithm?

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
13 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Nested Dolls

You're gonna need to take a look here Online Algorithms for Dilworth's Chain Partition and here Dilworth's theorem, and I think you will get it...

→ Reply
»
13 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

http://ncpc.idi.ntnu.no/ncpc2007/ncpc2007solutions.pdf

→ Reply
»
13 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Find The Longest Decreasing Subsequence But keep in mind that you can take 2 equal values like 3 3 2 2 1 1 is a valid decreasing subsequence

→ Reply
»
13 years ago, hide # |
← Rev. 2  
Vote: I like it +6 Vote: I do not like it

It is my solution :
Prerequisite : range tree
MAXN = 1000 highest value of width and height
T[1000] is array and all elemnt of T is zero
query(x, 1, MAXN, 1) = find the biggest number which is small or equal to x
upd(x, y, 1, MAXN, 1) is T[x] = y; 

    scanf("%d",&n);

    for(int h=0; h<n; h++)
    {
       int a, b;
       scanf("%d %d",&a,&b);
       D[a].push_back(b);
    }

    for(int h=1; h<=MAXN; h++)
    {
       for(int j=0; j<(int)D[h].size(); j++)
       {
         int k = query(D[h][j]-1, 1, MAXN, 1);

         L[k]--;

         if(!L[k])    upd(k, 0, 1, MAXN, 1);
       }

       for(int j=0; j<(int)D[h].size(); j++) upd(D[h][j], D[h][j], 1, MAXN, 1),L[D[h][j]]++;
    }

    for(int h=1; h<=MAXN; h++) ans += L[h];

    printf("%d\n",ans);
→ Reply
»
12 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

my greedy approach

→ Reply