1. C++ / Говнокод #16672

    +50

    1. 1
    2. 2
    3. 3
    4. 4
    5. 5
    6. 6
    7. 7
    8. 8
    9. 9
    if (tp==-1 || c==a[tp]-'a') tp++; else {
    		l[ts+1]=la;  p[ts+1]=ts;
    		l[ts]=l[tv];  r[ts]=tp-1;  p[ts]=p[tv];  t[ts][c]=ts+1;  t[ts][a[tp]-'a']=tv;
    		l[tv]=tp;  p[tv]=ts;  t[p[ts]][a[l[ts]]-'a']=ts;  ts+=2;
    		tv=s[p[ts-2]];  tp=l[ts-2];
    		while (tp<=r[ts-2]) {  tv=t[tv][a[tp]-'a'];  tp+=r[tv]-l[tv]+1;}
    		if (tp==r[ts-2]+1)  s[ts-2]=tv;  else s[ts-2]=ts; 
    		tp=r[tv]-(tp-r[ts-2])+2;  goto suff;
    	}

    Говнокод олимпиадный.

    http://e-maxx.ru/algo/ukkonen

    Запостил: gost, 09 Сентября 2014

    Комментарии (51) RSS

    • говнокод-то говнокод, а вы попробуйте написать его более читабельно. Ну, не учитывая переименование переменных. Если вам удастся добиться компромисса между длиной (олимпиады на время, помним) кода и его читабельностью - вам искренне будет благодарно все олимпиадное сообщество (без сарказма).
      Ответить
    • Где здесь С++, gost?!
      Ответить
      • >>> map<char,int> next;
        Здесь.
        Ответить
        • Ага. Пока многие олимпиадники заучивали свои структуры данных, я пинал балду и нагло юзал STL...

          По опыту - при мало-мальски нормальном алгоритме (не брутфорс) прога никогда не упиралась в память или таймауты...

          P.S. Хотя, возможно, из-за такого отношения к задротству мы дальше региональных туров и не покатались...
          Ответить
          • > STL
            ололо
            первая и последняя для меня олимпиада по информатике проводилась за уютными синими борманд турбо с++
            Ответить
            • Первая олимпиада была классе где-то в 9. Припёрся я на нее, думал, что нам дадут компы... Ага, хуй там! Вся олимпиада проводилась ручкой на бумажке. Чуть не устроил rage quit.

              Потом в физмате - те самые синеокие борманд-пасцаль, да борманд-хуй-поймешь-си-или-кресты. Олимпиады были пиздец унылые и проверялись левой пяткой преподов. Стимула как-то по-особому готовиться к ними не было никакого.

              А вот когда в институте катались на ACM - там уже можно было юзать шестую (вроде бы) вижуалку со всеми вытекающими.

              > последняя
              А мне не хотелось отказываться от халявной командировки на пару дней. Так что катались частенько :) Заодно закупались всяким железом да cd-r, которые в нашем городке стоили дороже. Ну и трофеи от олимпиад остались на память - флешка, мышка, да годная клава.
              Ответить
              • халявная командировка это всегда хорошо
                но ещё лучше, когда тебя в ней не напрягают и не возлагают надежд

                на ту областную "олимпиаду" по программированию мы поехали вообще без подготовки, т.к. нас никто не натаскивал от слова вообще
                максимум догадывались про сортировку пузырьком
                так что просто весело провели время (и заодно я посмотрел, в каком плачевном материальном состоянии находится областной технический вуз)
                Ответить
                • > не возлагают надежд
                  Да никто особых надежд на нас и не возлагал... Все прекрасно понимали, что если кто-то прошел на региональный тур, поехал туда и занял не последнее место - это уже круто.

                  > напрягают
                  А из натаскиваний было только прорешивание задачек за неделю до олимпиады. Выбирали что поинтересней, да решали... А чтобы дротить каждый день без перерывов - такого у нас не было.
                  Ответить
                  • > А чтобы дротить каждый день без перерывов - такого у нас не было.
                    Прочитать как "дотить каждый день". Задумался.
                    Ответить
                    • Не, мы тогда рубились в контру/старкрафт в машзалах (вместо лекций по машграфике и foxpro) или собирались у друга на хате и играли вшестером в worms...

                      P.S. Первая дота, емнип, уже была, но не зацепила.
                      Ответить
                      • Да я не о доте. Лично я никогда в неё не играл.

                        >Не, мы тогда рубились в контру/старкрафт в машзалах
                        Нам нигде и никогда такого не позволяли. Разве что в школе пару уроков кваки было. А, и в универе на древних компах практика дюка нюкема, тоже один или джва раза.
                        Зато в универе те кто сумели разлочить, сидели на лентах в инете. С тогдашним дефицитом траффика, это было самое ценное времяпровождение.
                        Ответить
                        • на компах с древней виндой в аудиториях были "червы", в которые можно было играть вчетвером по LAN
                          тем временем инет был в основном только в терминальном доступе к линуксячему серверу
                          сидели в инете, читали новости и проверяли почту через links

                          зато в школьные годы я как раз ходил в 10-11 классе на курсы информатики, если быстро выполняешь план занятия, можно было бы поиграть в need for speed 4 на минимальной графе, или с товарищем в фифу-98
                          был отличный стимул сделать за 20 минут то, что рассчитано на час, и потратить оставшееся время на поиграть

                          тем более, что дома у меня не то что компа, даже сраной денди не было
                          Ответить
                          • >need for speed 4
                            nfs3,4 - божественные игры. И божественный саундтрек.
                            Ответить
                        • > Нам нигде и никогда такого не позволяли.
                          Просто этот зал был довольно мощным (в то время как будущие программисты писали лабы на дерьме с 98й виндой, в этом зале изучали ворд экономисты и менеджеры) и часто простаивал, а админил его наш хороший друг. Его начальник, входя в зал, ржал над тем, как некоторые запоздало пытаются свернуть контру и запустить борманд паскаль, после чего разгонял нас. А минут через 5 игра продолжалась...

                          P.S. Вспоминается, как мы just for lulz меняли заставку в главном меню контры на скриншот из BP.
                          P.P.S. А вот инет там был только платный (помимо школьного анлима, который дико лагал).
                          Ответить
          • Блин, письма от их onlinejudge не приходят на майлинатор :(
            Ответить
            • Наивное решение с std::search() и std::string.find() отшибло по timeout'у :(

              Ибо наивный поиск "aaa...b" в "aa...aa" длится вечность. KMP тут, наверное, помог бы.
              Ответить
              • >std::search() и std::string.find()
                Et tu, Bjarne?!
                Даже в крестах, в 2011 не осилили тривиальный строковой алгоритм 70-х?

                >KMP тут, наверное, помог бы.
                А я предупреждал об возможности атак...
                Ответить
          • >Пока многие олимпиадники заучивали свои структуры данных, я пинал балду и нагло юзал STL...
            Сразу виден настоящий программист. Ленивый.
            Пока поцоны пишут велосипеды, борманд берет либу, решает задачу в 10 раз быстрее и идёт читать ГК.
            Ответить
            • Я, честно говоря, опасаюсь олимпиадников.

              Мне кажется, у них может быть деформированное восприятие. Они вероятно, привыкли писать быстро, монолитно, не задумываясь о мелочах, в расчёте на положительный кейс.

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

              Правда, это лишь измышления, напрямую с успешными олимпиадниками мне не вот прям работать приходилось. Видимо, они не опускаются до той работы, что достаётся мне.
              Ответить
              • А если админ-олимпиадник? Что-то сломалось - быстро понял, быстро написал говноскрипт, быстро решил. Ничего не простаивает, все рады.
                В это время админ-программист только начинает рисовать диаграмму классов универсального решения этой и подобных проблем на 20 лет вперёд.
                Ответить
                • Нет, безусловно, навык быстренько говнячить трудно переоценить. Главное, чтобы это не было безусловным рефлексом...
                  Ответить
                • >админ-программист только начинает рисовать диаграмму классов универсального решения
                  Думаю со временем каждый учится душить внутри себя подобные порывы и расставлять приоритеты.
                  Ответить
              • > писать быстро, монолитно, не задумываясь о мелочах, в расчёте на положительный кейс
                "Хуяк-хуяк и в продакшен", имхо, тоже важное умение. Быстрое прототипирование, проверка идей, одноразовые скрипты и т.п. Самое сложное - заставить себя выкинуть этот прототип на помойку, а не обвешивать его деталями и проверками, превращая в ядро большой и сложной системы...
                Ответить
                • Ну сначала ты думаешь - заработало, говнецо конечно но ведь будет вторая итерация...
                  А потом понимаешь что вторая итерация не наступит никогда... никогда...
                  Если конечно кто нибудь не удалит код
                  Ответить
    • //Тот же самый код, прокомментированный:
      const int N=1000000    // максимальное число вершин в суффиксном дереве
      ;
      string a;       // входная строка, для которой надо построить дерево
      int 
      t[N][26],   // массив переходов (состояние, буква)
      l[N],   // левая 
      r[N],   // и правая границы подстроки из a, отвечающие ребру, входящему в вершину
      p[N],   // предок вершины
      s[N],   // суффиксная ссылка
      tv,     // вершина текущего суффикса (если мы посередине ребра, то нижняя вершина ребра)
      tp,     // положение в строке соответствующее месту на ребре (от l[tv] до r[tv] включительно)
      ts,     // количество вершин
      la;     // текущий символ строки
       
      void ukkadd(int c) {
      suff:;      // будем приходить сюда после каждого перехода к суффиксу (и заново добавлять символ)
      if (r[tv]<tp) { // проверим, не вылезли ли мы за пределы текущего ребра
      	// если вылезли, найдем следующее ребро. Если его нет - создадим лист и прицепим к дереву
      	if (t[tv][c]==-1) {t[tv][c]=ts;l[ts]=la;p[ts++]=tv;tv=s[tv];tp=r[tv]+1;goto suff;}
      	tv=t[tv][c];tp=l[tv]; // в противном случае просто перейдем к следующему ребру
      }
      if (tp==-1 || c==a[tp]-'a') tp++; else { // если буква на ребре совпадает с c то идем по ребру
      	// разделяем ребро на два. Посередине - вершина ts
      	l[ts]=l[tv];r[ts]=tp-1;p[ts]=p[tv];t[ts][a[tp]-'a']=tv;
      	// ставим лист ts+1. Он соответствует переходу по c.
      	t[ts][c]=ts+1;l[ts+1]=la;p[ts+1]=ts;
      	// обновляем параметры текущей вершины. Не забыть про переход от предка tv к ts.
      	l[tv]=tp;p[tv]=ts;t[p[ts]][a[l[ts]]-'a']=ts;ts+=2;
      	// готовимся к спуску: поднялись на ребро и перешли по суффиксной ссылке.
      	// tp будет отмечать, где мы в текущем суффиксе.
      	tv=s[p[ts-2]];tp=l[ts-2];
      	// пока текущий суффикс не кончился, топаем вниз
      	while (tp<=r[ts-2]) {tv=t[tv][a[tp]-'a'];tp+=r[tv]-l[tv]+1;}
      	if (tp==r[ts-2]+1) s[ts-2]=tv; else s[ts-2]=ts; 
      	// устанавливаем tp на новое ребро и идем добавлять букву к суффиксу.
      	tp=r[tv]-(tp-r[ts-2])+2;goto suff;
      }
      }
      Ответить
    • if (tp==r[ts-2]+1) s[ts-2]=tv; else s[ts-2]=ts;

      олимпиадник тернарники не осилил?
      Ответить
      • Вполне паскальненько.
        В определённых кругах тернарники спорная штука.
        Ответить
        • Ну не спорнее чем копипаст
          Ответить
          • Тернарники не нужны же:
            s[ts-2] = tv * (int)(tp==r[ts-2]+1) + ts * (int)(tp!=r[ts-2]+1);
            Ответить
            • Вычисли его! Вычисли его еще раз! bool сам себя не кастанет!
              Ответить
              • Да, можно обойтись одним умножением:
                s[ts-2] = ts + (tv - ts) * (int)(tp==r[ts-2]+1);
                Ответить
                • Я вообще предлагаю форсить нахождение максимума из 2 интов таким способом

                  max = a + (b-a)* (int)((a+b)/b==a)
                  Ответить
                  • А тут точно должно быть частное, а не остаток?
                    Ответить
                    • да, %, сорри
                      Ответить
                      • Тогда другое дело. Только может получиться некроссплатформенно при отрицательном b.
                        Ответить
                        • да и переполнение. Но никто не совершенен
                          Ответить
                  • Я предлагаю форсить нахождение среднего из джвух интов как
                    x = (a + b) / 2
                    А поклонников старшего бита посылать за числами большей разрядности.
                    Ответить
            • <пирфоманс>А два умножения точно будут быстрее 1 условия?</пирфоманс>
              Ответить
              • Конпелятор божественной сишечки с параметром -O2 сам заменит умножение на ветвление.

                Убедитесь сами: http://gcc.godbolt.org/

                P.S. Проверил, шланг заменяет на cmov, а питух-гцц оставляет умножение.
                Ответить
                • > Конпелятор божественной сишечки с параметром -O2 сам заменит умножение на ветвление.
                  А зачем тогда в коде заменять ветвление на умножение?
                  Ответить
                  • Потому что так красивее и не надо два раза писать s[ts-2]=
                    Ответить
                    • s[ts-2] = (tp==r[ts-2]+1) ? tv : ts;
                      ИМХО, красивее.
                      Ответить
                      • int x[] = {ts, tv};
                        s[ts-2] = x[tp==r[ts-2]+1];

                        А так?
                        Ответить
                        • Нужно больше массивов, в исходном говне их было явно недостаточно
                          Ответить
                          • Наоборот же, вместо нескольких одномерных массивов можно ввести один многомерный.

                            l[N], r[N] ­→ lr[2][N]
                            p[N], s[N] → ps[2][N]
                            tv, ts → x[2]
                            И так далее.
                            Ответить
                            • ты тут нам так реляционные базы данных придумаешь
                              Ответить
                              • Много переменных — это костыль, потому что приходится городить ненужные ифы. А так можно будет сразу выбирать по индексу.
                                Ответить
                        • Вот это по-нашему!
                          В более общем случае кто-то будет городить свищи и горы тернарников, а кто-то напишет ассоциативный массив.
                          Ответить
                          • Поскольку нет переходов, конвейер процессора будет использоваться эффективнее. Это же даст 0,01% к пирфомансу!
                            Ответить
                            • Ну память (кеш L1) 3 такта.
                              Хотя думаю оно сумеет в cmov...

                              Не хотелось бы гадать, ибо пути компилятора неисповедимы.
                              Ответить

    Добавить комментарий