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(nm) 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";
}
}
**