Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

By alphadr, 6 years ago, ,

The problem is categorized as Nim in LightOJ. I solved the remaining 4 problems in the same category with no major difficulties (here), however I am stuck on this one.

Could someone please hint to the solution ? Is it only "basic" Nim, or is there something else I need to learn ?

Thanks.

• 0

By alphadr, 7 years ago, ,

Could you please tell me some problems which could be solved using matrix exponentiation on codeforces or other judges ?

Thanks.

• +3

By alphadr, 7 years ago, ,

http://codeforces.com/problemset/problem/7/D

Can someone please explain to me the problem ? I don't understand how the result was 6 for the second input case.

• +1

By alphadr, 7 years ago, ,

http://www.codeforces.com/gym/100155/problem/B

Does anyone have a clue how approach/solve the problem ?

• 0

By alphadr, 8 years ago, ,

This was the first time I implement ternary search, I figured out what it is, and how it matches to 215D - Hot Days, however, I keep getting Wrong answer on test 15 which seems to be common for a some of the other contestants as well (http://www.codeforces.com/contest/215/status)

Could someone help me please to figure out the bug in my solution ?

#define ll long long
ll n,m;
ll z,ti,Ti,xi,costi;
ll f(ll y) { // cost if got y buses
ll slc=m-((y-1ll)*z);
ll e=slc>z?(slc*xi):0ll;
return (y*costi)+e;
}
ll r(ll a,ll b) { // ternary search
assert(b>=a);
if((b-a)==0) return f(a);
if((b-a)==1) return min(f(a),f(b));
ll x=a+(b-a)/3;
ll y=b-(b-a)/3;
assert(x<y);
if(f(x)>=f(y)) return r(x+1,b);
return r(a,y-1);
}
int main() {
//    freopen("me.txt","r",stdin);
cin>>n>>m;
ll res=0;
for(int i=0;i<n;++i) {
cin>>ti>>Ti>>xi>>costi;
if(Ti>ti) {
z=Ti-ti; //maximum capacity per bus, except last bus
ll g=round(ceil((double)m/z)); // maximum number of buses
res+=r(1ll,g);
} else {
res+=(costi+(m*xi));
}
}
cout<<res<<endl;
return 0;
}


Thanks a lot :)

Edit: I managed to get AC when I brute forced the entire interval when b-a < 1000 (got WA on case 29 when tried b-a < 100):

if(b-a < 1000) {
ll res=f(a);
for(int i=a+1;i<=b;++i) res=min(res,f(i));
return res;
}


• 0

By alphadr, 8 years ago, ,

I thought 215B - Olympic Medal was an easy problem, I got the relation fairly easily, but then it gave me WA at test 10.

My first submission was:

double r2=sqrt( ((double)((r1*r1)*(b)*(p1)))/(a*p2+b*p1));

Where r1 and p1 are the maximum possible and p2 is the minimum possible, based on that relation, where its directly proportional with r1 and p2 and inversly proportiona with p2.

So I thought I may need long double, re-submitted with long double, WA again.

Then I thought the std sqrt function was not accurate enough, coded my own sqrt function.

Long story short, I made 11 WAs all trying to figure out whats wrong, until in the end I used the inverse of the relation, and voila AC from the first time !

long double r2=(1.0/(r1*r1))*(((a*p2)/(b*p1))+1); r2=pow(r2,-0.5);

But it was totally useless..the 11 WAs made my rank be 877, the lowest I ever got (so far :/)

I just hate those double precision problems...

Edit: Thanks to AlexDmitriev, I knew what was the mistake. 5000^4 > INT_MAX, I should have kept the numerator as double to avoid the overflow. I totally admit it was my mistake for overlooking the constraints. Hopefully it would be another trick which no one would fall into again :)