Программирование, т. 8

Почитай "грокаем алгоритмы"

Много раз слышал что норм для вката

Кто нибудь вообще запоминает информацию которую не использует? На правах бтв

Бтв(2) думал че за название странное, имя автора все расставило по местам

Кто нибудь вообще запоминает информацию которую не использует? На правах бтв

Нет офк, максимум помнишь что что-то слышал или помнишь где найти ее

бтв(2), ты че мне книгу от какой-то индуски посоветовал? roflanebalo

"Алгоритмы - это всего лишь пошаговые алгоритмы решения задач," - начало хорошее))

takpadazhi

Слышал что у индусов хорошие алгоритмы умножения

чуваки, кто нибудь в шаде учился? есть отзывы

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

Thats were u are

 

Кто нибудь вообще запоминает информацию которую не использует? На правах бтв

Нет офк, максимум помнишь что что-то слышал или помнишь где найти ее

 

бтв(2), ты че мне книгу от какой-то индуски посоветовал? roflanebalo

"Алгоритмы - это всего лишь пошаговые алгоритмы решения задач," - начало хорошее))

takpadazhi

 

кнут к твоим услугам

https://ru.wikipedia.org/wiki/Искусство_программирования

Решил попробовать стажировку в яндексе.

Тестовое задание первое, лимит 130мб 6 секунд, хуй во время вписываюсь. 

А вообще не честно что на с++ питон и жаву одинаковые лимиты

видимо ты проебался с сложность алгоритма, раз они взяли потолок по питону

и там явно не самый оптимизированный вариант взят

че за задание то, или оно персональное и нельзя светить? 

6 заданий на них 6 часов, это первое и я уже часа 2 с ним ебусь

Сперва упирался в память, а потом во время.

Не ебу сколько у них там тестовых наборов и какие они

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentSkipListSet;
import java.util.concurrent.atomic.AtomicInteger;

public class Main {

    public static void main(String[] args) {
        int wordCount = -1;
        List<String> words = new ArrayList<>(2048);
        try (Scanner scan = new Scanner(System.in)) {
            while (scan.hasNextLine()) {
                String nextLine = scan.nextLine();
                if (wordCount < 0) {
                    wordCount = Integer.valueOf(nextLine);
                    if (wordCount <= 0) {
                        break;
                    }
                } else {
                    words.add(nextLine);
                    if (--wordCount <= 0) {
                        break;
                    }
                }
            }
        }
        Map<AbstractMap.SimpleEntry<String, String>, AtomicInteger> graph = new ConcurrentHashMap<>(2048, 1f);
        words.parallelStream().forEach(string -> {
            int length = string.length();
            String prev = null;
            for (int i = 0; i < length - 2; i++) {
                String substring = string.substring(i, i + 3).trim();
                if (prev == null) {
                    prev = substring;
                } else {
                    AbstractMap.SimpleEntry<String, String> entry = new AbstractMap.SimpleEntry<>(prev, substring);
                    AtomicInteger mutableInt = graph.get(entry);
                    if (mutableInt == null) {
                        mutableInt = new AtomicInteger(1);
                    } else {
                        mutableInt.incrementAndGet();
                    }
                    graph.put(entry, mutableInt);
                    prev = substring;
                }
            }
        });
        int size = graph.size();
        Set<String> unique = new ConcurrentSkipListSet<>();
        graph.entrySet().parallelStream().map(Map.Entry::getKey).forEach(key -> {
            unique.add(key.getKey());
            unique.add(key.getValue());
        });
        System.out.println(unique.size());
        System.out.println(size);
        graph.entrySet().parallelStream().forEach(simpleEntryAtomicIntegerEntry -> System.out.printf("%s %s %d%n", simpleEntryAtomicIntegerEntry.getKey().getKey(), simpleEntryAtomicIntegerEntry.getKey().getValue(), simpleEntryAtomicIntegerEntry.getValue().get()));
    }
}

Финальный код. Понимаю уже что надо было сразу пилить свой класс на граф, а не ебаться с имеющимися.

Дохуя ошибок на этой странице, а первые уже смыло

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

Кстати пробовал в экзекьюторы запихивать таски между scan.nextLine() но тоже не сильно время забустилось

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;

public class Main {


    public static void main(String[] args) throws InterruptedException, ExecutionException {
        Scanner scan = new Scanner(System.in);
        int wordCount = -1;
        ExecutorService executor = Executors.newFixedThreadPool(8);
        Map<AbstractMap.SimpleEntry<String, String>, AtomicInteger> graph = new ConcurrentHashMap<>(2048, 1f);
        Set<String> unique = new ConcurrentSkipListSet<>();
        List<Future> futures = new ArrayList<>();
        while (scan.hasNextLine()) {
            String string = scan.nextLine();
            if (wordCount < 0) {
                wordCount = Integer.parseInt(string);
                if (wordCount <= 0) {
                    break;
                }
            } else {
                Future<?> submit = executor.submit(() -> {
                    int length = string.length();
                    String prev = null;
                    for (int i = 0; i < length - 2; i++) {
                        String substring = string.substring(i, i + 3).trim();
                        if (prev == null) {
                            prev = substring;
                            unique.add(substring);
                        } else {
                            AbstractMap.SimpleEntry<String, String> entry = new AbstractMap.SimpleEntry<>(prev, substring);
                            AtomicInteger mutableInt = graph.get(entry);
                            if (mutableInt == null) {
                                mutableInt = new AtomicInteger(1);
                            } else {
                                mutableInt.incrementAndGet();
                            }
                            graph.put(entry, mutableInt);
                            prev = substring;
                            unique.add(substring);
                        }
                    }
                });
                futures.add(submit);
                if (--wordCount <= 0) {
                    break;
                }
            }
        }
        futures.forEach(future -> {
            try {
                future.get();
            } catch (InterruptedException e) {
                e.printStackTrace();
            } catch (ExecutionException e) {
                e.printStackTrace();
            }
        });
        //scan.close();
        //thread.join();
        int size = graph.size();
        System.out.println(unique.size());
        System.out.println(size);
        graph.entrySet().parallelStream().forEach(entry -> System.out.printf("%s %s %d%n", entry.getKey().getKey(), entry.getKey().getValue(), entry.getValue().get()));
        System.exit(0);
    }
} 

Мей би сканер не лучший выбор, никогда не задавался вопросом маскимального быстродействия System.in System.out

Ууууу блять я долбоеб

Зачем я сука каждый раз дрочу put на mapу

ну задачка не выглядит суперсложной, но в джавовой лапше я так не опознаю затык, уже поздно

правда я больше охуеваю с начала задачи. причем тут вообще автоматическая генерация текстов к перебору бессмысленных последовательностей по 3 буквы из всех слов и их подсчета?

нахуя они вообще это вступление вставили?

сходу могу разве что сказать, что не понятно нахуя тебе трим в

String substring = string.substring(i, i + 3).trim();

тупо лишнее выделение памяти под такую же строку

там ведь ровно по 1 слову в строке, нет пробелов, трим никогда ничего не сделает

ну и как бы не оказалось, что параллелизация только хуже сделала

Я тоже хз, 

Последнее задание, сейчас бы помнить что такое мат ожидание

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        int wordCount = scanner.nextInt();
        List<String> words = new ArrayList<>(2048);
        while (wordCount-- > 0) {
            String nextLine = scanner.nextToken();
            words.add(nextLine);
        }
        Map<AbstractMap.SimpleEntry<String, String>, MutableInt> graph = new HashMap<>(4096, 1f);
        Set<String> unique = new HashSet<>(4096, 1f);
        for (String string : words) {
            int length = string.length();
            String prev = null;
            for (int i = 0; i < length - 2; i++) {
                String substring = string.substring(i, i + 3).trim();
                if (prev == null) {
                    prev = substring;
                    unique.add(prev);
                } else {
                    AbstractMap.SimpleEntry<String, String> entry = new AbstractMap.SimpleEntry<>(prev, substring);
                    MutableInt mutableInt = graph.get(entry);
                    if (mutableInt == null) {
                        mutableInt = new MutableInt();
                        graph.put(entry, mutableInt);
                        unique.add(substring);
                    } else {
                        mutableInt.integer++;
                    }
                    prev = substring;
                }
            }
        }
        System.out.println(unique.size());
        System.out.println(graph.size());
        for (Map.Entry<AbstractMap.SimpleEntry<String, String>, MutableInt> entry : graph.entrySet()) {
            AbstractMap.SimpleEntry<String, String> key = entry.getKey();
            MutableInt value = entry.getValue();
            System.out.printf("%s %s %d%n", key.getKey(), key.getValue(), value.integer);
        }
    }

    static class MutableInt {
        int integer = 1;
    }


    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;


        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String nextToken() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(nextToken());
        }

    }
}

Код с которым удалось добраться до 26 теста. хуй знает сколько их там всего. Но я хуй знает что тут оптимизировать кроме как написать свой класс для графа.

графы для эффективности обработки можно хуярить как матрицы, но если я правильно на ночь еще что-то думаю, то

26 букв размещением по 3 штуки будет 26! / 23! = 24*25*26 = 15600

а матрица на 15600*15600 уже пробьет твой лимит по памяти, так что по простому не отделаться

нужны либо разреженные матрицы, либо возможно вообще префиксные деревья, но на строке из 3 элементов оно вряд ли даст что-то

еще потенциально как я понимаю ты можешь убрать нахуй твой AbstractMap.SimpleEntry в качестве ключа, тк он наверняка очень неэффективен будет

и заменить его на просто строку склеенную из обоих слов. У строки гетхэшкод должен быть очень быстрым

не могу пока найти причин по которым этот чит привел бы к проблемам

убрать нахуй твой AbstractMap.SimpleEntry<String, String> в качестве ключа

Ну там хеш: хеш ключа^хеш значения.

По сути класс - обычная пара.

А вот конкатенация сожрет как и память, так и время будет занимать.

Я бы просто хранил бы 3-хсимвольные вершины  в своем классе и вычислял бы безколлизийный хэш при конструировании.

Тогда бы даже с коллекциями работало бы быстрее, ибо hashCode() O(1) а eqals тоже в одно машинное слово.

о, я придумал как упороться

твой алфавит всего 26 символов, то есть влазит в 5 бит

три буквы влезут в 15 => 16 бит, а два слова значит в 32

итого ты пишешь функцию перевода двух строк в такой вот интовый хэшкод и ебёшь всех как бох

я надеюсь джава не будет хоть инты в куче выделять по одному? а то у вас дженерики хуевые, кто вас знает

а и ещё не понял по склейку

зачем что-то клеить, вырезай сразу 6 символов как ключ. в конце только уников посчитаешь разрезая пополам ключ предварительно

накидал для графов можешь попробовать https://pastebin.com/JSYpCaEh

я хз чем это лучше чем твое решение просто если оно не пройдет то мы хотя бы будем понимать что там нужны какие-то оптимизации по типу того что вы сейчас обсуждаете

накидал для графов можешь попробовать https://pastebin.com/JSYpCaEh

 

я хз чем это лучше чем твое решение просто если оно не пройдет то мы хотя бы будем понимать что там нужны какие-то оптимизации по типу того что вы сейчас обсуждаете

Ошибка представления.

Ты забыл вывести число вершин и число пар

Вход

2
aaaaaaaaaaaaa
aaabbbaaabbba

Как надо

6
7
aaa aaa 10
aaa aab 2
aab abb 2
abb bbb 2
bbb bba 2
bba baa 1
baa aaa 1

добавил вывод https://pastebin.com/pSZ3dYdG

бтв то что pairs имеет тип long это называется лень считать. 40к * 30 в инт влезет

Но я сделал за тебя через

        out.println(adj.size());
        out.println(adj.entrySet().stream().mapToInt(value -> value.getValue().size()).sum());

К слову всего 36 тестов

Мде даже обидно, выходит 2 вложенные мапы выебали мою хуйню в одну. 

На иммутабельных интах