### jlcastrillon's blog

By jlcastrillon, 8 years ago,

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;
//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

• +9

By jlcastrillon, 8 years ago,

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.

• +3

By jlcastrillon, 8 years ago,

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

• -18

By jlcastrillon, 8 years ago,

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...

• +17

By jlcastrillon, 8 years ago,

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

• +24

By jlcastrillon, 8 years ago,

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);
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;


}

• -4

By jlcastrillon, 8 years ago,

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

• +3

By jlcastrillon, 9 years ago,

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.

• +12

By jlcastrillon, 9 years ago,

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....

• +6

By jlcastrillon, 9 years ago,

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