Форум DL

Мой профиль

По английски - Balanced Binary Trees

Этот метод также решает задачу
USACO 2007 January Gold: 3. Cow School

USACO JAN07 Problem 'schul' Analysis
by Bruce Merry / Richard Peng

Suppose that for a particular value of D, using the teacher's choices gives a ratio of M, and Bessie wants to improve this ratio. If she things of every test as being M plus or minus some number of marks (not percent), then she will want to drop the tests with the minimum number of marks over M, and keep those with the most marks over M. If it happens that the teacher's choice is different, then she can switch some of the tests to get more than 0 over M and thus improve her score.

A first attempt would be to verify this independently for each D. That is, for each D, determine the teacher-assigned mark, and look for the worst test kept in by the teacher and the best test dropped by the teacher ("better" meaning more marks above M). If substituting one for the other improves Bessie's score, then save this value of D. This gives an O(N^2) solution.

Quite a few contestants tried to insert heuristics into their code to improve runtime. Most of these relied on some assumption about the 'density' of the solution points and the locations where the min/max occurs. It was rather difficult to construct a data which fails both heuristics based on upper and lower bound, so two contestants still manged to get by with heuristic solutions.

There are several ways to go from here to get down to a O(nlogn) solution. First notice that the problem essentially reduces to finding the maximum/minimum values of the linear combination of a set of two variables. It suffices to consider the minimum case since the maximum case is a mirror equivalent. This can be thought as of either the x-intercepts of points on a plane or as the position where a certain line intersect a vertical line with a fixed x value. In both methods of visualization, it can be noticed that if a point is concave in relation to its two immediate neighbors, it can be deleted.

Both methods immediately leads to a O(nlogn) time solution using balanced binary trees. This can be explained in professor Brian Dean's animated notes found at:

http://www.cs.clemson.edu/~bcdean/cowschool.swf

This is also the only type of O(nlogn) solution implemented during the contest. Sorry to all the Pascal programmers as STL set gives C++ users a huge advantage should this solution be implemented. Nima Ahmadi Pour from Iran was the only person to implement one correctly (although Adrian Kuegel did come close). Nima's code is here:

#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <set>
#include <utility>
using namespace std;
double eps=1e-8;
FILE *fin=fopen("schul.in","r");
FILE *fout=fopen("schul.out","w");
struct test{
       int a,b;
       test(){}
       test(int t1,int t2):a(t1),b(t2){}
};
bool operator<(const test& t1,const test& t2){
       return t1.a*t2.b<t2.a*t1.b;
}
struct line{
       int a,b;
       line(){}
       line(int t1,int t2):a(t1),b(t2){}
};
bool operator<(const line& l1,const line& l2){
       return l1.b<l2.b;
}
set<line> s;
line last_line;
double last_x;
void reset(){
       s.clear();
}
double xinter(const line& l1,const line& l2){
       return double(l1.a-l2.a)/double(l2.b-l1.b);
}
double yinter(const line& l1,double x){
       return l1.b*x+l1.a;
}
double best(double x){
       double ans=-1e12;
       set<line>::iterator it=s.find(last_line);
       while (it!=s.end() && yinter(*it,x)>ans){
               ans=yinter(*it,x);
               ++it;
       }
       --it;
       last_x=x;
       last_line=*it;
       return ans;
}
void insert(const line& l){
       while (true){
               set<line>::iterator it1=s.lower_bound(l);
               if (it1==s.end())
                       break;
               set<line>::iterator it2=it1;++it2;
               if (it2==s.end())
                       break;
               if (it1->b==l.b){
                       if (it1->a<=l.a){
                               s.erase(it1);
                               continue;
                       }
                       return;
               }
               double x=xinter(*it1,*it2);
               if (yinter(l,x)<yinter(*it1,x)-eps)
                       break;
               s.erase(it1);
       }
       while (true){
               set<line>::iterator it1=s.upper_bound(l);
               if (it1==s.begin())
                       break;
               --it1;
               if (it1==s.begin())
                       break;
               set<line>::iterator it2=it1;--it2;
               if (it1->b==l.b){
                       if (it1->a<=l.a){
                               s.erase(it1);
                               continue;
                       }
                       return;
               }
               double x=xinter(*it1,*it2);
               if (yinter(l,x)<yinter(*it1,x)-eps)
                       break;
               s.erase(it1);
       }
       set<line>::iterator it1=s.lower_bound(l);
       if (it1!=s.end() && it1!=s.begin()){
               set<line>::iterator it2=it1;--it2;
               double x=xinter(*it1,*it2);
               if (yinter(l,x)<=yinter(*it1,x)+eps)
                       return;
       }
       s.insert(l);
       if (s.size()==1){
               last_line=l;
               last_x=-1e12;
       }
       else if (s.find(last_line)==s.end())
               last_line=l;
       else if (yinter(last_line,last_x)<yinter(l,last_x))
               last_line=l;
}
int n;
test t[50000];
double x[50000],min_one[50000],max_one[50000];
int main(){
       fscanf(fin,"%d",&n);
       for (int i=0;i<n;++i)
               fscanf(fin,"%d%d",&t[i].a,&t[i].b);
       sort(t,t+n);
       {
               int suma=0,sumb=0;
               for (int i=0;i<n;++i){
                       suma+=t[n-i-1].a;
                       sumb+=t[n-i-1].b;
                       x[n-i-1]=double(suma)/double(sumb);
               }
       }
       {
               reset();
               for (int i=1;i<n;++i){
                       insert(line(t[i-1].a,-t[i-1].b));
                       max_one[i]=best(x[i]);
               }
       }
       {
               reset();
               for (int i=n-1;i>=1;--i){
                       insert(line(-t[i].a,-t[i].b));
                       min_one[i]=-best(-x[i]);
               }
       }
       int cou=0;
       for (int i=1;i<n;++i)
               if (min_one[i]<max_one[i]-eps)
                       ++cou;
       fprintf(fout,"%d\n",cou);
       for (int i=1;i<n;++i)
               if (min_one[i]<max_one[i]-eps)
                       fprintf(fout,"%d\n",i);
       return 0;
}

Мой профиль

Здравствуйте! На страницах форума я видел, что существует EM-дерево, которое, по словам, писать проще, чем AVL и RB. Расскажите, пожалуйста, на чём оно основано.

Спасибо.

Мой профиль

EM-деревья - это наша разработка с Мишей Еськовым. Но есть лучшие деревья:
1. Декартовы. Смесь кучи, дерева и ТерВера.
2. AA-деревья. Упрощения B-дерева. Просто пишется.
3. SCAPEGOAT-деревья. Они несколько похожи на EM.

P.S. По последним двум деревьям искать инфу стоит на английском.

Мой профиль

В чём преимущества EM-деревьев в сравнении с остальными?

Мой профиль

Хм... Когда мы их писали дерево, то знали только AVL,RB и ну и еще пару. После написания мы изучали предыдущие работы по этой теме, и в итоге поняли, что:
1. Дерево новое.
2. Есть более хорошие деревья. Список можно увидеть в этой теме

Мой профиль

Спасибо.