Nov 2004
1 / 10
Nov 2004
Dec 2004
Adrian_Kosowski
Nov '04

Hi,

I would like to apologise to everyone for removing problem FEAST, and replacing it by another (all be it very similar smile ) problem - HOLIDAY. Problem FEAST will be reinserted in a later problemset. The constraint on the number of numbers will be decreased from 100 to about 20-30 (unless someone lets me know of a way to solve the task for 100 numbers).

To sum up: if you've spent some time trying to solve this problem - don't worry, it won't be wasted smile. If you don't know what the problem FEAST is about - don't worry, it will reappear for solving in a few months (and will probably be viewable much earlier).

Adrian_Kuegel
Nov '04

I think the explanation of the first sample output should say, that the shortest period is 3 days (not 2 days).

Adrian_Kosowski
Nov '04

Thanks.
Amusingly enough, the test data contains this test case and there has never been any error there wink.

Pascal_sof
Nov '04

There is probably an error in the conditions, I have a line

assert(1LLu <= t[i] && t[i] <= 1000000000000000000LLu);

in my code, and it fails ! So I assume there are some test cases where t_i > 10^18.

Adrian_Kuegel
Nov '04

I can confirm that.
I inserted
while(v<1);
assert(v<=1000000000000000000LL);
in my code, and got sigabrt (v is the t_i value).
I got even sigabrt with
assert(v<=9000000000000000000LL);
but with
assert(v<=9223372037000000000LL);
I got accepted.
So either the problem should say, that t_i fits into signed 64 bit integer, or it should remove the test cases > 10^18.

Adrian_Kosowski
Nov '04

Ouch, I added a few test cases manually and accidentally wrote a digit to many in one number that got copied to a few test cases. They have now been eliminated, rejudging is in progress. Thank you for your help and sorry.

Update: nothing interesting has changed in the status. Pascal is allowed 10 additional submissions for this problem in recompense for those lost on aborts smile.

system
Dec '04

Thanks for the correction... which doesn't help me understand why my code is not working anyway confused ..............

qbolec
Dec '04

Consider three holidays whith perdiods: 6,10,15.
Obviously gcd(6,10,15)=1.
Obviously the holidays are at:
0,6,10,12,15,18,20,24,30,...and so on with cycle lcm(6,10,15)=30
Obviously there are no two holidays in distance=gcd(6,10,15)=1.
..but some people seems to think different.

qbolec
Dec '04

I finally got accepted for the task HOLIDAY.
As I've suspected , to get the ACCEPTED I was forced to think in this manner:

given set of periods , the minimal distance is gcd of this set

this is obviously false. The proper thinking is:

given set of periods, the minimal distance is minimal gcd of some pair

I think that the problem should be rejudged or even better:
Make two different problems (becouse both are interesting!)
One: minimalize the gcd of whole set.
Second: minimalize the gcd of some pair.

Adrian_Kosowski
Dec '04

Thanks for pointing the problem out to us. The problem text was indeed badly malformed and didn't reflect my intentions. Apologies.

As a matter of fact, I decided to split the problem into 2 parts without knowing about your post smile. This increases the chance that this was the most appropriate way out of a rather awkward situation wink.