201 - Squares

[dedeibel]

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?

[57761RF]

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]

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

Thanks a lot in advance

[someone2]

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]

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]

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

Siva

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]

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]

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

Your answer is exactly correct??

[nnahata]

sorry sir !
I didn't get your english .... plz make it more clear.....

[DIR EN GREY]

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!!

[nnahata]

ya now i got it.........thxs DIR EN GREY

[oskarcah]

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.

[alamgir kabir]

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

please help me.
thanks.

[joehuang92]

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);
			
			printAnswer(nProblem, result);
			
			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.
		{
			this.edgeSet.add(new Edge(p1, p2));
			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))))
					this.edgeSet.add(new Edge(p1, right));
				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))))
					this.edgeSet.add(new Edge(left, p2));
				else break;
			}
		}
		else if (p1.getX() == p2.getX() && p2.getY() - p1.getY() == 1) // Adding a vertical edge.
		{
			this.edgeSet.add(new Edge(p1, p2));
			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))))
					this.edgeSet.add(new Edge(p1, lower));
				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))))
					this.edgeSet.add(new Edge(upper, p2));
				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]

It drives me crazy... I have tested several test cases with output OK but keep getting WA.
Please help me to check what have I done wrong.



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