10043 - Chainsaw Massacre

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

Moderator: Board moderators

Cloud
New poster
Posts: 10
Joined: Sat Dec 29, 2001 2:00 am
Contact:

10043 - Chainsaw Massacre

Post by Cloud » Thu Feb 28, 2002 8:17 pm

Help me plz :sad:

Code: Select all

/* @JUDGE_ID: xxxxx 10043 C++ */
#include <iostream.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define maxn 5000

typedef int (*fptr)(const void*, const void*);

struct point {
  int x,y;
} p[maxn];

int cmp(point *a,point *b) {
  return (*a).x - (*b).x;
}

int n,i,j,k;
int l,w,u,v;
int num;

void add(int xx,int yy) {
  p[n].x = xx, p[n++].y = yy;
  p[n].x = xx, p[n++].y = 0;
  p[n].x = xx, p[n++].y = w;
  p[n].x = 0, p[n++].y = yy;
  p[n].x = l, p[n++].y = yy;
}

int main() {
  cin >> num;
  while (num--) {
    cin >> l >> w;
    n = 4;
    p[0].x = 0, p[0].y = 0;
    p[1].x = l, p[1].y = 0;
    p[2].x = 0, p[2].y = w;
    p[3].x = l, p[3].y = w;
    while (cin >> k) {
      if (k == 0) break;
      cin >> u >> v;
      int dx = 0, dy = 0;
      if (k > 1) cin >> dx >> dy;
      for (i = 0; i < k; i++) add(u,v), u += dx, v += dy;
    }
    qsort((void *)p,n,sizeof(p[0]),(fptr)cmp);
    int maxs = 0;
    for (i = 0; i < n; i++) {
      int u = w, d = 0, j = i;
      int found;
      while (j < n - 1) {
	found = 0;
	while (++j) {
	  if (p[i].x < p[j].x) {
	    if (p[i].y >= p[j].y && p[j].y >= d) found = 1;
	    if (p[i].y <= p[j].y && p[j].y <= u) found = 2;
	  }
	  if (found || j == n - 1) break;
	}
	int tmp = (p[j].x - p[i].x) * (u - d);
	maxs = maxs > tmp ? maxs : tmp;
	if (found == 1) d = p[j].y;
	if (found == 2) u = p[j].y;
      }
    }
    cout << maxs << endl;
  }
  return 0;
}

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Post by shahriar_manzoor » Fri Mar 01, 2002 4:04 am

Send me a mail with your code attached.
address: shahriar@neksus.com

jaivasanth
New poster
Posts: 10
Joined: Tue Nov 26, 2002 4:19 pm

10043 Chainsaw massacre No idea please help....

Post by jaivasanth » Wed Nov 27, 2002 3:55 pm

I have no idea as to how to go about solving this problem...
Is there a DP soln... please explain.....

arnsfelt
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:

Post by arnsfelt » Wed Nov 27, 2002 10:32 pm

No, DP doesn't lead to a good solution.
Instead, a sweep-style algorithm is needed.
Aim at an O(n^2) time algorithm.

WARNING: Spoiler follows:








Consider the largest empty rectangle.
There are two cases:
1) Left edge is the left border of the forest.
2) There is a tree on the left edge.

Case 1 is a special case to be handled seperately.

Now for case 2:
For each point we perform a sweep.
During the sweep we maintain two y-coordinates representing
the upper and lower edge of the optimal rectangle having the first point
on the left edge and the current point on the right edge.

Now, only thing left is to handle case 1) and to figure out how to update

jaivasanth
New poster
Posts: 10
Joined: Tue Nov 26, 2002 4:19 pm

thanx...

Post by jaivasanth » Mon Dec 02, 2002 9:20 am

Thanx.. i was able to figure out the code...

Nak
New poster
Posts: 14
Joined: Sat Oct 26, 2002 5:59 am
Location: Sweden

Incorrect testdata?

Post by Nak » Sun Dec 15, 2002 11:55 am

I think the testdata in this problem is incorrect :-(

My assert(n_trees <= 1000); fails, without it i get accepted.

GigS
New poster
Posts: 2
Joined: Sat Feb 08, 2003 2:34 am

Post by GigS » Sat Feb 08, 2003 2:39 am

you must use bigger array ( 5050 should be ok ;) in that version.

but really you need only that points :

p[n].x = xx, p[n++].y = yy;
p[n].x = 0, p[n++].y = yy;

so array can be 2020

If you add all five points, you will get time limit exceeded.
#gadu gadu 35622

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Mon Feb 23, 2004 11:11 am

I think it should be noted that there are definitely MORE than 1000 trees. In fact, if I set my program's limit to 1000 trees, it gives WA. When I changed it to 5000 trees, I get AC.

I doubt you need 5000 trees, probably 2000 will do, but I'm too lazy to keep trying. :p

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Sat May 08, 2004 10:50 pm

i tried to do this sweep with all points including (0,0) in order to check for a border on the left side of our map.... though i keep on WA.... any test cases? tips? advices? code help?

the algo is (kinda) exactly what was described.... but I surely missed something

[cpp]#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int l,w;

vector<int*> p;
int pc;
int m;

void area(int p1, int x1, int y1, int p2, int y2) {

// cout << "new call: " << p1 << " and " << p2;
// cout << "\t\t(" << x1 << "," << y1 << ")\t(" << p[p2][0] << "," << y2 << ")" << endl;

int pn = p2 + 1;
while(pn!=pc && (p[pn][0]<p[p2][0] || p[pn][1]>y2 || p[pn][1]<y1)) {
pn++;
}

if(pn==pc) {
// so i got to the right border
int area1 = (l - x1) * (y2 - y1);
// cout << "right border area: " << area1 <<endl;
if(area1>m) {
m = area1;
}
return;
}


//cout << "next point at my right side: " << p[pn][0] << "," << p[pn][1] << endl;

// lets test if this area is bigger than the previous ones
int area1 = (y2 - y1) * (x1 - p[pn][0]);
if(area1>m) {
m = area1;
// cout << x1 <<","<<y1 << " e " << p[pn][0] << ","<<y2<<":" << area1 << endl;
}

if((p[pn][1] - y1) * (l-x1) > m) {
// this point will be my uppermost border
area(p1,x1,y1,pn,p[pn][1]);
}

if((y2 - p[pn][1]) * (l-x1) > m) {
// this point will be my bottom
area(p1,x1,p[pn][1],pn,y2);
}

}

bool ordena(const int *i1, const int *i2) {
return i1[0] < i2[0];
}

void executa() {

// if there are no points, its nice
if(pc==0) { cout << (l*w) << endl; return; }

/* cout << l << " x " << w << endl;
cout << pc << " trees"<< endl;*/

m = 0;

// adds a new point at 0,0
int iz[2];
iz[0] = 0;
iz[1] = 0;
p.push_back(iz);
pc++;

sort(p.begin(),p.end(),ordena);

// for(int i=0;i!=pc;i++) {
// cout << "tree #" << (i+1) <<": (" <<p[0] << "," << p[1] << ")"<<endl;
// }

int i,i2;
for(int i=0;i!=pc;i++) {
if(i!=0 && p[0]==p[i-1][0]) continue;
// cout << "\n\n\nstarting with tree number " << (i+1) << endl;
area(i,p[0],0,i,w);
}

cout << m << endl;
}

int main() {

int c,k,bx,by,dx,dy;
cin >> c;
while(c--!=0) {
pc = 0;
cin >> l >> w;
p.clear();
while(true) {
cin >> k;
if(k==0) break;
if(k==1) {
int *k = new int[2];
cin >> k[0] >> k[1];
if(k[0]==0 || k[0]==l || k[1]==0 || k[1]==w) continue;
p.push_back(k);
pc++;
continue;
}
cin >> bx >> by >> dx>>dy;
bx -= dx; by -= dy;
while(k--!=0) {
int *k = new int[2];
k[0] = (bx += dx);
k[1] = (by += dy);
if(k[0]==0 || k[0]==l || k[1]==0 || k[1]==w) continue;
p.push_back(k);
pc++;
}
}
executa();
}

}[/cpp]

d91-lek
New poster
Posts: 22
Joined: Thu Sep 16, 2004 2:25 am
Location: KTH, Stockholm
Contact:

Post by d91-lek » Fri Nov 12, 2004 7:08 pm

This is a problem:

Code: Select all

2
5 2
1 2 1
0
5 2
1 3 1
0
Answer:

Code: Select all

6
6
Whereas your code gives:

Code: Select all

6
5

xavier_lt
New poster
Posts: 2
Joined: Sun May 06, 2007 7:06 am

Post by xavier_lt » Sun May 06, 2007 7:13 am

could anybody give me more test datas ? I cannot get through this problem. here is my code : ( sorry for my poor english. )

Code: Select all

code deleted
Last edited by xavier_lt on Mon May 07, 2007 3:40 am, edited 1 time in total.

xavier_lt
New poster
Posts: 2
Joined: Sun May 06, 2007 7:06 am

Post by xavier_lt » Mon May 07, 2007 3:40 am

Left edge is the left border of the forest.
i haven't noticed that .... ac now....

mack_attack
New poster
Posts: 3
Joined: Mon May 05, 2014 11:10 pm

10043 - Chainsaw Massacre WA???

Post by mack_attack » Mon May 05, 2014 11:19 pm

Hi All

I keep getting WA when I try to submit an answer to 10043.
I've tested with the example input and I get the expected output, I even created a few more myself and always get the right answer.

I also noticed that my initial code that expected no more than 1000 trees (like the puzzle states) kept getting a Runtime Error.
I increased it to 2048 (too be safe) and now it runs but gets WA and I dont no why.

So wondering if the format of the input data is different from the specified one on the puzzle.

Any suggestions or extra test data?

Thanks

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

Re: 10043 - Chainsaw Massacre WA???

Post by brianfry713 » Wed May 07, 2014 9:22 pm

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

mack_attack
New poster
Posts: 3
Joined: Mon May 05, 2014 11:10 pm

Re: 10043 - Chainsaw Massacre WA???

Post by mack_attack » Wed May 07, 2014 9:57 pm

I looked at that post, I tried increasing my maximum tree count which just stopped me from getting Runtime error and took me to the Wrong Answer stage, and I tried the test data they gave with mine and it worked. There must be a special edge case that my solution doesn't work for.

I've tried, empty paddock, paddock with only trees on the borders, paddock with 1 tree, random generated paddock, paddock with the largest area completely enclosed with trees.

Its always returns the expected result. I can't think of any other cases could fail on.

Post Reply

Return to “Volume 100 (10000-10099)”