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;
}