Someone Please explain the difference between these two solutions for Compression Algorithm

@rishi_07 , I checked it, and i know that 10 and 18 are giving errors. Before anything else, I want to know about 7.

Also, when they ask at long contest etc that an error of upto ${10}^{-6}$ is ok, they mean relative error unless stated other wise.

Well, I am not sure on WHY setter used absolute error when entire world knows that these issues arise from it, but idk, I mean…yeah idk why any1 would do that. I am sympathetical to the issue as well, but I dont think anything can be done about it.

It should give, but it didn’t. I’ve had a few cases as well where c++ failed and python got it accepted. One example is problem CHEFYODA from february or march 2017 long challenge. I don’t remember the other one’s. If you want I can search other problems?

No, i tried 7 too. (I tried 7 and 18.) One of my friends tried 6 but he has a different formula so idk if that’s right or wrong!

I usually use set precision 8 so I didnt face MUCH issues. Well, the point is right said by @swetankmodi , it should give AC but didnt. There are some problems where this happens- its not the first one- and not the last one either. But it should change if you ask me.

Yeah, I very well remember CHEFYODA because I wasted 5 days on that only to realize that my solution is correct :expressionless:

4 Likes

Holy shit @swetankmodi

@d_skyhawk In your case your formula to calculate it is wrong review it

1 Like

Both the formula are exact same. Left one got WA. Right one AC.

I am talking about @d_skyhawk 's solution when he posted a screenshot where he used setprecision(10).

Dude both the formula are same. Just simplify one you will get the other. The first one was formulated by him and second one by me. We are teammates.

What I meant was in his questions both formulas are correct but when he posted another screenshot in the comments(look at his comment) , where he used ‘n’ instead on ‘n-1’!!otherwise in his original screenshot both are correct I guess its just about absolute error and sometimes it happens when they calculate absolute instead of relative error!!

2+((n-1)(k-1)2)/k
=2
(1+(n-1)(k-1)/k)
=2
(k+(n-1)(k-1))/k
=2
(k+nk-n-k+1)/k
=2
(n*(k-1)+1)/k
Please analyse before you comment

2 Likes

@swetankmodi check my above simplification. The two formulas (the original question one and the commented one) are interchangeable.

@rishi_07 thanks for this derivation. Even I told my teammate that this was wrong. Holy shit XD

@horizon121 please be review @rishi_07 's comment. I hope @admin takes a look at this.

Yes yes, actually my teammate was convinced that he had made a mistake in simplifyying the recurrence, so I commented without verifying it the second time. My bad. Thanks for this derivation!

Sorry about the formula I didn’t see that . Now when I looked closely you used setprecision(10) it does not guarantee that your answer will have 6 decimal places you need to use ‘std::fixed’ before setprecision if you want precision upto 10 decimal places.

FYI: I used fixed, still no good. Someone please explain us the error :confused:

Can anyone tell the motivation behind this formula?

1 Like

I understand the pain in this, but given ~600 teams solved the Q, I don’t think any action will be taken at all.

It comes down to prior experience with double type answers and precision. I remember in one CF contest when a solution by Sumeet.Varma failed with 0.00001 error, which was totally because of him using Java. (same code in C++ passed)

Having said that, I don’t think it was nice of them to give a Q with such brutal “absolute error” rather than “relative error”. In many ways, I liked last years problem set better :confused: But whats done is done!

12 Likes