pistone's blog

spoj problem : https://www.spoj.pl/problems/BABTWR/
By pistone, 13 years ago, In English

my approach is to create 3 rotations for each box  and sort the boxes according to increasing base area.

Then run LIS on the sorted data.

it gives correct results for test samples in the problem , still getting WA.

Need help !!!!

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Well, your approach is indeed correct, I've got AC with a similar solution.
However, what do you mean by LIS here? You should build the highest tower in terms of height, not a number of blocks.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    here after doing LIS , i add the heights of blocks in the LIS array.
    so the sum of heights of the blocks in LIS sequence is the maxheight .

    may be i am wrong in my approach
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Well, you can look at my code, if you want to:
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        hey thanks , got it

        but just for discussion sake  here is my code , can u find out the problem :


        // babtower.cpp : Defines the entry point for the console application.
        //

        //#include "stdafx.h"
        #include <iostream>
        #include <cstdio>
        #include <cstdlib>
        #include <vector>
        #include <set>
        #include <string>
        #include <algorithm>
        using namespace std;

        typedef struct{
         int length;
         int width;
         int height;
        }s;

        bool compare(const s& s1,const s& s2)
        {
         if((long long)(s1.length * s1.width) != (long long)(s2.length * s2.width));
             return (s1.length * s1.width < s2.length * s2.width);

         if(s1.width != s2.width)
          return (s1.width < s2.width);
         
         if(s1.length != s2.length)
          return (s1.length < s2.length);
         
         return s1.height < s2.height;
        }


        int main()
        {
         int i,j,k,l,n;
         int a,b,c,t;
            vector<s> v(200);
         
         int best[200];
            int pred[200];
         vector<int> in(200);
        while(cin>>n,!cin.eof())
        {
         if(n == 0)
          break;
         i = 0;
         
         j = 0;
         s temp;
         getchar();
         while(i < n)
         {
          cin>>a>>b>>c;

         
          if( a < b)
            {
             temp.length = a; temp.width = b ; temp.height = c;

             }
          else
            {
             temp.length = b; temp.width = a ; temp.height = c;

             }
            v[j++] = temp;
               if(a < c)
            {

                   temp.length = a; temp.width = c ; temp.height = b;


            }
            else
            {

              temp.length = c; temp.width = a ; temp.height = b;

            }
            v[j++] = temp;
            if(b < c)
            {

                    temp.length = b; temp.width = c ; temp.height = a;
           
            }
            else
            {
              temp.length = c; temp.width = b ; temp.height = a;
            }
            v[j++] = temp;

            i++;
         }

         
         for(i=0;i<j;i++)
         {
          best[i] = 1;
          pred[i] = i;
         }
         sort(v.begin(),v.begin() +j,compare);
         

         int maxheight = 0;
         for(i=1;i < j;i++)
         {
          for(k =0;k< i;k++)
          {

           if(v[i].length > v[k].length && v[i].width > v[k].width)
                    {
            if(best[i] < best[k] + 1)
            {

             best[i] = best[k] + 1;
             pred[i] = k;
            }


           }
           //cout<<best[i]<<endl;
          }

         

         }

         int max=0;
         int pos=-1;
         for(i=0;i< j;i++)
         {
          if(max < best[i] ){
           max = best[i];
           pos = i;
          }

         }
         
         int u , w;
         
         for(u = max,w=pos;u--;w = pred[w])in[u] = w;
         for(u =0;u< max;u++)
         {
          maxheight += v[in[u]].height;
         }
         cout<<maxheight<<endl;
         
        }
         return 0;
        }

        → Reply