Tutorials: Beginner Special 2.0

Problem Exam Time
Problem Setter under_cover123

Logic

DIFFICULTY:

EASY

PREREQUISITES:

Maths

PROBLEM:

Given N papers we have to select/get passed in more than half number of papers.
Given N is always ODD.

QUICK EXPLANATION:

Question is asking to select atleast (N/2)+1 papers.

EXPLANATION:

For any given N (ODD integer) possible outcomes for correct answer
passed in all n papers- nCn
passed in all n-1 papers- nCn-1

passed in all n/2+1 papers- nCn/2+1
So, final answer is - (2^n)/2;

Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll modInverse(ll a, ll m) { return power(a, m-2, m); }
ll power(ll a,ll b,ll m){ if(b==0) return 1; if(b==1) return a%m; ll t=power(a,b/2,m)%m; t=(t*t)%m; if(b&1) t=((t%m)*(a%m))%m; return t;}
#define endl "\n"
int main(){
	int t;
	cin>>t;
	while(t--){
		ll n;
		cin>>n;
		ll an=power(2,n,mod);
		an=(an*modInverse(2,mod))%mod;
		cout<<an<<endl;
	}
}


Problem Easy Dissy
Problem Setter under_cover123

Logic

DIFFICULTY:

EASY

PREREQUISITES:

Maths

PROBLEM:

Given an array of size N. we have to collect chocolates at some index.
we can transfer chocolates from an index i to j such that j is divisible by i.
We have to find the maximum number of chocolate any index can posses modulo 1000000007

QUICK EXPLANATION:

Go from N to 1.

EXPLANATION:

Go from N to 1. At any index j check the sum ‘S’ of all array[i] such that j%i==0 or j is divible by i in sqrt(j) time. Answer is the maximum of all S.

Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define endl "\n"
int main(){
	ll i,j,k,l,n;
	cin>>n;
	ll ar[n+1];
	for(i=1;i<=n;i++){
		cin>>ar[i];
	}
	
	ll an=0;
	for(i=n;i>=1;i--){
		k=0;
		for(j=1;j*j<=i;j++){
			if(i%j==0){
				k=(k+ar[j])%mod;
				if(i/j!=j)	k=(k+ar[i/j])%mod;
			}
		}
		an=max(an,k);
	}
	cout<<an<<endl;
}

Problem Maximizing Sum
Problem Setter under_cover123

Logic

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Dynamic Programming

PROBLEM:

Given an array with N integer. We have to find maximum Subarray sum we can obtain from the given array. We have special power of changing the sign(+ve to -ve OR -ve to +ve) of atmost k element of the array.

QUICK EXPLANATION:

Use 3-D DP.

EXPLANATION:

Use 3-D DP with states - (current_index,k_left,flag)
flag denotes whether the subarray is started or not.

Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define N 100005
#define endl "\n"
ll n,ar[N],dp[N][101][2];
ll maxval(ll i,ll k_lft,ll flg){
	if(i==n+1){
		if(flg==0) return -1e10;
		else return 0;
	}
	
	if(dp[i][k_lft][flg]!=-1e10){
		return dp[i][k_lft][flg];
	}
	if(flg==0){
		ll a,b,c=-1e10;
		a=maxval(i+1,k_lft,flg);
		b=maxval(i+1,k_lft,1)+ar[i];
		if(k_lft>0) c=maxval(i+1,k_lft-1,1)-ar[i];
		return dp[i][k_lft][flg]=max(a,max(b,c));
	}
	else{
		ll a,b=-1e10,c=0;
		a=maxval(i+1,k_lft,1)+ar[i];
		if(k_lft>0) b=maxval(i+1,k_lft-1,1)-ar[i];
		return dp[i][k_lft][flg]=max(a,max(b,c));
	}
}
int main(){
	#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	ll i,j,k,l,v;
	cin>>n>>v;
	for(i=1;i<=n;i++){
		cin>>ar[i];
	}
	for(i=0;i<=n;i++){
		for(j=0;j<=100;j++){
			dp[i][j][0]=-1e10;
			dp[i][j][1]=-1e10;
		}
	}
	ll an=maxval(1,v,0);
	cout<<an;
	return 0;
}

Problem Uchiha Clan
Problem Setter under_cover123

Logic

DIFFICULTY:

MEDIUM

PREREQUISITES:

Segment Trees and Binary Search

PROBLEM:

Given an array of size N. we have to find two integers k and l. such that 1<=k<l<=N and Maximum element of subarray from a[1] to a[k]=Maximum element from a[l] to a[n]=Minimum element from a[k+1] to a[l-1].

QUICK EXPLANATION:

Try to find k fixing the value of l at some index in array.

EXPLANATION:

We can fix l and do binary search for k.

Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define N 100005
#define endl "\n"
ll st[4*N],ar[N];
void build(ll node,ll nl,ll nr){
	if(nl==nr){
		st[node]=ar[nl];
		return ;
	}
	build(2*node,nl,(nl+nr)/2);
	build(2*node+1,(nl+nr)/2+1,nr);
	st[node]=min(st[2*node],st[2*node+1]);
}
ll query(ll node,ll nl,ll nr,ll ql,ll qr){
	if(nl>qr||ql>nr){
		return 1e18;
	}
	if(nl>=ql&&qr>=nr){
		return st[node];
	}
	ll a,b;
	a=query(2*node,nl,(nl+nr)/2,ql,qr);
	b=query(2*node+1,(nl+nr)/2+1,nr,ql,qr);
	return min(a,b);
}
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int t;
	t=1;
	while(t--){
		ll i,j,k,l,n;
		cin>>n;
		ll pre[n+2],suf[n+2];
		for(i=1;i<=n;i++){
			cin>>ar[i];
		}
		build(1,1,n);
		pre[0]=0; suf[n+1]=0;
		for(i=1;i<=n;i++) pre[i]=max(pre[i-1],ar[i]);
		for(i=n;i>=1;i--) suf[i]=max(suf[i+1],ar[i]);
		
		ll x=-1,y=-1;
		for(i=3;i<=n;i++){
			ll a=1,b=i-1,an=-1,mid,ans;	
			while(a<=b){
				mid=(a+b)/2;
				if(pre[mid]==suf[i]){
					an=mid;
					b=mid-1;
				}
				else if(pre[mid]<suf[i]){
					a=mid+1;
				}
				else b=mid-1;
			}
			if(an!=-1&&i-an>1){
				a=an+1; b=i-1; ans=-1;
				while(b>=a){
					mid=(a+b)/2;
					ll tmp=query(1,1,n,mid,i-1);
					if(tmp==suf[i]){
						if(pre[mid-1]==tmp){
							ans=mid; break;
						}
						else{
							if(pre[mid-1]>tmp) b=mid-1;
							else a=mid+1;
						}
					}
					else if(tmp<suf[i]){
						a=mid+1;
					}
					else b=mid-1;
				}
				if(ans!=-1){
					x=ans-1; y=i;
					break;
				}
			}
		}
		if(x!=-1){
			cout<<x<<" "<<y<<endl;
		}
		else cout<<"-1"<<endl;
	}
	return 0;
}

Problem Chocolates Production
Problem Setter vasu2907

Logic

DIFFICULTY:

MEDIUM

PREREQUISITES:

Array, FenwickTree

PROBLEM:

Chef has a microwave has the capacity to produce A chocolates per day but its productivity has been reduced to the production of B chocolates per day since microwave is defective. The productivity of the microwave can be restored to its full production, after K days of maintenance and construction.
Chef receives orders in the form of Di, Ai, meaning Ai new orders have been placed for the Di-th day. Each order requires single chocolate to be produced on precisely the specified day. The chef may choose to fill as many, or as few of the orders in a single day.
Since the order comes in, Chef wants to know the maximum number of orders he will be able to fill, if he starts repairing the microwave on Pith day.

QUICK EXPLANATION:

We can use two binary-indexed trees to maintain the prefix and suffix sums of the amounts we can produce with maximum production rates of B and A, respectively. Then we can just query the binary-indexed trees to find the maximum possible production given the start and end of the repairs.

EXPLANATION

We will use two binary-indexed trees. The first tree will store the number of orders we can fulfill if the production rate is a, while the second tree will store the number of orders that can be fulfiiled when the production rate is b.
So now, if we want to start repairing our microwave at day x, then the orders can be calculated by adding the following:
1> Orders fulfilled upto day x-1 with production b.
2> Orders fulfilled from day x+k to n with production a. This can be calculated by subtracting the orders fulfilled upto day x+k-1 with productivity a from orders fulfilled upto day n with productivity a.

Editorialist's Solution
#include <iostream>
using namespace std;
int n, k, a, b, q, act, x, y;
int ta[200005], tb[200005], dp[200005];
int getasum(int x) {
    int sum = 0;
    while (x) {
        sum += ta[x];
        x -= x&-x;
    }
    return sum;
}
int getbsum(int x) {
    int sum = 0;
    while (x) {
        sum += tb[x];
        x -= x&-x;
    }
    return sum;
}
void updatea(int x, int y) {
    while (x<=n) {
        ta[x] += y;
        x += x&-x;
    }
}
void updateb(int x, int y) {
    while (x<=n) {
        tb[x] += y;
        x += x&-x;
    }
} 
int main() {
    cin >> n >> k >> a >> b >> q;
    while (q--) {
        cin >> act;
        if (act == 1) {
            cin >> x >> y;
            updatea(x, min(y+dp[x], a)-min(dp[x], a));
            updateb(x, min(y+dp[x], b)-min(dp[x], b));
            dp[x] += y;
        } else {
            cin >> x;
            int ans=getbsum(x-1)+getasum(n)-getasum(x+k-1);
            cout << ans << endl;
        }
    }
} 

Problem Chocolates Distribution
Problem Setter vasu2907

Logic

DIFFICULTY:

EASY-MEDIUM, Stack

PREREQUISITES:

Array, FenwickTree

PROBLEM:

There are N tables in the hotel, and every table has ordered a certain number of cookies. Chef delivers 1 cookie each to every table in the range L to R, during 1 shift, where L and R can be any possible integers from 1 to N (L≤R) and can be different in different shifts.
You have to calculate the minimum number of shifts S required to serve the required amount of cookies on every table, and the range Li and Ri for each i-th shift.

QUICK EXPLANATION:

If the minimum on the entire array is equal to zero, then the problem naturally splits into subtasks, otherwise, the entire segment must be reduced by 1.

EXPLANATION

The main idea is greed.

Approach 1:
We look for the minimum in the array, subtract 1 from the entire array min times, the problem is split into several (i.e., at each moment of time, the problem = a segment of the original array). The minimum on the segment must be found quickly, in O (logN) using a segment tree.

Approach 2:
Let’s go from left to right and store, as we have already begun segments sticking out to the left, let it X. If the X < a i , then you need to start several new segments, if the X > a i , the few that have been initiated to finish in position i - 1 . Started segments can be stored in a stack. Of course, you only need to store the start position. The new X will be equal to a i .

Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef string str;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef stringstream strs;

#define X first
#define Y second
#define PB push_back
#define smax(a,b) a=max(a,b)
#define smin(a,b) a=min(a,b)
#define SZ(a) ((ll)a.size())
#define E(a) cout << #a << ' ' << a << '\n'
const ll M=5e5+5,LG=17,inf=1e18;
ll n;
int main()
{
    cin >> n;
    ll cnt=0;
    strs res;
    stack<ll> st;
    for(ll i=0;i<n;i++)
    {
        ll x;
        cin >> x;
        while (SZ(st)<x)
            st.push(i);
        while (SZ(st)>x)
        {   res << st.top()+1 << ' ' << i << '\n';
            st.pop();
            cnt++;
        }
    }
    while (SZ(st)>0)
    {   res << st.top()+1 << ' ' << n << '\n';
        st.pop();
        cnt++;
    }
    cout << cnt << endl << res.str();
} 

Problem Weird Animal
Problem Setter vasu2907

Logic

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

DSU

PROBLEM:

Given an array of size N. We have to find a value K such that the all consecutive nonempty segments whose values are less than K must be of equal length.

QUICK EXPLANATION:

Disjoint Set Union can be used to maintain different segments.

EXPLANATION

Firstly, sort the array in order from smaller to larger. Disjoint set union(DSU) datastructure can easily maintain information about the current number of segments.
We can also the map within the function of union, and information about the current size of segments (locations) too.
Now we can update the answer when it’s needed.

Editorialist's Solution
#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pp;
int sum[maxn],cntsum[maxn],n,a[maxn],ans,par[maxn],cnt;
pp b[maxn];
int find(int x) 
{	if(x==par[x]) return x;
    return par[x]=find(par[x]);
}
void unite(int x,int y)
{	x=find(x),y=find(y);
    cntsum[sum[x]]--,cntsum[sum[y]]--;
    sum[x]+=sum[y];	par[y]=x;
    cntsum[sum[x]]++;
    cnt--;
}
int main() 
{	cin>>n;
    for(ll i=1;i<=n;++i) 
    {	cin>>a[i];
        b[i].first=a[i];
        b[i].second=i;
        par[i]=i;
    }
    sort(b+1,b+n+1);
    ll mx=0,ans=0;
    for(ll i=1;i<=n;++i) 
    {	ll x=b[i].second;
        ll y=b[i].first;
        sum[x]=1;
        cntsum[1]++;
        cnt++;
        if(x!=n&&a[x+1]<a[x])unite(x,x+1);
        if(x!=1&&a[x-1]<a[x])unite(x-1,x);
        if(cnt==cntsum[sum[find(x)]])
        {	if(cnt>mx)
            {	mx=cnt;
                ans=y+1;
            }
        }
    }
    cout<<ans<<endl;
}

Problem Chocolate Seeds
Problem Setter vasu2907

Logic

DIFFICULTY:

MEDIUM

PREREQUISITES:

BinarySearch

PROBLEM:

The height of the i-th plant is equal to a_i at the moment. At each of the remaining M days, the chef can take a special watering and water W contiguous plants(he can do that only once a day), and the watered plant grows by one unit on that day. Chef wants to increase the height of the smallest plant to be as large as possible in the end.
Help the chef to find the maximum height of the smallest chocolate plant in the end.

QUICK EXPLANATION:

We can use binary search to find the height of the smallest chocolate plant, by checking that a minimum height k is possible to be attained in m days.

EXPLANATION

we can check in O(n) if some height is achievable. We go from left to right. For the current plant, we calculate how many times it needs to be watered to stand not lower than the checking value. If the current plant needs to be watered for h times, we will star h segments in the current plant. We would keep array, in which st[i] — number of segments, which starts in i-th plant. Also, we will keep variable, in which we will keep the number of segments, which cover the current plant. This variable could be updated at O(1). In order to a get new value, we need to subtract st[i - w].

Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll a[N], bit[N];
ll n,m,w;
void update(int i, int k)
{	while(i<N)
    {	bit[i]+=k;
        i+=(i&(-i));
    }
}
long long prefsum(int i)
{	ll ans=0;
    while(i>0)
    {	ans+=bit[i];
        i-=(i&(-i));
    }
    return ans;
}
bool check(ll k)
{	ll count=0,curval,diff;
    for(int i=1;i<=n;i++)
    {	curval=a[i] + prefsum(i);
        diff=max(0LL, k-curval);
        update(i, diff);
        update(i+w, -1*diff);
        count+=diff;
        if(count>m)	return 0;
    }
    return 1;
}
long long binsearch(ll low, ll high)
{	while(low<high)
    {	memset(bit, 0, sizeof(bit));
        ll mid=(low+high+1)>>1;
        if(check(mid))	low=mid;
        else			high=mid-1;
    }
    return low;
}
int main()
{	cin>>n>>m>>w;
    for(int i=1;i<=n;i++)	cin>>a[i];
    ll ans=binsearch(1, 1e15);
    cout<<ans<<endl;
}
2 Likes

can you explain the maximizing subarray a little bit more ,this is really hard to understand the code
or you can provide some material that will be helpful

2 Likes

In the DP recurrence, at any index i we have 2 cases

  1. We have started the subarray (flag=1)

           * In this case we have 3 options
           1. To end the subarray and return 0.
           2. To continue the subarray without using the special power
           3. To continue the subarray using the special power if k_left>0
    
  2. We have not started the subarray yet. (flag=0)

           * In this case we have 3 options
           1. Start the subarray without using the special power
           2. Start the subarray using the special power if k_left>0
           3. Just go to next element without taking current element
    

In both cases we have to return maximum of all options.

1 Like

Problems in the contest(question in order of the editorials):
Q1. Your answer is wrong for even N.
Q2. It does not make sense in maximizing sum\%mod
Q3. The constraints say K \geq 1. However, you have made cases where K = 0.
Q4. Copied from codeforces Div. 3 : Problem - F - Codeforces
Q5. Again problem in constraints, it is mentioned 1 \leq d \leq n, but you have made cases where d > n and d < 1.
Q7. You should have given more test cases here. What happens if the animal moves to a new location on the last day?

7 Likes

In the problem weird animal please explain the test case:

8
1 2 3 4 5 6 7 8

The answer that your code is giving is 2.

1 Like

CODECHEF+UNRATED+SCORE_BASED+BEGINNER_LEVEL is a disaster 80% of the times.

5 Likes

Chocolate Seeds : Solution: 41768704 | CodeChef

this solution have almost 15 lines of code and it seems very neat
but i am not getting this can any body explain this please

thanks
can you explain the last question Chocolate Seeds

I submitted 100 times during the contest and was getting wrong answer…now I came to know its because of k=0 and in ques the constraints are k>=1 :expressionless:

The solution is wrong, consider the test case:

8 8 1
3 3 3 3 3 3 3 3 

Correct Output should be 4.

Also Problem 2 problems, Uchiha Clan and Chocolate Distribution can have multiple answers.

I think he must have taken care of that.