Форум Всеукраїнської інтернет-олімпіади NetOI

LVV написав:

Пропоную поділитись своїми кращими рішеннями, які набрали максимальний бал. ...

Есть пара предложений по задаче Robot:

1) Если использовать двумерный массив для моделирования перемещения робота, то совсем не обязательно по окончанию "перемещений" сканировать ВСЮ матрицу на предмет подсчета нужных клеток. Достаточно считать их прямо по ходу "движения" - если после попадания на клетку там оказывается РОВНО "2", то cnt++, иначе - ничего не делаем.

2) Можно обойтись и без матрицы. После каждого хода (включая нулевой ход, приведший в стартовую клетку) получаем "хэш" клетки hash = i * 3000 + j; и заносим его в массив/список. По окончанию движения - подсчитываем число хэшей, повторяющихся в массиве более одного раза (для этого удобно сначала отсортировать массив).

По поводу этой задачи созрел вопрос к жюри...
Если немного изменить условие, зафиксировав размер поля = (n x n) и число ходов = M, то :
1-й способ использует k1*(n^2) памяти и имеет асимптотику О(M).
2-йспособ - использует только k2*M памяти и имеет асимптотику O(M log(M)) - из-за сортировки массива.

Т.о. получаем, что при достаточно большом числе M второй способ будет получать TimeLimit по сравнению с 1-ым способом, если этот самый TL задавать от "самого быстрого" решения. Но неужели 2-ой способ хуже? На всех известных мне контестах по ACM-правилам, а также на 4-ом туре Всеукра и на Межнаре по информатике максимальное время решения - фиксировано и приведено в условии задач.

Может, уже пора использовать общепринятые критерии ограничения по времени на решения ? И тем самым - приучать участников к общепринятым условиям контестов?

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

Поделюсь, пожалуй, своими версиями решений.

MaxBox2

#include <iostream>

int main()
{
    long long a;
    std::cin>>a;
    std::cout<<(a+3LL)/6LL;
    return 0;
}

Grain

#include <iostream>

int main()
{
    int T;
    int a,b;
    std::cin>>T;
    for(int i=0;i<T;++i)
    {
        std::cin>>a>>b;
        std::cout<<1+(a%2);
    }
    return 0;
}

Commerce

#include <iostream>

int main()
{
    int N,M;
    std::cin>>N;
    M=N/2+1;
    std::cout<<M*N-2*N-M*M+2*M;
    return 0;
}

Apples

#include <iostream>

int main()
{
    int T;
    unsigned long long A,B,C;
    std::cin>>T;
    for(int i=0;i<T;++i)
    {
        std::cin>>A>>B>>C;
        std::cout<<1+(
            ((A+B)&1ULL)+((B+C)&1ULL)+((C+A)&1ULL)!=2||
            ((A==0ULL)+(B==0ULL)+(C==0ULL)>1&&A+B+C!=1));
    }
    return 0;
}

Robot

#include <cstdio>

int main()
{
    int c,a,b,i,j,x[1024],y[1024];
    x[0]=0;y[0]=0;
    for(i=1;(c=fgetc(stdin))>13;i+=(c>32))
    {
        x[i]=x[i-1]+(c=='L')-(c=='R');
        y[i]=y[i-1]+(c=='U')-(c=='D');
    }
    for(a=0;i;a+=(b==1))
        for(j=--i,b=0;j--;)
            b+=(x[i]==x[j]&&y[i]==y[j]);
    printf("%d",a);
    return 0;
}

Все приведённые решения набирали полный балл на онлайн-проверке.

Как легко видеть, решение Robot имеет сложность O(M^2), и при этом укладывается в time-limit.

Но решение shoa169 с сортировкой, конечно, имеет преимущества.

При желании, если не ошибаюсь, можно реализовать решение, укладывающееся в O(M) времени и O(M) памяти, следующим образом:

#include <iostream>
#include <string>
#include <vector>

// Somewhat inspired by http://www.geeksforgeeks.org/find-duplicates-in-on-time-and-constant-extra-space/

int main()
{
    int answer;
    std::vector<std::vector<int> > y(2048);
    std::vector<int> v;
    int xc,yc;
    int x_min,x_max,y_min,y_max;
    std::string s;

    std::cin>>s;

    xc=1024;
    yc=1024;
    x_min=xc;
    x_max=xc;
    y_min=yc;
    y_max=yc;
    y[yc].push_back(xc);

    for(int i=0;i<s.size();++i)
        if(s[i]>='A'&&s[i]<='Z')
        {
            xc+=((s[i]=='R')-(s[i]=='L'));
            yc+=((s[i]=='U')-(s[i]=='D'));
            y[yc].push_back(xc);
            if(xc<x_min) x_min=xc;
            if(xc>x_max) x_max=xc;
            if(yc<y_min) y_min=yc;
            if(yc>y_max) y_max=yc;
        }

    v.resize(x_max-x_min+1,0);
    answer=0;

    for(int i=y_min;i<=y_max;++i)
    {
        for(int j=0,n=y[i].size();j<n;++j)
            if(v[y[i][j]-x_min]++==1)
                ++answer;
        for(int j=0,n=y[i].size();j<n;++j)
            v[y[i][j]-x_min]=0;
    }

    std::cout<<answer;
    return 0;
}

(Решение набирает полный балл на онлайн-проверке).
Таким образом заданный выше вопрос:

shoa169 написав:

По поводу этой задачи созрел вопрос к жюри...
Если немного изменить условие, зафиксировав размер поля = (n x n) и число ходов = M, то :
1-й способ использует k1*(n^2) памяти и имеет асимптотику О(M).
2-йспособ - использует только k2*M памяти и имеет асимптотику O(M log(M)) - из-за сортировки массива.

становится несколько менее актуальным.

Добавлю ещё, что
1. Выделение (и обнуление) памяти - небесплатно, и О(M) - это в каком-то смысле O(n^2+M) (здесь можно удариться в схоластику о том, как операционная система выделяет страницы виртуальной памяти, однако не буду развивать данную тему).
2. Если n намного меньше M, то на мой взгляд, да - 1-й способ лучше. Очевидно, n>2*M+1 рассматривать не особо осмысленно. Для небольших M разницу в ассимптотике измерить нетривиально. Если же n~M и M достаточно велико (чтобы появилась ощутимая разница во времени исполнения), то 1-й способ всё-равно требует чрезмерного количества памяти и использовать его не представляется возможным.

JP3005 написав:

а что означает эта строка std::cout<<(a+3LL)/6LL;
и вот этот участок кода std::cout<<1+(
            ((A+B)&1ULL)+((B+C)&1ULL)+((C+A)&1ULL)!=2||
            ((A==0ULL)+(B==0ULL)+(C==0ULL)>1&&A+B+C!=1));

std::cout вроде бы стандартный способ вывода (в библиотеке C++):
http://en.cppreference.com/w/cpp/io/cout
http://en.cppreference.com/w/cpp/io/bas … rator_ltlt

Если вопрос о суффиксе LL, то он означает целочисленную константу типа long long:
http://www.cplusplus.com/doc/tutorial/constants/

По логике работы строки близки к соответствующему коду от LVV.

Первая выводит a/6 округленное к ближайшему целому (типа long long и только для неотрицательных чисел; 0.5 округляется вверх).

Вторая почти эквивалентна условию от LVV, только записана в одно логическое условие (результат которого приводится к целому (true=1, false=0) и, сложенным с 1, выводится на стандартный output) использует несколько другие условия.

((A+B)&1ULL)+((B+C)&1ULL)+((C+A)&1ULL)!=2
Т. к. ни одна из операций не может изменить чётность пар A+B, B+C, и C+A, то если эти чётности не совпадают с таковыми для выиграшной позиции, то выиграшной стратегии не существует. Условие проверяет, что сумма последних бит в (A+B), (B+C), и (C+A) не равна 2 (т. е. сумме в выиграшной позиции).

((A==0ULL)+(B==0ULL)+(C==0ULL)>1&&A+B+C!=1)

В противном случае, выиграшной стратегии не существует только если как минимум 2 из 3-х чисел A, B и C равны 0, и при этом оставшееся число не равно 1 (что является выиграшной позицией).

Правка: по здравом размышлении, A+B+C!=1 надо заменить на A+B+C!=1ULL. Во имя единообразия.
Правка^2: немного уточнений.

Відредаговано FordPerfect (2014-11-15 18:34:37)

Як Commerce ,без циклів
var
  n: longint; z: int64;

begin
  read(n);
  if n mod 2 = 0 then
    z := sqr(n - 2) div 4;
  if n mod 2 = 1 then
    z := ((n - 3) * (n - 1)) div 4;
  write(z);
end.

FordPerfect написав:

или даже

Код:

print (input()-2)**2/4

Действительно, работает.

#include <iomanip>
#include <cmath>
using namespace std;
int main()
{  
double N;
cin >> N;
cout <<setprecision(15) << long(pow((N-2),2)/4);
return 0;
}

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

Commerce:
Z = (N-4)^2/4;

Maxbox2:
x = a/6;

Grain
cout << (B%2==0?1:2);

Эти задачи впору предложить на олимпиадах по математике, а не по информатике.

Відредаговано LVV (2014-11-19 05:27:47)

andervish написав:

Участвую в общем зачете, баллы, в принципе, не важны. Но для участников, ежели они отважатся писать олимпиаду на python, эти вещи могут оказаться критичными.

PS. Кстати, если в программе есть функции, которых нет в питоне <2.2, но они не запускаются при исполнении на тестах jn-line проверки, то такая программа пройдет проверку без ошибок. Поэтому ссылка на установщик вдвойне желательна.

Присоединяюсь к вышесказанному. Так и не смог найти, что в моей реализации Robot-а выдаёт "wrong answer" на тестах из условия в онлайне, хотя тест из условия локально - проходит. Хотелось бы всё-таки получить версию python хотя бы 2.6.