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