Текущ брой на Списание ИнфоМан
 


Балканска олимпиада по информатика 2005, Задача 1.1. CPU

Уловието на задачата може да прочетете тук.

Решение

Нека приемем, че съществува начин да се провери дали първите Tвръзки от входа могат да се разположат по окръжността, без да се пресичат никои две от тях. За да се реши задачата трябва да се намери такова T, че първите Tвръзки да могат да се поставят без да се пресичат, а първите T+1да не могат. Тогава отговорът на задачата е числото T. Това може да се реализира с двоично търсене.

Сега ще бъде описано как да се реализира проверкатаза фиксирано T, т.е. дали първите Tвръзки могат да се разположат по кръга без да се пресичат никои две от тях. За целта се използват две индексни дървета и една опашка.

Нека за всяка връзка наречем по-малкия и край първи, а по-големия - втори. Първото индексно дърво дава информация за всеки интервал [x,yкъде е първият край на връзката, която от всички връзки, които имат втори край в [x,y], има първи край с най-малка координата. Второто индексно дърво дава информация за всеки интервал [x,yкъде е вторият край на връзката, която от всички връзки, които имат първи край в [x,y], има втори край с най-голяма координата. За улеснение, когато две или повече връзки имат еднакви краища, дадената точка, която служи за техен общ край може да се разшири в няколко точки, за да се избегнат някои проблеми, които могат да възникнат по време на изпълнение на алгоритъма. Също така точки, които не служат за край на нито една връзка, могат да бъдат премахнати.

В началото първата връзка от списъка се поставя в опашката, а всички останали връзки се поставят в двете дървета. На всяка следваща стъпка се вади елементът от върха на опашката. Нека той е A.За него се намират всички връзки, с които той се пресича. Това става като за интервала, който обхваща дадената връзка [x,yв индексните дървета, се прави запитване и се изважда съответната връзка от дървото, след което се поставя в опашката. Всички връзки, които пресичат A, трябва да се поставят от противоположната страна на кръга спрямо A. Ако поне две от тях обаче се пресичат се оказва, че е невъзможно да се поставят всичките връзки от първите T. Ако не възникне такава ситуация, то всички връзки могат да бъдат разположени по кръга, без никои две от тях да се пресичат.

Когато за елемента A, който отговаря на интервала [x,yсе вадят елементи от първото от дърветата, те се вадят в ред на увеличаващ се първи край. За да не се пресичат две поредно извадени връзки трябва първата от двете да съдържа следващата. В противен случай двете ще се пресичат. Така лесно се проверява за извадените връзки от първото дърво дали има някои две, които се пресичат. Аналогично се постъпва и за второто дърво.

Ако извадените от двете дървета връзки не се пресичат, то тази с най-ляв първи край от първото дърво има и най-десен втори край. Аналогично тази с най-десен втори край от второто дърво има и най-ляв първи край. Следователно трябва да се провери дали тези две връзки не се пресичат. Ако не се пресичат, то никои други две от връзките също не се пресичат.

Сложността на описаната проверка е O(N*logN), тъй като всяка от N-те връзки се поставя и вади от дървото по веднъж, а дървото обработва заявките със сложност O(logN).Двоичното търсене, което се използва за намиране на T, ще направи O(logN) проверки, всяка със сложност O(N*logN). Така описаният подход за решаване на задачата има сложност O(N*log2N).

Примерна реализация

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define mx 262144
#define MAX(aa,bb) ((aa).b>(bb).b?(aa):(bb))
#define MIN(aa,bb) ((aa).a<(bb).a?(aa):(bb))
#define in stdin;
FILE*fn;
typedef struct {int a,b,n;}aut;
typedef struct {int l,m,r;aut ans;}node;
node h1[mx*2];
node h2[mx*2];

int build(int where,int l,int r,node*h,int ans)
  {h[where].l=l;
  h[where].r=r;
  h[where].m=(l+r)/2;
  if(ans==0){h[where].ans.a=where-mx;h[where].ans.b=ans;}
  if(ans==mx){h[where].ans.b=where-mx;h[where].ans.a=ans;}
  if(where>=mx)return 0;
  build(where*2,l,h[where].m,h,ans);
  build(where*2+1,h[where].m+1,r,h,ans);
  return 0;}

aut find1(int where,int l,int r,node*h)
  {if(h[where].r==r&&h[where].l==l)return h[where].ans;
  if(r<=h[where].m)return find1(where*2,l,r,h);
  if(l>h[where].m)return find1(where*2+1,l,r,h);
  return MAX( find1(where*2,l,h[where].m,h), find1(where*2+1,h[where].m+1,r,h));}

aut find2(int where,int l,int r,node*h)
  {if(h[where].r==r&&h[where].l==l)return h[where].ans;
  if(r<=h[where].m)return find2(where*2,l,r,h);
  if(l>h[where].m)return find2(where*2+1,l,r,h);
  return MIN( find2(where*2,l,h[where].m,h), find2(where*2+1,h[where].m+1,r,h));}

int update1(int where,aut n,node*h)
  {if(where>=mx)
    {h[where].ans=n;
    return 0;}
  if(n.a<=h[where].m)update1(where*2,n,h);
  else update1(where*2+1,n,h);
  h[where].ans=MAX(h[where*2].ans,h[where*2+1].ans);
  return 0;}

int update2(int where,aut n,node*h)
  {if(where>=mx)
    {h[where].ans=n;
    return 0;}
  if(n.b<=h[where].m)update2(where*2,n,h);
  else update2(where*2+1,n,h);
  h[where].ans=MIN(h[where*2].ans,h[where*2+1].ans);
  return 0;}

int cmp(const void*a,const void*b)
  {if(((aut*)a)->a==((aut*)b)->a)return ((aut*)a)->b-((aut*)b)->b;
  return ((aut*)a)->a-((aut*)b)->a;}
int cmp2(const void*a,const void*b)
  {if(((aut*)a)->b==((aut*)b)->b)return ((aut*)a)->a-((aut*)b)->a;
  return ((aut*)a)->b-((aut*)b)->b;}
int cmp3(const void*a,const void*b)
  {return *((int*)a)-*((int*)b);}

int t[mx];
int v[mx];
int aa[mx],ab[mx],ac;

int q[mx],qin,qou;

aut e1,e2,e3;
int q1,q2,q3,c1,c2,c3,c4;
int c;
aut ss[mx];

int clear()
  {
  memset(ss,0,sizeof(ss));
  memset(h1,0,sizeof(h1));
  memset(h2,0,sizeof(h2));
  memset(v,0,sizeof(v));
  memset(t,0,sizeof(t));
  memset(aa,0,sizeof(aa));
  memset(ab,0,sizeof(ab));
  memset(q,0,sizeof(q));
  q1=q2=q3=c1=c2=c3=ac=qin=qou=0;
  e1.a=e1.b=e1.n=0;
  e2=e3=e1;

  return 0;}

aut s1[mx];
int n;
int doit(int a)
  {int q1;
  clear();
  c=a+1;
  for(q1=0;q1<c;q1++){ss[q1]=s1[q1];ss[q1].n=0;}
  return 0;}
int find(aut e2)
  {aut e1;
  int c1,a,b;
  a=e2.a;b=e2.b;
  if(a>b){c1=a;a=b;b=c1;}
  e1.a=a;
  e1.b=b;
  c1=(int)bsearch(&e1,ss,c,sizeof(ss[0]),cmp)-(int)ss;
  c1/=sizeof(aut);
  return c1;}
int ll,rr,mm,oops;
int main()
  {

  freopen("cpu.in","r",stdin);
  freopen("cpu.out","w",stdout);

  fn=in;
  fscanf(fn,"%d %d",&c1,&n);
  for(q1=0;q1<n;q1++)fscanf(fn,"%d %d",&ss[q1].a,&ss[q1].b);
  for(q1=0;q1<n;q1++)
    if(ss[q1].a>ss[q1].b)
	  {c1=ss[q1].a;ss[q1].a=ss[q1].b,ss[q1].b=c1;}
  for(q1=0;q1<n;q1++){ss[q1].n=q1;s1[q1]=ss[q1];}
  fclose(fn);
  ll=1;
  rr=n;
  while(ll!=rr)
  {mm=(ll+rr)/2;
  oops=0;
  doit(mm);

  qsort(ss,c,sizeof(ss[0]),cmp);

  for(q1=0;q1<c;q1++){ss[q1].a*=1000;ss[q1].b*=1000;}

  for(q1=0;q1<c;q1++)
    {
    for(q2=q1;q2<c&&ss[q2].a==ss[q1].a;q2++);
    c2=q2;
    for(q2=q1;q2<c2;q2++)ss[q2].a+=c2-q2-1;
    }

  qsort(ss,c,sizeof(ss[0]),cmp2);

  for(q1=0;q1<c;q1++)
    {
    for(q2=q1;q2<c&&ss[q2].b==ss[q1].b;q2++);
    c2=q2;
    for(q2=q1;q2<c2;q2++)ss[q2].b-=q2-q1;
    }
  qsort(ss,c,sizeof(ss[0]),cmp);
  for(q1=0;q1<c;q1++){aa[ac++]=ss[q1].a;aa[ac++]=ss[q1].b;}
  qsort(aa,ac,sizeof(aa[0]),cmp3);


  for(q1=0;q1<c;q1++)
    {c1=(int)bsearch(&ss[q1].a,aa,ac,sizeof(aa[0]),cmp3)-(int)aa;
    c1/=sizeof(int);
    ss[q1].a=c1+1;
    c1=(int)bsearch(&ss[q1].b,aa,ac,sizeof(aa[0]),cmp3)-(int)aa;
    c1/=sizeof(int);
    ss[q1].b=c1+1;}

  build(1,0,mx-1,h1,0);
  build(1,0,mx-1,h2,mx);

  for(q1=0;q1<c;q1++)
    {update1(1,ss[q1],h1);
    update2(1,ss[q1],h2);}

  for(q1=0;q1<c;q1++)if(t[q1]==0)
  {
  e2.a=ss[q1].a;e2.b=0;update1(1,e2,h1);
  e2.b=ss[q1].b;e2.a=mx;update2(1,e2,h2);


  qin=qou=0;
  t[q1]=1;
  q[qin++]=q1;

  while(qin!=qou)
    {c1=q[qou++];
    c4=-mx;
    while(ss[c1].a+1!=ss[c1].b)
      {e1=find1(1,ss[c1].a+1,ss[c1].b-1,h1);
      if(e1.b==0||e1.b<=ss[c1].b)break;
      if(c4>e1.a){oops=1;goto end;}
      c4=e1.a;
      c2=find(e1);
      t[c2]=3-t[c1];

      e2.a=ss[c2].a;e2.b=0;update1(1,e2,h1);
      e2.b=ss[c2].b;e2.a=mx;update2(1,e2,h2);

      q[qin++]=c2;}
    c4=mx*2;
    while(ss[c1].a+1!=ss[c1].b)
      {e1=find2(1,ss[c1].a+1,ss[c1].b-1,h2);
      if(e1.a==mx||e1.a>=ss[c1].a)break;
      if(c4<e1.b){oops=1;goto end;}
      c4=e1.b;
      c2=find(e1);
      t[c2]=3-t[c1];

      e2.a=ss[c2].a;e2.b=0;update1(1,e2,h1);
      e2.b=ss[c2].b;e2.a=mx;update2(1,e2,h2);

      q[qin++]=c2;}
    }
  }
  end:
  if(oops==0)ll=mm+1;
  else rr=mm;
  }

  printf("%d\n",ll);


  for(q1=0;q1<c;q1++)
    v[ss[q1].n]=t[q1];

  return 0;}


Автор: Светослав Колев


обратно към брой 27