I'm new to Google Code Jam. I am very excited and thank you for providing me this opportunity to learn coding from world top programmers.
I were practicing on the “World Finals 2014” website. It seems that I found the solution for “Problem A” has a bug. I submitted my solution and it always shows “incorrect”. Then I compared my solution with the public programs on the “World Finals 2014” website. For the small practice test cases, the answers were different only on case #1. So I checked manually and thought my solution is correct. The code jam’s answer on the website did not consider the effect like one row swap after one column swap, for the first row and the first column. Please correct me where I was wrong. Thank you. Regards, Shenghua ====== Start ====== My Code, Filename: A.c ====== /********************************** News: http://mashable.com/2014/08/15/teen-from-belarus-wins-google-code-jam-on-his-first-try/ Problems: https://code.google.com/codejam/contest/7214486/dashboard#s=p0 Problem A. Checkerboard Matrix This contest is open for practice. You can try every problem as many times as you like, though we won't keep track of which problems you solve. Read the Quick-Start Guide to get started. Small input 4 points Solve A-small Large input 9 points Solve A-large Problem When she is bored, Mija sometimes likes to play a game with matrices. She tries to transform one matrix into another with the fewest moves. For Mija, one move is swapping any two rows of the matrix or any two columns of the matrix. Today, Mija has a very special matrix M. M is a 2N by 2N matrix where every entry is either a 0 or a 1. Mija decides to try and transform M into a checkerboard matrix where the entries alternate between 0 and 1 along each row and column. Can you help Mija find the minimum number of moves to transform M into a checkerboard matrix? Input The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing a single integer: N. The next 2N lines each contain 2N characters which are the rows of M; each character is a 0 or 1. Output For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the minimum number of row swaps and column swaps required to turn M into a checkerboard matrix. If it is impossible to turn M into a checkerboard matrix, y should be "IMPOSSIBLE". Limits 1 ≤ T ≤ 100. Small dataset 1 ≤ N ≤ 10. Large dataset 1 ≤ N ≤ 10^3. Sample Input 3 1 01 10 2 1001 0110 0110 1001 1 00 00 Output Case #1: 0 Case #2: 2 Case #3: IMPOSSIBLE In the first sample case, M is already a checkerboard matrix. In the second sample case, Mija can turn M into a checkerboard matrix by swapping columns 1 and 2 and then swapping rows 1 and 2. In the third sample case, Mija can never turn M into a checkerboard matrix; it doesn't have enough 1s. **********************************/ /********************************** Below is written by S.H.Song **********************************/ #ifdef _MSC_VER #define _CRT_SECURE_NO_WARNINGS #define ___ITOA _itoa #else #define ___ITOA itoa #endif #include <stdio.h> #include <stdlib.h> #include <string.h> #define T 100 #define N 1000 void process(FILE* fp_in, FILE* fp_out) { if (fp_in == NULL) return; char line[2*N+10]; int max_cases = 0; int case_number, max_lines, line_number; int already_impossible = 0; char** matrix = (char**) malloc(2*N*sizeof(char*)); matrix[0] = (char*)malloc((2*N)*(2*N)); for (int i=1; i<2*N; ++i) matrix[i] = matrix[i-1] + 2*N; while(1) { if (fgets(line, 2*N+10, fp_in) == NULL) break; if (max_cases == 0) { max_cases = atoi(line); if (max_cases <= 0 || max_cases > T) { fputs("Input ERROR MaxCases\n", fp_out); break; } case_number = 0; max_lines = 0; line_number = 0; already_impossible = 0; continue; } if (max_lines == 0) { max_lines = atoi(line); if (max_lines <= 0 || max_lines > N) { fputs("Input ERROR MaxLines\n", fp_out); break; } case_number++; max_lines *= 2; line_number = 0; already_impossible = 0; continue; } if ((strlen(line) != max_lines+1) && (strlen(line) != max_lines)) { fputs("Input ERROR Line\n", fp_out); break; } int value_invalid = 0; for (int i=0; i<max_lines; ++i) { if (line[i] != '0' && line[i] != '1') { value_invalid = 1; break; } matrix[line_number][i] = line[i]; } if (value_invalid){ fputs("Input ERROR Value\n", fp_out); break; } if (already_impossible == 0) { if (line_number == 0) { for (int i = 0; i < max_lines; ++i) { if (matrix[0][i] == '1') already_impossible++; } if (2 * already_impossible != max_lines) already_impossible = 1; else already_impossible = 0; } else { for (int i = 1; i < max_lines; ++i) { if ((matrix[0][i] == matrix[0][0] && matrix[line_number][i] != matrix[line_number][0]) || (matrix[0][i] != matrix[0][0] && matrix[line_number][i] == matrix[line_number][0])) { already_impossible = 1; break; } } } if (already_impossible){ char buffer[33]; fputs("Case #", fp_out); fputs(___ITOA(case_number, buffer, 10), fp_out); fputs(": IMPOSSIBLE\n", fp_out); } } ++line_number; if (already_impossible == 0) { if (line_number == max_lines) { for (int i=0; i<max_lines; ++i) { if (matrix[i][0] == '1') already_impossible++; } if (2 * already_impossible != max_lines) already_impossible = 1; else already_impossible = 0; if (already_impossible){ char buffer[33]; fputs("Case #", fp_out); fputs(___ITOA(case_number, buffer, 10), fp_out); fputs(": IMPOSSIBLE\n", fp_out); } } } if (already_impossible == 0) { if (line_number == max_lines) { int mode_01, mode_10, tmp; tmp = 0; for (int i=0; i<max_lines; ++i) { if (i%2+'0' != matrix[0][i]) tmp++; } mode_01 = tmp / 2; mode_10 = (max_lines - tmp) / 2; tmp = 0; for (int i=0; i<max_lines; ++i) { if (i%2+'0' != matrix[i][0]) tmp++; } if (matrix[0][0] == '0') { mode_01 += tmp / 2; mode_10 += tmp / 2; } else { mode_01 += (max_lines - tmp) / 2; mode_10 += (max_lines - tmp) / 2; } tmp = mode_01 < mode_10 ? mode_01 : mode_10; char buffer[33]; fputs("Case #", fp_out); fputs(___ITOA(case_number, buffer, 10), fp_out); fputs(": ", fp_out); fputs(___ITOA(tmp, buffer, 10), fp_out); fputs("\n", fp_out); } } if (line_number == max_lines) max_lines = 0; } if (case_number != max_cases || max_lines != 0) fputs("Input ERROR Ending\n", fp_out); free(matrix[0]); free(matrix); } int main(int argc, char *argv[]) { char * in_name = "practice.in"; char * out_name = "practice.out"; FILE *fp_in, *fp_out; if (argc == 1 || argc > 3) { printf("\nUsage:\n%s %s %s\nPress any key to exit...\n", argv[0], in_name, out_name); getch(); return 1; } if (argc > 1) in_name = argv[1]; if (argc > 2) out_name = argv[2]; if ((fp_in=fopen(in_name,"r")) == NULL) { printf("\nCannot open '%s'\nPress any key to exit...\n", in_name); getch(); return 1; } if ((fp_out=fopen(out_name,"w")) == NULL) { fclose(fp_in); printf("\nCannot open '%s'\nPress any key to exit...\n", out_name); getch(); return 1; } process(fp_in, fp_out); fclose(fp_out); fclose(fp_in); return 0; } ====== End ====== My Code, Filename: A.c ====== ====== Start ====== Test Cases from Website, Filename: A-small-practice.in ====== 100 8 1001110101000101 0110001010111010 1001110101000101 1001110101000101 0110001010111010 1001110101000101 0110001010111010 1001110101000101 0110001010111010 1001110101000101 0110001010111010 1001110101000101 0110001010111010 0110001010111010 0110001010111010 1001110101000101 3 001101 110110 001101 001111 110010 010010 2 1010 0101 1010 0101 4 11000101 11000101 00111010 00111010 11000101 00111010 00111010 11000101 5 0011100011 1100011100 1100011110 1100001110 1100011100 1100011100 0011100011 0011100011 0011100011 0011100011 1 10 10 2 0101 1010 1010 0101 2 1111 0111 1001 0001 3 010110 011100 110001 001011 100110 101001 3 100111 011010 100011 011010 011010 100101 8 1100001100111100 1000011100111100 1011010011000011 1100001100011110 0011110011000011 1100001100111100 0100101100111100 0011101011000011 1000010101111100 0011110011000011 1100001100111100 1010001100111100 0101110011000011 0111100011000011 0011110011100001 0111110010000011 1 10 01 2 0011 0011 1100 1100 3 010011 110100 101001 010110 101001 001110 3 010110 100110 011000 100011 010100 100011 3 100111 011001 110110 011011 000100 010001 2 1110 1110 0001 1110 1 01 10 4 01001000 01001101 01001101 10110011 01001001 10110010 10110010 00110000 10 01010100010100111101 10101011101011000010 10101011101011000010 10101011101011000010 01010100010100111101 01010100010100111101 10101011101011000010 01010100010100111101 01010100010100111101 01010100010100111101 01010100010100111101 01010100010100111101 10101011101011000010 01010100010100111101 10101011101011000010 01010100010100111101 10101011101011000010 10101011101011000010 10101011101011000010 10101011101011000010 4 10111100 01001011 01001111 10111100 10100100 00001011 01001011 10110101 4 11010100 00101011 00101011 11010100 11010100 11010100 00101011 00101011 2 1100 0011 1010 0101 1 01 00 1 10 01 1 01 10 3 011100 100011 100011 011100 100011 011100 2 1010 0101 1010 0101 1 11 10 4 11110001 00101110 11010001 10101110 11010001 00101110 11010001 00001110 7 10001011001011 10001011001011 01100100110100 10001011001011 10011011001011 01110100110100 01110100110100 01010100110100 10001011001011 01110100110100 01110100110100 01110100110100 10001011001011 10001011001011 3 011100 000111 010011 101001 100110 111000 2 1100 0111 0010 1110 2 1101 0101 0011 0011 4 01011010 01110010 10100101 10001110 00111001 10100101 11000101 01011010 2 0101 1001 1010 0110 2 0010 0111 0100 0100 1 01 10 2 0011 0110 0011 1110 1 01 10 6 011110010010 011110010010 100001101101 100001101101 011110010010 100001101101 100001101101 011110010010 100001101101 100001101101 011110010010 011110010010 4 01011001 01010011 10101100 10101100 01010011 10100110 11010001 00101110 1 00 11 1 01 10 4 11100100 11000100 00011011 00011010 11100100 01001011 11100100 00011011 4 10010011 10010011 01101100 01101100 01101100 01101100 10010011 10010011 3 001101 110010 001101 110010 001101 110010 1 01 10 1 10 01 2 0101 1010 1010 0101 2 0110 1001 1010 0101 5 1010101001 1000011110 1010101001 1010101001 0101010110 0101010110 0101010110 1010001011 0111100001 0101110100 5 0110000110 0110011110 1001110001 1101110001 0010001110 1001110001 0110001110 1001110001 0110000110 1000110001 7 01110101010001 10001010101110 01110101010001 10001010101110 01110101010001 10001010101110 01110101010001 01110101010001 01110101010001 10001010101110 10001010101110 10001010101110 01110101010001 10001010101110 3 100011 001110 100011 011100 011001 110100 5 0101110110 1010101001 1010101001 1010101001 1101010110 1101010110 0101010110 0101010110 1010101001 1010101001 9 100101010100010111 011010101011101000 100101010100010111 011010101011101000 100101010100010111 011010101011101000 100101010100010111 011010101011101000 100101010100010111 011010101011101000 100101010100010111 011010101011101000 100101010100010111 011010101011101000 100101010100010111 011010101011101000 100101010100010111 011010101011101000 1 01 10 4 10100011 10010011 01101100 00010011 10010011 00101100 01101100 11101110 9 101010101011001010 010101010100110101 010101010100110101 101010101011001010 010101010100110101 101010101011001010 010101010100110101 101010101011001010 010101010100110101 101010101011001010 010101010100110101 101010101011001010 010101010100110101 101010101011001010 010101010100110101 101010101011001010 010101010100110101 101010101011001010 1 01 10 1 10 01 3 110001 001110 110001 001110 110001 001110 2 0011 1100 1001 0110 4 10000111 01000111 01001101 11010010 10111000 00100111 01111000 10111000 3 111100 000011 100011 111100 100111 000100 10 01100001101010101011 10011110010101010100 01100001101010101011 10011110010101010100 01100001101010101011 10011110010101010100 01100001101010101011 10011110010101010100 01100001101010101011 10011110010101010100 01100001101010101011 10011110010101010100 01100001101010101011 10011110010101010100 10011110010101010100 10011110010101010100 01100001101010101011 10011110010101010100 01100001101010101011 01100001101010101011 1 10 01 4 01001011 10110100 10111000 01001011 01001011 10110100 10110100 01000111 1 10 10 2 1001 0101 1010 0110 4 11010100 10110001 11010001 10100110 01001011 01011001 00101110 00101110 2 1110 1100 0010 0001 4 10101100 01010011 01010011 10101100 10101100 01010011 01010011 10101100 2 1001 0110 0110 1001 3 000111 011010 011010 101001 110100 100101 5 0010011101 0010011101 1101100010 0010011101 1101100010 0010011101 0010011101 1101100010 1101100010 1101100010 2 0110 0110 1001 1001 10 01000111000110111001 01010111000110111000 01010111000110111000 10101000111001000111 10101000111001000111 01010111100110110000 01010111000110111000 10101000111001000111 10101000111001000111 10111000011001001110 01010111000110111000 10101000111001000111 01010111000110111000 10101000111001000111 10101000111001000111 01010111000110111000 01010110100110111000 01010111000110111000 10101001011001000111 10101000111001000111 2 0101 0000 1010 0101 1 01 10 3 010101 100110 001011 110100 111000 001011 2 0101 0101 1010 1010 2 1001 0110 0100 1001 1 10 01 4 00010111 11101000 11101000 00010111 11101000 00010111 00010111 11101000 9 110011001001001011 110011001001001011 001100110110110100 001100110110110100 110011001001001011 110011001001001011 001100110110110100 001100110110110100 001100110110110100 001100110110110100 001100110110110100 110011001001001011 110011001001001011 110011001001001011 001100110110110100 110011001001001011 110011001001001011 001100110110110100 3 001110 001110 001110 110001 110001 110001 4 01110001 01110001 10001110 10101001 10001110 10100110 01011001 01010110 9 100010101010101110 011101010101010001 100010101010101110 011101010101010001 100010101010101110 011101010101010001 100010101010101110 011101010101010001 100010101010101110 011101010101010001 100010101010101110 100010101010101110 100010101010101110 011101010101010001 100010101010101110 011101010101010001 011101010101010001 011101010101010001 1 00 01 4 00010111 01000111 10111000 01010110 10101001 10101001 01010110 11101000 5 0010110110 1001101010 0110010101 0111010100 1001001011 1001101010 1101101000 0110010101 0110010101 1000101011 1 00 10 2 1010 0101 1010 0101 5 1111010000 0100110101 1111001000 0000110111 1111000001 1111001000 0000101111 1011001010 0000111110 0000110111 3 011010 100101 011010 100101 100101 011010 4 01000101 01100101 00001011 01100101 11011010 10011010 01000101 10011010 4 11000110 01100011 01101001 10110100 00111001 10010110 01001011 10011100 5 1001101010 1001101010 0110010101 0110010101 1001101010 0110010101 0110010101 1001101010 1001101010 0110010101 ====== End ====== Test Cases from Website, Filename: A-small-practice.in ====== ====== Start ====== Output, Filename: google_says_this_is_correct.out ====== Case #1: 4 Case #2: IMPOSSIBLE Case #3: 0 Case #4: 3 Case #5: IMPOSSIBLE Case #6: IMPOSSIBLE Case #7: 1 Case #8: IMPOSSIBLE Case #9: IMPOSSIBLE Case #10: IMPOSSIBLE Case #11: IMPOSSIBLE Case #12: 0 Case #13: 2 Case #14: IMPOSSIBLE Case #15: IMPOSSIBLE Case #16: IMPOSSIBLE Case #17: IMPOSSIBLE Case #18: 0 Case #19: IMPOSSIBLE Case #20: 6 Case #21: IMPOSSIBLE Case #22: 3 Case #23: IMPOSSIBLE Case #24: IMPOSSIBLE Case #25: 0 Case #26: 0 Case #27: 2 Case #28: 0 Case #29: IMPOSSIBLE Case #30: IMPOSSIBLE Case #31: IMPOSSIBLE Case #32: IMPOSSIBLE Case #33: IMPOSSIBLE Case #34: IMPOSSIBLE Case #35: IMPOSSIBLE Case #36: IMPOSSIBLE Case #37: IMPOSSIBLE Case #38: 0 Case #39: IMPOSSIBLE Case #40: 0 Case #41: 6 Case #42: IMPOSSIBLE Case #43: IMPOSSIBLE Case #44: 0 Case #45: IMPOSSIBLE Case #46: 4 Case #47: 1 Case #48: 0 Case #49: 0 Case #50: 1 Case #51: IMPOSSIBLE Case #52: IMPOSSIBLE Case #53: IMPOSSIBLE Case #54: 2 Case #55: IMPOSSIBLE Case #56: IMPOSSIBLE Case #57: 2 Case #58: 0 Case #59: IMPOSSIBLE Case #60: 2 Case #61: 0 Case #62: 0 Case #63: 1 Case #64: IMPOSSIBLE Case #65: IMPOSSIBLE Case #66: IMPOSSIBLE Case #67: 4 Case #68: 0 Case #69: IMPOSSIBLE Case #70: IMPOSSIBLE Case #71: IMPOSSIBLE Case #72: IMPOSSIBLE Case #73: IMPOSSIBLE Case #74: 3 Case #75: 2 Case #76: IMPOSSIBLE Case #77: 4 Case #78: 2 Case #79: IMPOSSIBLE Case #80: IMPOSSIBLE Case #81: 0 Case #82: IMPOSSIBLE Case #83: 1 Case #84: IMPOSSIBLE Case #85: 0 Case #86: 3 Case #87: 8 Case #88: 2 Case #89: IMPOSSIBLE Case #90: 2 Case #91: IMPOSSIBLE Case #92: IMPOSSIBLE Case #93: IMPOSSIBLE Case #94: IMPOSSIBLE Case #95: 0 Case #96: IMPOSSIBLE Case #97: 2 Case #98: IMPOSSIBLE Case #99: IMPOSSIBLE Case #100: 3 ====== End ====== Output, Filename: google_says_this_is_correct.out ====== ====== Start ====== Output, Filename: I_think_this_should_be_correct.out ====== Case #1: 8 Case #2: IMPOSSIBLE Case #3: 0 Case #4: 3 Case #5: IMPOSSIBLE Case #6: IMPOSSIBLE Case #7: 1 Case #8: IMPOSSIBLE Case #9: IMPOSSIBLE Case #10: IMPOSSIBLE Case #11: IMPOSSIBLE Case #12: 0 Case #13: 2 Case #14: IMPOSSIBLE Case #15: IMPOSSIBLE Case #16: IMPOSSIBLE Case #17: IMPOSSIBLE Case #18: 0 Case #19: IMPOSSIBLE Case #20: 6 Case #21: IMPOSSIBLE Case #22: 3 Case #23: IMPOSSIBLE Case #24: IMPOSSIBLE Case #25: 0 Case #26: 0 Case #27: 2 Case #28: 0 Case #29: IMPOSSIBLE Case #30: IMPOSSIBLE Case #31: IMPOSSIBLE Case #32: IMPOSSIBLE Case #33: IMPOSSIBLE Case #34: IMPOSSIBLE Case #35: IMPOSSIBLE Case #36: IMPOSSIBLE Case #37: IMPOSSIBLE Case #38: 0 Case #39: IMPOSSIBLE Case #40: 0 Case #41: 6 Case #42: IMPOSSIBLE Case #43: IMPOSSIBLE Case #44: 0 Case #45: IMPOSSIBLE Case #46: 4 Case #47: 1 Case #48: 0 Case #49: 0 Case #50: 1 Case #51: IMPOSSIBLE Case #52: IMPOSSIBLE Case #53: IMPOSSIBLE Case #54: 2 Case #55: IMPOSSIBLE Case #56: IMPOSSIBLE Case #57: 2 Case #58: 0 Case #59: IMPOSSIBLE Case #60: 2 Case #61: 0 Case #62: 0 Case #63: 1 Case #64: IMPOSSIBLE Case #65: IMPOSSIBLE Case #66: IMPOSSIBLE Case #67: 4 Case #68: 0 Case #69: IMPOSSIBLE Case #70: IMPOSSIBLE Case #71: IMPOSSIBLE Case #72: IMPOSSIBLE Case #73: IMPOSSIBLE Case #74: 3 Case #75: 2 Case #76: IMPOSSIBLE Case #77: 4 Case #78: 2 Case #79: IMPOSSIBLE Case #80: IMPOSSIBLE Case #81: 0 Case #82: IMPOSSIBLE Case #83: 1 Case #84: IMPOSSIBLE Case #85: 0 Case #86: 3 Case #87: 8 Case #88: 2 Case #89: IMPOSSIBLE Case #90: 2 Case #91: IMPOSSIBLE Case #92: IMPOSSIBLE Case #93: IMPOSSIBLE Case #94: IMPOSSIBLE Case #95: 0 Case #96: IMPOSSIBLE Case #97: 2 Case #98: IMPOSSIBLE Case #99: IMPOSSIBLE Case #100: 3 ====== End ====== Output, Filename: I_think_this_should_be_correct.out ====== -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/2212bbe4-5a6c-4310-b6ff-275bd7a07d57%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
