Объяснение решения «подсчет количества подсетей» в Руководстве по программированию конкуренции

Question

Я натолкнулся на объяснение проблемы в руководстве для программиста-конкурента и не совсем понимаю, как оно охватывает все решения проблемы, и мне было интересно, если кто-нибудь мог бы объяснить это для меня. Я не уверен, что я просто не правильно понимаю решение, если я что-то упускаю из проблемы. Изображение вопроса и решения приведены ниже:

Насколько я понимаю, вопрос состоит в том, чтобы просто задать подсетки (четыре угла, которые делают Axb или Axa Box), где каждый угол черный. Их решение (из того, что я понимаю) состоит в том, что вы подсчитываете количество пар черного ящика в каждом столбце, а затем вычисляете общее количество, используя формулу count (count-1) / 2. Мой вопрос, если я правильно понимаю, как это охватывает все случаи? В моей голове был конкретный пример:

X O O O O O
O X O O O O
O O X O O O
X O O O O O 
O X O O O O
O O X O O O

и

X X X O O O
O O O O O O
O O O O O O
X X X O O O 
O O O O O O
O O O O O O

Разве эти два поля не дают один и тот же ответ, используя предоставленное решение? Вы бы получили count = 3 для обоих входов, которые вывели бы 3 для суммы для каждого входа, несмотря на то, что у них были разные решения. Я просто чувствую, что что-то упускаю, когда дело доходит до решения.

Спасибо за вашу помощь.

Answer 1

Алгоритм, заданный в виде псевдокода, является как бы внутренним l oop. Внешний l oop - это, как объяснено в предыдущем тексте, al oop по всем парам строк.

int count_subgrids(const int** color, int n)
{
    int subgrids = 0;
    for(int a=0; a<n; ++a)
        for(int b=a+1; b<n; ++b) {    // loop over pairs (a,b) of rows 
            int count=0;
            for(int i=0; i<n; ++i) {  // loop over all columns
                if(color[a][i]==1 && color[b][i]==1)
                    ++count;
            }
            subgrids += ((count-1)*count)/2;
        }
    return subgrids;
}

В вашем первом примере count=0 для любой пары строк, поэтому subgrid остается 0 тоже. Во втором примере есть три пары строк, а именно (a,b) = (0,1), (0,2) и (1,2), для которых count=2, например, subgrid=3 в конце.