10855 - Rotated square

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

Moderator: Board moderators

Post Reply
Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

10855 - Rotated square

Post by Chok » Tue Jul 19, 2005 6:59 pm

Hi all,
I'm getting WA for this easy problem. Please give me some I/O. By the way i'm giving the code to rotate the small square. Is it ok ???? Thankx in advance.

Code: Select all

void rotate_grid()
{
	int i,j;
	int sro1r,sro1c,sro2r,sro2c,sro3r,sro3c;
	int rot1r,rot1c,rot2r,rot2c,rot3r,rot3c,rot4r,rot4c;

	sro1r=0;		// 90 degree
	sro1c=n-1;

	sro2r=n-1;		// 180 degree
	sro2c=0;

	sro3r=0;		// 270 degree
	sro3c=-(n-1);

	// Given Second Square is already at rot[0][]][]
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			rot1r=i;	// 0 degree
			rot1c=j;
			rot2r=i+sro1r+j;	// 90 degree
			rot2c=j+sro1c-j;
			
			rot3r=rot2r+sro2r-j;	// 180 degree
			rot3c=rot2c+sro2c-j;

			rot4r=rot3r+sro3r-j;	// 270 degree
			rot4c=rot3c+sro3c+j;

			rot[1][rot2r][rot2c]=rot[0][rot1r][rot1c];
			rot[2][rot3r][rot3c]=rot[0][rot1r][rot1c];
			rot[3][rot4r][rot4c]=rot[0][rot1r][rot1c];			
		}
		sro1r--;
		sro1c--;

		sro2r--;
		sro2c++;

		sro3r++;
		sro3c++;
	}
	/*for(i=0;i<n;i++)
	{
		for(j=0;j<4;j++)
			pf(" %s",rot[j][i]);				
		puts("");
	}
	puts("");*/

}

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Tue Jul 26, 2005 11:30 am

Hi Chok

I have found a mistake in your code :)
just add this line after calling the rotated_grid() function.

Code: Select all

for (i = 0; i < n; i++) 
       rot[1][i][n] = NULL, rot[2][i][n] = NULL, rot[3][i][n]= NULL;
Thanks :)
MAP

Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

Post by Chok » Tue Jul 26, 2005 2:49 pm

Hi Prince,
Thanks for ur help. But i'm still not get ACC. I think my checking is not ok. Here is my full code. Please verify it. Thanks in advance.

Code: Select all

Cut after Acc...
Last edited by Chok on Wed Jul 27, 2005 5:21 pm, edited 1 time in total.

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Wed Jul 27, 2005 9:10 am

Hi

just increase ur max value and get your AC. :D

Thanks
MAP

Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

Post by Chok » Wed Jul 27, 2005 5:18 pm

Hi Prince,
Thank you very much. Got ACC. :D I missed those think. Again thanx. Bye and Good luck.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Sep 18, 2006 7:01 am

I changed my solution to one that only computes hash values, and it turns out that I can get AC in 0.006s

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Mon Jun 04, 2007 4:47 am

Interesting, what's your hash function? I wonder how it works.....

There's no upper bound on N or n correct? I tried brute force and got AC with 9.2 sec by luck. I guess that means N can be big?

Pregunt
New poster
Posts: 7
Joined: Thu Jun 16, 2005 8:17 am
Location: M
Contact:

n<=100

Post by Pregunt » Fri Jun 29, 2007 3:26 am

N<=100

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

Re: 10855 - Rotated squares

Post by brianfry713 » Sat Mar 08, 2014 3:18 am

I just got AC in 0.045 using the straightforward brute force method of making up to (N - n + 1) * (N - n + 1) * n * n comparisons or O(N * N * n * n). I stopped comparing the small square when there was a mismatch.

I improved my time to 0.009 using a hash.
First iterate fully through one dimension and use a rolling hash to shrink the small square to 1 by n and the large square to (N - n + 1) by N. Then iterate through the other dimension and you can reduce the small square to 1 by 1 and the large square to (N - n + 1) by (N - n + 1). Now you only have to make (N - n + 1) * (N - n + 1) comparisons and the whole code runs in O(N * N) which is optimal.
Check input and AC output for thousands of problems on uDebug!

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 10855 - Rotated squares

Post by uDebug » Thu May 15, 2014 9:02 am

Here's some input / output I found useful during testing / debugging.

Input:

Code: Select all

9 2
ABBAABABA
ABBBABABA
BAAAABBAB
BABBBABAB
ABBBBABAB
BBBABABAB
ABABABBBA
ABABABBBA
BBABABBAB
AB
BB
7 2
ABCCBAB
BCCBABA
BACCCAB
BABABCC
CABABAB
ABCBABA
BACCABA
AB
BC
0 0
AC Output:

Code: Select all

4 3 3 3
2 1 1 0
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

yammacode
New poster
Posts: 1
Joined: Sun Apr 05, 2015 9:34 pm

Re: 10855 - Rotated square

Post by yammacode » Sun Apr 05, 2015 9:38 pm

Hi. I got WA. Here's my code.
please your advice. thanks

Code: Select all

#include <iostream>

using namespace std;

int N, n;
char big[100][100];
char small[100][100];

int main(void) {

	std::cin>>N>>n;
	while(true) {
		if(N == 0 || n == 0)
			break;

		int result[4] = {0,0,0,0};

		for(int i=0; i<N; i++) 
			for(int k=0; k<N; k++)
				std::cin>>big[i][k];

		for(int i=0; i<n; i++) 
			for(int k=0; k<n; k++)
				std::cin>>small[i][k];


		for(int i=0; i<=N-n; i++) {
			for(int k=0; k<=N-n; k++) {

				int n_j = 0, n_l = 0;

				for(int j=i; j<i+n; j++) {
					n_l = 0;
					for(int l=k; l<k+n; l++) {
						if(big[j][l] != small[n_j][n_l++]) {
							goto fail;
						}
					}
					n_j++;
				}
				result[0]++;
fail: ;

				n_j = 0;

				for(int j=i; j<i+n; j++) {
					n_l = n-1;
					for(int l=k; l<k+n; l++) {
						if(big[j][l] != small[n_j][n_l--]) {
							goto fail2;
						}
					}
					n_j++;
				}
				result[1]++;
fail2: ;

				n_j = n-1;

				for(int j=i; j<i+n; j++) {
					n_l = n-1;
					for(int l=k; l<k+n; l++) {
						if(big[j][l] != small[n_j][n_l--]) {
							goto fail3;
						}
					}
					n_j--;
				}
				result[2]++;
fail3: ;

				n_j = n-1;
				for(int j=i; j<i+n; j++) {
					n_l = 0;
					for(int l=k; l<k+n; l++) {
						if(big[j][l] != small[n_j][n_l++]) {
							goto fail4;
						}
					}
					n_j--;
				}
				result[3]++;
fail4: ;

			}
		}

		std::cout<<result[0]<<" "<<result[1]<<" "<<result[2]<<" "<<result[3]<<std::endl;
		
		std::cin>>N>>n;
	}

	return 0;
}

yoyoshubham
New poster
Posts: 1
Joined: Fri Jun 24, 2016 10:33 am

Re: 10855 - Rotated square

Post by yoyoshubham » Sun Jun 26, 2016 9:02 am

Hi all! I am getting WA on the judge, but my code is giving correct output for sample test cases provided on https://www.udebug.com/UVa/10855 . Can anyone help me find out the mistake in my code.

Code: Select all

Deleted after getting AC :D 

Sebassmaster
New poster
Posts: 2
Joined: Fri Aug 19, 2016 1:51 am

Re: 10855 - Rotated square

Post by Sebassmaster » Sun Sep 25, 2016 10:12 pm

Hi All,

All testcases are passing (both from sample and uDebug), but I'm still getting WA. Please heeelp :(!!

Code: Select all

#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <cmath>

std::ostream& operator<<(std::ostream& out, std::vector<std::string> const& square)
{
     for(auto const& row : square)
          out << row << std::endl;
     return out; 
}

//#define DEBUG

namespace debug 
{
struct X {
	template<typename T>
	X& operator << (const T& x)
	{
#ifdef DEBUG
		std::cout << x;
#endif
		return *this;
	}
} cout;
}  // namespace mystd

using SquareT = std::vector<std::string>;

/**
 * @brief Rotates a certain layer of a square, in place.
 * It doesn't touch any field that's outside that particular layer.
 *
 * @param layer 0-Based layer to rotate
 * @param square square in which the layer will be rotated
 */
void rotate_layer_90(int const layer, SquareT& square)
{
     int const col_min = layer;
     int const col_max = square.size() - layer - 1;
     int const row_min = layer;
     int const row_max = col_max;//-> Making use that this is a square
     int const sub_square_size = row_max - row_min + 1;

     //Base case 1X1: The result is the same number, nothing to do
     if(sub_square_size == 1) return;

     //Base case 2X2: solved by swapping its elements in the correct order
     if(sub_square_size == 2){
          std::swap(square[row_min][col_min], square[row_min][col_max]);
          std::swap(square[row_min][col_min], square[row_max][col_min]);
          std::swap(square[row_max][col_min], square[row_max][col_max]);
          return;
     }

     char const temp_bottom_right_char = square[row_max][col_max];
     char const temp_upper_left_char = square[row_min][col_min];
     char const temp_upper_right_char = square[row_min][col_max];

     //Shifting Left column up 
     for (int i = row_min; i < row_max; ++i) {
          square[i][col_min] = square[i+1][col_min];
     }
     //Shifting upper row right
     for (int i = col_max; i > col_min; --i) {
          square[row_min][i] = square[row_min][i-1];
     }
     //Shifting right column down
     for (int i = row_max; i > row_min; --i) {
          square[i][col_max] = square[i-1][col_max];
     }
     //Shifting bottom row left
     for (int i = col_min; i < col_max; ++i) {
          square[row_max][i] = square[row_max][i+1];
     }

     square[row_min][col_min+1] = temp_upper_left_char;
     square[row_max][col_max-1] = temp_bottom_right_char;
     square[row_min+1][col_max] = temp_upper_right_char;
}


/**
 * @brief Rotates an entire square 90 degrees
 *
 * @param square square to rotate (immutable)
 *
 * @return a new square which is the 90 degrees rotation of the input square
 */
SquareT rotate_square_90(SquareT const& square)
{
     SquareT out(square);
     auto n = square.size();

     int const n_layers = std::floor((n+1)/2);
     //Cicle through layers
     for (int i = 0; i < n_layers; ++i) {
               rotate_layer_90(i, out); 
     }
     return out;
}


/**
 * @brief Checks if a small square is equal to a same size (possible)subset of a big square
 *
 * @param small small square
 * @param big big square
 * @param min_row smallest row to check in the big square
 * @param min_col smallest column to check in the big square
 * @param n_cols small square size
 * @param n_rows small square size
 *
 * @return 
 */
bool small_appears_in_big(SquareT const& small, SquareT const& big, int const min_row, int const min_col, int const n_cols, int const n_rows)
{
     for (int i = 0; i < n_rows; ++i) {
          for (int j = 0; j < n_cols; ++j) {
               if(small[i][j] != big[i+min_row][j+min_col])
                    return false;
          }
     }
     return true;
}


/**
 * @brief Counts the apparance of a specific small square in a big one
 *
 * @param small
 * @param big
 *
 * @return number of appareances of the small square in the big one
 */
int count_appearances(SquareT const& small, SquareT const& big)
{
     int const n_checkings = big.size() - small.size() + 1;
     int const n_rows = small.size();
     int const n_cols = small.size();
     int count = 0;
     for (int i = 0; i < n_checkings; ++i) {
          for (int j = 0; j < n_checkings; ++j) {
               int const min_row = i;
               int const min_col = j;
               if(small_appears_in_big(small, big, min_row, min_col, n_rows, n_cols))
                    count++;
          }
     }
     return count;
}


/**
 * @brief Reports the count of the appareances of the small square in the big square
 *
 * @param big_square
 * @param small_square
 *
 * @return A string containing the count of appareances of the small square in the big square in: 0deg, 90deg, 180deg and 270deg 
 */
std::string analyze_squares(SquareT const& big_square, SquareT const& small_square)
{
     std::stringstream out;
     
     int deg_0_appearances_count = count_appearances(small_square, big_square);

     auto deg_90 = rotate_square_90(small_square);
     int deg_90_appearances_count = count_appearances(deg_90, big_square);

     auto deg_180 = rotate_square_90(deg_90);
     int deg_180_appearances_count = count_appearances(deg_180, big_square);

     auto deg_270 = rotate_square_90(deg_180);
     int deg_270_appearances_count = count_appearances(deg_270, big_square);

     out << std::to_string(deg_0_appearances_count) << " " 
          << std::to_string(deg_90_appearances_count) << " " 
          << std::to_string(deg_180_appearances_count) << " " 
          << std::to_string(deg_270_appearances_count);

     return out.str();
}

int main(int argc, char *argv[])
{
     std::string line;
     while(std::getline(std::cin, line))
     {
          std::stringstream ss_line(line);
          int big_n, small_n;
          ss_line >> big_n >> small_n;
          if(big_n == 0 and small_n == 0)
               break;

          SquareT big_square, small_square;
          for (int i = 0; i < big_n; ++i) {
               std::string row;
               std::getline(std::cin, row);
               big_square.push_back(row);
          }
          for (int i = 0; i < small_n; ++i) {
               std::string row;
               std::getline(std::cin, row);
               small_square.push_back(row);
          }

          std::cout << analyze_squares(big_square, small_square) << std::endl;
     }
     return 0;
}


Post Reply

Return to “Volume 108 (10800-10899)”