solve.c

// 1. Input:
// A number N, representing the size of the square board grid. N rows of
// N characters each, where each character is either R (red) or A (blue).
//
// 2. Objective:
// Rearrange the rows of the board to maximize the area of the largest
// contiguous rectangular zone for each color (R for The Famous, A for
// The Warriors).
//
// Determine the winning team based on the larger rectangular area of
// their respective color:
//
// * 1 if The Famous wins.
// * 2 if The Warriors win.
// * 0 if it is a draw.
//
// 3. Output:
//  * Two integers:
//  * The winning team (1, 2, or 0).
//  * The area of the largest rectangle for the winning team.
//
// Constraints:
// * Teams can reorder the rows but not the colors within a row.
// * The solution must handle grids up to  1000 x 1000 .
//
// Ref: https://old.reddit.com/r/C_Programming/comments/1i5z5j2/
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define new(a, n, t)    (t *)alloc(a, n, sizeof(t), _Alignof(t))
typedef struct { char *beg, *end; } Arena;
static void *alloc(Arena *a, int count, int size, int align)
{
    int pad = (int)-(uintptr_t)a->beg & (align - 1);
    assert(count < (a->end - a->beg - pad)/size);
    char *r = a->beg + pad;
    a->beg += pad + size*count;
    return memset(r, 0, size*count);
}

#define S(s)    (Str){s, sizeof(s)-1}
typedef struct {
    char *data;
    int   len;
} Str;

static int parseint(Str s, int max)
{
    assert(s.len);
    int r = 0;
    for (int i = 0; i < s.len; i++) {
        assert(s.data[i]-(unsigned)'0' < 9);
        r = r*10 + s.data[i] - '0';
        assert(r <= max);
    }
    return r;
}

static Str split(Str s, int *cursor)
{
    char *beg = s.data + *cursor;
    char *end = s.data + s.len;
    for (; beg<end && *beg<=' '; beg++) {}
    char *cut = beg;
    for (; cut<end && *cut>' '; cut++) {}
    *cursor = (int)(cut - s.data);
    return (Str){beg, (int)(cut-beg)};
}

static int ***newtally(Arena *a, int size)
{
    int ***t = new(a, 2, int **);
    t[0] = new(a, size, int *);
    t[1] = new(a, size, int *);
    for (int i = 0; i < size; i++) {
        t[0][i] = new(a, size+1, int);
        t[1][i] = new(a, size+1, int);
    }
    return t;
}

static void register_run(int ***t, int who, int endx, int len)
{
    for (int n = 1; n <= len; n++) {
        for (int i = 1; i <= n; i++) {
            t[who][endx-n][i]++;
        }
    }
}

typedef struct {
    int who;
    int score;
} Result;

static Result solve(Str input, Arena scratch)
{
    int    cursor = 0;
    int    size   = parseint(split(input, &cursor), 1000);
    int ***tally  = newtally(&scratch, size);

    for (int y = 0; y < size; y++) {
        Str row = split(input, &cursor);
        assert(row.len == size);
        int run = 0;
        int last = 0;
        for (int x = 0; x < row.len; x++) {
            int who = row.data[x];
            assert(who=='A' || who=='R');
            who = who == 'A';
            if (who!=last && run) {
                register_run(tally, last, x, run);
                run = 0;
            }
            last = who;
            run++;
        }
        register_run(tally, last, size, run);
    }

    int best[2] = {0};
    for (int who = 0; who < 2; who++) {
        for (int x = 0; x < size; x++) {
            for (int len = 1; len <= size; len++) {
                if (len>best[who] && tally[who][x][len] >= len) {
                    best[who] = len;
                }
            }
        }
    }

    Result r = {0};
    r.who    = best[0]==best[1] ? 0 : 1 + (best[1]>best[0]);
    r.score  = best[0]>best[1] ? best[0] : best[1];
    r.score *= r.score;
    return r;
}

int main(void)
{
    int   cap   = 1<<28;
    char *mem   = malloc(cap);
    Str   input = S(
        "6 "
        "RARRRA "
        "RRAARA "
        "RARRRR "
        "AAARAA "
        "RAAARA "
        "RRRRRR "
    );
    Result r = solve(input, (Arena){mem, mem+cap});
    printf("%d %d\n", r.who, r.score);
    return 0;
}