1196 - Tiling Up Blocks

All about problems in Volume 11. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

300pounddog
New poster
Posts: 4
Joined: Tue Oct 22, 2013 1:57 am

1196 - Tiling Up Blocks

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;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1196 - Tiling Up Blocks WA

Try a case where n = 1.
Check input and AC output for thousands of problems on uDebug!

300pounddog
New poster
Posts: 4
Joined: Tue Oct 22, 2013 1:57 am

Re: 1196 - Tiling Up Blocks WA

brianfry713 wrote:Try a case where n = 1.
Oh silly me. Thanks a ton. ACed immediately!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1196 - Tiling Up Blocks WA

That is AC code
Check input and AC output for thousands of problems on uDebug!

Neo_1234
New poster
Posts: 3
Joined: Sat Jan 11, 2014 2:43 pm

Re: 1196 - Tiling Up Blocks WA

GOT AC ..
MANY MANY THANKS TO BRIANFRY
Last edited by Neo_1234 on Fri Nov 28, 2014 4:59 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1196 - Tiling Up Blocks WA

Change line 14 to:
return (p.l > l || (p.l == l && p.m > m));
Check input and AC output for thousands of problems on uDebug!

lawrencealgorithm
New poster
Posts: 2
Joined: Tue Sep 16, 2014 5:15 pm

Re: 1196 - Tiling Up Blocks

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.

``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1196 - Tiling Up Blocks

Always print a newline char at the end of the last line.
Check input and AC output for thousands of problems on uDebug!

lawrencealgorithm
New poster
Posts: 2
Joined: Tue Sep 16, 2014 5:15 pm

Re: 1196 - Tiling Up Blocks

brianfry713 wrote:Always print a newline char at the end of the last line.
Thank you very much. I'm AC now.

bradd123
New poster
Posts: 17
Joined: Thu Jul 03, 2014 11:13 am

Re: 1196 - Tiling Up Blocks

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");
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1196 - Tiling Up Blocks

bradd123, I changed your compare function: https://ideone.com/zumUOn
Check input and AC output for thousands of problems on uDebug!