Editorial: Beginners Special 1.0

Contest Link: BGS1


Problem Victory Number
Problem Setter hardik0899

Logic

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Math

PROBLEM:

Given an integer N, we have to find Sum of prime numbers from 1 to N.

QUICK EXPLANATION:

Find all the prime numbers till the given range i.e. 1e6 using sieve and use prefix sum to answer each testcase.

EXPLANATION:

Firstly, find all the prime numbers using seive.After finding the prime numbers use prefix sum to store sum of primes from 1 to any integer N.

Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define N 100005
#define endl "\n"
bool prime[1000001]; ll ar[1000001];
void SIE()
{
    for(ll i=1;i<=1000000;i++){
    	prime[i]=true;
	}
	
    for (ll j=2; j*j<=1000000; j++)
    {
        if (prime[j] == true)
        {
            for (ll i=j*2; i<=1000000; i += j)
                prime[i] = false;
        }
    }
}
int main(){
	SIE();
	ll i,j,n,t;
	for(i=2;i<=1e6;i++){
		if(prime[i]) ar[i]=ar[i-1]+i;
		else ar[i]=ar[i-1];
	}
	cin>>t;
	while(t--){
		cin>>n;
		cout<<ar[n]<<endl;
	}
	return 0;
}

Problem Unique Substrings
Problem Setter victory_vivek

Logic

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Math

PROBLEM:

Given a N strings and another string B. Find the unique substrings of B present in the set of N strings.

QUICK EXPLANATION:

Find the substrings of B and search them in the set of strings which is made from given N strings.

EXPLANATION:

Initially we make the set of N strings given. It is because searching complexity in set in.

Now generate the substrings of the string B and store them in the map. If the substring is previously present in the map then don’t search it in the set otherwise search the substring in the set of N strings and add it inside the map. If the substring is found in the set then increment the answer.

Editorialist's Solution
#include<bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
int main(){
	ll i,j;
	ll n,m;
	cin>>n;
	set<string> st;
	string s,b;
	for(i=0;i<n;i++){
		cin>>s;
		st.insert(s);
	}
	cin>>m;
	cin>>b;
	map<string,int>mp;
	ll cnt=0;
	for(i=0;i<b.size();i++){
		string val="";
		for(j=i;j<b.size();j++){
			val+=b[j];
			if(mp.find(val)==mp.end()){
				mp[val]=1;
				if(st.find(val)!=st.end()){
					cnt++;		
				}
			}
		}
	}
	cout<<cnt<<endl;
	return 0;
}

Problem Maximum Sum
Problem Setter under_cover123

Logic

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

DP, Maths

PROBLEM:

Given an array of length N, We have to find maximum sum which we can obtain starting from any index i, in atmax ‘k’ steps. With a conditions i.e. from index i we can go to either i+1 or i+2 only.

QUICK EXPLANATION:

USE Dp (dynamic programming) and iterate over all index.

EXPLANATION:

There will be 2 states in the DP
states - (current index, current value of K)
In each state we have 2 choices i.e.
1) from index i go to i+1 if i+1<=n
2) from index i go to i+2 if i+2<=n

handle the base cases such as -
if current value of k == 0 or current index > n:
//then no more elements can be taken, hence return 0

Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define endl "\n"
ll n,k; ll ar[1005]; ll dp[1005][1005];
ll maxval(ll i,ll cur_k){
	if(cur_k==0||i>n) return 0;

	if(dp[i][cur_k]!=-1){
		return dp[i][cur_k];
	}

	ll a=0,b=0;
	if(i+1<=n) a=maxval(i+1,cur_k-1)+ar[i+1];
	if(i+2<=n) b=maxval(i+2,cur_k-1)+ar[i+2];
	return dp[i][cur_k]=max(0ll,max(a,b));
}
int main(){
	ll i,j,l;
	cin>>n>>k;
	for(i=1;i<=n;i++){
		cin>>ar[i];
	}
	memset(dp,-1,sizeof(dp));
	ll an=0;
	for(i=1;i<=n;i++){
		an=max(an,maxval(i,k-1)+ar[i]);
	}
	cout<<an;
	return 0;	
}

Problem Hard problem
Problem Setter ken_

Logic

DIFFICULTY:

Medium

PREREQUISITES:

Trees, LCA & MATH

PROBLEM:

Given tree perform two queries, first to add node to an existing node of tree with given value of edge, second find value of edges on shortest path between two nodes.

QUICK EXPLANATION:

Just maintain LCA of tree created using binary lifting, crux of this question is finding LCA, and using that you will be able to find value.

EXPLANATION:

In a tree between two node their is only one path and it is the shortest path.
Let their be two node A, B, with LCA(A, B) as it’s lowest common ancestor.
So Value of shortest path is sum_of_value(A, LCA(A,B))) + sum_of_value(B, LCA(A,B))
hence all that left is finding LCA, which can be done using binary lifting technique.
Their are multiple way of finding sum after LCA, one way is:
In binary lifting for each vertex u , you store it’s 2^i the ancestor, where i<=20 according to constraints.
Hence you can also use same to store sum value also.

Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-ffloat-store")  
#pragma GCC optimize ("-fno-defer-pop")
typedef long long int ll; 
typedef long double ld; 
#define MAX 100005
ll n;
ll lca[3*MAX][21];
ll sum[3*MAX][21];
ll level[3*MAX];
void add_to_lca(ll u, ll v, ll c){
	level[v] = level[u]+1;
	lca[v][0] = u;
	sum[v][0] = c;
	for(ll i=1;i<=20;i++){
		if(lca[v][i-1] != -1){
			lca[v][i] = lca[lca[v][i-1]][i-1];
			sum[v][i] = sum[v][i-1] + sum[lca[v][i-1]][i-1];
		}
	}
}

ll find_sum(ll u, ll v){
	
	ll ans = 0;

	if(level[u] > level[v])swap(u, v);
	
	for(ll i=20;i>=0;i--){
		if(level[v] == level[u])break;
		if(level[v]-(1LL<<i) >= level[u]){
			ans += sum[v][i];
			v = lca[v][i];
		}
	}
	
	if(u==v){
		return ans;
	}
	
	for(ll i=20;i>=0;i--){
		if(lca[u][i] < 0)continue;
		if(lca[u][i] != lca[v][i]){
			
			ans += sum[u][i];
			u = lca[u][i];
			
			ans += sum[v][i];
			v = lca[v][i];
		}
	}
	return ans + sum[u][0] + sum[v][0];
}

int main()
{

	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	
	memset(lca, -1, sizeof(lca));
	memset(level, -1, sizeof(level));
	
	level[1] = 0;
	
	ll q;
	cin>>q;
	
	while(q--){
		ll type;
		cin>>type;
		
		if(type == 1){
			ll u, v, c;
			cin>>u>>v>>c;
			add_to_lca(u,v,c);
		}
		else{
			ll u, v;
			cin>>u>>v;
			cout<<find_sum(u, v)<<'\n';
		}
	}
}

Problem Interesting Test
Problem Setter under_cover123

Logic

DIFFICULTY:

MEDIUM

PREREQUISITES:

DP with Bitmasking, Maths

PROBLEM:

Given N arrays each of size M.We have to count number of triplets (i,j,k) where 1<=i<j<k<=N such that ith, jth and kth selected array have atleast 1 prime number in common.

QUICK EXPLANATION:

USE Dp with Bitmasking for storing primes in each array (dynamic programming).

EXPLANATION:

Have a look on range of elements in each array
Given -> 1<=element in each array<=20
Number of primes in this range = 2,3,5,7,11,13,17,19
Mask Formation - 8 bits to store 8 primes flag.

Change each array to mask with 8 bits. to represent the presence of primes 2,3,5,7,11,13,17,19 in that array.
In final we will have an array of size N representing mask of 8 bit for each array.

There will be 3 states in the DP
states - (current index,current mask, current of elements selected)
In each state we can select the current element if the count of selected elements is less than equal to 2.
So in each state we have 2 choices
1)select current element if count<=2
2)Go to next index without selecting current element

handle the base cases -
if i==n+1:
if mask>0 and count of selected element==3:
return 1
else:
return 0

Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define endl "\n"
#define mod 1000000007
ll ar[10005],n,m,dp[10005][1ll<<8][4];
ll maxval(ll i,ll mask,ll cnt){
	if(i==n+1){
		if(mask>0&&cnt==3) return 1;
		else return 0;
	}
	if(dp[i][mask][cnt]!=-1){
		return dp[i][mask][cnt];
	}
	ll a,b=0;
	a=maxval(i+1,mask,cnt)%mod;
	if(cnt<=2)
		b=maxval(i+1,(mask&ar[i]),cnt+1)%mod;
	return dp[i][mask][cnt]=(a+b)%mod;
}
int main(){
	ll i,j,k;
	cin>>n>>m;
	for(i=1;i<=n;i++){
		ll mm=0;
		for(j=1;j<=m;j++){
			cin>>k;
			if(k==2) mm=(mm|(1ll<<0));
			if(k==3) mm=(mm|(1ll<<1));
			if(k==5) mm=(mm|(1ll<<2));
			if(k==7) mm=(mm|(1ll<<3));
			if(k==11) mm=(mm|(1ll<<4));
			if(k==13) mm=(mm|(1ll<<5));
			if(k==17) mm=(mm|(1ll<<6));
			if(k==19) mm=(mm|(1ll<<7));
		}
		ar[i]=mm;
	}
	memset(dp,-1,sizeof(dp));
	ll an=maxval(1,(1ll<<8)-1,0)%mod;
	cout<<an;
	return 0;	
}

Problem Find A House
Problem Setter ken_

Logic

DIFFICULTY:

Medium

PREREQUISITES:

Convex Hull, Geometry

PROBLEM:

Given N integers in A[i], m integers in B[i] & C[i], query of range l to r in A[l],
find minimum value of expression { A[i]*B[j] + C[j], l <= i <= r, 1 <= j<= m }

QUICK EXPLANATION:

Standard Convex Hull Optimization Problem

EXPLANATION:

Think of them as lines y = mx + c, where m = B[i], c = C[i], hence line is represented as { m, c } now problem converts to a given x find a line which will give minimum y.
Here x is A[i], so for every A[i] find minimum y[i].
Then use any range query technique to find the min y in { y[i], l<=i<=r } in O(log(n)) time.
Now only problem left is to find the minimum y for a particular x.
Brute force solution is to find y for every line and take min of that, but it will be O(n
m) solution, which will give TLE.
Now if you draw all lines on a graph you will notice that only some lines will provide minimum value for given range of x,
hence, if we create a convex hull containing all edge which provided minimum y for a range, so just iterate over all x in sorted order
and find their minimum value.

Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-ffloat-store")  
#pragma GCC optimize ("-fno-defer-pop")
 
typedef long long int ll; 
typedef long double ld; 
 
#define MAX 100005
 
ll sparse_table[2*MAX][21];
ll A[2*MAX], B[2*MAX], C[2*MAX];	
 
struct Line {
	ll a, b;
	ll value(ll x){
		return a*x + b;
	}
	double intersect(Line l)
	{
		ll num = l.b - b;
		ll den = a - l.a;
		if(den < 0)
		{
			den = den * -1;
			num = num * -1;
		}
		if(den == 0)return 1e18;
		return (1.0L * num)/den;
	}
};
 
bool cmp(const Line &one, const Line &two){
	if(one.a > two.a)return true;
	if(one.a == two.a && one.b > two.b)return true;
	return false;
};
 
void preprocess(ll *ans, ll n){
	
	for(ll i=0;i<n;i++){
		sparse_table[i][0] = ans[i];
	}
	
	for(ll j=1;j<=20;j++){	
		for(ll i=0;i<n;i++){
				if(i+(1LL<<(j-1)) < n){
					sparse_table[i][j] = min(sparse_table[i][j-1], sparse_table[i+(1LL<<(j-1))][j-1]);
					//cout<<i<<" "<<j<<" "<<sparse_table[i][j]<<endl;
				}
		}
	}
	
}
 
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("test_cases/test_case4.txt", "r", stdin);
	freopen("test_cases/test_case4_output.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	ll n, m;
	cin>>n>>m;
	for(ll i=0;i<n;i++)cin>>A[i];
	for(ll i=0;i<m;i++)cin>>B[i];
	for(ll i=0;i<m;i++)cin>>C[i];
	vector < pair <ll,ll> > vec;
	
	for(ll i=0;i<n;i++){
		vec.push_back({A[i], i});
	}
	sort(vec.begin(), vec.end());
	
	vector <Line> lines, temp;
	for(ll i=0;i<m;i++){
		temp.push_back({B[i], C[i]});
	}
	sort(temp.begin(), temp.end(), cmp);
	for(ll i=0;i<m;i++){
		
		Line line = temp[i];
		
		while(lines.size() >= 2){
			Line a = lines.end()[-1];
			Line b = lines.end()[-2];
			if(a.intersect(b) >= b.intersect(line)){
				lines.pop_back();
			}
			else{
				break;
			}
		}
		
		lines.push_back(line);
	}
	
	ll ans[n];
	
	ll start = 0;
	
	for(ll i=0;i<n;i++){
		ll x = vec[i].first;
		while(start < (ll) lines.size() - 1){
			if(lines[start].value(x) > lines[start+1].value(x)){
				start++;
			}
			else{
				break;
			}
		}
		ans[vec[i].second] = lines[start].value(x);
	}
	preprocess(ans, n);
	ll q;
	cin>>q;
	
	while(q--){
		ll l, r;
		cin>>l>>r;
		l--;
		r--;
		ll diff = r-l+1;
		ll val = log2(diff);	
		cout<<min(sparse_table[l][val], sparse_table[r-(1LL<<val)+1][val])<<"\n";
	}	
}
4 Likes

Great :100:

1 Like

I guess the time limit for this problem Hard Problem was very tight. My time complexity for all the solutions that I submitted was same. Still it took me 8 round of optimizations to get it accepted. First of all I did by storing everything and then answering the queries in the end. Then I converted the whole code so that I could answer queries at the same time. However, it was still giving me TLE. I was also using fastio. Then eventually I changed my endl to “\n” and it worked. I think a time limit of 2 seconds instead of 1 second would have been much better in this question.

Really interesting logic for the problem Interesting Problem. Good Editorial, I must say.

2 Likes

@under_cover123 There are formatting issues with the codes that you posted.

1 Like

Updated

Yes , The constraints are very tight (Using endl change the time from 1.01 sec to 0.43 )
Thank You!!

2 Likes

lovely questions.Absolute Classics Yet very Interesting

1 Like

For the maximum sum problem if i take the array [4,3,4,6,8,10,6,9,10] and steps k=4 the maximum sum i was getting is 41 starting with array[2] and the solution provided here gives the maximum sum 37 can anyone explain this
My code:
#include <stdio.h>
#include <stdlib.h>
int max(int, int);
int max_sum(int *, int, int);
int main()
{
int n, k;
scanf("%d %d",&n,&k);
int a[n];
int i = 0;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}

int b[n];

for(i=0;i<n;i++)
{
    b[i] = max_sum((a+i),(n-i),k);
}

int max = b[0];

for(i=0;i<n;i++)
{
    if(max<b[i])
    {
        max = b[i];
    }
}

printf("%d",max);
return 0;
}

int max(int a, int b)
{
int max = a;
if(b>max)
{
max = b;
}
return max;
}

int max_sum(int *a, int n, int k)
{
int i = 0;
int sum1, sum2 ,temp = 0, sum=a[i], temp1 = k;
if(k==0)
{
return 0;
}
while(temp1!=0 && i<n)
{
if(i==n-1)
sum2 = sum;
else if(i==n-2)
{
sum1 = sum+a[i+1];
sum2 = 0;
}else
{
sum1 = sum + a[i+1];
sum2 = sum + a[i+2];
}
sum = 0;
temp = max(sum1, sum2);
if(temp == sum1)
{
i = i+1;
}else
{
i = i+2;
}
sum+=temp;
temp1–;
}
return sum;
}

According to your testcase the maximum elements which can be taken are 8,10,9,10 in 4 steps which will give Sum = 37.

then according to this the sample input given in the problem page arrray[3,5,-1,3,4] maximum elements chosen for 1st index are 5,3 and 4 and so maximum sum must be 12 but output is given 15

if i start with array[2] i.e, 4 in my test case the sum is as follows
step 1: 4 to 8 sum=12
step 2: 8 to 10 sum=22
step 3: 10 to 9 sum=31
step 4: 9 to 10 sum=41

**pls help me my code work find in my editor but not working there
and pls tell where and doing wrong :slight_smile: **
#include<bits/stdc++.h>
using namespace std;

int main() {
// your code goes here
int n;
cin>>n;
string str[n];
for(int i=0;i<n;i++)
cin>>str[i];
int m;
cin>>m;
string str2;
cin>>str2;
> int count =0;

for(int i=0;i<n;i++){
bool flag = str2.find(str[i]);
if(!flag)
count++;
}
cout<<count<<"\n";
return 0;
}