hoco's blog

spoj _ nested dolls
By hoco, 12 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?
»
12 years ago, # |
  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
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think your first link has a problem.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      At least for me it works, its a pdf file...

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        mine doesn't

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          it's working on my machine well too. I uploaded the file in another host ... maybe it'll help you :)

          link

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

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The solution in the editorial is easier. O(NlogK), where K is the length of largest antichain.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please tell me in which editorial I will get it. I am stuck with the same problem.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Its the one sparik1997 posted. Check the solution of problem G.

        → Reply
»
12 years ago, # |
  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
»
11 years ago, # |
← 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
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

my greedy approach

→ Reply