## 201 - Squares

Moderator: Board moderators

dedeibel
New poster
Posts: 3
Joined: Sun Mar 13, 2005 11:39 pm
Location: Germany
Contact:
Ah, thx.
I will give it another try.

But the problem didn't seem that hard to me. But now indeed bugy.

How to reset my stats?
so little time ...

57761RF
New poster
Posts: 1
Joined: Sun Apr 24, 2005 1:36 am

### 201 why don't work!

I don't Know Why don't work my program, I put it the most difficult input (a 9x9 square with all the arists) in it and solve it right.

input:

9
144
H 1 1
H 1 2
H 1 3
H 1 4
H 1 5
H 1 6
H 1 7
H 1 8
H 2 1
H 2 2
H 2 3
H 2 4
H 2 5
H 2 6
H 2 7
H 2 8
H 3 1
...
V 9 6
V 9 7
V 9 8

Output:

64 square (s) of size 1
49 square (s) of size 2
36 square (s) of size 3
25 square (s) of size 4
16 square (s) of size 5
9 square (s) of size 6
4 square (s) of size 7
1 square (s) of size 8

It's correct isn't it?

I don't know how I can subdue it, please I need help.

someone2
New poster
Posts: 10
Joined: Tue Jul 05, 2005 5:22 pm

### problem 201 (Squares) driving me crazy with WA!

Hi,
I have solved some problems before but this one is drving me crazy. Could someone who solved it give me just one counter example to this code? What is the trick in the judge's input? No matter what I try, it always gives a correct answer

Code: Select all

``````#include <iostream>
#include <stdio.h>

using namespace std;

#ifdef ONLINE_JUDGE
#define Fin stdin
#define Fout stdout
#else
#define Fin f1
#define Fout f2
#endif

int countSquares[90];
int H[90][80]; //Horizontal pieces just a 0 or a 1
int V[80][90]; //Vertical pieces just a 0 or a 1

int n; //number of dots

//check for a square starting at row,col and size "size"
char checkSquare(int size,int row,int col)
{
if(row+size>=n) return 0;
if(col+size>=n) return 0;

//upper horizontal part
for(int i=0;i<size;i++)
if(!H[row][col+i])
return 0;

//lower horizontal part
for(int i=0;i<size;i++)
if(!H[row+size][col+i])
return 0;

//right vertical part
for(int i=0;i<size;i++)
if(!V[row+i][col])
return 0;
//left vertical part
for(int i=0;i<size;i++)
if(!V[row+i][col+size])
return 0;

return 1;
}

int main(void)
{
#ifndef ONLINE_JUDGE
FILE* f1=fopen("squares.in","r");
FILE* f2=fopen("squares.out","w");
#endif
int nEdges;
int probNo=0;
while(1)
{
probNo++;
if(fscanf(Fin,"%d\n%d\n",&n,&nEdges)!=2)
break;
if(probNo!=1)
fprintf (Fout,"\n**********************************\n\n");

//reset edges
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
{
H[i][j]=0;
V[i][j]=0;
}
//reset square counter
for(int j=0;j<=n;j++)
countSquares[j]=0;

for(int i=0;i<nEdges;i++)
{
char c;
fscanf(Fin," %c",&c);
if(c=='H'||c=='h')
{
int x,y;
fscanf(Fin,"%d %d\n",&x,&y);
H[x-1][y-1]=1;
}
else if(c=='V'||c=='v')
{
int x,y;
fscanf(Fin,"%d %d\n",&x,&y);
V[y-1][x-1]=1;
}
else
while(1); //just to make sure the problem with the code is not an input problem. If there is a problem with the input, the program will fall in an infinte loop. (This doesn't happen)
}

for(int j=1;j<=n;j++)
{
for(int k=0;k<n;k++)
for(int m=0;m<n;m++)
if(checkSquare(j,k,m)) //check for all squares of all sizes
countSquares[j]++;
}

char found=0;
fprintf(Fout,"Problem #%d\n\n",probNo);
for(int i=1;i<=n;i++)
if(countSquares[i])
{
fprintf(Fout,"%d square (s) of size %d\n",countSquares[i],i);
found=1;
}

if(!found)
fprintf(Fout,"No completed squares can be found.\n");

}
#ifndef ONLINE_JUDGE
fclose(Fin);
fclose(Fout);
#endif

return 0;
}

``````

someone2
New poster
Posts: 10
Joined: Tue Jul 05, 2005 5:22 pm
Hmmm.. ok, I hate to say this, but I am officially challenging the online judge!!

I found the original judge test cases used in the ACM programming contest 1989 (This problem was part of it). The file contained 5008 test cases. I tried it, compared it to the judge output, and guess what? The files were identical. My program solved all 5008 problems correctly.

So? How could I still be getting wrong answer for this? Is there some kind of magic?

Too funny that out of THOUSANDS of problems, the second one I pick turns out to be like this!

Anyway, where can I file an official complaint against the judge? Thanks a lot

giuper
New poster
Posts: 1
Joined: Tue Aug 23, 2005 7:21 pm
Location: Salerno, Italy

### 201 Squares

Hi everybody,

I have a solution for 201 (Squares) that passes the test cases for the 1989 finals (available from http://contest.mff.cuni.cz/archive/finl1989/) but still I get WA from the judge.
Did this happen to any of you?

ausiva
New poster
Posts: 6
Joined: Sun Mar 12, 2006 7:01 pm

### Re: 201 Squares

I have the same problem...my output exactly matches with the output in the link...but still i get WA

Siva
giuper wrote:Hi everybody,

I have a solution for 201 (Squares) that passes the test cases for the 1989 finals (available from http://contest.mff.cuni.cz/archive/finl1989/) but still I get WA from the judge.
Did this happen to any of you?

nnahata
New poster
Posts: 6
Joined: Fri Sep 08, 2006 9:01 pm
Location: india
Contact:

### Why WA in 201 !!!!!

hi every one ..

My this code is working fine for every input case even the inputs which is given here for the same problem..

http://contest.mff.cuni.cz/cgi-bin/arch ... 9.tgz?b.in

But i m getting WA plz help me..

#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cassert>
#include <utility>

using namespace std;

#define EPS 1E-8
const int INF = (int)1E+9;

#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define forv(i, v) for (int i = 0; i < (int)(v.size()); ++i)
#define fors(i, s) for (int i = 0; i < (int)(s.length()); ++i)
#define all(a) a.begin(), a.end()
#define pb push_back
#define PII pair<int, int>
#define mp make_pair
#define VI vector<int>
#define VS vector<string>
main()
{
int n;
int z=1;
while(cin>>n)
{
if(z!=1)
{
cout<<"\n"<<"**********************************"<<endl;
cout<<"\n";

}
int sflag=0;
cout<<"problem #"<<z<<"\n"<<endl;
z++;
int nline;
cin>>nline;
bool V[n+1][n+1],H[n+1][n+1];
memset(V,false,sizeof(V));
memset(V,false,sizeof(V));
for(int i=0;i<nline;i++)
{
char c;
cin>>c;
int j,k;
cin>>j>>k;
if(c=='H')
H[k-1][j-1]=true;
if(c=='V')
V[j-1][k-1]=true;

}
for(int i=1;i<=n;i++)
{
int ans=0;
for(int j=0;j<n-i;j++)
{
//if(i==2)
//cout<<"ohmarham"<<j<<endl;
for(int k=0;k<n-i;k++)
{
int flag=0;
//if(i==2)
//cout<<"nahata1"<<j<<" "<<k<<" "<<flag<<endl;
for(int l=0;l<i;l++)
{
if(H[j+l][k]==false)
{flag=1;break;}
if(V[j][k+l]==false)
{flag=1;break;}
if(H[j+l][k+i]==false)
{flag=1;break;}
if(V[j+i][k+l]==false)
{flag=1;break;}
}
if(flag==0)
ans++;
}
}
if(ans!=0)
{cout<<ans<<" square (s) of size "<<i<<endl;sflag=1;}
}
if(sflag==0)
{
cout<<"No completed squares can be found."<<endl;

}
}
}

DIR EN GREY
New poster
Posts: 12
Joined: Thu Nov 09, 2006 11:49 am
You should try sample input which described in the problem statement as follow:

Code: Select all

``````4
16
H 1 1
H 1 3
H 2 1
H 2 2
H 2 3
H 3 2
H 4 2
H 4 3
V 1 1
V 2 1
V 2 2
V 2 3
V 3 2
V 4 1
V 4 2
V 4 3
2
3
H 1 1
H 2 1
V 2 1
``````
Do you understand my English???

nnahata
New poster
Posts: 6
Joined: Fri Sep 08, 2006 9:01 pm
Location: india
Contact:
sorry sir !
I didn't get your english .... plz make it more clear.....

DIR EN GREY
New poster
Posts: 12
Joined: Thu Nov 09, 2006 11:49 am
nnahata wrote:sorry sir !
I didn't get your english .... plz make it more clear.....
sorry

I copy your source code and comple it by gcc 4.1.1. And I ran your program with input described above. It is sample input (see http://acm.uva.es/p/v2/201.html). So correct program will output as follows:

Code: Select all

``````Problem #1

2 square (s) of size 1
1 square (s) of size 2

**********************************

Problem #2

No completed squares can be found.
``````
Actually, however, your program outputed as follows:

Code: Select all

``````problem #1

3 square (s) of size 1
1 square (s) of size 2

**********************************

problem #2

No completed squares can be found.
``````
Please check sample input and ouput carefully!!
Do you understand my English???

nnahata
New poster
Posts: 6
Joined: Fri Sep 08, 2006 9:01 pm
Location: india
Contact:
ya now i got it.........thxs DIR EN GREY

oskarcah
New poster
Posts: 1
Joined: Sun Feb 18, 2007 5:28 pm
In the output test in http://contest.mff.cuni.cz/archive/finl1989/ there is a triling line of asterisks, after the output of each problem, even in the last one.

But in UVA online-judge, you must not output the asterisk line after the last promblem's output.
ORCC

alamgir kabir
New poster
Posts: 37
Joined: Wed Oct 03, 2007 10:42 am

### Re: Why WA in 201 !!!!!

Anyone help me to find my fault? I am getting WA a lot of times.
Have I done wrong in my algorithm
My algorithm.
*check unit size square is formed.(means vertically or horizontally connected)
a boolean type array is used to flaging for connection.

Code: Select all

``````#include<stdio.h>
bool flagH [ 10 ] [ 10 ], flagV[ 10 ] [ 10 ];

void init( int n )
{
int i, j;
for(i = 1; i <= n; i ++ )
{
for( j = 1; j <= n; j ++)
{
flagH [ i ][ j ] = false;
flagV [ i ][ j ] = false;
}
}
return;
}
bool isValid( int n, int r, int c )
{
if( r > 0 && r <= n && c > 0 && c <= n )
{
return true;
}
return false;
}

bool isVcon( int a, int b, int c, int d )
{
int i, j;

for( i = a; i <= c; i ++)
{
for( j = b; j <= d; j ++)
{
if( !flagV [ i ][ j ] )
{
return false;
}
}
}
return true;;
}

bool isHcon( int a, int b, int c, int d )
{
int i, j;

for( i = a; i <= c; i ++)
{
for( j = b; j <= d; j ++)
{
if( !flagH [ i ][ j ] )
{
return false;
}
}
}
return true;;
}

int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);

int n, m, i, row, col, unit, j, count, kase = 1, a = 0;
char str [ 100 ], c;
bool print;

while( gets( str ) )
{
if( a )
{
printf("\n**********************************\n\n");
}
a = 1;
sscanf(str, "%d", &n);
gets( str );
sscanf(str, "%d", &m);

printf("Problem #%ld\n\n", kase ++);

init( n );

for( i = 0; i < m; i ++)
{
gets( str );
sscanf(str, "%c %d %d", &c, &row, &col);
if( c == 'H' )
{
if( isValid ( n, row, col ) && isValid(n, row, col + 1 ))
{
flagH [ row ][ col ] = true;
flagH [ row ][ col  + 1 ] = true;
}
}
else
{
int temp = row;
row = col;
col = temp;

if( isValid ( n, row, col ) && isValid(n, row + 1, col ))
{
flagV [ row ][ col ] = true;
flagV [ row + 1 ][ col ] = true;
}
}
}

//unit = 1;
print = false;

for( unit = 1; unit <= n; unit ++)
{
count = 0;
for( i = 1; i <= n; i ++)
{
for( j = 1; j <= n; j ++ )
{
if( isValid( n, i, j + unit ) && isValid( n, i + unit , j) && isValid( n, i + unit, j + unit ))
{
//printf("%ld\n", unit);
if( isVcon( i, j , i + unit, j ) && isHcon(i, j, i, j + unit)
&& isHcon( i + unit, j, i + unit, j + unit ) && isVcon( i, j + unit, i + unit, j + unit)
)
{
//printf("%d %d\n", i, j);
count ++;
}
}
}
}
if( count > 0 )
{
print = true;
printf("%d square (s) of size %d\n", count, unit);
}
}
if( !print )
{
printf("No completed squares can be found.\n");
}
}

return 0;
}

``````
thanks.

joehuang92
New poster
Posts: 9
Joined: Sat Nov 18, 2006 4:56 pm
Location: Taiwan
Contact:

### RTE all the time...

Dear all:

It's my first time using java submission on uva, and just as a lot of posts have mentioned, i seem to get only RTE verdicts due to some unknown reasons...

I even trimmed my main function so that only one System.out.println function exists, the judge still gives me an RTE.

Any help with this? My code goes with problem 201.

Code: Select all

``````import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

class Main {

static void main(String[] argv)
{
begin();
}

static void begin()
{
int nProblem = 1;
int width, nEdges;

String sBuf;
int xBuf, yBuf;

Scanner stdin = new Scanner(System.in);
while (stdin.hasNext())
{
width = stdin.nextInt();
nEdges = stdin.nextInt();

MeshGrid grid = new MeshGrid(width - 1, width - 1);

for (int i = 0; i < nEdges; i++)
{
sBuf = stdin.next();
xBuf = stdin.nextInt() - 1;
yBuf = stdin.nextInt() - 1;

if (sBuf.compareTo("H") == 0)
{
int temp = xBuf;
xBuf = yBuf;
yBuf = temp;

grid.addEdge(grid.getPoint(xBuf, yBuf), grid.getPoint(xBuf + 1, yBuf));
}
else if (sBuf.compareTo("V") == 0)
grid.addEdge(grid.getPoint(xBuf, yBuf), grid.getPoint(xBuf, yBuf + 1));
}

int[] result = new int[width + 1];
for (int i = 1; i <= width; i++)
result[i] = grid.findSquares(i);

nProblem++;
}
}

private static void printAnswer(int serial, int[] result)
{
if (serial > 1)
{
System.out.println();
System.out.println("**********************************");
System.out.println();
}

System.out.println("Problem #" + serial);
System.out.println();

boolean noSquare = true;
for (int i = 0; i < result.length; i++)
{
if (result[i] > 0)
{
System.out.println(result[i] + " square (s) of size " + i);
noSquare = false;
}
}
if (noSquare)
System.out.println("No completed squares can be found.");
}
}

class Grid
{
private Point[][] points;

public Grid(int width, int height)
{
points = new Point[height + 1][width + 1];
for (int i = 0; i <= height; i++)
for (int j = 0; j <= width; j++)
points[i][j] = new Point(j, i);
}

public boolean inRange(int x, int y)
{
return (x >= 0 && x <= this.getWidth() && y >= 0 && y <= this.getHeight());
}

public Point getPoint(int x, int y)
{
if (inRange(x, y))
return this.points[y][x];
else
return null;
}

public int getHeight()
{
return this.points.length - 1;
}

public int getWidth()
{
return this.points[0].length - 1;
}

public Point getPoint(Point p, int dx, int dy)
{
if (inRange(p.getX() + dx, p.getY() + dy))
return this.points[p.getY() + dy][p.getX() + dx];
else
return null;
}
}
class MeshGrid extends Grid
{
private Set<Edge> edgeSet;

public MeshGrid(int width, int height)
{
super(width, height);
this.edgeSet = new HashSet<Edge>();
}

public void addEdge(Point p1, Point p2)
{
if (p1.compareTo(p2) >= 0)
{
Point temp = p1;
p1 = p2;
p2 = temp;
}

if (p1.getY() == p2.getY() && p2.getX() - p1.getX() == 1) // Adding a horizontal edge.
{
for (Point right = this.getPoint(p2, 1, 0); right != null; right = this.getPoint(right, 1, 0))
{
if (this.edgeSet.contains(new Edge(right, this.getPoint(right, -1, 0))))
else break;
}
for (Point left = this.getPoint(p1, -1, 0); left != null; left = this.getPoint(left, -1, 0))
{
if (this.edgeSet.contains(new Edge(left, this.getPoint(left, 1, 0))))
else break;
}
}
else if (p1.getX() == p2.getX() && p2.getY() - p1.getY() == 1) // Adding a vertical edge.
{
for (Point lower = this.getPoint(p2, 0, 1); lower != null; lower = this.getPoint(lower, 0, 1))
{
if (this.edgeSet.contains(new Edge(lower, this.getPoint(lower, 0, -1))))
else break;
}
for (Point upper = this.getPoint(p1, 0, -1); upper != null; upper = this.getPoint(upper, 0, -1))
{
if (this.edgeSet.contains(new Edge(upper, this.getPoint(upper, 0, 1))))
else break;
}
}
else
System.out.println("[MeshGrid] Error : Adding oblique edges or non-unit edges.");
}

public int findSquares(int width)
{
int count = 0;

for (int i = 0; i < this.getWidth() - width + 1; i++)
{
for (int j = 0; j < this.getHeight() - width + 1; j++)
{
Point leftTop = this.getPoint(i, j);
Point rightTop = this.getPoint(leftTop, width, 0);
Point leftBot = this.getPoint(leftTop, 0, width);
Point rightBot = this.getPoint(leftTop, width, width);
if (this.edgeSet.contains(new Edge(leftTop, rightTop)) &&
this.edgeSet.contains(new Edge(leftTop, leftBot)) &&
this.edgeSet.contains(new Edge(leftBot, rightBot)) &&
this.edgeSet.contains(new Edge(rightTop, rightBot)))
count++;
}
}

return count;
}

public String toString()
{
return this.edgeSet.toString();
}
}
class Edge
{
private Point start, end;

public Edge(int x1, int y1, int x2, int y2)
{
this(new Point(x1, y1), new Point(x2, y2));
}

public Edge(Point start, Point end)
{
if (start.compareTo(end) <= 0)
{
this.start = start;
this.end = end;
}
else
{
this.start = end;
this.end = start;
}
}

public Point getStartPoint()
{
return this.start;
}

public Point getEndPoint()
{
return this.end;
}

public String toString()
{
StringBuilder sb = new StringBuilder();

sb.append("[").append(this.start.toString()).append("--").append(this.end.toString()).append("]");

return sb.toString();
}

public boolean equals(Object o)
{
if (!(o instanceof Edge))
return false;

Edge e = (Edge) o;
return this.getStartPoint().compareTo(e.getStartPoint()) == 0 &&
this.getEndPoint().compareTo(e.getEndPoint()) == 0;
}

public int hashCode()
{
int result = 7;
result = 23 * result + this.getStartPoint().getX();
result = 23 * result + this.getStartPoint().getY();
result = 23 * result + this.getEndPoint().getX();
result = 23 * result + this.getEndPoint().getY();

return result;
}
}
class Point implements Comparable<Point>
{
private int x, y;

public Point(int x, int y)
{
this.x = x;
this.y = y;
}

public int getX()
{
return this.x;
}

public int getY()
{
return this.y;
}

public int compareTo(Point p)
{
return (this.x - p.x != 0) ? (this.x - p.x) : (this.y - p.y);
}

public String toString()
{
StringBuilder sb = new StringBuilder();

sb.append("(").append(this.x).append(",").append(this.y).append(")");

return sb.toString();
}
}
``````

daniellee
New poster
Posts: 2
Joined: Fri Sep 21, 2012 7:40 pm

### 201 Squares

It drives me crazy... I have tested several test cases with output OK but keep getting WA.

#include <iostream>
#include <string>
#include <fstream>

using namespace std;

typedef struct direct_t{
bool V;
bool H;
bool B;
} direct;

direct ** ary = NULL;

int numRect(int x, int y, int len);

int main(void)
{
int size, line;
int program = 0;
#ifdef DEBUG
ifstream myfile ("test");
if(myfile.is_open())
{
myfile >> size;
myfile >> line;
while(!myfile.eof())
#else //DEBUG
{
cin >> size;
cin >> line;
while(!cin.eof())
#endif //DEBUG
{
// cout << "size: " << size << ", line: " << line << endl;
ary = new direct*[size];
for(int i = 0; i < size; i++){
ary = new direct[size];
}
for(int i = 0; i < size; i++){
for(int j = 0; j < size; j++){
ary[j].V = false;
ary[j].H = false;
ary[j].B = false;
}
}

for(int i = 0; i < line; i++){
char x;
int t1, t2;
#ifdef DEBUG
myfile >> x >> t1 >> t2;
#else //DEBUG
cin >> x >> t1 >> t2;
#endif //DEBUG
t1--;
t2--;
if( x == 'V' ){
if(t2 >= size || t1 > size)
continue;
ary[t1][t2].V = true;
if( ary[t1][t2].H )
ary[t1][t2].B = true;
}
if( x == 'H' ){
if(t2 >= size || t1 > size)
continue;
ary[t2][t1].H = true;
if( ary[t2][t1].V )
ary[t2][t1].B = true;
}
}
bool hasRect = false;
cout << "Problem #" << ++program << endl << endl;
//1st loop represents length of each squares
//use i to represent length of each sub-rect. 1 <= i < size
for( int i = 1; i < size; i++){
int counter = 0;
for( int x = 0; x < size - i; x++){
for( int y = 0; y < size - i; y++){
counter += numRect(x,y,i);
}
}
if(counter > 0){
hasRect = true;
cout << counter << " square (s) of size " << i << endl;
}
}
if(hasRect == false)
cout << "No completed squares can be found." << endl;
cout << endl;
for(int i = 0; i < size; i++){
delete ary;
}
delete ary;
#ifdef DEBUG
myfile >> size;
if(myfile.eof())
break;
myfile >> line;
#else //DEBUG
if(!(cin >> size >> line))
return 0;
#endif //DEBUG
cout << "**********************************" << endl << endl;
}

}
return 0;
}

//len is rectangle's length e.g. 1,2,3,4,5
//size is the size of whole rectangle e.g. 5x5

int numRect(int x, int y, int len){

if(ary[x][y].B){
for(int i = 0; i < len; i++){
//Check upper herizon line
if(ary[x+i][y].H == false){
return 0;
}
//Check lower herizon line
if(ary[x+i][y+len].H == false){
return 0;
}
//Chech left vertical line
if(ary[x][y+i].V == false){
return 0;
}
//Chech right vertical line
if(ary[x+len][y+i].V == false){
return 0;
}
}
}else{
return 0;
}
return 1;
}