"Автоматические друзья" ускорение алгоритма поиска

@Dewin · Регистрация: 17.07.2015

Студворк — интернет-сервис помощи студентам

Решал задание на Яндекс.Контест и возникла проблема,отправляю задание в систему и оно проходит только 24 теста из 32.
Условие:прикреплено
Задача:https://contest.yandex.ru/cont... r/#submits
Вот как я её решил.
Я понимаю что проблема в алгоритме поиска(много циклов),но как по другому решить не знаю.
Пробовал делать через двумерный массив,результат не меняется.

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.Scanner;
public class Main {
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b1[];
        int b2[];
        int b3[];
        int temp=0;
        int rez=0;
        b1 = new int[a];
        b2 = new int[a];
        b3 = new int[a];
 
        for (int i = 0; i < a; i++) {
            b1[i] = in.nextInt();//Заполняем массив
            b2[i] = in.nextInt();//Заполняем массив
            b3[i] = in.nextInt();//Заполняем массив
        }
        for (int jj = 0; jj < a - 1; jj++) {
            for (int j = jj + 1; j < a; j++) {
                temp = 0;
                if(b1[jj] == b1[j])
                    temp++;
                if(b2[jj] == b2[j])
                    temp++;
                if(b3[jj] == b3[j])
                    temp++;
                if (temp == 1)
                    rez++;
 
            }
 
        }
        System.out.print(rez);
    }
}

P.S. Первый раз на форуме

@easybudda · 20.07.2015, 18:59

Не по теме:

Сообщение от Dewin

Такую штуку нашел

Да ну, регистрации-шмегистрации...

Сообщение от KEKCoGEN

514k в задании сказанно

512 мегабайт, правда, по времени ограничение 2 секунды...
Вот это

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
package easybudda.possiblefriends;
 
import java.util.*;
import java.io.*;
 
public class PossibleFriends {
    static final String INPUT_FILE_NAME = "onlyone.in";
    static final int TESTS_COUNT = 3;
    static final int A = 0;
    static final int B = 1;
    static final int C = 2;
    static final int TEST_VALUES = 101;
    
    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws IOException {
        Scanner scanner = null;
        Set<?>[][] matrix = new Set<?>[TESTS_COUNT][TEST_VALUES];
        long friends = 0;
        
        try {
            scanner = new Scanner(new BufferedReader(new FileReader(INPUT_FILE_NAME)));
            int rows = scanner.nextInt();
            for ( int i = 0; i < rows; ++i ) {
                int a = scanner.nextInt();
                int b = scanner.nextInt();
                int c = scanner.nextInt();
                                
                if ( matrix[A][a] != null ) {
                    if ( ( matrix[B][b] == null ) && ( matrix[C][c] == null ) )
                        friends += matrix[A][a].size();
                    else {
                        Set<Integer> setA = new HashSet<Integer>((Collection<? extends Integer>) matrix[A][a]);
                        if ( matrix[B][b] != null )
                            setA.removeAll(matrix[B][b]);
                        if ( matrix[C][c] != null )
                            setA.removeAll(matrix[C][c]);
                        friends += setA.size();
                    }
                }
                if ( matrix[B][b] != null ) {
                    if ( ( matrix[A][a] == null ) && ( matrix[C][c] == null ) )
                        friends += matrix[B][b].size();
                    else {
                        Set<Integer> setB = new HashSet<Integer>((Collection<? extends Integer>) matrix[B][b]);
                        if ( matrix[A][a] != null )
                            setB.removeAll(matrix[A][a]);
                        if ( matrix[C][c] != null )
                            setB.removeAll(matrix[C][c]);
                        friends += setB.size();
                    }
                }
                if ( matrix[C][c] != null ) {
                    if ( ( matrix[A][a] == null ) && ( matrix[B][b] == null ) )
                        friends += matrix[C][c].size();
                    else {
                        Set<Integer> setC = new HashSet<Integer>((Collection<? extends Integer>) matrix[C][c]);
                        if ( matrix[A][a] != null ) 
                            setC.removeAll(matrix[A][a]);
                        if ( matrix[B][b] != null ) 
                            setC.removeAll(matrix[B][b]);
                        friends += setC.size();
                    }
                }
                
                if ( matrix[A][a] == null )
                    matrix[A][a] = new HashSet<Integer>();
                ((Set<Integer>)matrix[A][a]).add(i);
                if ( matrix[B][b] == null )
                    matrix[B][b] = new HashSet<Integer>();
                ((Set<Integer>)matrix[B][b]).add(i);
                if ( matrix[C][c] == null )
                    matrix[C][c] = new HashSet<Integer>();
                ((Set<Integer>)matrix[C][c]).add(i);
                
                /*
                System.out.printf("a = %d b = %d c = %d\n", a, b, c);
                System.out.println("Matrix[A][a] = " + matrix[A][a]);
                System.out.println("Matrix[B][b] = " + matrix[B][b]);
                System.out.println("Matrix[C][c] = " + matrix[C][c]);
                System.out.println("Friends count " + friends);
                */
            }
        }
        finally {
            if ( scanner != null )
                scanner.close();
        }
        
        System.out.println("Найдено " + friends + " возможных друзей");
    }
}

на 100 тысячах строк с тройками значений [1; 100] минуты за полторы отработало (перебора на 100К не дождался).

@Dewin · 21.07.2015, 10:00 **[ТС]**

easybudda, Теперь 21 тест проходит,я думаю что нужно идти по другому алгоритму в котором меньше проходов в цикле,только вот какому...

@KEKCoGEN · 21.07.2015, 10:11

Dewin, вы пробовали имплементировать мой алгоритм?

@Dewin · 21.07.2015, 15:12 **[ТС]**

KEKCoGEN, Прочитал его еще раз,думаю это то что нужно,попробую реализовать как смогу,совсем забыл про него

Добавлено через 4 часа 8 минут
KEKCoGEN, Что нужно сделать чтобы обратиться к созданному list'у?

Java
1
2
3
4
5
6
....
Map<Integer,List<Integer>> m1 = new HashMap<Integer,List<Integer>>();
        for (int i = 0; i < a; i++) {
            b1[i] = in.nextInt();//Заполняем массив
            m1.put(b1[i],new ArrayList<Integer>());
....

Добавлено через 5 минут
Все,нашел.

Java
1
m1.put(b1[i], new ArrayList<Integer>(Arrays.asList(i)));

Добавлено через 9 минут
Блин,теперь он их складывает,как же с этими листами и мапами сложно

@easybudda · 30.07.2015, 02:11

Сообщение от Dewin

только вот какому...

"Я думал, думал, я всё понял!" (с)

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
package easybudda.possiblefriends;
 
import java.util.Scanner;
import java.io.*;
 
public class PossibleFriends {
    static final String DEFAULT_FILE_NAME = "onlyone.in";
    static final int VALUES = 101;
    
    public static void main(String[] args) {
        Scanner scanner = null;
        int[][][] counters = new int[VALUES][VALUES][VALUES];
        int records = 0;
        
        try {
            scanner = new Scanner(new BufferedReader(new FileReader(DEFAULT_FILE_NAME)));
            records = scanner.nextInt();
            
            int a, b, c;
            for ( int i = 0; i < records; ++i ) {
                a = scanner.nextInt();
                b = scanner.nextInt();
                c = scanner.nextInt();
                counters[a][b][c] += 1;
            }
        }
        catch (IOException e) {
            System.err.println("Trouble with input file!");
            System.exit(1);
        }
        finally {
            if ( scanner != null )
                scanner.close();
        }
        
        int friends = 0;
        for ( int i = 1; i < VALUES; ++i ) {
            for ( int j = 1; j < VALUES; ++j ) {
                for ( int k = 1; k < VALUES; ++k ) {
                    if ( counters[i][j][k] != 0 ) {
                        int x, y, z;
                        for ( y = j + 1; y < VALUES; ++y ) {
                            for ( x = 1; x < VALUES; ++x ) {
                                if ( x == k )
                                    continue;
                                friends += counters[i][j][k] * counters[i][y][x];
                            }
                        }
                        for ( z = i + 1; z < VALUES; ++z ) {
                            y = j;
                            for ( x = 0; x < VALUES; ++x )
                                if ( x != k )
                                    friends += counters[i][j][k] * counters[z][y][x];
                            x = k;
                            for ( y = 0; y < VALUES; ++y )
                                if ( y != j )
                                    friends += counters[i][j][k] * counters[z][y][x];
                        }
                    }
                }
            }
        }
        
        System.out.println("Possible friends: " + friends);
    }
 
}

Не шибко быстрый, но не зависит от размера входа (если не считать времени на чтение файла). Зависит от плотности распределения значений. Без понятия, как сложность этого алгоритма определить. Кстати, если кто знает, где доходчиво объясняется, как определить сложность алгоритма, или может своими словами понятно объяснить - буду бескрайне благодарен!

Сообщение от KEKCoGEN

Определим матрицу смежности N x N где N - кол-во пользователей.

При количестве пользователей 100К это будет большая матрица, в пол-гига точно не влезет...

Новые блоги и статьи Все статьи Все блоги /
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .
Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .	Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .

@Dewin 1 / 1 / 1 Регистрация: 17.07.2015 Сообщений: 8
	21.07.2015, 10:00 [ТС]
	easybudda, Теперь 21 тест проходит,я думаю что нужно идти по другому алгоритму в котором меньше проходов в цикле,только вот какому... 0

@KEKCoGEN 2399 / 2224 / 565 Регистрация: 28.12.2010 Сообщений: 8,672
	21.07.2015, 10:11
	Dewin, вы пробовали имплементировать мой алгоритм? 0