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


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#1 2013-11-16 11:08:39

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Разбор задач

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

1. Total.
Элементарная задача на знание базовых алгоритмов, по всей видимости. Можно заметить, что всегда выгодно взять в выигрышные карточки n/2 самых дорогих. Это можно сделать просто отсортировав массив. После этого просто суммируем первые n/2 элементов и отнимаем то, что мы проиграем - сумму оставшихся карточек, которые будут проигрышными. Наиболее быстрые алгоритмы сортировки отработают здесь за O(nlogn), но в принципе, судя по ограничениям, здесь должна пройти и сортировка за O(n^2).
Наилучшая ассимптотика: O(nlogn).
Код на С++:

Код:

    int n;
    cin>>n;
    int*a=new int[n];
    
    for(int i=0;i<n;i++)
    cin>>a[i];
    
    sort(a,a+n);
    
    int ans=0;
    
    for(int i=0;i<n;i++)
    if(i<n/2)
    ans-=a[i];
    else
    ans+=a[i];
    
    cout<<ans<<endl;

2. Msum.
Так как заранее известно, как будет ходить каждый игрок, просто промоделируем эту игру. Если в конце у нас кто-то из игроков набрал больше очков, чем другой, то он выиграл. Иначе ничья.
Наилучшая ассимптотика: O(n).
Код:

Код:

    int n;
    cin>>n;
    long long a=0,b=0,t; // a - очки первого игрока, b - очки второго, t - переменная, хранящая число на входе
    
    for(int i=2;i<=n+1;i++)
    {cin>>t;
    if(i%2)
    b+=t*i;
    else
    a+=t*i;}
    
    long long c,d; // с - номер выигравшего игрока, d - его очки
    if(a>b)
    c=1,d=a;
    else if(a<b)
    c=2,d=b;
    else
    c=-1,d=a;
    
    cout<<c<<' '<<d<<endl;

3. Mcode.
Даже не знаю, что и сказать по этому поводу. Ограничения времени по задаче неприятно удивили. Ну да ладно, опишу своё решение, может, кто-нибудь потом выложет более оптимальное.

Итак, будем перебирать высоту самого оптимального прямоугольника. Вместе с тем для каждой высоты будем перебирать соответствующую ей ширину. При этом в таких пределах, чтобы всегда выполнялось h*w<=n. Легко заметить, что операций у нас будет выполнено примерно n/1+n/2+n/3+...+n/n=n(1+1/2+1/3+...+1/n). Легко заметить, что в скобках у нас находится гармонический ряд. В 1740 году Леонард Эйлер получил ассимптотическое выражение, позволяющее охарактеризовать эту сумму как O(lnn). Таким образом итоговая ассимптотика выходит O(nlogn). Обычно на задачах с ограничениями n<=1e6 этого вполне хватает, но... Это NetOI. И несмотря на то, что такое решение успевало выполниться на макс. тесте с лимитом проверки Online (50 мс), теперь оно на двух последних тестах даёт TLE и в итоге проходит лишь на оценку 18/20...
UPDATE: можно добиться прохождения всех тестов, если высоту перебирать не от единицы, а от большого числа, хотя это в целом неассимптотическая оптимизация.
Наилучшая ассимптотика: O(nlogn).
Код:

Код:

    int n;
    cin>>n;
    int ans=1e9;
    int root=sqrt(n);
    for(int i=max(1,root-30);i<=root;i++)
    for(int j=1;j*i<=n;j++)
    if(n-i*j+abs(i-j)<ans)
    ans=n-i*j+abs(i-j);
    cout<<ans<<endl;

4. Cub.
Симулируем контест. Можно перебирать каждую секунду и проверять, изменился ли во время неё баланс сил, а можно поступить более хитро и как бы использовать checkpoint'ы. Когда какая-нибудь команда сдаёт задачу, мы вначале проверяем, лидировала ли какая-то команда перед сдачей и если да, то начисляем ей очки за время, прошедшее с предыдущей сдачи кем-либо задачи. После этого инкрементируем счётчик сданных задач у этой команды. И, наконец, в конце надо ещё начислить очки той команде, которая лидировала к моменту времени 2880 секунд.
Наилучшая ассимптотика: О(n).
Код:

Код:

    int n;
    cin>>n;
    int a=0,b=0,c=0,d=0; // a - кол-во сданных задач у первой команды, b - у второй, c,d - очки первой и второй команд соответственно.
    
    int w,m,s,ps=0; // ps - предыдущий момент сдачи кем-либо задачи в секундах. 
    
    for(int i=0;i<n;i++)
    {
     cin>>w>>m>>s;
    
     s+=m*60;
    
     if(a>b)   
     c+=s-ps;
     if(b>a)
     d+=s-ps;
     
     if(w-1)
     b++;
     else
     a++;
     
     ps=s;
    }
    
    s=2880;
    
     if(a>b)   
     c+=s-ps;
     if(b>a)
     d+=s-ps;
    
    cout<<c<<' '<<d<<endl;

5. Cell.
Очень интересная задача. Очень жаль, что в отличие от mcode авторы не стали требовать константной ассимптотики и ограничились линейной при n=1e6. Решение для этой задачи за О(n) в целом интуитивно понятно и я не буду на нём останавливаться. Рассмотрим решение за O(1). Для начала обратим внимание, что нам удобнее рассматривать здесь нумерацию начиная с нуля, а не с единицы.
                                                            http://content.screencast.com/users/melfice/folders/Snagit/media/5bf0629f-e24b-495e-94e7-98f2238444e6/11.16.2013-10.36.png

Теперь отметим некоторые значимые клетки - углы.

                                                            http://content.screencast.com/users/melfice/folders/Snagit/media/80a0e70f-367b-45cc-85a8-bff821c20d76/11.16.2013-10.44.png

Для удобства пронумеруем их.
                                                            http://content.screencast.com/users/melfice/folders/Snagit/media/9f61ad74-3fed-4c65-9874-89962077f896/11.16.2013-10.50.png

Теперь обратим внимание на то, как получаются числа в углах. Пускай K(n) - число в каком-то углу.
K(1)=1;
K(2)=1+1;
K(3)=1+1+2;
K(4)=1+1+2+2;
K(5)=1+1+2+2+3;
Легко заметить, что такой вид сумм в углах позволяет нам обобщить эту функцию таким образом:
K(2n)=n(n+1)=n*n+n;
K(2n-1)=n(n+1)-n=n*n;

Как мы видим, принципиальная разница получилась в том, чётный наш угол или же нет. Покрасим все чётные углы в один цвет, а нечётные в другой.
                                                            http://content.screencast.com/users/melfice/folders/Snagit/media/ccd97e18-08a1-4ea1-acbb-8ec734d10000/11.16.2013-10.54.png

Что мы можем заметить далее - чётные и нечётные углы внутри себя отличаются тем, в какую сторону мы будем из них двигаться. Так, из нечётных (зелёных) углов мы можем двигаться либо вверх, либо вних, а из чётных - либо влево, либо вправо. Так как эти параметры чередуются, мы можем утверждать, что то, в какую сторону идёт движение от угла зависит лишь от того, чему равен остаток от деления его номера на 4. Добавим же ещё два цвета в нашу таблицу.
                                                            http://content.screencast.com/users/melfice/folders/Snagit/media/caf7b99d-96e4-4769-a786-e70c39d30bb1/11.16.2013-10.58.png

Наконец, мы можем заметить, что для любой точки мы можем быстро определить её координаты, если знаем координаты угла, который был до неё. Чтобы было проще понять, для каких клеток какие углы мы должны найти, покрасим каждую клетку в цвет соответствующего ей угла.
                                                            http://content.screencast.com/users/melfice/folders/Snagit/media/58c7fd41-d3c1-4602-bcd5-89086d429b28/11.16.2013-11.01.png

Наконец, мы определили для клетки номер соответствующего ей угла. Теперь нам остаётся лишь записать соответствующие формулы для ответа для четырёх случаев - для каждого из цветов.
                                                                                    http://content.screencast.com/users/melfice/folders/Snagit/media/8e816fc8-c5d0-4377-9bac-d668375148cb/11.16.2013-11.04.png
Numb - номер ближайшего угла, dist - расстояние до него. Деление целочисленное, с округлением в меньшую сторону.

Наилучшая ассимптотика: О(1).
Код:

Код:

    int k;
    cin>>k;
    
    k--;
    
    int n=sqrt(k);
    
    int sum=n*n;
    
    int numb=2*n-1; // Номер ближайшего угла, в котором находится значение вида n*n
    
    if(n*n+n<=k) // Искомый угол может быть либо numb, либо numb+1, проверяем это
    numb++,sum+=n;
    
    int x,y;
    
    int dist=k-sum;
    
    if(numb%4==1)
    x=1+numb/4,y=dist-numb/4;
    else if(numb%4==2)
    x=1+numb/4-dist,y=1+numb/4;
    else if(numb%4==3)
    x=-(1+numb/4),y=1+numb/4-dist;
    else
    x=-numb/4+dist,y=-numb/4;
    
    cout<<x<<' '<<y<<endl;

Відредаговано adamant (2013-11-16 12:04:26)

Поза форумом

 

#2 2013-11-16 11:30:14

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

BONUS:
Вскоре после прочтения условий мне пришла следующая мысль: а что, если mcode нам надо посчитать, не для одного заданного к, а для всех к в диапазоне? Возможно, кто-то решил задачу для одного такого K за О(1), тогда всё моё решение не имеет смысла, но если всё же такого решения не существует (в чём я уже не уверен после таких ограничений по времени при проверке), то всё хорошо smile

Изначально я делал это решение для случая, когда диапозон у нас - это [1..n], но сейчас я понял, что решение сойдёт и для диапазона [l..r].
Самое первое, что приходит на ум - перебрать все значения k и для каждого выдать решение за nlogn. Суммарная ассимптотика выйдет n*n*logn. Это очень много. Прибегнем к помощи динамического программирования. Пускай у нас есть ответ для k-1. Тогда мы имеем полное право заявить: если мы будем использовать в оптимальном прямоугольнике меньше, чем k плиток, то ответ для него будет равен ans[k-1]+1. Действительно, все такие варианты нами уже были перебраны. Значит, нам остаётся лишь посчитать, каким будет самый оптимальный вариант, если мы используем ВСЕ плитки. Первое, что приходит на ум - перебрать высоту от 1 до n и проверять, можем ли мы улучшить ответ. Тогда ассимптотика выйдет O(n*n). Можно заметить, что не имеет перебирать далее, чем sqrt(n). Этим мы сможем сократить ассимптотику решения ещё до O( n*sqrt(n) ). Однако, можно оптимизировать ещё лучше. Даже перебирая до sqrt(n), мы перебираем слишком много чисел, не являющихся делителем нашего числа плиток. Естественно, это нам не выгодно. Так и хочется перебирать ТОЛЬКО делители числа. И способ сделать так существует.

Давайте факторизуем (то есть, разобьём на простые делители) наше число k. Это можно легко сделать с помощью решета Эратосфена с линейным временем работы (алгоритм описан здесь: http://e-maxx.ru/algo/prime_sieve_linear). Пускай в нашем разложении оказалось X уникальных простых чисел. Пусть массив prime_val[1..X] будет хранить в себе сами эти числа, а массив prime_num[1..X] - количество вхождений каждого из них. Теперь заведём массив greedy[1..X], который будет обозначать кол-во вхождений каждого из простых чисел в перебираемый нами делитель. После этого мы просто сможем перебрать все делители, если будем перебирать все возможные значения в массиве greedy, например, в лексикографическом порядке. Ответ для l можно найти за nlogn. Таким образом, для диапазона [l..r] мы сможем получить ответ за O( (r-l)*cbrt(r) ), где cbrt(r) - кубический корень из наибольшего числа. Это связано с тем, что на небольших (до 1е9) числах кол-во делителей числа может быть оценено как кубический корень из него же.

Также прилагаю код, который может быть кому-то интересен. При проверке он, как ни странно, тоже набирает 18/20 баллов, хотя работает всё же значительно дольше.

Код:

const int MAXN=1000000;
const int MAXP=50000;
const int INF=1000000000;

int n;
cin>>n;
int erat[MAXN+1];
int back[MAXN+1];
int primes[MAXP];
int ans[MAXN];

ans[0]=0;

int p_size=0;
int k;
for(int i=2,h=1;i<=n;i++,h++)
{
if(!erat[i]) 
{erat[i]=i;back[i]=1;
primes[p_size++]=i;}

for(int j=0;j<p_size && primes[j]<=erat[i] && primes[j]*i<=n;j++)
erat[ primes[j]*i ]=primes[j],back[ primes[j]*i ]=i;

int ans1=ans[i-2]+1;

k=sqrt(i);
if(k*k==i)
{ans[i]=0;h=0;continue;}

int ans2=INF;

int prime_val[7];
int prime_col[7];

int prev_pr=0;
int d_size=0;
int t=i;

while(t!=1)
{
if(erat[t]==prev_pr)
prime_col[d_size-1]++;
else
{prime_val[d_size]=erat[t];
prime_col[d_size++]=1;
prev_pr=erat[t];}
t=back[t];
}

int greedy[7]={0};
int mul[7];

while(1)
{
int num=1;
for(int j=d_size-1;j>=0;j--)
{for(int k=0;k<greedy[j];k++)
num*=prime_val[j];mul[j]=num;}
ans2=min(ans2, abs(num-i/num) );

int cur=0;

if(num>=k)
while(cur<d_size && mul[cur]>=k)
greedy[cur++]=0;
if(cur>=d_size)
goto END;
greedy[cur]++;
while(greedy[cur]>prime_col[cur])
{greedy[cur]=0,greedy[++cur]++; 
if(cur>=d_size)
goto END;}

}
END: 
ans[i-1]=min(ans1,ans2);

}
cout<<ans[n-1]<<endl;

Поза форумом

 

#3 2013-11-16 14:13:27

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Разбор задач

Окей, линейное решение для Mcode. Используем решение для диапазона, описанное в предыдущем сообщении. При этом за l берём ближайшее число, являющееся квадратом целого числа. Очевидно, что для него ответ будет 0. Учитывая, что (n+1)^2=n^2+2*n+1, можно понять, что r-l у нас в худшем случае O(sqrt(n)). После этого высчитываем все числа до k перебором делителей за sqrt(n). В итоге получим ассимптотику О(n).

Решето использовать тут не имеет смысла, т.к. оно само выплняется за O(n) и время выполнения может только ухудшить.
Код:

Код:

int n;
cin>>n;
int ans_cur,ans_pre;


int root=sqrt(n);
ans_pre=0;


for(int i=root*root+1;i<=n;i++)
{
    ans_cur=ans_pre+1;
    for(int j=1;j<=root;j++)
    if(!(i%j))
    ans_cur=min(ans_cur,abs(j-i/j));
    ans_pre=ans_cur;
}
cout<<ans_pre<<endl;

Відредаговано adamant (2013-11-16 15:06:43)

Поза форумом

 

#4 2013-11-16 19:38:57

kiberok
Новий користувач
Зареєстрований: 2011-10-27
Повідомлень: 23

Re: Разбор задач

Расскажу свое решение MCode, которое работает за O(sqrt(K)).
Переберем меньшую сторону W искомого прямоугольника(за O(sqrt(K)), а вторую посчитаем как K/W.
Тогда "код" прямоугольника будет abs(W - K/W) + (K - W * (K/W)). Покажем, что для данной стороны W лучшая вторая это K/W.
Давайте уменьшим вторую сторону на L, тогда квадроподобие уменьшится максимум на L, а экономичность увеличится на W * L >= L.
Значит такое решение правильное.

Відредаговано kiberok (2013-11-16 19:40:07)

Поза форумом

 

#5 2013-11-18 12:02:25

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Разбор задач

adamant написав:

Mcode... в итоге проходит лишь на оценку 18/20...

При простом (тупом) переборе вариантов для нескольких К
for(int H=0; H<=K; H++)
    for(int W=H; W<=K/H; W++)
        cout << W-H+K-H*W << " ";
заметил, что наименьшее значение  |W-H|+K-H*W находится в самом конце "списка".
Немного оптимизировав, получаем код, проходящий 23 теста из 23 за 0.01 сек.:

Код:

#include  <iostream>
#include  <cmath>
using namespace std;
int main()
 {
int K;
cin >> K;
long S=K-1,s;
for(int H=int(pow(double(K),0.45)); H<=K; H++)
    for(int W=H; W<=K/H; W++)
    {
    s=W-H+K-H*W;
    if (s<S) S=s;
    }
cout << S<<endl;
    return 0;
 }

Вік живи - вік навчайся.

Поза форумом

 

#6 2013-11-19 15:07:19

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Разбор задач

5. Cell.

Задачу можно решить "в лоб". Вот только по таймлимиту она балансирует "на грани". То все тесты проходит, то не все... в зависимости от "настроения" принимающего сервера.
В заданиях №17 ДПА 2013 года для 9-х классов есть такая задачка:
Запишіть програму формування та виведення двовимірного масиву A розміру N × N, що містить N2 елементів (3 <= N <= 20) . Елементами масиву є натуральні числа від 1 до N2, що розташовані в порядку спадання відповідно до наведеної схеми.
25   24  23  22  21
10    9    8   7   20
11    2    1   6   19
12   3     4   5   18
13   14  15  16  17

Похожая схема расположения элементов и в задаче Сеll.
17    16    15    14     13
18     5     4      3      12
19     6     1      2      11
20     7     8      9      10
21     22   23    24     25

А с такого массива легко перейти к нужным координатам, взяв за центр координатной оси 1.

Код:

#include  <iostream>
using namespace std;
int main()
{
int N=1001,c=N*N,p=0,n,d=N/2;
int **A= new int*[N];
        for(int i=0;i<N;i++)
            A[i]= new int[N];
for (; p<N/2+1; p++)
{
for ( int i = N-1-p; i > 0+p; i--   ) A[N-1-p][i]=c--;
for ( int i = N-1-p; i > 0+p; i--   ) A[i][0+p]=c--;
for ( int i = 0+p;   i < N-1-p; i++ ) A[0+p][i]=c--;
for ( int i = 0+p;   i < N-1-p; i++ ) A[i][N-1-p]=c--;
}
A[p-1][p-1]=c--;
cin >> n;
for(int i=0; i<N; i++)
      for(int j=0; j<N; j++)
        if (A[i][j]==n)
        {
            cout << j-d << " " << d-i << endl;
            return 0;
        }
}

Відредаговано LVV (2013-11-19 15:16:18)


Вік живи - вік навчайся.

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt