Конкурс CodeForces > 1761 \ Задача C (Построение множества) — Как решить эту задачу? ⇐ C#

[Anonymous]

Ребята, я работал над этой проблемой с утра (4 часа назад) и до сих пор не нашел правильного ответа. Как я могу установить подмножества с этими условиями? Например, набор A является подмножеством A2, но не подмножеством A3 и т. д. Как мне установить правильный алгоритм? Может ли кто-нибудь мне помочь?
ссылка на проблему: https://codeforces.com/contest/1761/problem/C#
< ul>
[*]Объяснение проблемы:
Задача «Построение множества» от Codeforces требует построения наборов на основе заданной двоичной матрицы с определенными правилами включения и сравнения. Давайте разберемся:

Объяснение проблемы

• Входные данные:
  • У вас есть двоичная матрица b с размерами n x n, где каждый элемент равен 0 или 1. .
• Выход:
  • Вам необходимо создать n наборов ( A_1, A_2, \dots, A_n ), состоящих из различных целых чисел от 1 до ( n ).
  • Условия:
    
    Каждый комплект должен быть непустой и различимый.
  • Матрица b указывает на отношение подмножества между этими наборами:
    
    Если b[j] = 1, то набор ( A_i ) должен быть правильным подмножеством ( A_j ).
  • Если b[j] = 0, то набор ( A_i ) не должен быть подмножеством ( A_j ).
• Правильное подмножество:
  • Набор ( A_i ) — это правильное подмножество ( A_j ), если все элементы ( A_i ) находятся в ( A_j ), а ( A_i ) строго меньше (т. е. ( A_i \neq A_j )).

Построение наборов
Чтобы создать наборы:
< ol>
[*]Начните с каждого набора, содержащего его индекс: ( A_i = {i+1}).
[*]Для каждой единицы в матрице b[j ] добавьте элементы ( A_i ) к ( A_j ).

Пример
Для например, если матрица b равна:

Код: Выделить всё

0 1 0
0 0 1
0 0 0

• Это указывает на то, что ( A_1 ) должно быть правильным подмножеством ( A_2 ), а ( A_2 ) должно быть правильным подмножеством ( A_3 ). Таким образом, у вас может быть:
  
  ( A_1 = {1} )
• ( A_2 = {1, 2} )
  ( A_3 = {1, 2, 3} )

Это обеспечивает правильные отношения подмножества, как указано в матрице b.
Примечания по реализации
Решение включает в себя перебор матрицу и обеспечение того, чтобы наборы были построены в соответствии с правильными отношениями подмножеств. Для каждой единицы в матрице устанавливаются соответствующие отношения множества. Если встречается ноль, соответствующие множества не должны иметь отношения подмножества.
Пример:

Код: Выделить всё

- Input
2
4
0001
1001
0001
0000
3
011
001

- Output
3 1 2 3
2 1 3
2 2 4
4 1 2 3 4
1 1
2 1 2
3 1 2 3

• Мой код C# здесь:

Код: Выделить всё

int t = int.Parse(Console.ReadLine());

for (int i = 0; i < t; i++)
{
int n = int.Parse(Console.ReadLine());
int[,] b = new int[n, n]; // nxn size, 2d array def

for (int j = 0; j < n; j++)
{
for (int k = 0; k < n; k++)
{
b[j, k] = int.Parse(Console.ReadLine()); //gets the matrix members
}
}

List sets = new List(); //a list for Sets

for (int j = 0; j < n; j++)
{
HashSet set = new HashSet(); // a new set for j. row
set.Add(j++);

for (int k = 0; k < n; k++)
{
if(b[j,k] == 0) {
set.Add(k++);

} else if(b[j,k] == 1) {
set.Add(k++);
if(sets[k].Contains(k++))
set.Remove(k++);
}
}

sets.Add(set);
}
}

Что мне делать после этого?
Я пытался решить проблему, но не смог найти правильного решения. Я ожидаю **помощи ** в поиске *правильного *и *действительного *решения.

Подробнее здесь: https://stackoverflow.com/questions/788 ... e-this-pro