LONGCOOK - Editorial

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 :slight_smile:

13 Likes

Hi, Would someone please review my solution for this ( LONGCOOK ) problem. I’ve got an AC, but I just wanted to know that was my approach and method correct or not.
Thanks!
Link : Link to solution

1 Like

Wait, why does the editorial not mention that intersections can only happen in February? Or did I miss something?

8 Likes

After a google search, I came to know that there are only 14 different types of calenders ( 7 for each day of week * 2 for is the year leap or not ). By manually going through those, I came to know that intersections are only possible in february.

1 Like

I used a hash table, …easy to read code. :slightly_smiling_face: CodeChef: Practical coding for everyone

1 Like

This is my solution for this problem
https://www.codechef.com/viewsolution/29599627
Please help me to find out…why i am getting Runtime Error(NZEC) and how can i fix it…
Thanks in advance!

I want to add one more point to it…
Intersection will occur for any of the following point…

  • The first day of February is Saturday, irrespective of the fact whether the year is leap year or not.

  • The first day of February is Sunday but the year should not be leap year.

6 Likes

https://www.codechef.com/viewsolution/29705655
I got TLE please help

@tmwilliamlin following are my observations for this problem, but it is giving WA. Will you please correct me why this approach is wrong :

  1. Jan 1 will be Monday for every 28 years of cycle.
  2. If year==leap and Feb1==Saturday then overlapping
    else if Feb1==Saturday or Feb1==Sunday then overlapping
3 Likes

I used the same logic but getting wrong ans

I solved this problem with similar approach.
I got partial point for it , you can see my solution. link is already above-mentioned.
For the proof of this logic.
You can see the table.
Link is https://drive.google.com/file/d/1RNLDUIsocFInSuPXJk-8q_7GRdxR2AFH/view?usp=sharing

1 Like

Years like 1900 2100 2200 are not leap years, so the 28-year cycle is broken at each of these years. This makes the coding more tricky, as you need to divide the range into separate centuries.

4 Likes

I didn’t realize that this was true, but it’s not necessary to solve the problem with this observation.

2 Likes

My Approach.

Hint: Level 1 Observe that each month long challenge starts on First Friday so First Friday must have to come on either of the dates 1 2 3 4 5 6 7 so lets pick first 5 days then max time till long challenge will run is on 15 th of february and remaining days if considered not a leap year are 13 and obviously there will be two sundays in those thirteen days and

also one point of obervation is that if a month is of more than 29 days then there will be no overlap thus we are safe for every month except february now what if friday comes on 6th of february so challenge wiill last upto 16th and so there will be 12 days left if normal year and 13 days if its leap year so when it is a leap year no issue is there when friday is on 6th so issue comes when Friday is there on 6th and year is non leap year also another case of issue is that when friday comes in any of the years february on 6th of february so our main task reduces to finding those yrs in which friday comes on 7th of feb and those non leap years on which friday comes on 6th of feb.

now what was my trick to reduce the overall complexity of the solution from O(y2-y1) to O (400) per query was that at first I found a general pattern of these years that in which years these overlapping situations is coming and also my soul point of observation is that in every 400 years these situations comes 101 times and also repeatedly modulo 4 you can observe yourself by running brute force and getting when there is overlap you can brute force upto 2000 years and observe these array of 101 years what I found was like this I am printing it here for you. {3 , 9 ,14 , 15 ,20 , 25 , 26 ,31 , 37 ,42 , 43 ,48 , 53 , 54 ,59 , 65 ,70 , 71 ,76 , 81 , 82 ,87 , 93 ,98 , 99 ,105 ,110 , 111 ,116 , 121 , 122 ,127 , 133 ,138 , 139 ,144 , 149 , 150 ,155 , 161 ,166 , 167 ,172 , 177 , 178 ,183 , 189 ,194 , 195 ,200 , 201 ,206 , 207 ,212 , 217 , 218 ,223 , 229 ,234 , 235 ,240 , 245 , 246 ,251 , 257 ,262 , 263 ,268 , 273 , 274 ,279 , 285 ,290 , 291 ,296 , 302 , 303 ,308 , 313 , 314 ,319 , 325 ,330 , 331 ,336 , 341 , 342 ,347 , 353 ,358 , 359 ,364 , 369 , 370 ,375 , 381 ,386 , 387 ,392 , 397 , 398}

observe 2003 2009 2014 2015 2020 and 2025 all values are repeated every 400 years and thus our task becomes very simple that if the difference in y2 and y1 is lesser than 400 then we can just simply traverse and enumerate ourselves and if also the differnece is larger we know that we have 101 years per every 400 perfect such years in that way I optimised my approach for all cases and it runs max O(400) per test case thus overall time complexity reduces to 0.4 seconds and thus it is solvable.

1 Like

if i am not wrong you come up this observation by assuming every 4th year is a leap year. right? and it is wrong because 96th year is leap year but 100 is not. so here we can’t say Jan 1 will be Monday for every 28 years of cycle.

1 Like

I think that is obvious by a little skimming of calendar

if it is not leap year it can only happen in feb given that first day of feb is either sat or sun.
if it is leap it can only happen in feb given that first day is sat.
not other month can have intersection of contests.

Yes, I agree to your point. I assumed every 4th year as a leap year.

1 Like

give me test cases in which my submission is failed.
my submission

Well, I was too lazy to do even a little skimming.

1 Like