jlcastrillon's blog

By jlcastrillon, 11 years ago, In English

Some problems ask to find how many numbers from A to B have a certain property, if the problem of finding how many numbers of k (0-9) digits have that property can be solved using a function F(k,property) in O(H) and when you update the left of a number the property can be updated in O(S) then there is a solution for the problem in O(H * S * log10^2(n)).

Let M(x) the amount of numbers less than x that have that property. Then M(B + 1) — M(A) is the solution to our problem, or M(B) — M(A) + h where (h = 1 if B have the property, else h = 0) To find M(x) we need to make a few observations. A number x less than y iff the length of x is less than the length of y or if they have equal length and there is a digit x[i] < y[i] and for all digits j < i this holds x[j] = y[j], that is ,they are equal from left to right until a digit i where x[i] < y[i], when this happens then all digits y[j] j > i can be in the range(0-9) and then F(k,property) can be used. We can use this to find all the numbers less than x having the desired property.

sol  = 0
remain = lengthof(x)
// we find the digit where they first differ x[i] < y[i] and for all digits j < i x[j] = y[j]
for each digit x[i] of x from left to right{
    remain--;
    // now we find all the digits that can be at y[i] and are less than x[i]
    for each digit d from 0 to x[i] - 1{
        property' = (property if digit d replaced digit x[i]) 
        sol += F(remain,property')
    }
    update property after deletion of digit x[i]
}

Here I have a sample C++ code to solve the following problem How many integers in the interval [A, B] are there such that the sum of their digits is S

#define ll long long
bool mem[N][N];
ll D[N][N];
// this is the function F(k,property)
ll F(int dig,int sum){
	if(dig == 0)
		return (ll)(sum  == 0);
	if(mem[dig][sum])
		return D[dig][sum];
	mem[dig][sum] = 1;
	ll ret = 0LL;
	for(int i = 0;i<=9;i++)
		ret += F(dig - 1,sum - i);
	D[dig][sum] = ret;
	return ret;
}

// this is M(x)
ll solve(ll x){
	ll ret = 0;
	sprintf(cad,"%lld",x);
	int len = strlen(cad);
        //sum is the desired property
	int sum = s;
	int qued = len;
        // we find the digit where they first differ x[i] < y[i] and for all digits j < i x[j] = y[j]
	for(int i = 0;i < len;i++){
		qued--;
		int d = cad[i] - '0';
                // now we find all the digits that can be at y[i] and are less than x[i]
		for(int j = 0;j <d;j++){
                        //sum - j = property'
			if(sum - j >= 0){
				ret += F(qued,sum - j);
			}
		}
                //update property after deletion of digit x[i]
		sum -= d;
	}
	return ret;
}

//this is the solution to the problem sol = solve(b + 1) - solve(a);

Some problems to solve

and many other you can find anywhere

Full text and comments »

  • Vote: I like it
  • +9
  • Vote: I do not like it

By jlcastrillon, 11 years ago, In English

Hi I have been trying to solve this problem http://www.spoj.com/problems/KL11B/ The solution I have found so far uses BIT + Treap(Balanced Tree) and worst case complexity is log^2(n) for each query. Some users have accepted the problem using a lot less time and memory than other users that I know they used this solution. Is there a faster solution to this problem or it was just constant optimization?, would there be a faster to code solution to this problem having at most log^2(n) complexity for each query.

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it

By jlcastrillon, 12 years ago, In English

Could any one tell me how the formula for the contribution points works?

Full text and comments »

  • Vote: I like it
  • -18
  • Vote: I do not like it

By jlcastrillon, 12 years ago, In English

Here is the problem Given a set of N points and some query points, What is the farthest point from the set to each of the query points. Here are a couple of questions: Is it the same time complexity when finding the nearest neighbor? Where can I find some theory about this?

If there is a better way (with the same or less time complexity) to solve this problem using a suitable amount of code please let me know...

Full text and comments »

  • Vote: I like it
  • +17
  • Vote: I do not like it

By jlcastrillon, 12 years ago, In English

Given n circles n <= 1000, how can I find the area of union of all this circles?

Full text and comments »

  • Vote: I like it
  • +24
  • Vote: I do not like it

By jlcastrillon, 12 years ago, In English

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=524&page=show_problem&problem=4023

root :: Regionals 2011 :: Africa/Middle East — Arab Contest problem Fence.....

I have been trying to solve this problem, but I am getting WA , my solution first finds the the length of the cable that covers the edge of any circle. That is I first find for each circle the union of angles according to the tangents, then this angles equals 2pi — ang. And then I find the circles that have at least one incident tangent with an interval not covered by any other circle and I add up this length. here is my solution implemented in c++. I would like to know When my code is failing...thanks in advance..

struct event{ long double ang; int o; event(long double aa,int oo){ ang = aa;o = oo; } bool operator <(const event e) const{ return ang < e.ang; } }; vector E; long double nor(long double ang){ if(ang < 0) return ang + 2.0 * pi; if(ang > 2.0 * pi) return ang — 2.0 * pi; return ang; } void addevent(long double beg,long double end){ if(beg < end){ E.push_back(event(beg — eps / 2.0,1)); E.push_back(event(end,-1)); }else{ E.push_back(event(beg — eps / 2.0,1)); E.push_back(event(2.0 * pi,-1));

    E.push_back(event(0.0 - eps / 2.0,1));
    E.push_back(event(end,-1));
}

}

long double deg(long double ang){ return ang * 180.0 / pi; } long double dist(int i,int j){ return hypot(X[i] — X[j], Y[i] — Y[j]); }

long double BEG[N]; long double END[N]; long double dists[N];

int main(){ scanf("%d",&t); while(t--){ scanf("%d",&n); for(int i = 0;i<n;i++) scanf("%llf%llf%llf",&X[i],&Y[i],&R[i]);

    if(n == 1){
       printf("%.5llf\n",2.0 * (long double)R[0] * pi);
       continue;
    }
    long double res = 0.0;
    long double rr = 0.0;


    for(int i = 0;i < n;i++){
       E.clear();
       for(int j =0 ;j<n;j++){
         if(i == j) continue;
         long double r1 = R[i];
         long double r2 = R[j];
         long double d = dist(i,j);
         long double ang = nor(atan2(Y[j] - Y[i],X[j] - X[i]));
         long double a,ta;
         if(r1 == r2){
          a = pi / 2.0;
          ta = d;
         }else if(r1 < r2){
          long double d1 = d  / (r2 / r1 - 1.0);
          a = pi - acos(r1 / d1);
          ta = sqrt((d + d1) * (d + d1) - r2 * r2) - sqrt(d1 * d1 - r1 * r1);
         }else{
          swap(r1,r2);
          long double d1 = d  / (r2 / r1 - 1.0);
          a = acos(r1 / d1);
          ta = sqrt((d + d1) * (d + d1) - r2 * r2) - sqrt(d1 * d1 - r1 * r1);
         }
         long double beg = nor(ang - a);
         long double end = nor(ang + a);
         addevent(beg,end);
         BEG[j] = beg;
         END[j] = end;
         dists[j] = ta;
       }
       sort(E.begin(),E.end());
       int si = E.size();
       long double tot = 0.0;

       long double in = 0.0;
       int cc = 0;
       vector<long double> inter;
       if(E[0].ang + 2.0 * pi - E[si - 1].ang > eps ){
         inter.push_back(E[0].ang);
         inter.push_back(E[si - 1].ang);
       }
       for(int j =0 ;j<si;j++){
         if(E[j].o == 1){
          cc++;
          if(cc == 1){
              if(j != 0)
                 inter.push_back(E[j].ang);
              in = E[j].ang;
          }
         }else{
          cc--;
          if(cc == 0){
              tot += E[j].ang - in;
              if(j != si - 1)
                 inter.push_back(E[j].ang);
          }
         }
       }


       if(fabs(tot - 2.0 * pi) < eps){
         continue;
       }else{
         int ss = inter.size();

         for(int k = 0;k<ss;k++){
          long double ma = 0;
          for(int j = 0;j<n;j++){
              if(i == j) continue;
              if(fabs(BEG[j] - inter[k] ) < eps || fabs(END[j] - inter[k] ) < eps)
                 ma = max(ma,dists[j]);
          }
          rr += ma;
         }
         tot = 2.0 * pi - tot;
         res += (R[i] * tot);
       }
    }
    printf("%.5llf\n",res + rr/2.0);
}
return 0;

}

Full text and comments »

  • Vote: I like it
  • -4
  • Vote: I do not like it

By jlcastrillon, 12 years ago, In English

here is the link http://coj.uci.cu/contest/comming.xhtml good luck for everyone...

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it

By jlcastrillon, 12 years ago, In English

http://coj.uci.cu/contest/contestview.xhtml?cid=1169

Caribbean Online Judge (COJ) coj.uci.cu invites you to participate in a progressive contest that will be held tomorrow. Take a look at the link for more information.

This is a very interesting kind of contest, it consists of some levels ordered by difficulty where you need to solve an amount of problems to make it to the next level.

I hope you enjoy it.

Full text and comments »

  • Vote: I like it
  • +12
  • Vote: I do not like it

By jlcastrillon, 12 years ago, In English

This problem looks like knapsack with repetition but limits are huge and I can't find a solution using DP, Could anyone tell me how to solve it, here is the link. http://poj.org/problem?id=3900

I have seen this kind of problems several times but I have never been able to solve them. Thanks in advance....

Full text and comments »

  • Vote: I like it
  • +6
  • Vote: I do not like it

By jlcastrillon, 12 years ago, In English

I have been trying to solve this problem but I don't seem to find a correct solution to it. http://acm.tju.edu.cn/toj/showp3260.html

Full text and comments »

Tags tju
  • Vote: I like it
  • +1
  • Vote: I do not like it