Editorial for COCI '09 Contest 3 #6 Planete


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

With X \mid Y we denote that X divides Y, i.e. there exists k such that kX = Y.

Let us denote with X_1, X_2, \dots, X_m duration of events in days. Note that saying:

  • "Between dates A and B there were \alpha_1 events 1, \alpha_2 events 2, etc."

is the same as saying:

  • "365 \mid (\alpha_1 X_1 + \alpha_2 X_2 + \dots + \alpha_m X_m-(B-A))".

where B-A is the difference in days between dates A and B. Further, we can split that into:

  • "5 \mid (\alpha_1 X_1 + \alpha_2 X_2 + \dots + \alpha_m X_m+A-B)"
  • "73 \mid (\alpha_1 X_1 + \alpha_2 X_2 + \dots + \alpha_m X_m+A-B)"

(note that 365 = 5 \times 73). Since 5 and 73 are prime numbers, using Gaussian elimination, we can find all possible remainders of X's when divided by 5 and 73 (separately). Using the Chinese remainder theorem, we can further determine the remainder of each X when divided by 365.


Comments

There are no comments at the moment.