ECOO 2014 Regional - Problem #2: Black and Grey

I was actually at this regional competition and this file is the raw code that I used to be marked. I've fixed up this code with comments and made it more of a perfect solution over here.

The problem:

You have a 10x10 board made of tiles that are black on one side and light grey on the other, but right now they're all showing their grey side. Imagine the patterns you could make! For example, suppose you imposed a grid over the tiles to divide them into squares of the same size with no tiles left over. There are four grid sizes that would work: 1x1, 2x2, 5x5 and 10x10, as shown below (the tiles are in grey, the grids are shown with black lines).

Now imagine that each grid is a checkerboard where the top left square is a black square, like this:

Now imagine flipping over all the tiles that are underneath black grid squares. Do the 1x1 grid first, then 2x2, then 5x5, then 10x10. You're going to get some cool patterns. The pictures below show the results.

DATA21.txt (DATA22.txt for the second try) will contain 10 test cases. Each test case consists of six lines. The first line contains a single integer N (1 ≤ N ≤ 1000000) representing the size of the board. The next 5 lines each contain two integers R and C, separated by a space. R and C represent the row and column of a tile on the board (1 ≤ R,C ≤ N). Rows are numbered top down starting at 1 and columns are numbered left to right starting at 1. Your job is to simulate the pattern-making process described above for an NxN board, and then output a single line of 5 characters representing the five tiles in the locations given in the test case, in the order they originally appeared in the file. Each tile should be represented by an uppercase B or G depending on whether it is showing its black or grey side in the final pattern. Note that there are 2 test cases in the sample data below, but the real data files will contain 10 test cases.

Sample Input	5 5	10 10
10	12
5 1	6 6	Sample Output
5 2	7 7	GBBGG
5 3	8 8	GGGGG
5 4	9 9

My solution (in Java at the contest):

import java.util.*;
import java.io.*;

public class Problem_2_Black_And_Grey {

    public static void main(String[] args) {

        try {
            //System.out.println("Stated");
            Scanner file = new Scanner(new File("C:\\Users\\Tony\\Desktop\\DATA21.txt"));

            while(file.hasNextLine()) {

                ArrayList<String> list = new ArrayList<String>();

                for (int l = 0; l < 6; l++) {
                    list.add(file.nextLine());
                }

                int n = Integer.parseInt(list.get(0));

                int[][] board = new int[n][n];

                ArrayList<Integer> factors = factors(n);
                
                int[][] transformed = new int[n][n];
                
                for (int factor : factors) {
                    
                    int blackGrid = n / factor;
                    int numberOfGrids = factor;
                    
                    for (int i = 0; i < numberOfGrids; i++) {
                        for (int j = 0; j < numberOfGrids; j++) {
                            
                            for (int k = i * blackGrid; k < i * blackGrid + blackGrid; k++) {
                                for (int l = j * blackGrid; l < j* blackGrid + blackGrid; l++) {
                                    if ( (i+j)%2 == 0) {
                                        board[k][l] = 1;
                                    } else {
                                        board[k][l] = 0;
                                    }
                                }
                            }
                        }
                    }
                    
                    // add matrices
                    for (int i = 0; i < n; i++) {
                        for (int j = 0; j < n; j++) {
                            
                            if (transformed[i][j] == 1 && board[i][j] == 1) {
                                transformed[i][j] = 0;
                            } 
                            else if (transformed[i][j] == 1 && board[i][j] == 0) {
                                transformed[i][j] = 1;
                            }
                            else if (transformed[i][j] == 0 && board[i][j] == 1) {
                                transformed[i][j] = 1;
                            }
                            else if (transformed[i][j] == 0 && board[i][j] == 0) {
                                transformed[i][j] = 0;
                            }
                        }
                    }
                    
                }
                
                /*for (int[] i : transformed) {
                    for (int j : i) {
                        System.out.print(j + " ");
                    } 
                    System.out.println();
                }
                System.out.println("\n\n");*/
                
                for (int i = 1; i < 6; i++) {
                    int row = Integer.parseInt(list.get(i).split("\\s+")[0]);
                    int col = Integer.parseInt(list.get(i).split("\\s+")[1]);
                    
                    if (transformed[row-1][col-1] == 0) {
                        System.out.print("G");
                    } else {
                        System.out.print("B");
                    }
                }
                System.out.println();
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public static ArrayList<Integer> factors (int n) {

        ArrayList<Integer> list = new ArrayList<Integer>();
        
        for (int i = n; i >= 1; i--) {
            if (n % i == 0) list.add(i);
        }
        
        /*for (int i = (int)Math.sqrt(n) + 1; i >= 1; i--) {
            if (n % i == 0) list.add(i);
        }
        
        for (int factor : list) {
            list.add(n / factor);
        }*/
        
        return list;
    }
}

DOWNLOAD as .java

My test cases (as .txt files):

Using their sample input:

10
5 1
5 2
5 3
5 4
5 5
12
6 6
7 7
8 8
9 9
10 10

And the output to that is:

GBBGG
GGGGG

DOWNLOAD as .txt

And that is exactly the expected output.

Using their first judging test input:

1
1 1
1 1
1 1
1 1
1 1
5
4 1
5 1
1 3
4 3
4 5
27
14 1
24 22
15 8
13 22
4 20
319
307 214
234 311
137 19
267 154
240 109
1538
783 351
1506 1197
477 439
1325 842
784 418
13711
2348 7747
5816 1804
10205 2840
10332 12335
1277 2310
34214
25681 30923
32867 2906
18070 18771
9621 21171
33276 19876
614576
173191 304281
117755 193532
85644 136805
247497 148351
315064 276058
410114
3527 330138
69103 115910
251323 359304
328877 71422
409274 89398
587138
183328 314509
437196 203282
169760 324622
131740 301442
352404 158612

And the output to that is:

BBBBB
BGGBB
GGGBB
GGBGG
BBBBG
BGBBB
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at Problem_2_Black_And_Grey.main(Problem_2_Black_And_Grey.java:22)

DOWNLOAD as .txt

The only six outputs that it gives are exactly correct. The reason the JVM ran out of memory is because an array of size 34214 x 34214 is too large. On a computer with 4 GB of RAM, this will most likely crash on the sixth input (13711). At the competition, we were using a computer with 8 GB of RAM, so it crashed on the seventh input (34214). We tested a one-line piece of code in another testing class that was just an array of that size and it crashed, so we could guarantee that it was the size of the array that was causing us to run out of heap space. And the exception occurred at line 22 in the class, which is this line: int[][] board = new int[n][n]; We tried using a boolean array instead to keep it as small as possible (1-bit instead of 32-bit data type, boolean vs int), but it still ran out of memory.

Obviously our solution was correct, we just couldn't optimize it to not run out of memory. To fix that, I will attempt to cut down on the size of the board by ignoring the part of the board that we don't need. We only need to find a few specific coordinates on the board, so we can just create the board to the minimum requirements by looking at the farthest row for each of the coordinates and also the farthest column.

Using their second judging test input:

5
3 3
1 5
1 1
5 5
5 1
41
35 14
3 38
8 41
23 4
22 40
82
47 37
45 34
36 68
20 26
68 67
1445
101 370
101 430
431 255
1126 654
687 1160
6702
4809 523
4257 5094
6414 1986
5624 4159
6673 39
9594
1683 3751
8567 7491
8723 8739
1137 5924
231 8237
279066
76150 149858
5431 157348
275668 30742
187266 148885
197615 236474
789635
120147 481547
327898 252985
477382 285895
595923 103869
154417 62088
337263
22311 96668
30460 131774
109613 15105
128666 259127
90148 138195
778168
132111 466313
765166 582561
182188 650557
96282 765697
482808 675730

And the output to that is:

GGGGG
BBBBG
GGBBB
GBBGG
GBBGB
GGBGG
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at Problem_2_Black_And_Grey.main(Problem_2_Black_And_Grey.java:22)

Similar to the first judging test input, the only six outputs are exactly correct. I can assume the rest would be correct with our algorithm, if only the memory would allow for the testing. We didn't actually submit our code for this second set of data because we didn't want to risk it.

DOWNLOAD as .txt