Саратовский государственный университет в рамках Чемпионата мира по программированию ACM-ICPC 2010/11 с 19-го по 23-е октября 2010 проводит ХIII Четвертьфинальные соревнования Чемпионата мира по программированию Южного региона России.
За право выйти в полуфинал Чемпионата мира будут бороться команды вузов из Астраханской, Волгоградской, Воронежской, Нижегородской, Пензенской, Ростовской, Самарской, Саратовской, Тамбовской, Ульяновской областей, Краснодарского, Ставропольского краев, из республик Адыгея, Марий Эл, Мордовии, Северной Осетии, Татарстан. 63 команды примут участие в соревновании.
Кроме того, 19-го октября 2010 будет проведена IХ Региональная командная олимпиада школьников по программированию, которая является отборочным этапом на Всероссийскую командую олимпиаду школьников. Лучшие пять школьных команд завоюют право участия в финальном этапе олимпиады.
На официальном сайте http://contest.sgu.ru/ вы сможете следить за результатами в процессе соревнования.
Уже пятый год подряд кроме официального соревнования участникам предлагается неофициальное развлекательное соревнование Code Game Challenge. В рамках Code Game Challenge команды будут писать программы, которые будут помещаться в симулятор игрового мира, чтобы напрямую соревноваться с программами других участников! Таким образом, вместо проверки на наборе тестов, ваши подходы будут помещаться непосредственно в эмулятор игрового мира, чтобы непосредственно соревноваться с программами других команд.
23-го октября в 11:00 на сайте http://acm.sgu.ru/ состоится онлайн-контест по задачам четвертьфинала. В систему будут интегрированы результаты участников официального онсайт соревнования.
Всем удачи!
MikeMirzayanov
UPD: Соревнование закончено. Всем спасибо за проявленный интерес! Результаты соревнования опубликованы.
Поздравляем победителей соревнований:- Саратовский государственный университет #2 (Иванов, Рахов, Кузнецов) — 1 место (9 решенных задач)
- Нижегородский государственный университет (Епифанов, Вадимов, Шмелев) — 2 место (8 решенных задач)
- Саратовский государственный университет #1 (Фефер, Агапов, Бондаренко) — 3 место (8 решенных задач)
- Саратовский государственный университет #2
- Нижегородский государственный университет
- Саратовский государственный университет #1
- Волгоградский государственный технический университет #1
- Саратовский государственный университет #3
- Казанский федеральный университет #1
- Ульяновский государственный технический университет
- Самарский государственный аэрокосмический университет #2
- Волгоградский государственный университет #1
- Таганрогский технологический институт Южного Федерального университета #1
- Астраханский государственный университет
- Таганрогский технологический институт Южного Федерального университета #2
- Адыгейский государственный университет
- Самарский государственный аэрокосмический университет #1
Не приготовил ли ты им какой нить сюрприз? )
Мне кажется, что на столь серьезном мероприятии и в столь уважаемом ВУЗе всё и всегда должно было и быть на высшем уровне. Или прецеденты уже бывали?
Я уже не помню в чем именно, вроде в одной задаче были неверные тесты и в итоге это довольно сильно повлияло на штрафное время лидеров, вот и решили их уровнять по этому показателю.
На топкодере тоже бывали ошибки в решениях жюри, причем как просто небольшие баги, так и в принципе неверные алгоритмы решения...
И это нормально, чем выше уровень мероприятия, тем меньше вероятность ошибок, но она никогда не ноль.
Отлично. Я давно ждал возможности реабилитироваться после четвертьфинала 2009 года. Я и моя команда очень усердно тренировались, чтобы на этот раз съездить минимум в Санкт-Петербург.
Всем удачи. Увидимся в среду ; )
А когда будут результаты?
Круто, с победой Saratov SU #2! Вот как знал, что могут занять первое место :)
С выходом в полуфинал команду Volgograd STU #1.
Хочется посмотреть, что там за задачи, которые никто не сдал... Такие пади даже в Петрозаводске не дают.
Задача А довольно четкая. Мы сделали критическую ошибку в том, что не подумали перед тем, как писать и наш путь к простому и элегантному коду был долгий. В результате получилось не очень много. Но мы посадили пару багов и не успели их найти. Мораль: думайте, перед тем как писать такое.
посмотрим сколько на acm.sgu.ru сделают. 10 вполне реально сдать. я правда до начала ЧФ думал что 11 сдадут...
Сортируем точки по возрастанию x, а при равных x по убыванию y. Теперь чтобы найти максимальную длину пути можно забыть про x и найти наибольшую возрастающую подпоследовательность по y. К сожалению, саму длину нам искать не надо, но оказывается можно модифицировать стандартный алгоритм нахождения LIS за логарифм под наши нужды. А именно, будем поддерживать не только массив a[i] из минимальных элементов, на которые закачиваются все возможные подпоследовательности длины i, но и при его обновлении будем складывать в такие же "корзины" сами точки. Итого, после рассмотрения всех элементов последняя корзина у нас будет содержать все точки которыми может заканчиваться самый длинный путь. Мы будем идти по этим корзинам от последней к первой и, убирая лишние точки, делать вывод о том, обязательная точка или возможная (если после убирания лишних в корзине осталась одна точка, то она обязательная, если больше одной, то все они возможные).
>Илья Литерман, выпускник СГУ, в настоящий момент являющийся одним из руководителей компании Crid Dynamics
:(
P.S. Отправил исправление. Посмотрим, как долго у них займет проверка)
Снарк крут =)
sum = size(a) + size(b) + ( size(t) | g[a][t] && g[t][b] )
size(x) - размер компоненты x.
#include <iostream>
#include <iomanip>
#include <math.h>
double mi=0.0;
int n;
int a[401];
double s[401],b[401];
double k=0;
using namespace std;
void funt(int h,double d)
{
for (int i=h-1; i>=1; i--)
{ s[i]=s[i+1]-d;
};
for (int i=h+2; i<=n; i++)
{ s[i]=s[i-1]+d;
};
k=0;
for (int i=1; i<=n;i++)
k=abs(s[i]-a[i]+0.0)+k+0.0;
if (k<mi)
{
mi=k;
for (int i=1; i<=n;i++)
b[i]=s[i];
}
}
int main()
{
cin >>n;
for (int i=1; i<=n; i++)
cin>>a[i];
double f=(a[n]-a[1]+0.0)/(n-1+0.0);
s[1]=a[1];
for (int i=2; i<=n;i++)
{
s[i]=s[i-1]+f;
k=abs(s[i]-a[i]+0.0)+k+0.0;
};
mi=k;
for (int i=1; i<=n;i++)
b[i]=s[i];
double dist;
for (int i=1; i<n; i++)
{
dist=(a[i+1]-a[i]+0.0);
s[i]=a[i]; s[i+1]=a[i+1];
funt(i,dist);
};
cout<<fixed<<setprecision(4)<<mi<<endl;
for (int i=1; i<=n; i++)
cout<<fixed<<setprecision(10)<<b[i]<<" ";
return 0;
}
{ s[i]=s[i-1]+d;
}
http://pastie.org/1250704
Попробую немного объяснить.
Вершин у нас до 200.Дорог в маршруте тоже <=200.
Сделаем массив boolean NextIter[N][I],где N-это количество дорог в маршруте,и Next[N][I]==TRUE,если город I входит в маршрут длиной N.
Тогда,очевидно,можно получить какие города входяд в маршрут длиной N+1,зная какие города входят в N:
for(int i=0;i<r;i++)//текущее количество дорог
{
for(int j=0;j<n;j++)
{
if(NextIter[i][j])//Если j входит в текущий маршрут
{
for(int k=0;k<n;k++)//перебираем все соседние города
{
if(G[j][k]==lgs[i])NextIter[i+1][k]=true;//Если расстояние до них-то что нужно,добавляем в NextIter[N+1]
}
}
}
}
Ответом будет такие I,для которых NextIter[r][I]=TRUE
#include <iostream>
using namespace std;
int main()
{
char s[26];
int d[26][26],n,m,bom=0,k=0,rem,max=0,remx=0,remy=0;
cin>>n>>m;
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){ d[i][j]=0;}}
for(int i=0;i<n;i++)
{
cin>>s;
for(int j=0;j<m;j++)
{
if(s[j]=='.') d[i][j]=1; else d[i][j]=2;
if(d[i][j]==2) {d[n][j]++;d[i][m]++; bom++;}
}
}
Не могли бы люди, сдавшие задачу Running Hero, сказать, за какую сложность её предполагалось решать? Судя по ограничениям, O(N^2) должно проходить, однако TL #9 на Java.
UPD: ого, TL 9 - это на acm.sgu.ru, а вот на neerc.ifmo.ru/trains это же решение получает Accepted. Что-то я совсем ничего не понимаю =/ . Особенно интересной ситуацию делает то, что с другой задачей(а именно Rectangles с четвертьфинала Центрального региона) все абсолютно наоборот - на neerc.ifmo.ru/trains TL 29, а на другом сайте(к сожалению забыл название) - OK...
Разбиваем все запросы на 200 групп по q = 200 запросов, затем смотрим, какие ребра из неизмененных точно войдут в МСТ. Получится граф с O(q) вершинами. На нем уже можно и Краскала позапускать