Page 1 of 1
1196 - Tiling Up Blocks
Posted: Tue Oct 22, 2013 3:29 pm
by 300pounddog
Hi there. I can't seem to find out whats causing the WA with my code. Help please?
Also, any tips on troubleshooting effectively? I think I am weak in thinking of the corner cases...
Thanks a lot.
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,temp,maxx;
vector< pair<int,int> > blocks;
vector<int> dp;
struct sort_pred {
bool operator()(const std::pair<int,int> &left, const std::pair<int,int> &right) {
if(left.first == right.first) return left.second < right.second;
return left.first < right.first;
}
};
int main(){
scanf("%d",&n);
do{
maxx=0;
blocks.clear();
blocks.assign(n,make_pair(0,0));
dp.clear();
dp.assign(n,0);
for(int w=0;w<n;w++){
scanf("%d %d",&blocks[w].first,&blocks[w].second);
}
sort(blocks.begin(), blocks.end(), sort_pred());
dp[0] = 1;
for(int q=1;q<n;q++){
for(int w=0;w<q;w++){
if(blocks[q].first >= blocks[w].first && blocks[q].second >= blocks[w].second){
dp[q] = max(dp[q],dp[w]+1);
if(dp[q]>maxx)maxx=dp[q];
}
}
}
printf("%d\n",maxx);
scanf("%d",&n);
}while(n!=0);
printf("*\n");
return 0;
}
Re: 1196 - Tiling Up Blocks WA
Posted: Tue Oct 22, 2013 10:17 pm
by brianfry713
Try a case where n = 1.
Re: 1196 - Tiling Up Blocks WA
Posted: Wed Oct 23, 2013 1:18 am
by 300pounddog
brianfry713 wrote:Try a case where n = 1.
Oh silly me. Thanks a ton. ACed immediately!
Re: 1196 - Tiling Up Blocks WA
Posted: Tue Dec 03, 2013 2:51 am
by brianfry713
That is AC code
Re: 1196 - Tiling Up Blocks WA
Posted: Mon Jul 14, 2014 7:54 pm
by Neo_1234
GOT AC ..
MANY MANY THANKS TO BRIANFRY
Re: 1196 - Tiling Up Blocks WA
Posted: Tue Jul 15, 2014 8:30 pm
by brianfry713
Change line 14 to:
return (p.l > l || (p.l == l && p.m > m));
Re: 1196 - Tiling Up Blocks
Posted: Tue Sep 16, 2014 5:33 pm
by lawrencealgorithm
Anyone help me please!! My code is now Wrong Answer, however, I can't find anything wrong in my code. I know my code is long, but please help me troubleshoot this. Thank you very much.
Code: Select all
var
l,m:array[1..10000] of integer;
d:array[0..10001] of integer;
n,k:integer;
procedure enter();
var
i:integer;
begin
readln(n);
for i:=1 to n do readln(l[i],m[i]);
end;
procedure swap(var x,y:integer);
var
tmp:integer;
begin
tmp:=x;
x:=y;
y:=tmp;
end;
procedure sort(lt,rt:integer);
var
i,j,pp:integer;
pvt1,pvt2:integer;
begin
i:=lt;
j:=rt;
pp:=random(rt-lt+1)+lt;
pvt1:=l[pp];
pvt2:=m[pp];
repeat
while (l[i]<pvt1) or ((l[i]=pvt1) and (m[i]<pvt2)) do inc(i);
while (l[j]>pvt1) or ((l[j]=pvt1) and (m[j]>pvt2)) do dec(j);
if (i<=j) then
begin
swap(l[i],l[j]);
swap(m[i],m[j]);
inc(i);
dec(j);
end;
until (i>j);
if (lt<j) then sort(lt,j);
if (i<rt) then sort(i,rt);
end;
function search(x:integer):integer;
var
lt,rt,mid:integer;
begin
lt:=1;
rt:=k;
while (lt<=rt) do
begin
mid:=(lt+rt)>>1;
if (x>=d[mid-1]) and (x<d[mid]) then exit(mid);
if (x>=d[mid-1]) then lt:=mid+1 else rt:=mid-1;
end;
exit(-1);
end;
procedure solve();
var
i,j:integer;
begin
sort(1,n);
k:=1;
d[0]:=0;
d[1]:=10001;
for i:=1 to n do
begin
j:=search(m[i]);
d[j]:=m[i];
if (j=k) then
begin
inc(k);
d[k]:=10001;
end;
end;
writeln(k-1);
end;
procedure main();
begin
randomize;
while (true) do
begin
enter();
if (n=0) then
begin
write('*');
break;
end;
solve();
end;
end;
begin
main();
end.
Re: 1196 - Tiling Up Blocks
Posted: Tue Sep 16, 2014 8:46 pm
by brianfry713
Always print a newline char at the end of the last line.
Re: 1196 - Tiling Up Blocks
Posted: Wed Sep 17, 2014 11:50 am
by lawrencealgorithm
brianfry713 wrote:Always print a newline char at the end of the last line.
Thank you very much. I'm AC now.
Re: 1196 - Tiling Up Blocks
Posted: Sun Feb 01, 2015 8:47 pm
by bradd123
Why Runtime Error for this code? I can't figure out.
Code: Select all
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAX 10010
struct block{
int l;
int m;
};
block a[MAX];
int val[MAX];
bool compare(const block& lhs, const block& rhs){
return lhs.l<=rhs.l;
}
int lis(int n){
if(n==0) return val[n]=1;
if(val[n]!=-1) return val[n];
int max=0;
for(int i=0;i<n;i++){
if(a[i].m<=a[n].m){
int temp=lis(i);
if(max<temp) max=temp;
}
}
return val[n]=max+1;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n;
while(scanf("%d",&n)&&n!=0){
memset(val,-1,sizeof val);
for(int i=0;i<n;i++){
scanf("%d %d",&a[i].l,&a[i].m);
}
sort(a,a+n,&compare);
int total=0;
for(int i=0;i<n;i++){
int temp=lis(i);
if(total<temp) total=temp;
}
printf("%d\n",total);
}
printf("*\n");
}
Re: 1196 - Tiling Up Blocks
Posted: Mon Feb 02, 2015 11:42 pm
by brianfry713
bradd123, I changed your compare function:
https://ideone.com/zumUOn