Сокращение временной сложности с п ^ 2

Question

В классе n учеников.Скоро будет межшкольный научный тест, в котором будут вопросы по 4 предметам, для простоты назовите их 1,2,3 и 4.В команде должно быть 2 студента.Любой студент в равной степени может быть хорошим или плохим по определенному предмету.

Мы заданы в качестве входных n строк, в каждой по 4 записи.Ученик хорош по i -ому предмету, если i -й столбец равен 1. Я должен выяснить общее количество способов, которыми школа может отправить команду, чтобы два ученика вместезнать все 4 предмета.

Например,

S1: 1 1 1 1
S2: 1 1 0 1
S3: 1 0 1 1
S4: 0 0 1 1
S5: 0 0 0 0

Ученик 1 может пойти с любым учеником, поскольку все предметы - его сила.=> 4

Студент 2 может пойти с S3 и S4, так как S2 хорош по предметам 1,2 и 4, а S3 и S4 хорошо по предмету 3. => 2 (Обратите внимание, что (S1, S2)было уже подсчитано)

S3 пойдет с одним хорошим у субъекта 2 => нет

S4: аналогично, нет.

Следовательно, ans = 4 + 2 = 6

Мое решение: -

ans=0;
//arr is the array containing subject-wise "strength" of students
for(int i=0;i<n;i++){
    ArrayList<Integer> a=new ArrayList<>();
    for(int j=0;j<4;j++)
        if(arr[i][j]==0)
            a.add(j);
    if(a.size()==0)
        ans+=n-i-1;
    else
        for(int j=i+1;j<n;j++){
            bool=false;
            for(int k=0;k<a.size();k++){
                if(arr[j][a.get(k)]==0)
                    break;
                bool=true;
            }
            if(bool)
                ans++;
        }
}
System.out.println(ans);

Теперь я знаю, что мое решение верное, но его временная сложность составляет O (n ^ 2), и я ищу лучшее решение длятак же.Спасибо!

Answer 1

Вы можете уменьшить сложность количества учеников, потратив память на комбинации предметов.

Составьте список из 2 ^ s элементов, где s - количество предметов.Индексируйте список комбинациями предметов, интерпретируемых как двоичное число.Например, S2 имеет значение 13, и отсутствует значение 2.

Сначала подсчитайте «потребности», которые может удовлетворить каждый студент.Для каждой комбинации 1 битов в известных предметах учащегося увеличивайте этот индекс списка подсчета.

for student in student_list:

    score =   # student's covered subjects as an int

    tally = [0]*16
    for idx in range(16):
        if idx & score == idx:
            tally[idx] += 1

Теперь у вас есть список того, сколько учеников может охватить каждую комбинацию необходимых предметов.Это O (n * 2 ^ s)

Для каждого учащегося найдите необходимый балл, 1-е дополнение к баллу студента.Теперь просто сложить все подсчеты для нужных результатов.

team_ct = 0

for student in student_list:

    needed =   # student's needed subjects as an int; this is 15-score (above)
    team_ct += tally[needed]

Теперь каждая пара была посчитана дважды, поэтому разделите team_ct на 2. Да, этот последний бит кодаможет быть сброшен в одну строку:

team_ct = sum([tally[15-score] for score in foo]) / 2

, где foo является структурой всех оценок учащихся.Эта часть O (n) .