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


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

Ви не зайшли.

#1 2013-02-05 23:56:49

seland
Новий користувач
Зареєстрований: 2012-12-28
Повідомлень: 14

Розбір завдань 3-го туру

Перш за все, дякую журі за цікаві завдання! Є чому повчитися. А стосовно третього туру, дуже цікаво, що то за магічні два останні тести в задачі Пігулія, які не пройшли 90% розв'язків учасників. Особисто в мене система видає Bad Data, хоча з введенням начебто все добре.

Поза форумом

 

#2 2013-02-08 09:08:55

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

Re: Розбір завдань 3-го туру

Хорошие были задачки. smile К сожалению традиции NetOi таковы, что решения мы увидим лишь через несколько месяцев.
А участники не очень спешат поделиться своими 60-бальными  решениями sad


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

Поза форумом

 

#3 2013-02-08 10:04:31

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

Re: Розбір завдань 3-го туру

Я бы поделился своими решениями, как и на прошлых двух турах, но этот был особо неудачным для меня и ни одно из моих решений 60-бальным не является.
Четвёртая похожа на алгоритм Дейкстры с некоторыми изменениями (за расстояние до вершины считается не сумма веса рёбер, а максимальный вес из пути).
Вторая - вероятно, решается с помощью этого.
В третьей надо, проходя по башне, удалять элементы из неё сразу когда встречаем второй элемент, при этом прибавляя к ответу количество кубиков между ними.
То есть, если мы имеем на входе башню из:
1 5 3 4 2 5 3 4 2 1
То сначала удалим пятёрки, прибавив к ответу 3.
1 3 4 2 3 4 2 1
Затем удаляем тройки, прибавляя к ответу 2.
1 4 2 4 2 1
Затем четвёрки, прибавляя к ответу 1.
1 2 2 1
Затем двойки, прибавляя к ответу 0.
1 1
И, наконец, единицы, прибавляя к ответу, опять таки 0.

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

Поза форумом

 

#4 2013-02-08 14:15:37

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

Re: Розбір завдань 3-го туру

Paint "в лоб" решается легко, вложенными циклами:
Рассматриваем различные пары точек (два цикла i,0,N; j,i,N; ) и для каждой пары (Xi,Yi)-(Xj,Yj) рассматриваем все имеющиесся точки (третий цикл z,0,N; ) на принадлежность прямой: (Xz-Xi)*(Yj-Yi)==(Yz-Yi)*(Xj-Xi).
Правда, при N=1000 придётся произвести около 500 000 000 проверок на выполнение условия, а значит тайм-лимит выдержан не будет.

Можно использовать двумерный массив, индексы которого являются координатами точек. Тогда достаточно в обнулённом массиве отметить, единицами, наличие координат, и, для каждой из 500 000 возможных прямых рассматривать не все 1000 вариантов, а определить целочисленный шаг для координат, и проверять через этот шаг наличие единицы в двумерном масиве. Но тут возникает другая проблема: даже для битового массива (в С++ есть bitset) объём 1000000 х 1000000 слишком велик.
Учитывая, что точек (ячеек) в таком огромном массиве используется всего лишь 1000, следует использовать так называемый разреженный массивы.

Відредаговано LVV (2013-02-08 16:46:21)


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

Поза форумом

 

#5 2013-02-08 14:40:18

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

Re: Розбір завдань 3-го туру

Я в пятой пробовал решать так:
1. Сортируем все точки по значению х. (Если х у двух точек одинаково, то по у)
2. Делаем тройной цикл. При этом, чтобы максимально уменьшить ассимптотику, не рассматриваем все тройки точек отдельно, а формируем отрезок, состоящий из точек, лежащих на одной прямой с i-ой и j-ой точкой. После этого когда ответ сформирован, плюсуем к ответу
(s*(s-1)*(s-2))/2
3. Теперь проходимся по двумерному логическому массиву tab[n][n] и устанавливаем ячейки, индексами для которых выступают индексы точек на этой линии значение false, чтобы потом на каждой итерации j делать проверку на то, что tab[i][j]==true, чтобы не проверять по второму кругу уже отброшенных отрезки.

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

Поза форумом

 

#6 2013-02-08 15:22:46

Alex_Bulany
Новий користувач
Зареєстрований: 2009-01-26
Повідомлень: 17

Re: Розбір завдань 3-го туру

Для успішного розв’язку задачі № 5 потрібно звести складність до n^2 log(n).
А. Перебираємо по всім точкам від 1 до n-2 і знаходимо трійки точок, до яких обов’язково входить і-та.
  Б. Сортуємо інші точки (j від i+1 до n) за напрямом від і-ї точки. Я пробував три способи, вони дають приблизно однаковий результат за часом:
    а. (тип double)За кутовим коефіцієнтом k прямої, яка проходить через точки Pi та Pj.
       Для вертикальної прямої можна обрати, наприклад, k=3*10^9.
    б. (тип int64) За векторним добутком (Xk-Xi)(Yj-Yi)-(Xj-Xi)(Yk-Yi).
    в. (тип int) За вектором PiPj. Коефіцієнти вектора скорочують на НСД((Xj-X),(Yj-Yi)).
        Окремо розглядаються горизонтальний та вертикальний одиничні вектори.
  В. Визначається кількість точок К, що лежать на одній прямій. Тоді кількість трійок збільшується на 3К(К-1)/2.
Найбільший час проходження одного теста – 0,38с.
#include <iostream>
#include <cstdio>
#include <stdlib.h>
using namespace std;
#define N 1001
int G(int a,int b){
  return (b)?G(b,a%b):a;
}
struct L{int x,y;};
L a[N];
int C(const void* a,const void* b){
  const L* c = (L*)a;
  const L* d = (L*)b;
  int k=c->x-d->x;
  if(k)return k;
  return (c->y-d->y);
}
int main(){
  int i,j,k,m,n,r,x[N],y[N],dx,dy,q,res=0;
  scanf("%d",&n);
  for(i=0;i<n;i++)
    scanf("%d%d",&x[i],&y[i]);
  for(i=0;i<n-2;i++){
    for(m=-1,j=i+1;j<n;j++){
      dx=x[i]-x[j];dy=y[i]-y[j];
      if(dx)
        if(dy){
          if(dx<0){dx=-dx;dy=-dy;}
          r=G(dx,abs(dy));
          if(r>1){dx/=r;dy/=r;}
          a[++m].x=dx;a[m].y=dy;
        }else {a[++m].x=1;a[m].y=0;}
      else {a[++m].x=0;a[m].y=1;}
    }
    qsort(a,m+1,sizeof(L),C);
    for(q=k=1;k<=m;k++)
      if((a[k].y==a[k-1].y)&&(a[k].x==a[k-1].x))q++;
      else{if(q>1)res+=q*(q-1);q=1;}
    res+=q*(q-1);
  }
  cout << 3*res/2 << endl;
  return 0;
}

Відредаговано Alex_Bulany (2013-02-08 15:31:27)

Поза форумом

 

#7 2013-02-08 19:38:38

Zip753
Новий користувач
Звідки: Донецк
Зареєстрований: 2012-10-13
Повідомлень: 5

Re: Розбір завдань 3-го туру

Я тоже писал решение за N^2*logN, но оно не прошло некоторые тесты по времени. Идея такая: перебираем все пары точек, для каждой пары составляем уравнение прямой, нормируем его (как-либо приводим к общему виду) и записываем в массив коэффициенты. Потом сортируем коэффициенты и считаем, сколько различных прямых получилось. Ну и там небольшая магия по поводу количества точек. Ничего такого ужасного и временеёмкого не делал, всего лишь сортировка. Тем не менее...

Поза форумом

 

#8 2013-02-15 13:10:52

jurij
Новий користувач
Зареєстрований: 2009-01-23
Повідомлень: 40

Re: Розбір завдань 3-го туру

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

#include "iostream.h"
using namespace std;
int main()
{
  int  w[600]={0};
    int a, b, i, j=1, k=0, m, p=1 ;
     cin >> m >> a;
     for (i=2; i<m; i++)
    {  cin >> b;
       if  ((a>b) && (j==1) || (a<b) && (j==-1))  p++; else
       {j=-j;w[k]=p;k++; p=1;}
       a=b;
    }  if (j==-1) w[k]=p+1; else {w[k]=p; k++;w[k]=1;}
    p=0;
    for (i=1; i<=k; i=i+2)
    {
      if (w[i-1]%2==0 && w[i]%2)
      {cout << p+w[i-1] << " ";p=p+w[i-1]+w[i];continue;}
      if (w[i-1]%2 && w[i]%2==0)
      {cout << p+w[i-1] +1<< " ";p=p+w[i-1]+w[i];continue;}
      p=p+w[i-1]+w[i];
    }     
    return 0;
}

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt