hoco's blog

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

| 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...

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

    i think your first link has a problem.

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

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

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

        mine doesn't

        • »
          »
          »
          »
          »
          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

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    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.

    • »
      »
      »
      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.

      • »
        »
        »
        »
        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.

»
11 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

»
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);
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it