SUNDAY - Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Utkarsh Gupta
Tester: Abhinav Sharma, Manan Grover
Editorialist: Lavish Gupta

DIFFICULTY:

Simple

PREREQUISITES:

Loops

PROBLEM:

A particular month has 30 days, numbered from 1 to 30.

Day 1 is a Monday, and the usual 7-day week is followed (so day 2 is Tuesday, day 3 is Wednesday, and so on).

Every Saturday and Sunday is a holiday. There are N festival days, which are also holidays. Note that it is possible for a festival day to occur on a Saturday or Sunday.

You are given the dates of the festivals. Determine the total number of holidays in this month.

EXPLANATION:

We can have an array holiday of length 30, where holiday[i] is 1 if it is a holiday on i^{th} day, and 0 otherwise.

Because Day 1 is a Monday, we have Saturday on Day 6, 13, 20, 27. Similarly, we have Sunday on Day 7, 14, 21, 28.

We can also take the N holidays from the input, and mark the respective dates as 1 in the holiday. Finally, we need to count the total number of holidays using this array.

Note that a concise way to represent a Saturday is - i^{th} day is a Saturday if i\%7 = 6, where \% denotes the modulus sign.
Similarly, i^{th} day is a Sunday if i\%7 = 0

TIME COMPLEXITY:

O(N + 30) for each test case.

SOLUTION:

Editorialist's Solution 
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll ,ll>
using namespace std ;
const ll z = 998244353 ;


int main()
{
    int t ;
    cin >> t ;
    while(t--)
    {
        int n ;
        cin >> n ;
        vector<int> holiday(31) ;

        for(int i = 1 ; i <= 30 ; i++)
        {
            if(i%7 == 0 || i%7 == 6)
                holiday[i] = 1 ;
        }
        
        for(int i = 0 ; i < n ; i++)
        {
            int u ;
            cin >> u ;
            holiday[u] = 1 ;
        }

        int ans = 0 ;
        for(int i = 1 ; i <= 30 ; i++)
            ans += holiday[i] ;

        cout << ans << endl ;
    }

    return 0;
}
2

Much simpler O(N) solution

void solve() {
	int n, sum = 8, day;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> day;
		if ((day - 6) % 7 && (day - 7) % 7)
			sum++;
	}

	cout << sum;
}
3

Plzz will you check my code what’s wrong in this code…

#include <bits/stdc++.h>
using namespace std;

int main() {
int t,n, arr[8],count=8;
cin>>t;
int ar[]= {6,7,13,14,20,21,27,28};
while(t–)
{
cin>>n;
count=count+n;
for(int j=0;j<n;j++)
{
cin>>arr[j];
for(int k=0;k<8;k++)
{
if(arr[j]==ar[k])
{
count–;

        }
        }
    }
   
    cout<<count<<endl;
    count=8;
}
return 0;

}

4

why sum=8??

5

Hey, you have initialized the size of arr[] as 8, whereas n can be up to 30, leading to the code trying to access index out of bounds and thus causing a Runtime Error.

6

Because if we take a month having 30 days where day 1 is Monday, and we are assuming Saturdays and Sundays as holidays, we get a total of 8 days of holiday just because of them falling on weekends.
The dates of those 8 days of weekends are: 6,7,13,14,20,21,27,28