Take the 2-minute tour ×

I have a table which consists of nonnegative integers that are layed out in this manner: Each element in the table is the minimum value that does not appear to its left or above it. Here's an example of a 6x6 grid:

0 1 2 3 4 5
1 0 3 2 5 4
2 3 0 1 6 7
3 2 1 0 7 6
4 5 6 7 0 1
5 4 7 6 1 0 

The first row and column begin with 0 1 2 3 4 5... In coordinates (x,x) is always a 0, as you can see. On each tile after that, you have to place the smallest positive number that doesn't already exist on the same row or column. Much like in a sudoku-puzzle: There cannot be a number twice on the same row and column.

Now I have to print the number in the given coordinates (y,x). For example [2, 5] = 5

I came up with a working solution, but it takes way too much memory and time, and I just know there's another way of doing this. My time limit is 1 second, and the coordinates I have to find the number at can go up to (1000000, 1000000).

Here's my code at the moment:

#include <iostream>
#include <vector>

int main()
    int y, x, grid_size;
    std::vector< std::vector<int> > grid;

    std::cin >> y >> x; // input the coordinates we're looking for

    grid.resize(y, std::vector<int>(x, 0)); // resize the vector and initialize every tile to 0

    for(int i = 0; i < y; i++)
        for(int j = 0; j < x; j++)
            int num = 1;

            if(i != j) { // to keep the zero-diagonal

                for(int h = 0; h < y; h++)
                    for(int k = 0; k < x; k++) { // scan the current row and column
                        if(grid[h][j] == num || grid[i][k] == num) { // if we encounter the current num
                            num++;                                   // on the same row or column, increment num
                            h = -1; // scan the same row and column again

                grid[i][j] = num; // assign the smallest number possible to the current tile


    /*for(int i = 0; i < y; i++) {            // print the grid
        for(int j = 0; j < x; j++)            // for debugging
            std::cout << grid[i][j] << " ";   // reasons

        std::cout << std::endl;

    std::cout << grid[y-1][x-1] << std::endl; // print the tile number at the requested coordinates
    return 0;

So what should I do? Is this easier than I think it is?

share|improve this question
Are the numbers in the grid always following the pattern in your sample? Then you don't need to instantiate it in memory at all, but the number at the given coordinates can be simply calculated using an appropriate formula. –  πάντα ῥεῖ Jan 7 '13 at 13:14
It's not trivial, but it certainly can be done without creating a table in memory. You have to find out how the numbers are layed out in the next rows and columns. –  Bartek Banachewicz Jan 7 '13 at 13:18
I've been scratching my head with my pencil and a piece of paper for an hour or so. I know it's definitely not going to fit into any array or anything.. Just can't come up with the formula –  Olavi Mustanoja Jan 7 '13 at 13:23
Are the rows always following the same pattern? i.e. is the next row always the previous one shifted by one position? –  Ivaylo Strandjev Jan 7 '13 at 13:24
What you're looking for is called a (reduced) Latin square. –  larsmans Jan 7 '13 at 13:39

1 Answer 1

up vote 5 down vote accepted

To summarize your question: You have a table where each element is the minimum nonnegative integer that does not appear to its left or above. You need to find the element at position (x,y).

The result is surprisingly simple: If x and y are 0-based, then the element at (x,y) is x XOR y. This matches the table you have posted. I have verified it experimentally for a 200x200 table.

The proof:

It's easy to see that the same number won't appear twice on the same row or column, because if x1^y = x2^y then necessarily x1=x2.

To see that x^y is minimal: Let a be a number smaller than x^y. Let i be the index (from the right) of the leftmost bit where a differs from x^y. The ith bit of a must be 0 and the ith bit of x^y must be 1.

Therefore, either x or y must have 0 in the ith bit. Suppose WLOG it was x that had 0. Represent x and y as:

x = A0B
y = C1D

Where A,B,C,D are sequences of bits, and B and D are i bits long. Since the leftmost bits of a are the same as those in x^y:

a^x = C0E

Where E is a sequence of i bits. So we can see that a^x < y. The value that appered in the (a^x)th row on the same column was: (a^x)^x = a. So the value a must have already appeared in the same row (or column, if it was y that had 0 in the ith bit). This is true for any value smaller than x^y, so x^y is indeed the minimum possible value.

share|improve this answer
this would be really cool. The way I would prove this theory empirically is by writing a brute-force solution for upto say 50 and if your solution works for all those tables than you really are a genius :) –  Ivaylo Strandjev Jan 7 '13 at 14:42
You can prove it by generating columns and rows of various grid sizes with this method and check them for meeting the conditions. –  πάντα ῥεῖ Jan 7 '13 at 14:47
@g-makulik: I wouldn't call that "proving", I'd prefer a mathematical proof. I've verified it now for at least up to a 200x200 table. –  interjay Jan 7 '13 at 15:01
I tested it and it works. Your solution is correct and I'm dumbfounded. Verified with a 1000000x1000000 table (don't ask where I got it). I don't understand it. Exactly what does x^y do? –  Olavi Mustanoja Jan 7 '13 at 15:05
@OlaviMustanoja: I've managed to prove it but the proof is more complicated than I would have liked. x^y is the bitwise XOR of x and y, it can appear in surprising places such as the solution to the game of Nim –  interjay Jan 7 '13 at 15:38

Your Answer


