×

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

 11 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. asked 05 Nov '17, 23:18 542●1●13 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! answered 06 Nov '17, 02:06 250●7 accept rate: 0% +1 to this (06 Nov '17, 02:07) 2 My words precisely!!. And YES, LAST YEARS SET WAS <33333333333333 (06 Nov '17, 02:10)
 7 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 :/ answered 06 Nov '17, 00:08 600●8 accept rate: 15%
 6 @admin Please look into the matter answered 05 Nov '17, 23:55 5★rishi_07 316●1●7 accept rate: 20%
 6 We were too getting WA with similar code. answered 06 Nov '17, 00:20 983●14 accept rate: 11% You should have used a higher precision (like cout <
 6 @admin pls look into the matter...hoping for a resolution or an explanation of what went wrong!!! answered 06 Nov '17, 00:22 81●2 accept rate: 0%
 5 @admin This is a serious issue. Please look into the matter. answered 06 Nov '17, 00:10 5★nky_007 61●2 accept rate: 0%
 4 Okay @vijju123 then what about this one. This gives WA too. Here I used setprecision(10) answered 05 Nov '17, 23:29 542●1●13 accept rate: 0% 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) 2 You should have used a higher precision (like cout <
 4 @admin I think, there is some issue with tester's solution. answered 06 Nov '17, 00:16 51●2 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) 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) 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) 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) I think 7 should give AC as well. Can anyone confirm? (06 Nov '17, 00:39) @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) 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) 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) 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) 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) Holy shit @swetankmodi (06 Nov '17, 00:56) showing 5 of 13 show all
 4 @admin please do something for this answered 06 Nov '17, 00:26 4★sonu_628 420●8 accept rate: 10%
 3 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 answered 06 Nov '17, 00:27 31●1 accept rate: 0% WA in python? Mind sharing your code if it's allowed to? (06 Nov '17, 00:38)
 3 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. answered 06 Nov '17, 14:07 51●1 accept rate: 0%
 2 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<
 1 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 :/. answered 05 Nov '17, 23:25 15.5k●1●20●66 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★
 1 Can anyone tell the motivation behind this formula? answered 06 Nov '17, 01:39 4★shadow10 11●2 accept rate: 0%
 1 @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!! answered 06 Nov '17, 11:01 201●5 accept rate: 0% 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)
 1 @ak_1andonly I do agree, just spent hours debugging code rather than solving problems. answered 06 Nov '17, 15:18 20●2 accept rate: 0%
 1 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 answered 07 Nov '17, 09:38 230●1●8 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) 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 post yours. (09 Nov '17, 11:09)
 0 they can at least give some partial credits to other solutions with the relative error of 0.0000001 answered 06 Nov '17, 03:23 11●1 accept rate: 0%
 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. answered 08 Nov '17, 20:45 5★kvsk 53●1●4 accept rate: 0%
 0 @swetankmodi please provide solution for compression algorithm. answered 24 Mar '18, 15:10 2★des1997 20●3 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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