You are not logged in. Please login at www.codechef.com to post your questions!

×

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

These are my two solutions for the question Compression Algorithm.

I cannot understand the difference between the 2 solutions. Note: THe expected precision was 10^-6. alt text

asked 05 Nov '17, 23:18

d_skyhawk's gravatar image

4★d_skyhawk
542113
accept rate: 0%


12

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 :/ But whats done is done!

link

answered 06 Nov '17, 02:06

pandusonu's gravatar image

5★pandusonu
2507
accept rate: 0%

+1 to this

(06 Nov '17, 02:07) swetankmodi ♦♦6★
2

My words precisely!!. And YES, LAST YEARS SET WAS <33333333333333

(06 Nov '17, 02:10) vijju123 ♦♦5★

Same here mate, my c++ code gave me a WA and the same code in python gave me AC. I kind of experienced this before so I quickly used python without wasting time. I still don't know why c++ does this to us :/

link

answered 06 Nov '17, 00:08

swetankmodi's gravatar image

6★swetankmodi ♦♦
6008
accept rate: 15%

@admin Please look into the matter

link

answered 05 Nov '17, 23:55

rishi_07's gravatar image

5★rishi_07
31617
accept rate: 20%

We were too getting WA with similar code.

link

answered 06 Nov '17, 00:20

dushsingh1995's gravatar image

4★dushsingh1995
98314
accept rate: 11%

You should have used a higher precision (like cout <<fixed<<setprecision(30)<<endl; or use fixed point notation by using cout<<fixed<<setprecision(7)<<ans<<endl;

(06 Nov '17, 10:39) admin ♦♦0★

@admin - We even tried setprecision(15), still WA. It's really disheartning to see similar solution getting AC when there is only difference of setprecision. :(

(06 Nov '17, 11:25) dushsingh19954★

Use fixed. And also change 1 to 1.0 everywhere

(08 Nov '17, 01:19) soham12346★

@admin pls look into the matter...hoping for a resolution or an explanation of what went wrong!!!

link

answered 06 Nov '17, 00:22

kmalhotra30's gravatar image

4★kmalhotra30
812
accept rate: 0%

@admin This is a serious issue. Please look into the matter.

link

answered 06 Nov '17, 00:10

nky_007's gravatar image

5★nky_007
612
accept rate: 0%

Okay @vijju123 then what about this one. This gives WA too.

Here I used setprecision(10)

alt text

link

answered 05 Nov '17, 23:29

d_skyhawk's gravatar image

4★d_skyhawk
542113
accept rate: 0%

edited 05 Nov '17, 23:32

I am not completely sure when we go this deep into decimals dear, I am sorry for that :(. But the reason you got WA is realted to absoute value being used, being rutheless (${10}^{-6}$ doesnt make sense to me since correct algo gives very near answers). I also feel that relative error should ahd been considered.

(05 Nov '17, 23:35) vijju123 ♦♦5★
2

You should have used a higher precision (like cout <<fixed<<setprecision(30)<<endl; or use fixed point notation by using cout<<fixed<<setprecision(7)<<ans<<endl;

(06 Nov '17, 10:40) admin ♦♦0★

@admin I think, there is some issue with tester's solution.

link

answered 06 Nov '17, 00:16

vikas_nitd's gravatar image

4★vikas_nitd
512
accept rate: 0%

No, there's either an issue with the judge (a bug) or it's a feature (they're checking absolute error and not relative error)

(06 Nov '17, 00:19) swetankmodi ♦♦6★

They intentionally checked absolute error, and trust me things get dicey when you aim for this high precision. Usually people tolerate an absolute error of 0.01, or relative error of ${10}^{-6}$, which make sense to me. Absolute error of ${10}^{-6}$ was really, well, rutheless.

(06 Nov '17, 00:22) vijju123 ♦♦5★
1

Yeah i said it might be a bug or even a feature. I've experienced this 5-6 times so I knew they wanted me to use python xD or play with c++ mechanics to get the correct result (exact)

(06 Nov '17, 00:26) swetankmodi ♦♦6★
2

@swetankmodi but we used setprecision(10) still WA.

(06 Nov '17, 00:27) rishi_075★

@rishi_07 I used setprecision 18 Still WA.

(06 Nov '17, 00:38) swetankmodi ♦♦6★

I think 7 should give AC as well. Can anyone confirm?

(06 Nov '17, 00:39) vijju123 ♦♦5★

@vijju123 Kindly check the photo posted by d_skyhawk in comment section. There upto 10 precision was used. Leave all of that aside, this is not the first time we are solving this type of precision related questions. 0.6lf works everywhere where 10^-6 precision is needed. I don't understand why it failed here.

(06 Nov '17, 00:44) rishi_075★

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

(06 Nov '17, 00:47) vijju123 ♦♦5★

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?

(06 Nov '17, 00:47) swetankmodi ♦♦6★

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!

(06 Nov '17, 00:50) swetankmodi ♦♦6★

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.

(06 Nov '17, 00:52) vijju123 ♦♦5★
4

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

(06 Nov '17, 00:55) swetankmodi ♦♦6★

Holy shit @swetankmodi

(06 Nov '17, 00:56) vijju123 ♦♦5★
showing 5 of 13 show all

@admin please do something for this

link

answered 06 Nov '17, 00:26

sonu_628's gravatar image

4★sonu_628
4208
accept rate: 10%

Even I used round off function in python and got wrong answer even for precision upto 7 places because it was rounding off. This must be looked into @admin

link

answered 06 Nov '17, 00:27

fireballpup's gravatar image

2★fireballpup
311
accept rate: 0%

WA in python? Mind sharing your code if it's allowed to?

(06 Nov '17, 00:38) swetankmodi ♦♦6★

This years questions were not testing the skills but the knowledge of the language a person use, getting a WA just because of precision difference is unjust. Ranklist would have been a total stranger to the current Ranklist.

link

answered 06 Nov '17, 14:07

ak_1andonly's gravatar image

4★ak_1andonly
511
accept rate: 0%

Ya this icpc tested our skills in programming language and math and not algorithms how does make sure the right teams are selected to regionals ,this needs to improve in forthcoming years and getting wa for not typing cout<<fixed;was annoying and losing a place in regionals because of that is even more annoying to say the truth this contest might have discouraged many debues in icpc even icpcsc @admin

link

answered 06 Nov '17, 21:18

lokesh2002's gravatar image

4★lokesh2002
1199
accept rate: 5%

edited 06 Nov '17, 22:15

In one previous comment stating about 600solved the pblms ok where they ordered based on who found the algorithm first to say truth it's no I even had a personal experience where our team got the algorithm first but my friends team got the code right before and the time difference was more than 3/4 hrs,and the even annoying part was interanal error which even reduced our confidence level .

(06 Nov '17, 22:26) lokesh20024★

Simple. In case answer is like-

1.00000589999, then %6lf prints 1.000006 while %8lf prints 1.00000590000. Seems ok right? But what if expected answer was something like, 1.0000048, and you are getting "000055" ? Its rounded upto "0.000060" Meaning its a case where ${10}^{-7}th$ digit made a difference. Usually, they shouldnt ask THIS close precision, and if asking then their should be checking based on $relative$ error [like happens on CF] instead of absolute. People cant control language's mechanics :/.

link

answered 05 Nov '17, 23:25

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

2

I agree with you that using relative error could have been a better decision. It made situation harsh with some participants. During testing, we used either fixed precision and didn't think such issues can arise.

(06 Nov '17, 10:46) admin ♦♦0★

@admin but our code gives correct answer for the testcase you provided in the other post. (Submission ID: 16117083). Please recheck the issue.

(06 Nov '17, 11:22) rishi_075★

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

link

answered 06 Nov '17, 01:08

horizon121's gravatar image

4★horizon121
112
accept rate: 0%

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

(06 Nov '17, 01:10) rishi_075★

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

(06 Nov '17, 01:12) horizon1214★

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.

(06 Nov '17, 01:14) rishi_075★

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

(06 Nov '17, 01:20) horizon1214★
2

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

(06 Nov '17, 01:27) rishi_075★

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

(06 Nov '17, 01:31) rishi_075★

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

(06 Nov '17, 01:33) swetankmodi ♦♦6★

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

(06 Nov '17, 01:33) d_skyhawk4★

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!

(06 Nov '17, 01:34) swetankmodi ♦♦6★

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.

(06 Nov '17, 01:36) horizon1214★

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

(06 Nov '17, 01:37) swetankmodi ♦♦6★
showing 5 of 11 show all

Can anyone tell the motivation behind this formula?

link

answered 06 Nov '17, 01:39

shadow10's gravatar image

4★shadow10
112
accept rate: 0%

@d_skyhawk It might be because you are using "ios_base::sync_with_stdio(false)". It disables the synchronization between the C and C++ standard streams. By default all the standard streams are syncronized, and after that you have used cin as well as printf, that might be the error in this case. Bdw Im not sure about this. This might be the case!!

link

answered 06 Nov '17, 11:01

bhola_nit's gravatar image

5★bhola_nit
2015
accept rate: 0%

edited 06 Nov '17, 21:41

I thing using ios_base disables the auto-sync after every IO operation. So if you use printf, only then it will explicitly sync with c and c++ stream and not after every cin/cout. (I may be wrong though)

(06 Nov '17, 14:45) swetankmodi ♦♦6★

@ak_1andonly I do agree, just spent hours debugging code rather than solving problems.

link

answered 06 Nov '17, 15:18

light_of_orion's gravatar image

1★light_of_orion
202
accept rate: 0%

edited 06 Nov '17, 15:37

Can someone please explain me how you derived that formula? Even after spending so much of time I couldn't figure it out? @d_skyhawk @vijju123 @swetankmodi @rishi_07

link

answered 07 Nov '17, 09:38

yadnesh_viper's gravatar image

3★yadnesh_viper
23018
accept rate: 0%

Its a bit of difficult derivation. The inspiration is, -

Total possible strings are ${K}^{N}$. Now, think of strings with block of 1,2,3.... and so on.

You will get a formula which is is nothing but differential of $x*{(1+(k-1)x)}^{N}$ . The first half isnt known to me, my teammate derived that - I resumed from this differential part and completed the formula for him :3

(07 Nov '17, 11:56) vijju123 ♦♦5★

I derived a recurrence and solved it using generating functions. It's like 2 pages long, you want me to post or someone with an easier solution would be willing to help?

(08 Nov '17, 00:38) swetankmodi ♦♦6★

@swetankmodi post yours.

(09 Nov '17, 11:09) yadnesh_viper3★

they can at least give some partial credits to other solutions with the relative error of 0.0000001

link

answered 06 Nov '17, 03:23

rohitx007's gravatar image

3★rohitx007
111
accept rate: 0%

Our code gives the correct output for the above mentioned test case and even with all other test cases. Our submission with id, 16113398, gives WA during the contest. @admin, Please look into this issue. PS: While calculating the absolute error of our answer, consider the full answer with more than six places after the decimal as the expected answer and not the truncated one.

link

answered 08 Nov '17, 20:45

kvsk's gravatar image

5★kvsk
5314
accept rate: 0%

@swetankmodi please provide solution for compression algorithm.

link

answered 24 Mar '18, 15:10

des1997's gravatar image

2★des1997
203
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,112

question asked: 05 Nov '17, 23:18

question was seen: 3,724 times

last updated: 24 Mar '18, 15:10