Здравствуйте, Буравчик, Вы писали:

Б>http://code.google.com/codejam/contest/
Б>В правой части — Previous Contests. Верхняя строчка — искомая квалификация. Остальное — задачи с 2008 года.

Прикольные задачки, но очень простые. Из третей задачи естественным образом получается этюд для любителе CT C++.

Я так понял, что надо написать программу, которая ищет сколькими способами можно найти заданную подпоследовательность (в задаче это "welcome to code jam").

В целом, как решать понятно. Нужно собрать автомат, которому скормить последовательность, а он в конце посчитает нужный ответ. Но, насколько я понял условия, оптимизировать надо время работы программы, а подпоследовательность меняться не может, то хорошо бы автомат строить ещё ДО получения задания. Например в CT.
Собственно вот и этюд: написать С++ программу, которая строит такой автомат в СТ...

Здравствуйте, Erop, Вы писали:

E>В целом, как решать понятно. Нужно собрать автомат, которому скормить последовательность, а он в конце посчитает нужный ответ. Но, насколько я понял условия, оптимизировать надо время работы программы, а подпоследовательность меняться не может, то хорошо бы автомат строить ещё ДО получения задания. Например в CT.
E>Собственно вот и этюд: написать С++ программу, которая строит такой автомат в СТ...

Не совсем понятно о каком автомате идет речь. Но если этот автомат проходит по всем возможным вариантам, то ускорять работу автомата по-моему бесполезно. Количество вариантов растет экспоненциально. Значит при таком подходе получится решить "small", но не "large".

А вот с помощью динамики эту задачу можно решить за О(длина строки * длина паттерна).

Здравствуйте, Буравчик, Вы писали:

Б>Не совсем понятно о каком автомате идет речь.
Б>А вот с помощью динамики эту задачу можно решить за О(длина строки * длина паттерна).

Ну тот самый автомат, который ты назвал "динамикой".
Состояние автомата такое: на каждую позицию образца храним сколькими способами можно дойти до этой позиции в образце.

А переход делаем так: на каждую букву храним список позиций в состояни автомата, в которые можно перейти по этой букве.
Ну и соответственно во всех этих позициях делаем += счётчик из предыдущей позиции.
Вот заполнение этой второй таблички и можно бы перенести с СТ...

Ясно, что задача имеет чисто академический интерес, но и тем не менее...

Здравствуйте, Erop, Вы писали:

E>В целом, как решать понятно. Нужно собрать автомат, которому скормить последовательность, а он в конце посчитает нужный ответ. Но, насколько я понял условия, оптимизировать надо время работы программы, а подпоследовательность меняться не может, то хорошо бы автомат строить ещё ДО получения задания. Например в CT.
E>Собственно вот и этюд: написать С++ программу, которая строит такой автомат в СТ...

Там, казалось бы, автомат получается со сверхбольшим словом состояния — вектор чисел (по модулю 1000) длиной в искомую последовательность плюс 1.

//                     0         1
//                     0123456789012345678
const char phrase[] = "welcome to code jam";
const int length = sizeof(phrase)-1;

int state[length+1] = { 1, };

void shift(int i) { (state[i+1] += state[i]) %= 1000; }

const char* text;
for( ; *text; ++text )
{
    const char t = *text;
    
    switch(t)
    {
    case 'w': shift(0); break;
    case 'e': shift(1); shift(6); shift(14); break; // если два шифта смежные, надо делать справа налево
    case 'l': shift(2); break;
    case 'c': shift(3); shift(11); break;
    case 'o': shift(4); shift(12); break;
    case 'm': shift(5); shift(18); break;
    case ' ': shift(7); shift(10); shift(15); break;
    case 't': shift(8); break;
    case 'd': shift(13); break;
    case 'j': shift(16); break;
    case 'a': shift(17); break;
    }
}
int total = state[length];

Буду подумать, как эту красоту на boost/mpl перепереть.

Здравствуйте, Кодт, Вы писали:

Ну да, до этого места всё очевидно.

К>Буду подумать, как эту красоту на boost/mpl перепереть.
Ну в этом и вопрос.

А можно подробнее, для глупых — где там автомат

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

Можно пойти еще дальше и сразу заполнять матрицу с кешем в итоге будет квадратичная сложность алгоритма.

Здравствуйте, bayda, Вы писали:

B>Можно пойти еще дальше и сразу заполнять матрицу с кешем в итоге будет квадратичная сложность алгоритма.

А квадратичная от чего?

Смотри, как бы можно было это решать.

Заводишь массив целых чисел, соответсвующих позиции перед образцом, позициям между буквами образца, и позиции за образцом. В каждом числе будем хранить скольбкими способами можно дойти до этой позиции образца
Зануляем это всё, в 0-ю позицию пишем 1 и начинаем обрабатывать строку по одному символу.
Типа когда к нам приходит какой-то сомвол, скажем 'a', то мы смотрим в каких позициях образца может быть 'a', например это 5-я, 7-я и 28-я позиции. Соответсвенно во всех способах, которыми мы к этому моменту могли прийти в 6-ю позицию, можно принять символ 'a' и тем самым получить ровно столько новых способов прийти в 7-ю позицию, сколько есть способов прийти в 6-ю.

То есть мы должны к 7-му числу прибавить 6-е, к 5-му, 4-е и к 28-му 27-е. Ну и так далее по всем буквам.
спсики позиций получаем заранее, так что поиск не нужен, как бы...

Так что без рекурсии и кэша, а просто проползя с таким вот вектором вдоль предъявленного текста, получаем в конце число способов выбрать из текста образец...

Здравствуйте, bayda, Вы писали:

B>А можно подробнее, для глупых — где там автомат

B>Помоему она решается брутфорсом.

Брутфорсом решается всё на свете, вопрос лишь в цене брутфорса.

B>Но так как это долго будет работать мы можем обратить внимание на то, что наша рекурсивная ф-ция вызывается очень часто для одних и тех же значений.
B>Поэтому можно прикрутить небольшой кеш, куда складывать уже вычисленные значения.
B>И если в кеше уже есть значение — то будем брать его оттуда.
B>Можно пойти еще дальше и сразу заполнять матрицу с кешем в итоге будет квадратичная сложность алгоритма.

Пойдём ещё дальше и будем хранить не всю матрицу, а только интересующий нас столбец.
И получаем обычное динамическое программирование.
А сложность там — O(S) памяти и O(T*S) времени, где S — длина искомой строки, T — длина текста.
На самом деле, скорость можно поднять до O(T*R), где R — количество повторений вхождений символов в строке (для "welcome to code jam" R=4 — пробелы).

E>> А квадратичная от чего?
Округлил, когда говорил квадратичная — на самом деле O( M * N ),
где M — длина искомой строки, N — длина входной строки.

E>> Смотри, как бы можно было это решать.
E>> ....
Спасибо, идею понял — интересно.

K>> Пойдём ещё дальше и будем хранить не всю матрицу, а только интересующий нас столбец.
скорее два столбца, вычесленный и текущий — над которым работаем на данной итерации

Здравствуйте, Erop, Вы писали:

E>Смотри, как бы можно было это решать.

E>Заводишь массив целых чисел, соответсвующих позиции перед образцом, позициям между буквами образца, и позиции за образцом. В каждом числе будем хранить скольбкими способами можно дойти до этой позиции образца
E>Зануляем это всё, в 0-ю позицию пишем 1 и начинаем обрабатывать строку по одному символу.
E>Типа когда к нам приходит какой-то сомвол, скажем 'a', то мы смотрим в каких позициях образца может быть 'a', например это 5-я, 7-я и 28-я позиции. Соответсвенно во всех способах, которыми мы к этому моменту могли прийти в 6-ю позицию, можно принять символ 'a' и тем самым получить ровно столько новых способов прийти в 7-ю позицию, сколько есть способов прийти в 6-ю.

E>То есть мы должны к 7-му числу прибавить 6-е, к 5-му, 4-е и к 28-му 27-е. Ну и так далее по всем буквам.
E>спсики позиций получаем заранее, так что поиск не нужен, как бы...

По-моему вы с Кодтом слегка перемудрили. Вот мой write only исходник решения этой задачи. В таком варианте вроде и CT версия попроще должна быть.

const string s = "welcome to code jam";
string u;
int f[512][20];
int len;

int Count(int i, int j)
{
    if (j == len) return 1;
    if (i == u.size()) return 0;
    int& res = f[i][j];
    if (res != -1) return res;
    res = Count(i+1, j);
    if (u[i] == s[j])
    {
        res += Count(i+1, j+1);
    }
    res %= 10000;
    return res;
}

int main()
{
    len = s.size();
    ifstream ifs("c.in");
    ofstream ofs("c.out");
    getline(ifs, u);
    int t;
    sscanf(u.c_str(), "%d", &t);
    for (int test = 0; test < t; ++test)
    {
        memset(f, -1, sizeof(f));
        getline(ifs, u);
        int res = Count(0, 0);
        ofs << "Case #" << test+1 <<": " << setfill('0') << setw(4) << res << endl;
    }
    return 0;
}

Здравствуйте, bayda, Вы писали:

B>скорее два столбца, вычесленный и текущий — над которым работаем на данной итерации
Зачем? Это же копировать лишнее всё время прийдётся!
Вполне достаточно идти от больших позиций к маленьким и всё...

Здравствуйте, _DAle_, Вы писали:

_DA>По-моему вы с Кодтом слегка перемудрили. Вот мой write only исходник решения этой задачи.
Это медленнее. Там же предъявляют сразу пачку фрагментов для подсчёта числа вариантов?
На каждый фрагмент прийдётся занулять int f[512][20]...

_DA>В таком варианте вроде и CT версия попроще должна быть.
С чего бы? CT-то только автомат сам строит по образцу. Фрагменты-то в RT предъявляются...

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, _DAle_, Вы писали:

_DA>>По-моему вы с Кодтом слегка перемудрили. Вот мой write only исходник решения этой задачи.
E>Это медленнее. Там же предъявляют сразу пачку фрагментов для подсчёта числа вариантов?
E>На каждый фрагмент прийдётся занулять int f[512][20]...

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

_DA>>В таком варианте вроде и CT версия попроще должна быть.
E>С чего бы? CT-то только автомат сам строит по образцу. Фрагменты-то в RT предъявляются...
Ну я имел ввиду, что сами шаблончики проще, если бы у нас все было в константах. А так.. написать генератор cpp кода с инстанцированием нужных шаблонов

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, bayda, Вы писали:

B>>скорее два столбца, вычесленный и текущий — над которым работаем на данной итерации
E>Зачем? Это же копировать лишнее всё время прийдётся!

ну тут, если быть дотошным то std::vector<>::swap(...) поможет избежать излишней траты времени.
т.е. будет два вектора previous и current, а в конце каждой итерации их будет свопать.

E>Вполне достаточно идти от больших позиций к маленьким и всё...
тоже вариант, почему-то это мне сразу не пришло в голову

Здравствуйте, _DAle_, Вы писали:

_DA>Это медленнее, но исходный посыл был вроде решить задачу. При данных ограничениях сложность копеечная. Да, и занулять f необязательно, и вообще рекурсию можно убрать, я просто показал простое рекуррентное соотношение.

Посыл был "решить как можно быстрее"

E>>С чего бы? CT-то только автомат сам строит по образцу. Фрагменты-то в RT предъявляются...
_DA>Ну я имел ввиду, что сами шаблончики проще, если бы у нас все было в константах.

С чего проще?

Здравствуйте, bayda, Вы писали:


B>ну тут, если быть дотошным то std::vector<>::swap(...) поможет избежать излишней траты времени.
B>т.е. будет два вектора previous и current, а в конце каждой итерации их будет свопать.
Ну если уж реально быть дотошным, то надо ещё занулять. Либо весь вектор, либо как-то интеллектуально.
В то время, как вариант с одним вектором никаких издержек не порождает прост и прям

E>>Вполне достаточно идти от больших позиций к маленьким и всё...
B>тоже вариант, почему-то это мне сразу не пришло в голову
Ну бывает...
Мне от чего-то казалось, что решение очевидное. И нетривильно тут только написать CT генерилку автомата, IMHO
Ясно, что написать RT-генерилку -- дело плёвое...

К сожалению, меня понял только Кодт...

Здравствуйте, Erop, Вы писали:

E>>>С чего бы? CT-то только автомат сам строит по образцу. Фрагменты-то в RT предъявляются...
_DA>>Ну я имел ввиду, что сами шаблончики проще, если бы у нас все было в константах.

E>С чего проще?

Уговорил, не будет проще.

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, Буравчик, Вы писали:

Б>>http://code.google.com/codejam/contest/
Б>>В правой части — Previous Contests. Верхняя строчка — искомая квалификация. Остальное — задачи с 2008 года.

E>Прикольные задачки, но очень простые. Из третей задачи естественным образом получается этюд для любителе CT C++.

E>Я так понял, что надо написать программу, которая ищет сколькими способами можно найти заданную подпоследовательность (в задаче это "welcome to code jam").

E>В целом, как решать понятно. Нужно собрать автомат, которому скормить последовательность, а он в конце посчитает нужный ответ. Но, насколько я понял условия, оптимизировать надо время работы программы, а подпоследовательность меняться не может, то хорошо бы автомат строить ещё ДО получения задания. Например в CT.
E>Собственно вот и этюд: написать С++ программу, которая строит такой автомат в СТ...

Такие задачки можно (и нужно) параллелить. Например, так (в два потока):

/* Sample output
Number of tests: 7
Test #1:
thread #0: left
thread #1: right
Test #2:
thread #0: left
thread #1: right
Test #3:
thread #0: left
thread #1: right
Test #4:
thread #0: left
thread #1: right
Test #5:
thread #0: leftthread #1: right

Test #6:
thread #0: left
thread #1: right
Test #7:
thread #0: left
thread #1: right
*/

#include <iostream>
#include <iomanip>
#include <fstream>

#include "omp.h"

#define PARALLEL

using namespace std;

const __int64 module = 10000;

// welcome string
const char welcome[] = "welcome to code jam";
const int len = sizeof(welcome) - 1;
struct Positions {
    static int pos[256][1 + len]; // for each char # of occurences and positions (0-based)
    Positions() {
        // fill in positions for all chars in str
        memset(pos, 0, sizeof pos);
        for (int i = 0; i < len; ++i) {
            pos[(unsigned char)welcome[i]][++pos[(unsigned char)welcome[i]][0]] = i;
        }
    }
} positions;
int Positions::pos[256][1 + len];

// statistics
__int64 stats_left[len + 1];
__int64 stats_right[len + 2];

// count
void count_left(const char * text, const int split) {
    memset(stats_left, 0, sizeof stats_left);
    stats_left[0] = 1;
    int max = 0; // maximum substring length found so far
    const char * end = text + split;
    while (text < end && *text != welcome[0]) ++text;
    while (text < end) {
        int * row = &Positions::pos[(unsigned char)*text++][0];
        const int num = *row;
        for (int i = 0; i < num; ++i) {
            if (*++row > max) break;
            stats_left[*row + 1] = (stats_left[*row + 1] + stats_left[*row]) % module; // bug: doesn't work for 'double-letters'
            if (*row == max) {
                ++max;
                break;
            }
        }
    }
}

void count_right(const char * text, const int split) {
    memset(stats_right, 0, sizeof stats_right);
    stats_right[len + 1] = 1;
    int min = len - 1; // minimum position found so far - 1
    const char * end = text + split;
    text += strlen(text);
    while (text > end && *--text != welcome[len - 1]) {}
    while (text >= end) {
        int * row = &Positions::pos[(unsigned char)*text--][0];
        const int num = *row;
        for (int i = num; i > 0; --i) {
            if (row[i] < min) break;
            stats_right[row[i] + 1] = (stats_right[row[i] + 1] + stats_right[row[i] + 2]) % module; // bug: doesn't work for 'double-letters'
            if (row[i] == min) {
                --min;
                break;
            }
        }
    }
}

// ******* MAIN *******
void main(void) {
    ifstream ifil("c.in");
    ofstream ofil("c.out");
    int N;
    char buf[1024];
    {
        ifil.getline(buf, 1024);
        sscanf_s(buf, "%d", &N);
    }
    cout << "Number of tests: " << N << endl;
    ofil << setfill('0');
    for (int test = 0; test < N; ++test) {
        cout << "Test #" << (test + 1) << ':' << endl;
        ifil.getline(buf, 1024);
        int split = strlen(buf) / 2;
#ifdef PARALLEL
    #pragma omp parallel sections shared(buf, split)
    {
    #pragma omp section
    {
        cout << "thread #" << omp_get_thread_num() << ": ";
#endif
        cout << "left" << endl;
        count_left(buf, split);
#ifdef PARALLEL
    }
    #pragma omp section
    {
        cout << "thread #" << omp_get_thread_num() << ": ";
#endif
        cout << "right" << endl;
        count_right(buf, split);
#ifdef PARALLEL
    }
    }
#endif
        __int64 result;
        {
            result = stats_left[len] + stats_right[1];
#ifdef PARALLEL
    #pragma omp parallel for reduction(+:result)
#endif
            for (int i = 1; i < len; ++i) {
                result = (result + stats_left[i] * stats_right[i + 1]) % module;
            }
#ifdef PARALLEL
            result %= module;
#endif
        }
        ofil << "Case #" << (test + 1) << ": " << setw(4) << result << endl;
    }
    ifil.close();
    ofil.close();
}

Здравствуйте, Erop, Вы писали:

К>>Буду подумать, как эту красоту на boost/mpl перепереть.
E>Ну в этом и вопрос.

Сперва определюсь, как делать свитч.
Удобнее всего — на таблице функций. Это быстро работает (хотя и медленно компилируется).

// для ввода-вывода
#include <iostream>
#include <iomanip>
#include <string>

using std::cin;
using std::cout;
using std::endl;

// std::fill_n, std::for_each
#include <algorithm>

/////////////////////
// Boost MPL

#include <boost/mpl/vector_c.hpp>

#include <boost/mpl/size.hpp>
#include <boost/mpl/range_c.hpp>

#include <boost/mpl/filter_view.hpp>
#include <boost/mpl/equal_to.hpp>
#include <boost/mpl/at.hpp>
#include <boost/mpl/int.hpp>

#include <boost/mpl/reverse.hpp>
#include <boost/mpl/copy.hpp>

#include <boost/mpl/for_each.hpp>

//////////////////////////
// Boost PP

// fill the table
#include <boost/preprocessor/repetition/enum.hpp>


///////////////////////
// compile time...

namespace mpl = boost::mpl;

// искомая фраза
typedef mpl::vector_c<char,
    'w', 'e', 'l', 'c', 'o', 'm', 'e', ' ',
    't', 'o', ' ',
    'c', 'o', 'd', 'e', ' ',
    'j', 'a', 'm'
    > phrase;

// длина фразы
const int len = mpl::size<phrase>::value;

// номера позиций
typedef mpl::range_c<int, 0, len> allpositions;
// как мы уже знаем, инкремент вектора состояния делается от хвоста к голове: подготовимся
typedef mpl::reverse< allpositions, mpl::back_inserter< mpl::vector_c<int> > >::type invpositions;

// номера позиций (от хвоста к голове) данной буквы
template<char C>
struct positions_of :
    mpl::filter_view<
        invpositions,
        mpl::equal_to< mpl::at<phrase, mpl::_>, mpl::int_<C> >
    >
{};

void print_char(char c) { cout << c; }

////////////////////////////
// run time...

// вектор состояния
// раз уж всё тащим в CT, то и с динамической памятью заморачиваться не будем
int cases[len+1];

// начало: {1, 0,...,0 }
void init_cases()
{
    cases[0] = 1;
    std::fill_n(cases+1,len, 0);
}

// перенос с позиции N на N+1
void shift(int n)
{
    cout << "shift(" << n << ") ";
    (cases[n+1] += cases[n]) %= 1000;
}

// перенос всех позиций для данной буквы
template<char C> void processC()
{
    cout << "processC<" << C << "> ";
    mpl::for_each< positions_of<C> >(shift);
}

// таблица функций
// в диапазоне printable ascii (уж больно долго, зараза, компилится... сократил объём работ)
void (* const processes[128-32])(void) =
{
    // генерируем с помощью PP
    // к сожалению, BOOST_PP_ENUM(256...) дал отсечку по глубине раскрытия макросов
    // пришлось по кусочкам напилить
#define PROCESS(z,n,t) processC<(t+n)>
    BOOST_PP_ENUM(32, PROCESS, 32) ,
    BOOST_PP_ENUM(32, PROCESS, 64) ,
    BOOST_PP_ENUM(32, PROCESS, 96) ,
#undef PROCESS
};

// скармливаем автомату очередной символ
void feed_char(char c)
{
    cout << "'" << c << "' --> ";
    if(c >= 32 && c <= 128)
    {
        void(*f)() = processes[ (unsigned char)c-32 ];
        f();
    }
    else
        cout << "skip" << endl;
    cout << endl;

    // распечатываем вектор состояния
    for(int i=0; i!=len+1; ++i)
        cout << std::setw(4) << std::setfill('0') << cases[i] << " ";
    cout << endl;
}


int main()
{
    // проверяем, как выглядит фраза
    cout << "phrase: ";
    mpl::for_each<phrase>(print_char);
    cout << endl;

    // построчно читаем входной файл (или консоль) и для каждой строки решаем задачу
    std::string text;
    while(std::getline(cin, text))
    {
        cout << "input: " << text << endl;
        init_cases();
        std::for_each(text.begin(), text.end(), feed_char);
        cout << "result = " << cases[len] << endl;
    }
}

Здравствуйте, vadimcher, Вы писали:

V>Такие задачки можно (и нужно) параллелить. Например, так (в два потока):
А можно на пальцах изложить, что и как там параллелится? Что-то у меня под вечер мозг опух с листа читать.