Ссылка на привила:
http://algorithm.contest.yandex.ru/rules/
перечень языков: http://algorithm.contest.yandex.ru/compilers/

из местных кто-то примет участие или все настолько ленивы?

1с там нету.

времени нет.

предлагаю от местных послать туда NS-а...

(1) у меня ощущение что я могу уже программировать все что программируется...

надо у NS спросить

(4) Ну тогда дерзай. Может ощущения станут более реальными.

(6) см (2)

(4) 100 минут нет на решение задачи? Может пора ну его эти форумы в топку?

(3) он всех посылателей сам не пошлёт?

Я буду. В мейловском ксати вышел в отбор, но 16-го буду в отпуске (день отлета), так что в отборе участвовать не буду. Обидно, но что поделаешь...

(10) молоток!

(8) 100 миунт есть

(3) I место — 300 тысяч рублей;

Стоит ли попу рвать за такую мелочь?

(4) Современное олимпиадное программирование - такая вещь, что без знания на зубок основных (на текущий момент) олимпиадных алгоритмов, шансов где-то что-то занять практически нет. Можешь попробовать свои силы на http://codeforces.ru/

(12) согласно правилам "Каждый раунд длится 100 минут. "

(14) Зачем оно вообще нужно? За 100 минут реализовать какой-нибудь дурацкий парсер, который нахрен никому не нужен.

(14) если с чего-то не начать - ничего не получится

(13) главный приз будет типа так: вакуха с месячной зп от половины приза за 1 место

(15) Ок, уговорил, зарегался, выбрал C++

(19) хороший выбор! К сожаления в ++ никогда не был сильно силён

(13) помнится, Сергей рвал попу за 500$ ;) даже с учетом инфляции, 300 тыр поболе будет...

(21) что за Сергей?

А где нибудь есть пример того что было в 2012?

а , нашел http://codeforces.ru/blog/entry/2028

(16) Нет там никаких парсеров. Только олимпиадные задачи.

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

Забыл проголосовать.

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

(28) аналогично, но н в виду поверхности а т.к. много лет ни на сишняке ни на паскале не ваял

Там, наверно, математика будет
Скучно

Для 1Сников надо свою олимпиаду
Типа на лучшую бизнес-логику, лучший код

Вот чё фирма 1С не проводит такие олимпиады. Глядишь, не было бы ут 11

(29) Ну а словами рассказать решение конечно-же сможешь?
Давай я наугад тебе олимпиадной задачи дам условие...

(33) давай. Надо мозги тренировать, не всёж монетезировать всё и вся

(34) А смысл? Несколько тысяч задач на Codeforces.
Бери любую пятую с Div.1.

(33) давай попробуем

(36) http://codeforces.ru/contest/311/problem/E

http://codeforces.ru/contest/303/problem/C
Вот совсем простая.

Вообще достаточно написать как ты примерно будешь делать.
И сообщить сложность алгоритма. Зная количество входных данных (оно всегда есть в условии), легко узнать влезаешь ли в time limit (примерно 10^9 операций за 3 секунды можно выполнить)

http://codeforces.ru/contest/302/problem/D
А вот это совсем просто - решение можно описать одним словом.

(40)метод симспона?

(38) что за хрень такая(три горизонтальных черты перечёркнуты)?

+ (42) в смысле что остаток от деления этих чисел на m различен?

(41) дейкстра. Но ограничения не очень жесткие, поэтому в tl влезает флойд.

(41) не равны по модулю. Соответственно да, разный остаток от деления.

(45) 2 сек и 256 мб - дв тут перебором в лоб можно успеть посчитать (в смысле для m=2, не взлетело - для m=3 и т.п.)

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

ну т.е. всё опять упёрлось во время

(0) я не могу участвовать по условиям конкурса

нет

(46) конечно-же простая прикидка показывает что перебором не успеть.

Надо сына развернуть в сторону этих олимпиад

Допустим правильный ответ около 10^6
Остаток от деления мы должны проверить для 5000 чисел для каждого делителя до 10^6.
Как ты собрался успевать полным перебором?

(14)
Кстати да. Там очень важно понимание алгоритмов и матана. 1сникам там делать нечего.

Насчет "могу решить любую задачу" - многократные чемпионы мира по олимпиадному спортивному программированию скорей всего так сказать не могут.
http://codeforces.ru/problemset/problem/303/E
Вот эту задачу Геннадий Короткевич решить не смог.
Кстати, я знаю как она решается :)

(55) мда, как же это все далеко от программирования на 1С ;)...

берите Guk-а

(47) Нет конечно. Нужно читать учебники не по мат. играм, а по программированию (повышению уровня в алгоритмах)
Вот отличный список тематической литературы:
http://with-champions.ru/library.html
И есть очень полезный сайт
http://e-maxx.ru/index.php

(58) Ты в танках то какое место занял в итоге?

(59) Вроде последнее.
Я выиграл футболку, прошел во второй этап, и выложил стартового бота. Думаю что выше чем на последнее место он вряд ли мог рассчитывать.

Но танки - это не олимпиадное программирование, это AI.
Типа codeforces.nl

Если в AI немного поднапрягшись я без проблем выходил на первое место, что в танках, что в голландском чемпионате,
то в олимпиадном программировании на текущий момент мне не светит ничего кроме призовых футболок. Хотя я начинал именно с олимпиадного программирования, но за 25 лет уровень задач стало совсем другой, и скорости их решения выросли на порядок. Думаю годик потренироваться, может выйду тогда на приличный уровень.

(61) Эти задачи сопоставимы с теми что решаются на чемпионатах мира по программированию, когда команды решают максимальное количество задач на время?

(62)  которые на codeforces div 1, яндекс алгоритм, mail code cup и т.д. - да, примерно уровня чемпионатов мира. Выигрывают их те же люди что и чемпионаты мира. Когда командные чемпионаты - просто обычно дается больше задач.

для примера что выигрывали победители прошлогоднего code cup
http://russiancodecup.ru/round/10/results
Ники кликабельны.

Командный чемпионат мира называется ACM-ICPC

(64) Крутые ребята, большенство даже на программеров задротов не похожи)

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

(67) не у всех ботанический вид, но у многих :)

в (60) конечно-же codecup.nl, а не codeforces.nl

(69) ты кстати еще в юбилейном обитаешь? Если да до через пару месяцев будем соседями)

(70) Неа, там купили квартиру, но жена отказывается туда переезжать пока западный скоростной не достроят.

(71) Ну так скоро уже вроде)

(51) на контрольном примере чисел менее десятка, самое большое из них менее 20

(55) наверное для каждого посчитать среднее значение и дисперсию и уже на основании результатов сравнения этих величин строить прогноз

(55) Для каждой точки-станции помтроить покрытие с дистанцией равной количеству времени на станции. После этого как то найти путь, с минимальным непокрытым участком

(73) при чем тут контрольный пример?
(75) ???
(74) мда...

(73) решение будет прогнано через тесты, которые удовлетворяют  условиям в задаче, и твое решение будет забраковано, так как не уложится в TL. так как решение плохое - имеет плохую сложность алгоритма.
(74) то что ты написал - не решение. И естественно дисперсия и среднее для ранжирования при равномерном распределении ничем не помогут.
(75) по условию видно, что время на путь между двумя любыми точками всегда больше бонуса. Считаем разницу расстоянием между вершинами, так как она всегда неотрицательна - легко можем найти кратчайший путь по графу дейкстрой или флойдом.

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

что то упорно не вижу этого в условии

(78) смотрим на формулу расстояния, на условие целочисленности координат точки, и на условие на a и d

Расстояние не может быть меньше единицы, а d всегда не меньше a
Значит d*расстояние>=a

(79)
Формула расстояния (а вернее времени  потраченного на расстояние)
Т=(|xi?-?xj|?+?|yi?-?yj|.)*d
Условие цлочесленности координат: координаты целочисленны
Условие на a от 1 до 1000
d от 10^3 до 10^5

Действительно, но меня смущает, что тогда слишком просто как то, что то не так

Это задача второго дивизиона.

Все так. У меня естественно решение прошло тесты.

http://algorithm.contest.yandex.ru/contest/306/standings
Вот тут в реальном времени можно отслеживать результаты первого, тестового раунда.
Шансов у меня конечно нет, но я поучаствую.
До начала осталось 7 минут.

Тестовый тур закончился.

Народ бушует, типа очень простая вторая задача, и слишком сложные остальные. Для того чтоб пройти достаточно было "в темную" решить вторую задачу. Либо решить любые две задачи.
Я решил две - первую в открытую, и третью " в темную".
Кто не прошел или не участвовал - с семи вечера восьмого июля до семи вечера девятого июля можно выделить час сорок, и попытаться выйти в основную часть.
Выходит 2000 участников, так что скорей всего выйти будет достаточно просто.

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

(87) так ты прошёл или нет?

ща зарегимся

(88) прошел конечно.

А где ссылка на задачи?

А в (84) задачи не показывает?

(92) Неа, только рейтинг вижу.

(93) Тогда зарегистрируйся.

Попробую что-нибудь на php написать)

(95) Наличие решений укладывающихся в time limit гарантируется только на Java, С/С++, Pascal

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

(94) Да я зареген вроде бы.

(98) Тогда зайди под своим логином.

(99) Ты меня совсем за дурака считаешь?)

http://algorithm.contest.yandex.ru/contest/306/problems/

(100) А что пишет в ссылке (101)?

Пишет "Соревнование началось."

(103) Круто! А у меня пишет "Соревнование завершено" :)
Обновление страницы не помогает?
http://algorithm.contest.yandex.ru/contest/306/
А по этой ссылке?

(104) Да один фиг, тоже самое "Соревнование началось.".

Ладно фиг с ним.
Вы хоть выкладывайте задачки, интересно.

http://contest.yandex.ru/contest/ContestList.html
Тут, четвертая сверху.

(106) Есть подозрение что выкладывание задач нарушает правила, ибо может помешать тем кто хочет потренироваться вживую по ссылке в (107)

(108) Условие задачи, не решение ведь.

(109) Решение задач ведь на время. Если человек увидит заранее условие, то это ему собьёт результат.

Наверно просто еще не успели дать возможность решения тем кто не участвовал.

Понятно, ну ладно.

http://algorithm.contest.yandex.ru/contest/306/enter/?lang=ru
И с этой ссылки ничего не получается?

Вот условие первой задачи:

Окружности

Ограничение времени 2 секунды
Ограничение памяти 64Mb
Ввод circles.in
Вывод circles.out

Легенда


На плоскости расположен набор из n окружностей. Каждая окружность задана тремя различными точками, через которые она проходит. Найдите наибольшее количество окружностей, имеющих один и тот же радиус.


Формат ввода


В первой строке входного файла задано целое число n (1 ? n ? 1400). В последующих n строках заданы по шесть целых чисел x1, y1, x2, y2, x3, y3 — координаты трёх точек, не лежащих на одной прямой и задающих соответствующую окружность (0 ? xi, yi ? 1400).


Формат вывода


Одно целое число — количество окружностей, имеющих наиболее часто встречающийся в наборе радиус.


Пример


Ввод

Вывод


3
0 0 0 1 1 0
0 0 2 0 0 2
1 1 1 2 2 1

Вместо знаков вопроса в условии - <=

(114) терпимо

(116) Это та задача, которую решило большинство (естественно кроме третьей, которая совсем простая)
Третья:

Выбери цифры

Ограничение времени 2 секунды
Ограничение памяти 64Mb
Ввод number.in
Вывод number.out

Легенда


Дана последовательность из восьми цифр, каждая из которых равна 1, 2 или 3. Требуется выбрать из них четыре цифры так, чтобы число, полученное при выписывании этих цифр в том же порядке, в каком они были в последовательности, оказалось как можно меньше.


Формат ввода


Первая строка входного файла содержит восемь цифр, каждая из которых равна 1, 2 или 3, записанных подряд без пробелов.


Формат вывода


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


Пример 1


Ввод

Вывод


12333333

1233



Пример 2


Ввод

Вывод


32111111

1111



Пример 3


Ввод

Вывод


12131211

1111



Пример 4


Ввод

Вывод


33333323

3323



Пример 5


Ввод

Вывод


32333313

2313

Нельзя им доверять, мне вон за прошлые танчики заслуженную футболку не прислали :-(

(119) Это были не они. (там был mail.ru, а тут yandex)
Мне за танки футболку прислали, причем весьма оперативно.

(96), да пофиг, я всё равно ничего не выиграю

(121) Футболку выиграть шанс есть всегда. Для этого достаточно решить всего одну задачу.
"Ещё одна хорошая новость: мы решили почти удвоить количество сувенирных футболок. Теперь майку с символикой Яндекс.Алгоритма получат 75 лучших участников отборочного этапа и ещё 75 человек, выбранных случайным образом — из тех, кто решил хотя бы одну задачу. И, разумеется, все финалисты."

Тестирующая система, на которой будут проверяться решения участников, поддерживает следующие компиляторы:

— Delphi
— Free Pascal
— GNU С++  (4.6)
— GNU С++ 0x (4.6)
— GNU С++ 0x x32 (4.6)
— GNU С++ x32 (4.6)
— Java 7
— Java 6
— GNU С (4.6)
— GNU С x32 (4.6)
— Python 2.7
— Python 3.2
-----------
А php куда дели? Вспоминать С/С++, устанавливать IDE ради конкурса пожалуй не стану

(123) Значит и не было.

(123) Писал на GNU С++
Что то первая задача оказалась не такой уж тривиальной. Застопорился на том месте где надо было вычислить радиус окружности по трем точкам - казалось бы фигня, а на деле вышло не так уж и просто.

(125) Вычислить то как раз просто, а что дальше?
Такие задачи, где нужно точное равенство - решать можно только в целых числах.

(125) Вышел?

(126) Дай посмотреть твой код к первой, похоже я на ней затупил
(127) Нет, я не участвовал

(127) Я арендовал только вчера centos машину на 14 дней. Поставил на ней g++ и начал тренироваться

import java.io.*;
import java.util.*;

public class z2 {
   public static long nod(long a, long b) {
       while (b != 0) {
           long temp = a % b;
           a = b;
           b = temp;
       }
       return a;
   }

   public static void main(String[] args) throws IOException {
       File file = new File("circles.in");
       File file1 = new File("circles.out");
       FileOutputStream fos = new FileOutputStream(file1);

       Scanner in = new Scanner(file);
       PrintWriter out = new PrintWriter(new OutputStreamWriter(fos));
       int n = in.nextInt();
       double e = 0.00000000001;
       long[] rr1 = new long[n];
       long[] rr2 = new long[n];
       int[] ch = new int[n];
       int kol = 0;
       for (int i = 0; i < n; i++) {
           long x1 = in.nextLong();
           long y1 = in.nextLong();
           long x2 = in.nextLong();
           long y2 = in.nextLong();
           long x3 = in.nextLong();
           long y3 = in.nextLong();
           long a = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
           long b = (x3 - x2) * (x3 - x2) + (y3 - y2) * (y3 - y2);
           long c = (x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3);
           long r1 = a * b * c;
           long r2 = Math.abs((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1))
                   * Math.abs((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1));
           long no = nod(r1, r2);
           r1 = r1 / no;
           r2 = r2 / no;
           boolean f = false;
           for (int j = 0; j < kol; j++) {
               if ((r1 == rr1[j]) && (r2 == rr2[j])) {
                   ch[j]++;
                   f = true;
                   break;
               }
           }
           if (f == false) {
               rr1[kol] = r1;
               rr2[kol] = r2;
               ch[kol] = 1;
               kol++;
           }
       }
       int max = 0;
       for (int i = 0; i < kol; i++)
           max = Math.max(max, ch[i]);
       out.println(max);
       in.close();
       out.flush();
       out.close();
   }
}
// но правильней брать НОД между каждой стороной и площадью отдельно.

(130) И оно правильное?
Я просто шел тем же путем (с незначительной вариацией), но я наткнулся на следующую проблему:
Если взять твой код как основу обсуждения ( у меня в принципе то же самое, только через малость другие вычисления)
То оценим максимальные a,b,c
это будет 1400^2 каждый
long r1 = a * b * c; дает максимально 1400^6
а это превышает 2^64-1 что максимально можно сохранить в беззнаковом 64-битном целом.
(кстати long в java это еще и вроде знаковое целое, это еще в два раза меньше, не так ли?)
Как доказать что
long r1 не превысит 2^64-1 я что то не нашел способа

(131) Оно неправильное, но оно прошло. Правильное в комментариях.
r1 = a * b * c; Максимально больше 2^63, но меньше 2^64
1400^6 кстати меньше 2^63

Доказать легко. Максимально три стороны прямогугольного треугольника, квадраты равны
1400^2, 1400^2 и 2*(1400^2) - по теореме Пифагора.
Их произведение явно меньше 2^64.
В Java нужно извращаться с НОД по каждой стороне, так как нет беззнакового 64 бит целого. Но можно использовать BigInteger.

У меня такое решение, потому что изначально было написано что координаты меньше 1000, потом они поправились что 1400, но я этого не увидел. Слава богу решение прошло.

(133) А почему ты считаешь, что максимальный r1 будет при прямоугольном треугольнке?

(132) Да я неправильно сказал, ошибся, в оценке я взял максимальные
a,b,c 2*1400^2
тогда r (макс)= 1400^6*8 что больше чем 2^64-1

(136) Такие стороны в условие никак не влезают.

(137) Это я понимаю, но без ответа на (135) я другой способ оценки максимального r=a*b*c не вижу.

(135) А почему ты считаешь что нет? :)

(139) Да я как бы и не утверждаю, что нет, я лишь свожу это к нерешенной подзадаче:
Внутри квадрата NxN находится треугольник, все углы треугольника внутри квадрата.
Вопрос: Какое максиамльное может быть произведение сторон треугольника?

А вообще надо Ненавижу1С брать в пару на чемпионата, в качестве математика, чтобы не отвлекаться на такие подхадачи

(140) Зря заморачиваешься. :)
Никто на олимпиадах доказательств не требует.
Если сомневаешься, используй длинную арифметику.

(142) Я уже этот момент так же чекнул, длинная арифметика садит производительность как раз для 1400-ох прямоугольных треугольников расчет радиусов с НОДами выходит за пределы 2-х секунд.

(143) Не выходит, и близко не выходит. Тебе длинную арифметику нужно использовать всего 1400 раз.

Но её не нужно использовать. Пробуешь в светлую unsigned long long, видишь что прошло, и на этом успокаиваешься :)

Насчет "длинки" - для каждого треугольника требуется выполнить только одну длинную операцию - одно произведение обычных чисел с длинным результатом. Треугольников 1400, то есть нужно выполнить 1400 длинных произведения. Я берусь утверждать что в две секунды уложится 10^8 длинных произведений. Что явно больше 1400.

(140) Еще НОД находить надо на длинке

(147) Не надо.

Три квадрата сторон a, b, c (каждый из которых без вопросов влезает даже в int32)
Квадрат удвоенной площади S (который влезает с огромным запасом).

темп=НОД(a,s)
а=а/темп
S=S/темп

темп=НОД(b,s)
b=b/темп
S=S/темп

темп=НОД(c,s)
c=c/темп
S=S/темп

И теперь произведение трех сторон может допустим выйти за long long, поэтому только для них выполняем длинное произведение храня результат в двух long long

После всех операций НОД(a,s)=1, НОД(b,s)=1, НОД(c,s)=1 из чего следует что НОД(a*b*c,s)=1

(149) Да, верно. НОД можно вычислять над UINT32.

(151) зачем? uint64.
А потом в двух uint64 вычисляешь произведение a, b и c
Младшие 64 бита равны просто a*b*c,
Старшие - старшие 32 бита от произведения старших 32 бит a*b и c

Я что то задумался о правилах. Допустим у меня есть две регистрации, фейк и реальная. Фейковой регистрацией я решаю задачи по 100 минут в открытую пока они не заработают. Потом захожу под реальной регистрацией и внезапно решаю задачи за пять минут каждую, да еще и в темную. Так что ли?

(153) в квалификации все кто пишет выше некоторого уровня пройдут. Все-таки 2000 выходящих мест. Если тебе требуются такие трюки чтоб выйти в основную часть, то какой в этом смысл? В основной части трюки не пройдут.

задача C судя по турнирной таблице самая простая, у меня то же трудностей с ней не оказалось.
мое решение (gnu c++)
>>
#define IN_FILE file_in
#define OUT_FILE file_out
#define IN_FILE_NAME "number.in"
#define OUT_FILE_NAME "number.out"

#include <iostream>
#include <fstream>
#include <cstring>
#include <sstream>
#include <map>

using namespace std;

int main ()
{
   string mystr;
   ifstream IN_FILE;
   ofstream OUT_FILE;
   char str1[10],str2[10],result[5], tempchar;
   char *f;
   try
   {
       IN_FILE.open(IN_FILE_NAME);
       getline(IN_FILE,mystr);    
       IN_FILE.close();
       std::strcpy(str1,mystr.c_str());
       strcpy(str2,str1);
       f = str1;
       for(int i=5;i<9;i++)
       {
       str1[i]=str2[i];
       str1[i+1]='\0';    
       f = strstr(f, "1")==0 ? (strstr(f, "2")==0 ? strstr(f, "3") : strstr(f, "2")): strstr(f, "1");
       result[i-5] = f[0];
       f = &f[1];
       }
       result[4]='\0';
       OUT_FILE.open(OUT_FILE_NAME);
       OUT_FILE << result;
       OUT_FILE.close();
     }
   catch (std::ifstream::failure e) {
     std::cerr << "Exception opening/reading/closing file\n";
   }
   return 0;
}

import java.io.*;
import java.util.*;

public class z2 {
   public static String s;

   public static int minn(int a, int b) {
       char mi = '9';
       int ch = 0;
       for (int i = a; i <= b; i++)
           if (s.charAt(i) < mi) {
               mi = s.charAt(i);
               ch = i;
           }
       return ch;
   }

   public static void main(String[] args) throws IOException {
       File file = new File("number.in");
       File file1 = new File("number.out");
       FileOutputStream fos = new FileOutputStream(file1);

       Scanner in = new Scanner(file);
       PrintWriter out = new PrintWriter(new OutputStreamWriter(fos));
       s = in.nextLine();
       int nach = -1;
       for (int i = 1; i <= 4; i++) {
           nach = minn(nach + 1, 3 + i);
           out.print(s.charAt(nach));
       }
       out.println();
       in.close();
       out.flush();
       out.close();
   }
}

Сейчас проходит финал ЧМ ACP ICPC, пока ИТМО на втором месте среди более чем ста команд со всего мира.
СПбГУ на пятом, МГУ на восьмом.

ИТМО на первом месте.

http://icpc2013.ru/competition/live.xml?lang=ru#second
Вот турнирная таблица в реальном времени.

http://static.kattis.com/icpc/wf2013/
Вот тут красивее таблица.

Красавцы!

это что за чудо:"Kazakh-British Technical University"?

(161) Они и так многократные чемпиона, а сейчас еще Короткевича (tourist) с беларуси к себе взяли.
(162) http://www.kbtu.kz/

1 место! и в первой десятке ещё 3 команды!!!

Отрыв ИТМО от конкурентов - уже в две решенные задачи.

(165) ИТМО всех зарулит. жалко, меня в свое время на факультет к парфенову не взяли.

(164) Призовых 12 мест. Первые четыре - золото, потом четыре серебра, и четыре бронзы. Из 12 призовых - 5 Российских университета. Вопрос к недавней ветке - вы действительно думаете что Российские программисты не лучшие?!

(167) там ветка была кривая... я так и написал, что: Не вижу корреляции между именем ветки и вариантами ответа!

(160) Тут рейтинг с чатом http://ahmed-aly.com/ICPC.jsp :)

(169) Там тормоза, я на кнопку обновить боюсь нажимать, подвисает на 10 минут.

(170) УМВР

(171) Очень странно. Скрипт явно тормозит на той стороне (сайт выдергивает инфу с официального при помощи php кода)

(170) у кого как. у меня норм :)

(163) кста, а ведь ровно половина золота у exUSSR

(174) золота = призовых мест

Саратов подозрительно плохо идет. Должны тоже выйти в призеры.

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

(0) Я бы принял - но я тупой =\

(163) Короткевич крутой...

(179) Лидер рейтинг-листа на всех олимпиадных сайтах - конечно крутой :)

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

Турист написал последнюю задачу, "B",
если всё верно, то ИТМО решило все задачи, и недосягаема для конкурентов по очкам.

"G" у них неправильно решена, еще две посылки подряд сделали.

все?

На сайте результатов пока нет.

G задачу объясняют. которую никто не решил :)

говорят что решение ИТМО по G задаче было ближе всех к истине :)

где финальные результаты-то?

Интересно что за задачка была.

(189) минимальное покрытие прямоугольниками "страны" :)

по рейтингу в таблице смешно прокоментровали ведущие = Раша, Чайна, Чайна, Раша, Раша, Чайна. Типа где остальные :) ?

задача B про игру в казино. ее только Токио решили.

(192) те, что сейчас отражаются как pending - они подали решение меньше, чем за 60 минут до конца. могут и засчитать.

(193) ясно

Вышли девушки с мочалками танцевать, скоро результат походу объявят)

"B" у ИТМО пишут что точно засчитали. Вопрос в "G"
И у ИТМО точно первое место.

а что тут мюнхен делает? где финальная таблица?

(196) Крутяк!

(197) Еще не было объявления результатов.

видео тупит :(

(200) У меня все хорошо кажет.

Смотрю я на задачи B и G и не понимаю, что в них сложного :)
Неужели другие задачи проще :)

(202) Где ты взял их условие?

Судя по результатам самая простая задача F

(203) видео надо было смотреть :)

(205) Расскажи своими словами их условие.

за Ижевск обидно - перевелись видать у нас талаланты :)

https://icpc.kattis.com/problems

проблема в том, что ресурсы ограничены

(202) Если тебе они кажутся очень простыми, значит ты не понял условие. Ибо лучшие программисты мира их решить не смогли.

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

(210) чо и выпендрится нельзя :)

Ж - найти минимальное число прямоугольных клеток, на которых можно разметить многоугольник

(211) Ты уверен что это B? А где-же тогда А?

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

(214) см. 208 - они там сверху вниз

G = https://icpc.kattis.com/problems/maptiles
B = https://icpc.kattis.com/problems/bettor

(215) Не совсем понял. Типа я в шахматы играю лучше всех, только проблема в том что нужно играть по правилам?
Суть задачи не в том чтоб выдать решение которое будет считаться миллиард лет. Это не решение.
(216) Ошибаешься. Там первая задача например вообще не с ICPC. А просто так, образец.

(217) ?? почему так?

(219) в видео так было :)

(218) тогда нужна таблица соответствия

Только что сказали - ИТМО все задачи.

(222) супер

(222) Красавцы!

"Taras Shevchenko Kiev National University"

Чел на 7 месте, он что один все решал?

(225) Это университет имени Тараса Шевченко.

Произношение английское у нашего ведущего отвратное.

(226) ))

Осталось 2 места объявить.

Все наши первые!

Shanghai Jiao Tong University, второе место, 9 задач.

Ну и трансляция, так и не увидел что они решили.

Всё, нашел. Не решили они G.
ITMO solved 10 out of 11 questions correctly.
http://icpcnews.tumblr.com/post/54508561834/and-the-winner-is

(233) Так эту задачу походу никто не решил.

В первых 16 мест 7 российских команд, 2 китайских и 2 польских, остальные по одной.

(235) это получается среди поляков хватает сильных программистов?

(235) опять-же 9 из 16 - команды exUSSR!!!

Какую страну профукали...

(236) Да, значит не только Томек Чайка у них крутой.

(0) А какого класса задачи там будут решаться на тестировании??? Учетные, математическое программирование или еще чего-то?

Так как мой опыт в математическом программировании не очень богат, да и на C++/Pascal в последний раз я программировал лет 6 назад, конено, решу, но во время не уложусь.

(240) олимпиадные. Не уверен что кто-либо в мире может быть уверен что решит любую олимпиадную задачу. Даже без лимита по времени.

Никогда не понимал зачем заниматься бесполезными задачами , когда вокруг столько всего интересного но которое при этом будет приносить деньги.  Я например в прошлом году занимался несколькими задачами
Построение оптимальных запросов с помощью  самообучающейся экспертной системы.
Построение кластерной,реалтайм системы для различных СУБД.
Построение транзакционной шины данных для гетерогенных сред.
В этих задачах и математики хватает и программирования. Самое главное что эти задачи в том или ином виде решены и начинают уже приносить деньги. Зачем тратить свои усилия на бесполезные задачи? Не понимаю!

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

(242)
1. Хобби.
2. Есть единственный способ сравнить свой уровень с другими программистами - чемпионаты по программированию.

У тебя есть хобби? Или не понимаешь зачем это нужно? :)

(244) Лучше если хобби совместить с работой.

(243) Никогда не понимал зачем заниматься бесполезной факторизацией, когда вокруг cтолько... :)

Если бы я в детстве занимался футболом. Я был бы с большим удовольствием профессиональным футболистом.:) Возможно об ИТ и не думал бы.

(245) Тренировка ума, скорости написания и понимая условия задачи, навыков алгоритмирования - пригодится в работе. То есть это хобби, которое развивает рабочие качества. Точнее само участие не развивает конечно, а вот подготовка к нему позволяет стать более сильным программистом.

(248) А если кандидат на собеседовании не ответит на вопрос почему люки круглые. Вряд ли его спасут места на олимпиаде.

Все - таки одно дело иметь навыки крутить всю жизнь массивы, списки на скорость, а другое дело широкий кругозор.

Например, американские, европейские университеты имеют в сто раз больше ресурсов чтобы заманить гениев к себе в универ. Ну сам подумай, никто никогда не пойдет учиться в ИТМО, если его берут ,например, в МГУ или в университет Миссисипи или Кембридж.

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

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

(249) эти олимпиады не чтоб научиться писать, а чтоб оценить и показать свой уровень. Чтоб хорошо выступать нужно
1. Уметь быстро и правильно прочитать задание.
2. Уметь быстро и безошибочно писать код.
3. Понимать что такое сложность алгоритма, и уметь быстро придумать алгоритм с хорошей сложностью для нестандартнлй задачи.

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

Не участие в олимпиадах повышает уровень программиста, а уровень программиста можно оценить результатами на олимпиадах. А это не одно и то же.

Насчет итмо - лидер рейтинг листа topcoder и codeforce - учится именно в итмо. А взяли бы я думаю его в любой топовый айтишный вуз мира. Только зачем идти в другой вуз, если лучших програмистов готовит итмо? Что доказывает уже пятый титул чемпиона мира среди вузов.

Задач сравнимых с сортировкой пузырьком на чемпионатах мира естественно не бывает.

Виноват, на topcoder он в данный момент второй.

По словам вице-президента спонсора турнира корпорации IBM Майкла Карасика, всем членам команд, завоевавшим золото, будет предложена работа в IBM. Таким образом, питерским студентам придется сделать сложный выбор - продолжить работу на лидера среди российских соцсетей или попробовать свои силы в одной из крупнейших мировых IT-корпораций.

РИА Новости http://digit.ru/it/20110531/382217588.html

Кроме IBM и вконтакте среди спортивных программистов  набирают сотрудников такие компании как Яндекс, Гугл, Майкрософт, Фейсбук и т.д.

Продолжаю разбирать тестовый раунд. Удивила вторая задача, почему так мало решивших, ведь это известная всем задача Эрдеша-Страуса http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Straus_conjecture

(253) Я даже её условие не смотрел. :) Решил первую, посмотрел какую больше решают, посмотрел третьей, решил её, остальные даже не читал.

И в википедии не вижу быстрого решения.

В условии a,b,c - различные ПОЛОЖИТЕЛЬНЫЕ числа.

Хотя небольшая подсказка в википедии есть - решать нужно брутфорсом.

(256) Там все есть в этой статье, включая все алгоритмы нахождения этих дробей.
Я набросал такое решение ко второй задаче
http://yadi.sk/d/l1ddqnIo6TjTp

там применяется в зависимости от обстоятельств полиноминальный алгоритм (самы простой на случай n%3=2), алгоритм грейди (выдаст решение если повезет) и наконец когда ничего из этого не помогло то брутфорс

(257) Оно проходит тесты?

На случаи закладываться в олимпиадном программировании (ускорять отдельные случаи) не имеет смысла, так как тесты специально подбираются согласно условиям данным в задаче так, чтоб было максимальное время выполнения. То есть в самом сложном тесте не будет ни одного n такого, что n%3=2.

Поэтому нет смысла рассматривать эти случаи, и нужно писать чисто брутфорс.

Даже если нет таких тестов изначально - например на codeforces есть такое понятие как взлом.

(258) А фиг знает, я скачал тесты, распаковал, а как пользоваться ими, я не понял.

Набил сам всяческих случайных чисел, например при входном файле с 9-ю строками:
9
4
32
6700
1543
870
33540
321
458
752

Отрабатывает за доли секунды и выдает
6 3 2
352 32 11
7880936097300 2807301 1676
354737573202 595599 386
8992823730 94831 218
4944425712208710 70316611 8386
75125556 8668 81
70074 458 153
188752 752 251

(291) А там нет возможности отослать решение?!

У меня есть такая возможность.

(261) Отправил я твое решение, на третьем тесте TL, не укладывается в две секунды.
1 ok 4ms / 384.00Kb
2 ok 3ms / 380.00Kb
3 time-limit-exceeded 2.04s / 260.00Kb

ага, где то надо 0,04s сэкономить

(265) Намного больше надо сэкономить. Через две секунды выполнение аварийно прекращается. Это не значит что у тебя программа за 2 секунды с копейками завершила тесты.
Сам третий тест - 14497 чисел от 4 до 15000.
Это не самый сложный тест.

Вру, это второй тест. Третьего в архиве не вижу.

Попробуй для теста в цикле 15000 раз разложить на сумму дробей число 4/14983

(268) На моей виртуальной машина справился меньше чем за долю секунды.
В выходном файле 15000 строк вида
3150163628363442 56126319 3746
3150163628363442 56126319 3746
3150163628363442 56126319 3746
3150163628363442 56126319 3746
3150163628363442 56126319 3746
3150163628363442 56126319 3746
3150163628363442 56126319 3746

Да и так видно, что на второй тест ушло 2 ms, тут что то они непостижимо жуткое набросали в третий тест

Сделай тест от 4 до 15000, с выводом времени счета, и посмотри на каком числе дольше всего считает. Или подвисает.

4/7303 - сложный вариант.

4/7951

хм, он у меня на числе 49 что то помер, надо поковырять

441 42 18

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

Дома попробую написать.

(274) а где условие этой задачи?

(278) Представить число 4/n, где n - целое, n>=4 и n<=15000
В виде 1/a+1/b+1/c, где 2^64>a>b>c>0.
На входе до 15000 значений n, ограничение по времени 2 секунды.

(278)
Дана дробь 4/n, требуется представить её в виде суммы 1/a+1/b+1/c, где a > b > c — целые положительные числа.
Формат ввода

Входной файл состоит из нескольких тестовых примеров. В первой строке входного файла задано одно целое число T ? 15?000 — количество тестовых примеров. В каждой из последующих T строк содержится одно целое число 4 ? n ? 15?000.
Формат вывода

Для каждого тестового примера выведите в отдельной строке такие целые 263 > a > b > c > 0, что 4/n=1/a+1/b+1/c, или три нуля, если такое представление невозможно.
Пример
Ввод    
1
4

Вывод
6 3 2

(278) Насколько я понимаю сейчас после регистрации условия задач доступны. В принципе и отсыл должен быть доступен.

(281) до этого у меня не дойдет )),  просто интересно что вы вдвоем так обсуждаете.
(280) спасибо

(279) а ограничение только по времени?
что мешает заранее подготовить таблицу и выдавать из неё ответы?

(283) Ничто не мешает. Только в код таблицу включить надо.

(283) По памяти так же ограничение 250к

(284) для N<15000 это не проблема
(285) а вот это уже все объясняет

кроме частного случая (n%3=2), вроде таким же способом пишутся формулы для случаев:
n%3=0
n%6=4

(285) А где такое написано?
Вижу ограничение  64Mb.

хм, действительно. Тогда можно просто заранее подготовить табличку от 1 до 15000 в которой уже будут лежать строки с ответами

На Республиканской олимпиаде по математике надо было написать калькулятор, который мог использовать две переменные, скобки и плюсы/минусы. Один из участников реализовал используя типа 1С-ной команды "Шаблон". Разумеется его результат не засчитали, т.к. проверяется не умение "заполнить табличку", а умение писать программы. Я думаю тут так же будет.

+289 хотя на тестовом этапе может и пройдет

(289) (290) это называется прекалк, разрешено правилами.

(291) Прикольно, не знал

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

(290) насколько я понимаю, для нешкольных олимпиад, других этапов проверки  кроме тестирования нет (взломы - тоже иесты). А с читерством борются входящими ограничениями

(294) Только что на codeforces запретили заимствование чужого кода. Так что появилась проверка кода.

(295) как это можно проверить? что является базой для проверки?

(293) Ну ты то добился 2 сек?
Можно кэшировать простые числа. Тогда если мы разложили какое нибудь
4/p
то легко разложим
4/(p*q) просто помножив все три числа из ответа для 4/p на q

б.., что то у меня и D задача не укладывается в лимит времени.
Валится на этом тесье
479001600
(это 12!)

(297) Нет, я еще не писал.
Да, так и надо делать, аналог решета Эратосфена.

(296) e-maxx, википедия  и т.д. Проверяют по факту жалобы.

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

(301) Про какие раунды идет речь?
Квалификационный тур состоит из одного раунда длительностью 100 минут.

Главный совет - прочитать условие всех задач.
Выбрать наиболее простую, и начинать с неё.

А что тогда означает время в таблице положения участников тестового раунда? На какой минуте задачу послали?

Задача C у первого места выслана уже на 6-ой минуте да еще и с трех попыток. Читерство?

(304) А таблица положения участников и статистика доступна уже во время соревнований? Или только по окончании? Можно просто по ней сориентироваться какая задача простая

(304) Естественно да.
(305) Не вижу никаких проблем для первого места сделать её за 6 минут. Турист вообще за 2 минуты её сделал. И у первого места выслана она с первой попытки.
(306) Не помню. Вроде можно, иначе с чего я вдруг третью задачу стал решать?

(305) Откуда три попытки взял? С первой попытки у него выслана.

Третью задачу самое быстрое решили за две минуты, первую - за шесть. Турист тоже первую сделал за 6, но выслал в темную, и скорей всего получил TL.

а сам то решил?

(310) Что решил? Я уже вышел в основную часть.
Да, решил и первую и третью.

Хотя нет, на первой вряд ли TL, скорей всего неверное решение.

вот разбор задач тестового раунда.
http://codeforces.ru/blog/entry/8198
Прикол, но авторское решение второй задачи - прекалк.
Но оба решивших уложили решение в две секунды.

первое место успело за 9 минут, мгновенно вспомнить про эрдеша-штрауса, решить вторую задачу, сделать код для прекалька, запустить (что более двух минут), сделать код с прекальком, отослать.

(314) Для решения второй задачи не надо вспоминать про Эрдера-штрауса.
Достаточно предположить что разложение всегда есть, запустить тест до 15000, и убедиться в этом.

На codeforce есть пост от одного из решивших, он ничего про эрдера-штрауса не знал.

И повторю - оба решивших сделали без прекалка.

Про 9 минут, мгновенно и т.д. - вообще ничего не понял.

Первое место, кстати - всего-лишь призер чемпионата мира.
Странно думать что призеру чемпионата мира недостаточно 10 минут на каждую из данных задач.

первое место, отправило задача А на 25-ой минуте, а задачу Б на 34-ой. Разница в 9 минут

(318) И чего в этом странного?

http://codeforces.ru/blog/entry/8168#comment-138805
Вот его решение

(319) в том что у меня решение этой задачи, причем с невписывающимся в таймлайн временем исполнения заняло полдня.

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

(321) Считается что в спортивном программировании чемпионы пишут примерно в 20 раз быстрее середнячков. Середнячков олимпиадного программирования, имеющих опыт и достижения. :) Насчет шансов выйти в финал я написал в самом начале - абсолютно без шансов, человеку не имеющему опыта в олимпиадном программировании. Это примерно то-же самое что шашист выучит правила шахмат, и тут-же захочет выйти в финал ЧМ.
А вот шансы на футболку например у меня есть.

Ну и возможность оценить свои силы.

(321) В смысле способен решить любую из этих задач?
Вторую ты не решил.

(324) Почему же, я просто не захотел реализовывать прекальк, т.к. не нащел интересным это делать. Или у тебя сомнения, что я прекальк map не смогу сделать?
А то решение, что у меня есть, легко спосрбно такой прекальк сформировать....секунд за 15
Из его решения я понял, что надо запастись на чемпионат прекальком простых чисел, где нибудь до миллиона.

(325) Нет, ты не смог как он уложить в две секунды без прекалка.
Не нужен прекалк простых чисел. А нужна всего-лишь заготовленная процедура факторизации. Которая есть у всех сильных олимпиадных программистов.
Хотя на результат она особо не влияет. Готов поспорить что за две минуты любой из чемпионов легко напишет её с нуля.
А поиск простых чисел напишет с нуля за минуту.

(326) Я и не говорил, что решу задачу как он, без прекалька.
Меня вообще удивляет, что его решение прокатило в таймлайн. Оно разве что для 24k+1 проканает

(327) В смысле? Я тебя не понимаю. Как ты считал сколько времени занимает его решение? У него за десятую долю секунду сосчитало для всех чисел до 15000.
Проверил - поиск простых чисел Эратосфеном и я за минуту напишу. Поиск всех простых до миллиона занимает тысячную долю секунды.

import java.io.*;
import java.util.*;

public class z2 {
   public static void main(String[] args) throws IOException {
       PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
       boolean[] a = new boolean[1000000];
       Arrays.fill(a, true);
       int ch=0;
       for (int i = 2; i < 1000000; i++)
           if (a[i]) {
               //out.print(i); out.print(' ');
               ch++;
               for (int j = i + i; j < 1000000; j += i)
                   a[j] = false;
           }
       out.println(ch);
       out.flush();
   }
}

78498 простых чисел до миллиона.

Имея простые числа написать быструю факторизацию - еще 1 минута писанины.

Вот такая кривизна на Java у меня во второй задаче зашла (время решения одна секунда)

import java.io.*;
import java.util.*;

public class z2 {
   public static int[] p = new int[100000];

   public static long res(long m, long n, long c, long k, int nom) {
       if (k >= n * c)
           return 0;
       if ((k + c * n) % (4 * c - n) == 0)
           return k;
       while (p[nom] <= n) {
           int ch = 0;
           long p1 = p[nom];
           long m1 = m;
           while (m1 % p1 == 0) {
               ch++;
               m1 /= p1;
           }
           m1 = m / p1;
           long k1 = k * p1;
           for (int i = 1; i <= ch; i++) {
               long l = res(m1, n, c, k1, nom + 1);
               if (l > 0)
                   return l;
               m1 /= p1;
               k1 *= p1;
           }
           nom++;
       }
       return 0;
   }

   public static void main(String[] args) throws IOException {
       File file = new File("fraction.in");
       File file1 = new File("fraction.out");
       FileOutputStream fos = new FileOutputStream(file1);

       Scanner in = new Scanner(file);
       PrintWriter out = new PrintWriter(new OutputStreamWriter(fos));
       // Scanner in=new Scanner(System.in);
       // PrintWriter out = new PrintWriter(new
       // OutputStreamWriter(System.out));
       boolean[] a = new boolean[100000];
       Arrays.fill(a, true);
       int ch = 0;
       for (int i = 2; i < 100000; i++)
           if (a[i]) {
               p[ch] = i;
               ch++;
               for (int j = i + i; j < 100000; j += i)
                   a[j] = false;
           }
       long[] r1 = new long[15001];
       long[] r2 = new long[15001];
       long[] r3 = new long[15001];
       Arrays.fill(r1, 0);
       Arrays.fill(r2, 0);
       Arrays.fill(r3, 0);
       for (int i = 4; i <= 15000; i++)
           if (r1[i] == 0) {
               long n = i;
               for (long c = n / 4; c <= 3 * n / 4; c++) {

                   if (4 * c > n) {
                       long l = res(n * c * n * c, n, c, 1, 0);
                       if (l > 0) {
                           r1[i] = ((n * n * c * c / l + c * n) / (4 * c - n));
                           r2[i] = ((l + c * n) / (4 * c - n));
                           r3[i] = c;
                           for (int j = i + i; j <= 15000; j += i)
                               if (r1[j] == 0) {
                                   r1[j] = r1[i] * j / i;
                                   r2[j] = r2[i] * j / i;
                                   r3[j] = r3[i] * j / i;
                               }
                           break;
                       }
                   }
               }

           }
       int k = in.nextInt();
       for (int i = 0; i < k; i++) {
           int pp = in.nextInt();
           out.print(r1[pp]);
           out.print(' ');
           out.print(r2[pp]);
           out.print(' ');
           out.println(r3[pp]);
       }
       out.flush();
       out.close();
       in.close();
   }
}

вру, намного быстрее секунды, так как в секунду вошел ввод/вывод. И такое решение если нет разложения - это увидит, и даст правильный ответ.

Кому интересно, четвертая задача.
На самом деле проще первой.
Решается "в лоб", полным перебором.
Вывод результата сделал "методом треугольника"
Такой используется для вывода PV в шахматных программах.

import java.io.*;
import java.util.*;

public class z3 {
   public static long[][] res = new long[1000][1000];

   public static int r(long n, int kol, long nach) {
       int max = 0;
       res[kol][kol] = n;
       for (long i = nach; i * (i + 1) <= n; i++) {
           if (n % i == 0) {
               int max1 = r(n / i, kol + 1, i + 1);
               if (max1 > max) {
                   max = max1;
                   res[kol][kol] = i;
                   for (int j = kol + 1; j <= kol + max; j++)
                       res[kol][j] = res[kol + 1][j];
                   if (kol <= 1)
                       break;
               }
           }
       }
       return max + 1;
   }

   public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(new
        OutputStreamWriter(System.out));
       //Scanner in = new Scanner(new FileReader("proddiff.in"));
       //PrintWriter out = new PrintWriter(new OutputStreamWriter(
       //        new FileOutputStream("proddiff.out")));
       long n = in.nextLong();
       int kol = r(n, 0, 1);
       out.println(kol);
       for (int i = 0; i < kol; i++) {
           out.print(res[0][i]);
           out.print(' ');
       }
       out.println();
       out.flush();
       out.close();
       in.close();
   }
}

Этот изврат (яндекс алгоритм) не для тру кодеров, а для людей которые собирают и главное помнят решения подобных задач, на самом деле они все простые и решаются с помощью вложенных циклов и периодических проверок условий. Участников даже язык не поднимается называть программистами. Как правило 90 % участников студенты-неудачники, у которых полно свободного времени. И само предназначение данных турниров, скрытая реклама компании спонсора. Обходите эту мерзость, не стоит оно того, да и футболка с любым логотипом стоит 500 р.

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

(333) Это не твое решение, ты просто списал то, что было в (320)

(328) Объясняю, я оценил предложенный брутфорс и мне показалось, что он фуфловый по производительности (вероятно недалеко ушел от моего решения). А то, откуда взялась производительность, это вот это вот решето:
                         for (int j = i + i; j <= 15000; j += i)
                              if (r1[j] == 0) {
                                  r1[j] = r1[i] * j / i;
                                  r2[j] = r2[i] * j / i;
                                  r3[j] = r3[i] * j / i;
                              }
которое отсутствует в моем решении, но у меня была уже идея реализовать его в (297)

Я уверен, если к моему решению приделать это решето, то оно так же не проиграет в производительности. Сейчас правда уже не проверишь, т.к. почему то закрыли загрузку задач

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

Отсюда вопрос, при сдаче задания в открытую сообщается номер проваленного теста. А что в этом тесте - видно?

(338) В смысле списал?
Я ни строчки кода ни с кого не списал. :)
Я вроде и не говорил что это мой алгоритм, тяжело написать свое, когда уже читал верное решение.

Его решение лучше твоего, потому что количество делителей n*n*c*c заметно меньше чем второй цикл в твоем решении.
Чистое время счета для всех чисел от 4 до 15000 (без учета ввода и компиляции) на Java на моей машине - 0.050 секунд.

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

(33) В смысле того, что ты просто облек в код то, что было уже выведено другими.

(340) у меня на второй цикл попадает только в тяжелых запущенных случаях, типа числа 49, т.е. это будет 1 случай из 24-х. К тому же сам автор решения признает это:
"Но если это объединить с конструктивом и запускать только для простых чисел вида 24*k+1, то должно получится мега шустро "


(339) т.е. при сдаче в открытую мне скажут "Тест 15 WA" и дальше гадай сам что за тест смог с 15 попытки завалить мой алгоритм на неправильный ответ

(341) 1. я не понял, к чему ты это. Естественно если я видел его пост и его алгоритм, и это лучшее брутфорсное решение, то реализовано будет именно оно.
2. Тоже не понял к чему это. Оба решивших не знали этой задачи. И при этом решили. Какая разница с какими ограничениями можно решить задачу если заранее знать её теорию?
3. Да. Будет сказана только ошибка, сам тест не покажут.

Ладно, собираюсь вступить в борьбу завтра во второй половине дня. Сегодня наделаю заготовок:
- Эратосфен
- Рекурсивный перебор делителей
- Нахождение обратной матрицы

может еще чего в голову придет

Насчет использования чужого кода -
"Разрешается использование любого prewritten code, опубликованного в Интернете до старта квалификации, в случае, если это не нарушает права автора данного кода."
Хороший сборник алгоритмов -
http://e-maxx.ru/algo/
И заметно ускоряют написание заготовки по вводу-выводу
(работа с файлами, ввод массива)

http://algorithm.contest.yandex.ru/
Стартовал квалификационный раунд.
Записаться еще можно, начать решать можно в любое время до 9 июля 19.00 по Москве. На решение отводится 100 минут (1ч.40м.)

(346) А где ты смотришь статистику?

Положение ведь можно смотреть только после старта, после начала отсчета времени?

(346) Обсуждение запрещено правилами соревнований, поэтому "во избежание" пост скрою.

(348) хм, действительно скрыли. Но было доступно положение час назад и даже названия задач прочитал. А сейчас только большая кнопка старта.

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

(351) ИМХО это глюк.

Короче, я закончил. Не очень удачно, не хватило чуть времени для решения еще одной задачи. Но и так нормально.

Задал вопрос - подтверили что это баг, никто не должен естественно видеть статистику. Так что пост с статистикой удаляю.

Решил в режиме дорешивания все задачи.
Точнее все кроме одной, которой решение вывел, но реализовать уже не в состоянии. Вырубаюсь.
Ушло на решение всех задач (кроме кодирования проблемной) около 5 часов. То есть чтоб решать всё, нужно ускоряться как минимум в три раза.

ого, ты всю ночь что ли не спал? Ты же вроде вышел уже в отборочный, чего ты там вообще решал?
5 часов это немного, у меня где то столько же ушло на вторую задачу в тестовом раунде (если считать с той точки зрения, что я ее все таки решил)

господа, может вопрос нубовский, но никто не знает каким методом 1С решает СЛАУ которая строится при расчёте себестоимости при РАУЗ?

вопрос снят

(356) спал конечно. :)

Отослал последнюю неотосланную задачу - ведикт ОК, так что все задачи у меня (правда в режиме дорешивания) решены.

Я что то перенервничал, 2 задачи ушли быстро, на 3-ю убил кучу времени - пытался ее даже бросить, но другая задача что то еще хуже, кинулся на бесконечный ряд, потерял время на изучение теории, бросил. В итоге что попало вышло. На конец времени был на 118-ом аж месте (но я там в темную отправил поэтому еще съеду скорее всего)

10 минут осталось до конца раунда

243-244 место в итоге у меня. Вообщем прошел

Через 1,35 можно будет обсуждать.

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

Что то не понимаю, раунд вроде кончился, а я что то все съезжаю и съезжаю по чуть чуть вниз, уже 248-249

а... понял

Раунд закончится в 20.40

Турист красиво решил все задачи в темную.

(361) решение ряда под спойлером.

Сделаем замену, x=1/b
И посмотрим во что превращается ряд при a=0.
Теперь возьмем почленно производную по х при любом а, и домножим на х.
Чтоб проще считать программно производную в радикалах, сделаем замену к=x-1 (x=k+1)
Получив формулу, подставив 1/к = b/(b-1) можно решить задачу в целых числах.

А сглючило меня что если позиция в игре  ним выиграна, то выигрывающий ход один, хотя понятно что это не так, например возьмем нечетное количество кучек по одному камню.
Что нужно искать количество единиц в старшем разряде с нечетным количеством единиц, я нагуглил в последнюю минуту контеста.
Надо было конечно пятую решать. Она простая. Я её после контеста решил легко и быстро.

(371) Это то я быстро нашел, что взять производную по z и домножить на z, https://en.wikipedia.org/wiki/Polylogarithm#Particular_values
Но потом я почему то подумал, что не стоит вычислять для всех 10-ти а производные, т.к. много времени займет+риск ошибки и решил, что надо использовать ту формулу, которая с S(n,k) числа Стирлинга второго рода. Я попытался набросать небольшой алгоритм, для вычисления чисел Стирлинга он не сошелся, и я бросил, т.к. понял, что увязаю в этой задаче и теряю время

(373) Я не имел в виду ручной расчет производных.
Вот мой код.
http://likecode.ru/code/51dc4d97afb73/

Делаем замену, x=1/b При a=0 получаем ряд x+x^2+x^3... Почленно продифференцируем, и полученный ряд домножим на x. Получим 1*x+2*x^2+... — то есть получили ряд при a=1. Еще раз почленно продифференцируем и домножим на x. Получим 1^2*x+2^2*x^2+3^2*x^3... — ряд при a=2 и т.д. Сумма ряда при a=0 равна x/(1-x), сделаем замену t=x-1 (то есть x=t+1) Сумма ряда при этом стала равна -1-1/t. Возьмем производную, получим 1/t^2, домножим на x=t+1, получим 1/t+1/t^2 — это сумма ряда при a=1. Опять возьмем производную, и домножим на (t+1) и т.д. Коэффициенты при 1/t^j — будем хранить в массиве. Получив все коэффициенты сделаем замену 1/t=b/(1-b)

Комментарий к популярной фразе "Могу решить ЛЮБУЮ олимпиадную задачу".
http://codeforces.ru/blog/entry/8265#comment-140481
Если в том году были задачи, которые я до сих пор не знаю как решать, то задачи этого года....
//
То есть двукратный медалист чемпионата мира не может решить любую задачу.

Через 15 минут стартует первый тур основной части.
http://algorithm.contest.yandex.ru/contest/308/enter/

Я каким-то образом умудрился накосячить (втемную) в третьей, простейшей задаче :(
В итоге вместо сразу выигранной футболки, 130 место.

(377) Где можно посмотреть условия задач ?

(378) для не участников еще не выложены.

Вот задача которую никто не решил.

Государственные дороги

Ограничение времени    5 секунд
Ограничение памяти    512Mb
Ввод    стандартный ввод
Вывод    стандартный вывод
Легенда

В средние века на территории Байтландии существовало несколько государств. При этом границы государств постоянно изменялись, в результате чего крупные города переходили из одного государства в другое. Сейчас историки пытаются выяснить конфигурацию государств в разное время.
Один из применяемых ими способов основывается на упоминании в хрониках статуса соединяющих города дорог. Если в какой-то исторический момент дорога имеет статус государственной, то историки считают, что соединяемые ею города в этот момент точно принадлежат одному и тому же государству. Однако для передвижения использовались и дороги местного значения, о которых хроники даже не упоминают. Поэтому утверждение о том, что любые два города в одном государстве соединены государственной дорогой, в общем случае неверно, равно как и утверждение, что между любыми двумя городами, принадлежащими одному государству, можно было проехать исключительно по государственным дорогам.
Для проверки этого подхода историкам нужна система, сохраняющая данные о статусе дорог в хронологическом порядке и отвечающая на запросы относительно того, возможно ли, что в текущий (с точки зрения внутренней хронологии системы) момент заданные города — и только они — образовывали единое государство.
Формат ввода

Первая строка ввода содержит два целых числа n и q (1 ? n ? 1?000?000, 1 ? q ? 2?000?000) — количество городов в средневековой Байтландии и количество событий (записей в хрониках и запросов). Города занумерованы последовательными целыми числами от 1 до n.
Далее идут события и запросы, перечисленные в хронологическом порядке (запрос относится к тому моменту времени, когда произошли все перечисленные до него события, но не произошло ни одного события, перечисленного после него). Каждая из q строк обозначает событие или запрос и имеет следующий формат:
«» (событие первого типа) обозначает, что дорога между городами u и v получила статус государственной (1 ? u < v ? n);
«» (событие второго типа) обозначает, что дорога, которая получила статус государственной в результате m-го с начала хроник события первого типа, перестала быть таковой (m может принимать значения от 1 до количества событий первого типа, произошедших перед данным);
«» — запрос: могло ли на момент, описываемый всеми уже обработанными событиями, существовать государство, список городов которого состоял из k городов с номерами  (1 ? k ? n, 1 ? u1 < u2 < … < uk ? n).
На всех упоминаемых в хрониках дорогах движение является двусторонним, при этом любые два различных города соединены не более чем одной дорогой.
На момент инициализации базы (до первого запроса) ни одна дорога не имела статуса государственной. Одна и та же дорога может менять статус с государственной на обычную и наоборот сколько угодно раз. Гарантируется, что каждое m встретится в событиях второго типа не более одного раза. Сумма всех значений k не превосходит 2?000?000.
Формат вывода

В ответ на каждый запрос выведите в отдельной строке «YES» в случае, если данный список городов мог быть полным списком городов некоторого государства в соответствующий момент, и «NO» в противном случае.

Не участвовал, не смог сегодня.
Но, думаю, в первом раунде чего то добиться было шансов мало. Поучаствую в остальных двух

(383) Если бы я не лажанулся в третьей задаче - занимал 24 место, выигрывал футболку (все с зачетными очками получают футболку), и шансы на выход в финал хоть и оставались призрачными, но уже появлялись зачетные очки, которые приближают к участию в финале. Так что шансы для меня лично были.

(381) Уже озвучили, решается элементарно За O(количестводорог+Сумма(k)) - при помощи Zobrist key.
То есть укладывается с огромным запасом.

Это возможно нужно умножить на логарифм количества дорог.
Если хранить Зобрист каждой дороги в индексированной структуре.

Не нужно умножать. У меня решение на Java уложилось в TL впритык, c индексированной структурой не уложится.

В этом туре поделил 14-106 место. Застрял на третьей задаче. Не смог запихнуть свое решение в TL.

104-106 :)

Вообще не понял что за фигня с лягушками. Убил на них время.
В тестовом первом примере высота кочек всегда =1
Усталость первой лягушки 1,2,3,4....
Вторая увеличивает усталость если у первой усталось четная
Третья увеличивает усталость когда у второй усталость четная.

ПОлучается по усталостям 1-ой, второй и третьей по ходам

1 1 1
2 2 2
3 2 3
4 3 3
5 3 3
6 4 4
7 4 5
8 5 5
9 5 5
10 6 6
11 6 7
12 7 7
13 7 7
14 8 8
15 8 9

Итого лягушки находятся на кучках с номерами (ИхУсталость-1)
Первая лягуха на 14-й кучке. Согласно тестового примера, расстояние между 1-й и 3-й должно быть 10. Но 15-9=6
ЧЯДНТ

(390) Я её даже условие не читал. Вечером прочитаю.

(390) "Если лягушка не прыгала, то и следующие тоже не прыгали. Это непонятно из условия, но понятно из семпла."
(с) http://codeforces.ru/blog/entry/8344#comment-141473

(392) Яндекс лажанулся, правда, пострадал при этом я

(393) Да, накосячили в двух задачах - первой и третьей.

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

(395) Это разве не задача в целых числах?

(396) эта задача вообще на другую тему.
Влоб решать, через целочисленную площадь - не уложишься в tl.

А проблема в том, что в лучшем решении на java - long - не хватает разрядов, double - не хватает точности, а BigInteger не укладывается в tl. То есть решать нужно на длинной арифметике на двух лонгах.
При этом на c++ все ок с double.

В понедельник подъем в 4 утра?

(399) угу, я уже будильник поставил.
Прикинул - если войду в 150, то в итоге по трем раундам войду в сотню, и получу очередную футболку :)

Писать в 5 утра конечно жесть.
Первую задачу сдал с седьмой! попытки - не видел что для расчета среднего делаю целочисленное деление.
Шестую задачу со второй - не увидел что переполняю int возведением в квадрат.
В итоге на остальные задачи времени не хватило.

Но занял 104 место, должно хватить для футболки.

(401) Так я не понял, сколько ввитоге задач засчитали ?

(402) Две - первую и шестую.
Футболку выиграл, в итоге 89-ое место.

Все 25 вышедших, за исключением двух кандидатов - гроссмейстера codeforces. Кандидаты, оба, сыграли всего по 2-3 турнира, и просто видимо не успели набрать рейтинг.

Ну печально че уж. Теперь, зная о таких чемпионатах, думаю набить руку и к следующему чемпионату представлять из себя реальную угрозу.

Вот эти два кандидата codeforces
http://community.topcoder.com/tc?module=MemberProfile&cr=8357090
http://community.topcoder.com/tc?module=MemberProfile&cr=8365685
Оба гроссы TopCoder, один Поляк, второй Словак.
Так что не гроссам - без шансов выйти в финал.

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

(407) тебе же не 20 лет. Странно...

(408) а фигли...
http://www.kinopoisk.ru/film/666935/

смотрел ксатит это киношку, нормально...

В Яндексе хорошие зарплаты, я даже хотел резюме туда лет пять назад послать, не послал только потому что моя тогдашняя подруга устроилась директором в тот-же департамент :)

Не пять лет назад, а или в 2005-ом, или в 2007-ом. Точно не помню.

(403) молодец, чо уж там :)