Russian Code Cup — крупнейшая в России ежегодная открытая олимпиада для самых сильных программистов. Общий призовой фонд составляет 18 тыс. долларов. Предварительные этапы олимпиады проходят онлайн, а финал — в Москве. В 2012 г. соревнование пройдет уже во второй раз. В первом Russian Code Cup приняли участие более 3 000 человек.

Russian Code Cup — это вызов для тех, кто считает себя настоящим профи в программировании.

Первый тур весеннего Russian Code Cup состоится 27 мая. Чтобы принять участие, нужно зарегистрироваться.

http://russiancodecup.ru/

на сайте примеры задач...
сдается мне абсолютное большинство одинэсников их не сделает ;)

(0) а на 1С можно решать? :)

(1) там жестокие ограничения по времени и памяти, какая нафих 1С

(0) зашёл, увидел слово "ахроматическое", испугался, вышел

Антипалиндром
Ограничение по времени    2 секунды
Ограничение по памяти    256 мегабайт
Палиндромом называют строку, читающуюся одинаково с обеих сторон. Задана строка s. Найдите ее наибольшую по длине подстроку, не являющуюся палиндромом.
Формат входных данных    Входные данные содержат строку s. Она состоит только из строчных букв латинского алфавита, не пуста, а ее длина не превышает 100000 символов.
Формат выходных данных    В выходной файл выведите ответ на задачу. Если все подстроки s являются палиндромами, выведите в выходной файл NO SOLUTION.
Примеры    
Входные данные    Выходные данные
abba    abb




это за 2 секунды надо код написать ?

такая же фигня!
ну про антипалиндром я может и сделаю...
а про ахроматическое да ни в жисть...

(5) это фигня со вторых семестр вузов : дискретная математика

(6) я физик и дискретной математики у меня не было ;)

(4) 2сек на выполнение кода.
Вот то что задание неккоректное это да...
Из условия не понятно, входящая строка S изначально является палиндромом целиком или этот палиндром в ней еще найти надо?
Если строка S изначально вся полидром то зачем писать вообще код? Ответ будет:
подстрока = Лев(S,СтрДлина(S)-1);
или
подстрока = Прав(S,СтрДлина(S)-1);

(8) садись два
непрошел

все там корректно - страка может быть произвольная, вообще без палиндрома.. или вся быть палиндромом, или содержать гденить в серединке комбинацию aabbbbbaa

(0) да да ... настоящий прог

да настоящий 1сник 10 000$ за день зарабатывает и на логане ездит.

(0) + малый призовой фонд. от 100$ тыс.

(7) из какого вуза ?

(12) 9 классов средней школы г. Усть Заж.пинска

(13) не знаю

(9) В условии из (4) ни где не сказано что строка S "может быть произвольная, вообще без палиндрома", а в примере, там же, она является вся палиндромом. Поэтому я сразу оговорился в (8), что задание некорректно -)
Для твоего примера:
zxcxcaabbbbaazerty (палидром - aabbbbaa)
решение будет тоже самое что и выше:
подстрока = Лев(S,СтрДлина(S)-1);
или
подстрока = Прав(S,СтрДлина(S)-1);
так как в условии надо найти максимальную подстроку исходной строки S а не палидрома

ps отдай дневник -)

(15) там нигде не написано, что строка S - обязательно палиндром

(15) русские буквы позабыл? :)
найти надо "Антипалиндром"

В задаче антипалиндром есть непонятки.

выходные данные:
В выходной файл выведите ответ на задачу. Если все подстроки s являются палиндромами, выведите в выходной файл NO SOLUTION.

Входные данные    
abba
Выходные данные
abb

че такое abb? если это непалиндром подстроки, то почему он один, вить их больше
ab
ba
abb
bba

или я что-то не так понял?

п.с. У меня всегда так с этими олимпиадными задачами, и их условиями.

(18)ыыыы

1. ab и ba непоходят ибо они наименьшие по длинне
2. задача поставлена так "Найдите ее наибольшую по длине подстроку, не являющуюся палиндромом"
то есть пример abba не имеет решения ибо там нет наибольшей по длинне строки, так как abb и bba по длинне равны - то есть ни одна из них не является "наибольшей"

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

(17) Антипалиндром -  строка не являющаяся палиндромом. неа? -)
Надо найти максимальную такую подстраку.
Пример:
zxclcaabbbbaazerty (палибром внутри этой строки - "aabbbbaa")
максимальная подстрака не являющеяся палидромом
подстрока = Лев(S,СтрДлина(S)-1);
или
подстрока = Прав(S,СтрДлина(S)-1);

что не так? -))

(19)Все теперь понятно. Спасибо

(20) не так то, что вся этма строка не палиндром

какие мелочи
клиент для андройда стоит 5 миллионов

(15) Если входная строка "aaaaaaaaaaaaaaaaaaaaaaaaaaaa", то твой кон не работает...

+(24) кон = код

где функция определения палиндром или нет ?

а вообще нужно отщипывать по одному символу слева и справа
если встретили антипалиндром то он "наибольший" и задача решене

если ниче не встретили выводим нусубжект

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

задача решена в теории. реализовывать надо?

(27) "а вообще нужно отщипывать по одному символу слева и справа
если встретили антипалиндром то он "наибольший" и задача решене
если ниче не встретили выводим нусубжект"

Это шляпа, а не решение.

(28)Почему этот алгоритм не решит задаче?
тогда какие будут ваши варианты? перебрать все возможные подстроки, но тогда за 2 сек не успееете когда строка у вас 100000 символов

Как ба я написал условие:
Есть искодная трока S длинной от 2 до 100000 символов которая может содержать палидромы.
Найдите максималную подстраку палидрома которая не будет сама являться палидромом.

(29) Хотя... Я тут подумал... Наверное я поторопился с выводами :)

Функция палиндром (стр)
  длинаСтроки = стрДлина (стр);
  количество = Цел ( длинаСтроки  ) / 2;
  Для н = 1 по количество Цикл
      Если Сред(Стр, н, 1) <> Сред (Стр, длинаСтроки - н + 1) Тогда
          Возврат Ложь;
      КонецЕсли;
  КонецЦикла;
  Возврат Истина;
КонецФункции

(19) abb или bba

(33) давай упростим задачу

есть две строки:

abb
и
bba

верни пожалуйста максимальную из них по длинне

(34)Максимальные обе. А наибольшей, действительно нет.
Про графы задачка интересная, только она больше математическая, как мне кажется.

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

обходим всю строку посимвольно сначала и с конца одновременно - проверяем ее на палиндром и одновременно проверяем, что не все символы одинаковые. Время О(длина строки)

случай 1. строка не палиндром - это ответ
случай 2. все символы одинаковые - ответа нет
случай 3. строка палиндром
тогда подстрока от 2 символа до n - гарантировано не палиндром - эта подстрока ответ

(37) от символа 2 до n гарантировано антипалиндром, но не факт, что максимальный

(38) ну как же не факт, больше только вся строка, но она палиндром

+(37) n это последний символ строки

(40) а, тогда да

С полиндром хрень
?(ЭтоПолиндром(Строка),Сред(Строка,2),Строка);

Куда за бабаками подходить?

(37) твой алгоритм перестает работать если палиндром в строке есть и расположен нессиметрично..
например строка вида


uuuabbap

(42) забыл случай, когда все символы одинаковые
и вообще ты опоздал после (37)

(43) не перестанет, он выдаст
uuabbap

+(45) вру uuuabbap

(45) а да...
еще раз внимательно перечитал условие.. да все верно

тупым перебором можно просто решить задачу

(47) только время будет O(n^2)

(37) А интересно в решении подобных задач допускается применение многопоточности?
Ведь исходную строку можно побить на несколько, скажем так, "орбит" и сканировать одновременно несколько пар фрагментов одновременно.
"Орбита" - пара подстрок одинаковой длины равноудаленных от центра

итак
вот вам
http://clck.ru/d/KH8gRJ8P184rz
только в случае с abba
мой алгоритм возвращает bba
НО вить тоже верно?

(50) нах нам ехе, ты алгоритм покажи

(50) локдир туда впихнул??))

bool Palindrom(char *str)
{
   char str2[10000];
   int l = strlen(str);
   for(int i = 0;i<l;i++)
       str2[i] = str[l-i-1];
   str2[l] = '\0';
   if(strcmp(str,str2) == 0)return true;
   return false;
}
char* FindNoPalindrom(char* str)
{
   if(strlen(str) <=1) return "NO";
   if(Palindrom(str))
       return FindNoPalindrom((char*)&str[1]);
   else
       return str;
}
int _tmain(int argc, _TCHAR* argv[])
{
   while(1)
   {
       cout<<endl;
       cout<<"Input String"<<endl;
       char str[10000];
       cin>>str;
       if(strcmp(str, "-1") == 0)break;
       
       cout<<FindNoPalindrom(str);
       
   }
   cout<<"exit";
   return 0;
}

(53)Отщипывал тока первый символ. потом подумал. а надо ли последний?

(53) квадратичная зависимость времени от длины строки

(55)что?

(56) говорю, у тебя время выполнения алгоритма O(n^2) где n - длина строки
у меня O(n)

(57)аналогичный алгоритм. почему у меня времени больше?
или где ваше решение?

(58) моё в (37)
хотя нет, у вас алгоритм почти всегда быстро найдет за O(n) - кроме одинаковых строк
просто это на первый взгляд из него не видно, почти зачет в общем

(59)Меня больше интересует проблема того, что
в случае с abba
мой алгоритм возвращает bba. не как в примере.

я вить больше чем уверен, что проверяют не люди, а они как-то программкой программки проверяют.

(60) по идеи алгоритм вообще должен выдавать число
хотя тут сложности нет на проверку, думаю учли, всего три варианта:
1. либо вся строка
2. либо решения нет
3. либо одна из подстрок: откусили первый символ или откусили последний

итак переходим ко 2-й задаче.
и опять трудности в понимании условия:
дано число n Найдите ахроматическое число цикла длиной n. А где взять граф?

(62) Вам дано число n. Найдите ахроматическое число ЦИКЛА длиной n

то есть граф это цикл из n вершин

А чего голосовалки нет?
Задачи какие-то слишком простые, участвовать не буду - в июне в отпуске.

Длин=стрдлина(стр);
Если Длин<2 тогда
 возврат ложь;
конецесли;
перв=лев(стр,1)
полиндром=1;
одинсимвол=1;
Для а=1 по цел(длин/2) цикл
тек=сред(стр,а,1);
Если тек<>сред(стр,Длин+1-а,1)) тогда
     полиндром=0;
     прервать;
Иначеесли тек<>перв тогда
     одинсимвол=0;
Конецесли;
КонецЦикла;
Если полиндром=0 тогда
возврат стр;
Иначеесли (одинсимвол=1)и(перв=сред(стр,цел(длин/2)+1,1)) тогда
возврат ложь;
Иначе
возврат лев(стр,длин-1);
КонецЕсли;
// Задача явно не для олимпиад. Либо хотят устроить массовость за счет легких задач на первом туре

Вторая еще лучше - если нечетно, то выводим 3, иначе 2,
потом (a div 2) раз выводим "12", и если а нечетно, еще выводим один раз "3"

Посмотрел финальные задачи - тоже ничего сверхъественного, например задача о черепашке - просто классика динамического программирования.

(67) давай сложную

(68) Ну в финале там уже более менее задачи.
Но непонятно зачем на первых этапах они организуют такую массовость?
Надо сразу отсеивать тех у кого шансов в финале нет.

А задачи в финале надо давать нестандартные, я не мастер выдумывать задачи - но задача о торте, и о черепашке - явно не первой свежести, условие остальных пока не читал.

(69) Зачем отсеивать? Для многих важна не победа, а участие.

(70)Да не будем показывать пальцем!

(70) Потому что они позиционируются как крутое соревнование среди профи, а задачи первого тура на уровне школьной контрольной по программированию.

(72)Ну видать задача первого тура выяснить, человек умеет вообще код писать или нет

Выйти можно из любого отборочного. Так что буду участвовать.

http://habrahabr.ru/company/mailru/blog/119187/
Вот тут есть примеры решений задач.

(1) http://russiancodecup.ru/rules/#rounds
3.Решением задачи является программа, написанная на одном из допустимых языков программирования: Java, Python, C/C++, C#, Perl.
Проверяющая система будет использовать следующие компиляторы:
•Java 6.0
•Python 3.1
•Python 2.6
•Microsoft Visual C# 2010 Express Edition
•Microsoft Visual C/C++ 2010 Express Edition
•GNU C/C++ MinGW 4.5
•Perl 5.10
•PHP 5.3.6

Попробовал - что-то очень медленно у меня на JAVA пишется :(

Что-то ветка затухла, неужели никто кроме меня не хочет попробовать свои силы?
Результаты вчерашней попытки написания на JAVA у меня - первый этап предыдущего отборочного тура - все задачи по 10 минут, последняя за час. В последней долго разбирался с работой с длинными числами в JAVA.

а че, ассемблер уже не котируется?

(79) А что, бывают олимпиады на ассемблере?

(0) Да ладно про полидром то че не решить, вот с графами надо разбираться.
В полидроме надо перебрать все комбинации возможных строк и проверить является ли полидромом, если не является запомнить длину и само подстроку и т.д. В результе будет самый длинный не полидром.

(78) Ты молодец конечно. Нам на тебя надо равняться, ты исключение из всех конфигурастов. Займись просветительской работой над конфигурастами. Расскажи с чего начать, какие книги почитать. Только не надо кнута советовать :)

По сути это ближе к математической олимпиаде, математика которую нужно воплотить в коде.

(81)Твое решение про палиндром не зачтут, т.к. оно не уложится в ограничение по времени. Правильный подход см в (37)

Кнут хороший... мне очень первый том нравится...
даже больше чем руководство по ассемблеру system 360/370

Через полчаса старт первой квалификации.

(86)дашь списать?

Дам, через три часа после старта. :)

Полностью пролетел на неумении работать со строками в JAVA.
Постоянный вылет с непонятной ошибкой, если строка только одна, причем если больше - то всё почему-то работает.

В итоге первую задачу написал, а на четвертой завис.

import java.io.*;
import java.util.Scanner;
public class z4 {
   public static void main(String[] args) throws IOException {
       
       BufferedReader in = new BufferedReader(
               new InputStreamReader(System.in));
       Scanner in1 = new Scanner(System.in);
       int m=in1.nextInt();
       String[] s;
       s=new String[m+1];
       for (int i=1;i<=m;i++)
       {
       s[i] = in.readLine();
       };
       int n=in1.nextInt();
       String[] e;
       e=new String[n+1];
       for (int i=1;i<=n;i++)
       {
       
       e[i] = in.readLine();
       };
       String ss,ss1,ss2="";
       char c;
       int d=e[1].length();
       int t=0;
       for (int i=0;i<d;i++)
       {
           ss1="";
           for (int j=1;j<=n;j++)
           {
               ss1=ss1+e[j].substring(i,d);
               if (i>0) {ss1=ss1+e[j].substring(0,i);};
           };
           ss1=".."+ss1+"..";
           ss="";
           for (int j=0;j<ss1.length();j++) {c=ss1.charAt(j);if (c!='.'){ss=ss+c;}else{ss=ss+"QQ";}};
           //System.out.println(ss);
           for (int j=1;j<=m;j++) ss=ss.replaceAll("Q"+s[j]+"Q","Q");
           //System.out.println(ss);
           ss=ss.replaceAll("Q"," ").trim();
           if (ss.length()<2) {t=t+1;ss2=ss2+Integer.toString(i)+" ";};
           
       }
       System.out.println(t);
       System.out.print(ss2);
   }

}

Почему-то вылетает, если входная строка всего одна.

При этом для квалификации было достаточно решить всего две задачи...

Блин, не знал что replaceAll, не просто заменяет, а применяет регулярные выражения,
Иначе бы написал замену простым проходом.

Прикол, но уже на куче тестов проверил - у меня всё работает, а у них выдавала рунтайм еррор.
ЧТо-то странное...

Чемпион предыдущего года решил всего две задачи.
В четвертой задачи сами организаторы предлагают решение основанное на словаре и хеш-функции. У меня с одной задачи 371-ое место из нескольких тысяч участников. Придется сделать вторую попытку второго июля.

Бред какой-то - как я написал не читает из файла, работает только при ручном построчном вводе, а если поменять in.readLine(); в двух местах на in1.next() - то всё работает. И их тест проходит. :(

(0) пора уже Mista Code Cup организовывать с присвоением победителю "Почетные 22 см"

Всю ветку не читал, Рома Печенкин будет участвовать? Как единственный профи на форуме.

(4)
  Если Палиндром(s) Тогда
    Результат = Лев(s, n-1) или (или Сред(s, 2, ))
  Иначе
     Результат = s
  КонецЕсли;

автор темы тролль
было же уже много аналогичных кодеджемов и сфера если совсем скучно

(100)

(96) первый приз похоже заслуженно получит NS

(99) да тролль и не скрываю этого ;)

да я сто лет не заходил на форум, регнулся во втором этапе приму участие, если не напьюсь опять)

втором квалификационном раунде*

Вопреки известной поговорке «спички детям не игрушка», один мальчик очень любит играть со спичками. Но он не балуется ими, не разжигает огонь, а решает различные головоломки. Например, он умеет приравнивать число девять к числу одиннадцать, переложив только одну спичку.
Недавно родители этого мальчика подарили ему несколько наборов, каждый из которых состоит из двенадцати спичек. Мальчик начал собирать из них различные геометрические фигуры. Он уже собрал много различных фигур, но теперь ему стало интересно: из каких наборов возможно склеить каркас параллелепипеда при помощи двенадцати спичек из набора и клея? Ломать спички нельзя и ни одна из спичек не должна выступать за каркас.
Ваша задача состоит в том, чтобы по известным длинам спичек для каждого набора проверить, можно ли из них склеить каркас параллелепипеда.



итак мой вариант решения:
1) помещаем числа в массивчик
2) сортируем числа
1 1 1 1 2 2 2 2 3 3 3 3 (дада эти самые)
3) берем по 4-ре числа. если в каждой четверке числа равны, то тогда УЕС иначе нет.

в каком случае мой алгоритм будет не рабочим?

а блин там ответы есть....

на кодеджеме на той же квалификации вроде веселее все было

(101) Первый не получу.
Я разговаривал с человеком - олимпиадные программисты - это специализация, они постоянно занимаются решением олимпиадных задач, у них куча готовых тестов, и знают они весьма специфичные олимпиадные вещи, типа полиномиальных хешей и т.д.

У меня цель одна - пройти в финал, ну и сначала конечно-же пройти в отборочный тур. За 20+ лет прошедших с последней олимпиады я напрочь потерял навык.

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

После того как система дала рунтайм еррор - у меня было еще навалом времени.
И третью задачу всяко успевал сделать. Но на меня просто нашел ступор.
(105) Это правильный алгоритм.

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

(108) сортировать? это же больше операций

(110) Там есть описание решения на сайте на последней закладке.
И на олимпиадах никто не считает количество операций, считают О()
В данном случае число значений в массиве фиксировано, и поэтому любое решение это О(1), и в любом случае уложится в 2 секунды.

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

И больше операций чем в каком методе решения?

(111) мне кажется собрать словарь дешевле
хотя конечно на 12 элементах не скажется
зато сразу размер словаря отсеивает часть вариантов, плюс просто проверяем на 4

(112) Собрать словарь - сложность алгоритма такая-же как и сортировка - n ln n
Тебе в словарь нужно добавить n слов, бинарный поиск на уже наличие - логарифм.

(113) ты не учитываешь, что мы ищем не среди 12 элементов, а среди трех
иначе отбрасываем сразу

(114) Если среди трех - то любой метод О(1), и разница только в скорости написания. С сортировкой, особенно если она у тебя готовая - намного быстрее.
Хотя какой-нибудь пузырек пишется за две минуты. Я им и сделал.

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

(116) А я про сотрировку, которая пишется моментально.
Для а=1 по т-1 цикл
Для б=а+1 то т цикл
  Если м[а]>м[б] Тогда
    темп=м[а];
    м[а]=м[б];
    м[б]=темп;
  Конецесли;
КонецЦикла;
КонецЦикла;

И повторюсь - у большинства участников сортировкка готовая, они её просто копируют в проет. А ты свой принцип вместо минуты будешь писать 10, и решив все задачи отстанешь на 45 очков.

Про Палидром придумал вот так:


Если ЭтоПалиндром(S) Тогда
   Если СтрЧислоВхождений(S, Лев(S,1)) = СтрДлина(S) Тогда
       Возврат "NO SOLUTION";
   Иначе
       Возврат Сред(S,2);
   КонецЕсли;
Иначе
   Возврат S;    
КонецЕсли;

(117) отсортированный массив еще надо обработать
сейчас условия перечитаю и попробую сделать на питоне

кстати в условии первой задачи возможны спички нулевой длины?

блин, залез на сферу, посмотрел на свои примеры, точно не сегодня)

(120) Я проверку не делал, мне решение засчитали.
Посмотри условие, вроде там в условии длины целые положительные.

(119) его не надо обрабатывать.
Если (м[1]=м[2])и(м[2]=м[3])и(м[3]=м[4])и(м[5]=м[6])и(м[6]=м[7])и(м[7]=м[8])и(м[8]=м[9])и(м[9]=м[10])и(м[10]=м[11]) Тогда
можно
иначе
нельзя

Если (м[1]=м[2])и(м[2]=м[3])и(м[3]=м[4])и(м[5]=м[6])и(м[6]=м[7])и(м[7]=м[8])и(м[9]=м[10])и(м[10]=м[11])и(м[11]=м[12]) Тогда
блин!