PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author: Jatin Nagpal
Tester: Radoslav Dimitrov
Editorialist: William Lin
DIFFICULTY:
Easy
PREREQUISITES:
Google Search, Dates, Prefix Sums
PROBLEM:
You are given several queries, each one gives you a range of months. The answer for each query is the number of months in the range such that the period of 10 days starting from the first Friday intersects with the second-last Sunday.
QUICK EXPLANATION:
Iterate through all months, starting from January of year 0, keeping track of the day of the week of the first day of each month. We can use a few loops to find the first Friday and the second-last Sunday and calculate the answer for each month accordingly. We can create the prefix sums of the answers for the months to answer range queries efficiently. Everything cycles in 400 years, so we only have to calculate the prefix sums for 400 years.
EXPLANATION:
The first thing we need to figure out is, given a particular month and a year, does an intersection happen in this month.
Does an intersection happen in a particular month
Let s be the day of the week of the first day in this month (we can use 0 for Sunday, 1 for Monday, and so on), and let d be the number of days in this month. I will explain how we can find s later. To find d, we can use the following rules (which can be Google-searched):
Rules for days in a month
- If the month is 1, 3, 5, 7, 8, 10, or 12, d=31
- Else, if the month is not 2, d=30
- Else, if it is not a leap year, d=28
- A year is a leap year if it is a multiple of 400, or if it is a multiple or 4 but not 100 (from the problem statement, also from Google Search)
- Else, d=29
Let’s index the days starting from 0. In order to find the day of the week of day i, we can use the formula (s+i)\mod 7.
Finding the first Friday is pretty simple: We start from d1=0 and increment d1 until (s+d1)\mod 7 = 5.
Finding the second-last Sunday isn’t too much harder: We start from the last day of the month, d2=d-1, and decrement d2 until (s+d2)\mod 7 = 0. That gives us the last Sunday, so we should subtract d2 by 7 to find the second-last Sunday.
Since a Long Challenge lasts for 10 days, the Long Challenge and Cook-Off intersect if d1+10>d2.
To pass the second subtask with y\le 10^6, we can simply iterate through all months within this range and calculate the prefix sums. The prefix sums will allow us to answer queries in constant time.
First, Google-search the day of the week of January 1, 0, and we find that it is a Saturday. So, the first month has s=6.
After processing the first month, we can find the day of the week of the first day in the next month by setting s to (s+d)\mod 7. After processing each month, we can add the number of days to s to find the day of the week of the start of the next month.
Sadly, this will not pass the last subtask with y\le 10^9.
Notice that the answer for a month only depends on several factors:
- The type of the month
- Whether the year is a leap year
- The day of the week of the first day in the month
The first 2 properties cycle every 400 years. What about the 3rd property? We can simply multiply by 7, the number of days in a week, to get a cycle of 2800.
This works, but if you Google-search the day of the week of January 1, 400, then you will find out that the starting day of the week also cycles every 400 years!
Using this observation, we will only calculate the prefix sums for 400 years. In order to answer range queries, we will use the standard trick of splitting the range [l, r] into 2 prefixes: prefix r minus prefix l-1. This will make calculations simpler later on.
To calculate the answer for a prefix of y years and m months, we can split it into \left\lfloor \frac{y}{400} \right\rfloor cycles of 400 years, and then there will be a remainder of y \mod 400 years and m months.
Then, the answer is \left\lfloor \frac{y}{400} \right\rfloor multiplied by the answer for a single cycle of 400 years, added to our precalculated prefix sum of the first y \mod 400 years and m months.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define f(i,x,n) for(int i=x;i<n;i++)
// 0 Sunday, 1 Monday... 6 Saturday
int day(int date, int month, int year)
{
int yc = (year%100 + ((year%100)/4) )%7;
int arr[] = {0,3,3,6,1,4,6,2,5,0,3,5};
int mc = arr[month-1];
int cc = 2* (3-((year/100)%4) );
int dn = date;
int lc = 0;
if(month<=2 && ( (year%4==0 && year%100!=0) || (year%400==0) ))
lc = 1;
return (7+yc+mc+cc+dn-lc)%7;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int t;
cin>>t;
while(t--)
{
int m1,y1,m2,y2,ans=0;
cin>>m1>>y1>>m2>>y2;
if(m1>2)
y1++;
if(m2<2)
y2--;
if(y2-y1<=400)
{
for(int i=y1;i<=y2;i++)
{
int dy = day(1,2,i);
if(dy == 6)
ans++;
else if(dy == 0 && (!( (i%4==0 && i%100!=0) || (i%400==0)) ) )
ans++;
}
cout<<ans<<'\n';
continue;
}
while(y1%400!=0)
{
int i=y1;
int dy = day(1,2,i);
if(dy == 6)
ans++;
else if(dy == 0 && (!( (i%4==0 && i%100!=0) || (i%400==0)) ) )
ans++;
y1++;
}
while(y2%400!=399)
{
int i=y2;
int dy = day(1,2,i);
if(dy == 6)
ans++;
else if(dy == 0 && (!( (i%4==0 && i%100!=0) || (i%400==0)) ) )
ans++;
y2--;
}
cout<<ans+((y2-y1+1)/400)*101<<'\n';
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
#define endl '\n'
#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back
using namespace std;
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
int m1, m2, year_1, year_2;
void read() {
cin >> m1 >> year_1 >> m2 >> year_2;
}
bool leap(int y) {
if(y % 400 == 0) return true;
if(y % 4 == 0 && y % 100 != 0) return true;
return false;
}
int64_t period[400][13], overall;
int64_t ans(int y, int m) {
return period[y % 400][m] + overall * (y / 400);
}
void solve() {
//m1--;
//if(m1 == 0) { m1 = 12; year_1--; }
m2++;
if(m2 == 13) {
m2 = 1;
year_2++;
}
cout << ans(year_2, m2) - ans(year_1, m1) << endl;
}
set<int> v31 = {1, 3, 5, 7, 8, 10, 12};
void prepare() {
int disp = 6;
for(int i = 0; i < 400; i++) {
for(int j = 1; j <= 12; j++) {
int days = 0;
if(v31.count(j)) days = 31;
else if(j == 2) days = leap(i) ? 29 : 28;
else days = 30;
int st = 0, st_cook = days - 1;
if((st + disp) % 7 <= 5) {
st += 5 - (st + disp) % 7;
} else {
st += 5 + (7 - (st + disp) % 7);
}
st_cook -= (st_cook + disp) % 7 + 7;
int ny = i, nm = j + 1;
if(nm == 13) nm = 1, ny++;
if(ny == 400) {
overall = period[i][j];
if(st + 10 > st_cook)
overall++;
} else {
period[ny][nm] = period[i][j];
if(st + 10 > st_cook)
period[ny][nm]++;
}
disp += days;
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
prepare();
int T;
cin >> T;
while(T--) {
read();
solve();
}
return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int c[4801];
ll solve(int m, int y) {
//y/400 is the number of 400 year cycles
//multiply that by c[4800] to find the answer for those cycles
ll r=(ll)c[4800]*(y/400);
//then, we have a prefix of y%400 years and m months left
r+=c[y%400*12+m-1];
return r;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
//the current day of the week, january 1 2000 is a saturday, which is 6
int s=6;
//loop through all years
for(int y=0; y<400; ++y) {
//loop through all months
for(int m=1; m<=12; ++m) {
//number of days in this month
int d;
if(m==1||m==3||m==5||m==7||m==8||m==10||m==12)
d=31;
if(m==4||m==6||m==9||m==11)
d=30;
if(m==2) {
//special case for february
d=!y||y%4==0&&y%100?29:28;
}
//find the first friday (d1) and the last sunday (d2)
int d1=0, d2=d-1;
while((s+d1)%7!=5)
++d1;
while((s+d2)%7)
--d2;
//cookoff is the second last sunday, so subtract 1 week
d2-=7;
//long challenge last for 10 days and ends at d1+10
//if that's greater than d2, there's an overlap
//add it to our prefix sum
c[y*12+m]=c[y*12+m-1]+(d1+10>d2);
//update the day of the week for the next month
s=(s+d)%7;
}
}
int t;
cin >> t;
while(t--) {
int m1, y1, m2, y2;
cin >> m1 >> y1 >> m2 >> y2;
//increment the second date by 1 month
++m2;
if(m2>12) {
m2=1;
++y2;
}
//split our range sum into 2 prefix sums
cout << solve(m2, y2)-solve(m1, y1) << "\n";
}
}
Please give me suggestions if anything is unclear so that I can improve. Thanks