Блог пользователя Bidanets

Автор Bidanets, история, 22 месяца назад, По-русски

Условие задачи

Дан набор строк $$${S}_{1}, {S}_{2}, \ldots, {S}_{n}$$$ (в общем случае разной длины), состоящих из строчных букв латинского алфавита.

Дана строка $$$T$$$ (запрос пользователя), также состоящая из строчных букв латинского алфавита.

Каждая строка $$${S}_{i} (i = 1, \dots, n)$$$ содержит не более $$$k$$$ слов.

Строка $$$T$$$ также содержит не более $$$k$$$ слов.

Слова отделены пробелами.

Необходимо найти «наиболее похожую» на запрос пользователя строку из набора $$${S}_{1}, {S}_{2}, \dots, {S}_{n}$$$.

Будем учитывать, что:

  1. Пользователь мог поменять слова местами.

  2. Пользователь мог ввести только часть (подпоследовательность) строки, которую хотел найти в наборе.

  3. Пользователь мог допустить опечатки: пропуск букв, написание лишних букв, замена букв на другие.

Решение

Рассмотрим простейшее решение.

Переберём все перестановки слов запроса $$$T$$$.

Для каждой перестановки слов $$${T}_{permutation}$$$ переберем все строки $$${S}_{i}$$$, и запустим алгоритм $$$LCS({T}_{permutation}, {S}_{i})$$$.

LCS — longest common subsequence.

Из всех строк $$${S}_{1}, {S}_{2}, \dots, {S}_{n}$$$ выберем те строки, для которых величина $$$|LCS({T}_{permutation}, {S}_{i})|$$$ — максимальна. Также запомним для какой именно перестановки $$${T}_{permutation(saved)}$$$ была получена эта максимальная величина LCS. Обозначим полученное множество строк как $$$L$$$.

Теперь вычислим расстояние Левенштейна между соответствующими $$${L}_{i}$$$ и $$${T}_{permutation(saved)}$$$.

Выберем единственную строку $$${L}_{ans}$$$, для которой расстояние Левенштейна с соответствующей $$${T}_{permutation(saved)}$$$ — минимально. Эта строка и будет ответом.

Код на Java:

public int F(char x, char y)
{
    if (x == y) return 0;
    else return 1;
}

public int GetDist(String a, String b)
{
    int[][] D = new int[100][100];
    D[0][0] = 0;
    for (int i = 1; i < a.length(); i++)
    {
        D[i][0] = i;
    }
    for (int j = 1; j < b.length(); j++)
    {
        D[0][j] = j;
    }
    for (int i = 1; i < a.length(); i++)
    {
        for (int j = 1; j < b.length(); j++)
        {
            int m = F(a.charAt(i), b.charAt(j));
            int val1 = D[i][j-1] + 1;
            int val2 = D[i-1][j] + 1;
            int val3 = D[i-1][j-1] + m;

            int minv = Math.min(val1, val2);
            minv = Math.min(minv, val3);
            D[i][j] = minv;
        }
    }
    return D[a.length()-1][b.length()-1];
}



public String[] swap(String data[], int left, int right)
{
    // Swap the data
    String temp = data[left];
    data[left] = data[right];
    data[right] = temp;

    // Return the updated array
    return data;
}


public int Compare(String a, String b)
{
    for (int i = 0; i < Math.min(a.length(), b.length()); i++)
    {
        if (a.charAt(i) < b.charAt(i))
        {
            return -1;
        }
        if (a.charAt(i) > b.charAt(i))
        {
            return 1;
        }
    }
    if (a.length() < b.length()) return -1;
    if (a.length() > b.length()) return 1;
    return 0;
}

public String[] findNextPermutation(String p[])
{
    for (int a = p.length - 2; a >= 0; --a)
    {
        if (Compare(p[a], p[a+1]) == -1)
        {
            for (int b = p.length-1; ; --b)
            {
                if (Compare(p[b], p[a]) == 1)
                {
                    String t = p[a];
                    p[a] = p[b];
                    p[b] = t;
                    for (++a, b = p.length-1; a < b; ++a, --b)
                    {
                        t = p[a];
                        p[a] = p[b];
                        p[b] = t;
                    }
                    return p;
                }

            }
        }
    }
    return p;
}

public int Factorial(int n)
{
    int fact = 1;
    for (int i = 2; i <= n; i++)
    {
        fact *= i;
    }
    return fact;
}

public int GetLenMaxSubSeq(String a, String b)
{
    int[][] dp = new int[100][100];

    dp[0][0] = 0;
    for (int i = 1; i <= a.length(); i++)
    {
        dp[i][0] = 0;
    }

    for (int j = 1; j <= b.length(); j++)
    {
        dp[0][j] = 0;
    }

    for (int i = 1; i <= a.length(); i++)
    {
        for (int j = 1; j <= b.length(); j++)
        {
            if (a.charAt(i-1) == b.charAt(j-1))
            {
                dp[i][j] = dp[i-1][j-1] + 1;
            }
            else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
        }
    }

    int maxv = 0;
    for (int i = 0; i <= a.length(); i++)
    {
        for (int j = 0; j <= b.length(); j++)
        {
            if (dp[i][j] > maxv)
            {
                maxv = dp[i][j];
            }
        }
    }
    return maxv;
}

public Pair PermutateSubSeq(String a, String b)
{
    int max_len = 0;

    String[] b_arr = b.split("\\s+");
    Arrays.sort(b_arr);

    String res = "";

    for (int cur_permutation = 0; cur_permutation < Factorial(b_arr.length); cur_permutation++)
    {
        int cur_len = GetLenMaxSubSeq(a, b);

        if (cur_len > max_len)
        {
            max_len = cur_len;
            res = b;
        }

        b_arr = findNextPermutation(b_arr);
        b = "";
        for (int i = 0; i < b_arr.length-1; i++)
        {
            b += b_arr[i] + " ";
        }
        b += b_arr[b_arr.length-1];
    }

    Pair pair = new Pair();
    pair.Val = max_len;
    pair.str = res;

    return pair;
}

public int GetIndex(String name, int N)
{
    int index = 0;
    int maxlensubseq = 0;
    int min_dist = 10000;

    for (int i = 0; i < N; i++)
    {
        Pair p = PermutateSubSeq(arr[i], name);
        int cur_subseq_len = p.Val;
        String str = p.str;

        if (cur_subseq_len > maxlensubseq)
        {
            maxlensubseq = cur_subseq_len;
            index = i;
        }

        if (cur_subseq_len == maxlensubseq)
        {
            int cur_dist = GetDist(arr[i], str);
            if (cur_dist < min_dist)
            {
                min_dist = cur_dist;
                index = i;
            }
        }
    }
    return index;
}

Полный текст и комментарии »

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

Автор Bidanets, история, 9 лет назад, По-русски

Здравствуйте, уважаемые участники CF! Кто-нибудь из сообщества поступал в ШАД? Если да, то есть такие вопросы: как вы готовились к экзаменам на поступление? какие рекомендации мы могли бы дать поступающим? сколько примерно книг можно брать на экзамен? можно ли на экзамене пользоваться конспектами? как проходит экзамен? где можно посмотреть (и можно ли вообще) статистику поступивших за прошлые годы? конкурс общий для всех филиалов или для каждого отдельно?

Было отправлено письмо на почту ШАД. В ожидании ответа.

UPD: Пришел ответ, может кому будет полезно: На экзамене можно пользоваться любыми печатными или рукописными материалами. Под запретом любая техника (например, нельзя смотреть сканированные книги с ноутбука). По поводу задачников вряд ли что-то можно добавить к спискам, приведённым в программе для поступающих. По алгебре однозначно мы рекомендуем задачник Кострикина. На хабрахабре есть разборы двух вариантов письменного экзамена: http://habrahabr.ru/company/yandex/blog/220561/ http://habrahabr.ru/company/yandex/blog/262543/ Во втором из них есть небольшая статистика решивших. Других данных по успехам поступающих на письменном экзамене мы не публиковали. В филиалах конкурс отдельный и проходные баллы часто отличаются от московских, хотя они обычно используют наши варианты письменного экзамена.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

Автор Bidanets, история, 9 лет назад, По-русски

Здравствуйте, уважаемые участники CF! Заинтересовали генетические алгоритмы. Возможно, кому-нибудь попадались задачи, решаемые генетическим алгоритмом? На Википедии говорится, что генетические алгоритмы применяются в игровых стратегиях, но поиск в интернете почти ничего не дал. Так же интересны задачи из области, в которой объединены медицина/биология/генетика и программирование/математика, решаемые генетическими алгоритмами. Если кому-попадались задачи (может на марафонах каких-нибудь), буду очень рад, если вы расскажите о них. Так же если кому попадались задачи, связанные с транспортом и инфраструктурой городов, решаемые вышеуказанным алгоритмом, было бы интересно, если вы расскажите об этом.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

Автор Bidanets, 10 лет назад, По-русски

Здравствуйте, участники сообщества CF! Кто-нибудь знает, существуют ли разборы чемпионатов Урала в интернете? Если да, то не могли бы вы поделиться ссылкой? А то поиском гугла ничего не нашел. :) А еще интересуют разборы Петрозаводских сборов. Есть ли они в открытом доступе?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +24
  • Проголосовать: не нравится

Автор Bidanets, 10 лет назад, По-русски

Уже третий день не работает тимус. В чем может быть проблема? Кто-нибудь знает о том, когда возобновят работу?

Написал на почту [email protected]. письмо, жду ответа.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +58
  • Проголосовать: не нравится