11368 - Nested Dolls

jahideu · Post by **jahideu** » Sun Dec 02, 2007 8:47 am

Hi to all,
Can anyone tell me what is the trick is here?
Give me some input.[/i]

sclo · Post by **sclo** » Sun Dec 02, 2007 8:04 pm

Greedy. I used a multiset to implement it.

tajbir2000 · Post by **tajbir2000** » Fri Jan 23, 2009 6:35 pm

#include<stdio.h>
#include<stdlib.h>

typedef struct{
	int H,W;
}doll;

doll d[20002];

compare_function(const void *a,const void *b){
	doll *x= (doll *)a;
	doll *y= (doll *)b;

	if(x->W != y->W)return x->W - y->W;
	else return x->H-y->H;
}


int main(){
	int cas,n_doll,i,j,k,count;

	scanf("%d",&cas);
	while(cas--){
		scanf("%d",&n_doll);
		for(i=0;i<n_doll;i++)
			scanf("%d %d",&d[i].W,&d[i].H);

		qsort(d,n_doll,sizeof(doll),compare_function);

		count=1;
		for(i=0;i<n_doll-1;i++){
			if(d[i].H>d[i+1].H || d[i].H == d[i+1].H || d[i].W>d[i+1].W || d[i].W == d[i+1].W)
				count++;

		}
		printf("%d\n",count);
	}
	return 0;
}

pls help me.......

tajbir2000 · Post by **tajbir2000** » Fri Jan 23, 2009 7:35 pm

i have got some problems of my code
input.
1
3
9 6 10 5 10 7

output
2

(9 6,10 7)and(10 5)

but my code gives.
3

dibery · Post by **dibery** » Fri Feb 07, 2014 7:16 pm

Another test for someone who may stuck.

Input:
1
4
10 20
10 30
15 40
18 25

Output:
2

cutenemo · Post by **cutenemo** » Tue Feb 11, 2014 5:49 am

I'm getting WA for this one.

I've tried the following cases and I get them all correct. any more cases?

Code: Select all

1000
 3
 20 30 40 50 30 40
 4
 20 30 10 10 30 20 40 50
 3
 10 30 20 20 30 10
 4
 10 10 20 30 40 50 39 51
 7
 10 10 20 20 30 30 10 10 20 20 10 10 10 10
 5
 10 10 10 10 10 10 10 10 10 10
 3
 9 6 10 7 10 5
 4
 10 20 10 30 15 40 18 25
 4
 10 10 20 20 10 10 20 20
 Sample Output
 1
 2
 3
 2
 4
 5
 2
 2
 2

cutenemo · Post by **cutenemo** » Tue Feb 11, 2014 5:59 am

I just saw that the problem is on the UVa toolkit. I will check it.

Repon kumar Roy · Post by **Repon kumar Roy** » Fri Oct 10, 2014 5:50 pm

Getting TLE ..
My algo is :
1.Sorting in increasing order of w
2.Then use LISNLogk() , to find LIS in h, and delete the dolls of the LIS ,
3.Repeating Step 2 till all the dolls are deleted

Code: Select all



#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<iterator>
#include<cassert>
#include <sstream>
#include <climits>
#include <list>
#include <string>
using namespace std;

/*------- Constants---- */
#define MX 21000
#define ll long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define FOR(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
/* -------Global Variables ------ */
ll x,y,d;

/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;

/*------ template functions ------ */
template < class T > inline T gcd(T a , T b ) { if(b==0) return a; else return gcd(b, a%b);}
template < class T > inline T lcm(T a , T b ) { return  a*b / gcd(a, b);}
template < class T > inline T extended_euclid_returning_gcd(T a,T b){ T t; if(b==0){d = a;x=1;y=0;} else {extended_euclid_returning_gcd(b, a%b); t=x; x=y;y = t-(a*y/b);}}
template < class T > inline T absolute(T a ) { if(a>0) return a; else return -a;}
template < class T > inline T reverse_num( T a ){ T x=0,tmp = a; while(tmp) { x=10*x+ tmp % 10; tmp/=10;} return x;}
template <class T > inline T big_mod(T base, T power){ T res=1; while (power) { if(power&1){ res*=base; power--;} base =base *base; power/=2;} return res;}

struct Node {
	int wid , hi;
	Node(){}
	Node(int a , int b ) {wid = a ; hi = b;}
	
	bool operator < (const Node &a) const {
		if( wid <  a.wid) return true;
		return false;
	}
	
};
Node arr[MX];
int L[MX];
int n;
int I[MX];
int del[MX];

int lisNLogK()
{
	I[0] = -19999900;
	for( int i = 1 ; i <=n ; i ++){
		I[i] = 1000000000;
	}
	
	int lisLen = 0;
	for( int i = 0 ; i < n ; i ++){
		if ( del[i]==1 ) continue;
		int low = 0 , high = lisLen , mid;
		while (low <= high) {
			mid = (low + high) /2 ;
			
			if ( I[mid ] < arr[i].hi ) low = mid + 1;
			else high = mid -  1;
		}
		
		I[low] = arr[i].hi;
		L[i] = low;
		if( low > lisLen){
			lisLen = low ;
		}
	}
	
	for ( int i = n-1 , k = lisLen; i >= 0 ; i --){
		if( L[i]== k && del[i] == 0){
			k --;
			del[i] = 1;
		}
	}
	return lisLen;
}
int main()
{
	int test , a , b;
	
	cin >> test;
	
	while (test --) {
		cin >> n;
		for ( int i  = 0 ; i < n ; i++){
			cin >> a >> b;
			arr[i] = Node(a, b);
		}
		sort(arr, arr + n);
		
		int lis =0;
		int ans= 0;
		while (lis <n) {
			lis += lisNLogK();
			ans ++;
			
		}
		
		cout<< ans << endl;
		ms(del, 0);
	}
	
	
	return 0;
}

brianfry713 · Post by **brianfry713** » Sat Oct 11, 2014 2:19 am

Here is one way to solve it, you could swap h and w.

Sort in non-increasing order of h. If two dolls have the same h, sort them in non-decreasing order of w.
Maintain a sorted array of available doll's w, initially empty.
Iterate through the dolls. Using a binary search, find the smallest available w greater than the current w and replace it with the current w. If none are available, increase the output count and add the current w to the end of the array.

Each test case can be solved in O(m log m).

anacharsis · Post by **anacharsis** » Tue Nov 17, 2015 7:14 pm

Some I/O

In:

Code: Select all

AC Out:

Code: Select all

OJ Board