Discussion @ 1583. Cheese @ Timus Online Judge

Vedernikoff Sergey Why so few ACs and so low percent of ACs??? [14] // Problem 1583. Cheese 27 Oct 2007 20:33

Very easy problem, not harder than Pineapple... Why so few people solved it???

svr Re: Why so few ACs and so low percent of ACs??? [12] // Problem 1583. Cheese 27 Oct 2007 21:34

Binary search can apply not more 120 people!

Vedernikoff Sergey Re: Why so few ACs and so low percent of ACs??? [11] // Problem 1583. Cheese 28 Oct 2007 02:59

What does it mean - not more than 120 people??? Pineapple was solved by about 300 authors!

svr Re: Why so few ACs and so low percent of ACs??? [10] // Problem 1583. Cheese 28 Oct 2007 08:01

This is my prognoze (bookmaker).
To solve this problem we must know two things:
1) 3d geometry and volumes;
2) binary search after 1 is implemented.
So we divide 300 by 2 and have ~120-150.
P.S. The problem has also very difficult component:
3) precision question
and this is why so many people can't it solve and I am too.
AC!!!!
What does phrase W equals exactly 500 mean?
|W-500|<eps and eps=10^-16?
answer: if (W(x1)<=500)and (W(x2)>=500)) and
|x1-x2|<0.5*0.000001 then ans:=round((x1+x2)/2).
P.S.2: Tricky moments:
1)next cut must be measured
from previous rounded integer value;
2) |x1-x2|<0.00000001 ! 0.0000001 is too small

Edited by author 28.10.2007 11:25

Lomir Re: Why so few ACs and so low percent of ACs??? [8] // Problem 1583. Cheese 28 Oct 2007 14:04

Binnary search must be applied in integers.
Also there is one trick in the statement:
"...at which a cut should be made so that the weight of the NEXT piece be exactly 500 grams."
So we must add not just 500gramms each time, but the mass of cutted part (some more or less then 500) add 500 and search.

This was a reason of my WAs.

Vedernikoff Sergey Re: Why so few ACs and so low percent of ACs??? [7] // Problem 1583. Cheese 28 Oct 2007 15:38

I've done binsearch with reals and easily got AC. What concerns 500-gramm pieces - of course, we should measure mass from previous REAL cut, but not virtual and exactly-calculated - it is quite clear from the statement and ordinal logic...

Edited by author 28.10.2007 15:38

svr Re: Why so few ACs and so low percent of ACs??? [6] // Problem 1583. Cheese 28 Oct 2007 21:35

Logic for integer rounded previous bound!
This is realy made bound and exists but REAL cut is
virtual!

maksay Re: Why so few ACs and so low percent of ACs??? [5] // Problem 1583. Cheese 30 Oct 2007 16:13

Question
It is said that the machine which cuttes uses micrometer scale. So it can cut piece only in places with coordinates which are integer micrometers value. But after that it is said that a coordiante of current cut is ROUNDED to micrometers. What does that mean? The places where we can cut have integer micrometers value coordinats or the answers are integer micrometers value but we can cut at any position?

Vedernikoff Sergey Re: Why so few ACs and so low percent of ACs??? [4] // Problem 1583. Cheese 30 Oct 2007 17:37

Yes, places where we can cut have integer coordinates. So, mass may not equal to 500 grams, and you should choose such integer place for a cut to make it as close to 500 grams as possible.

maksay Re: Why so few ACs and so low percent of ACs??? [3] // Problem 1583. Cheese 31 Oct 2007 14:21

thanks a lot

Alias (Alexander Prudaev) Re: Why so few ACs and so low percent of ACs??? [2] // Problem 1583. Cheese 31 Oct 2007 21:44

Sergey, you are wrong if you understand statematn at first time as autors it is not mean that statement is absolutely
right and is not ambigious

Vedernikoff Sergey Re: Why so few ACs and so low percent of ACs??? [1] // Problem 1583. Cheese 31 Oct 2007 22:13

But I've read russian version of the problem and didn't find any ambiguity in it! It is almost equal to the english version of the statement. Where is ambiguity?

svr Re: Why so few ACs and so low percent of ACs??? // Problem 1583. Cheese 31 Oct 2007 22:20

Ambiguity is absent but absent also care about
solvers, many mathematical and computing unimportant troubles precence.

Python Re: Why so few ACs and so low percent of ACs??? // Problem 1583. Cheese 2 Jul 2019 15:05

Thanks for your advice!

svr Re: Why so few ACs and so low percent of ACs??? // Problem 1583. Cheese 7 Nov 2007 11:15

Next very easy but strangely seldom solved-1566: post office envelops.
I solved it during 1 hour as problem 2 level of second
division of TopCoders. Only two different
geometric situations, float considaration without
integer arithmetic and only 27 AC.

Innokentiy WHY WA8 [1] // Problem 1583. Cheese 8 Jul 2016 15:50

Lomir Some test [1] // Problem 1583. Cheese 27 Oct 2007 23:54

Victor Barinov (TNU) If you have WA2 [2] // Problem 1583. Cheese 17 Jan 2008 04:33

liuctic I tried several methods, real b-search and interger b-search, but still WA2 // Problem 1583. Cheese 6 Dec 2007 12:26

Tipikin Evgeniy (USU) WA2 [2] // Problem 1583. Cheese 30 Oct 2007 22:31

Arthur could anyone give some test data? [2] // Problem 1583. Cheese 28 Oct 2007 12:28

Discussion of Problem 1583. Cheese