!!! Hello Everyone !!!
If you are starting CP we have a contest for you to try :- Codenovation
This contest was for specially for 1st year HBTU Students by CodeChef HBTU Chapter
!!! Thank you for your Participation !!!
Here is the editorial for HBTU CP Contest 1:- Codenovation :->
Problem A
-
Code :- HBTU001A
-
Problem Link :- The Trip
-
Setter :- Rohit Pratap Singh
-
Tester :- Shivangi Dubey
-
Editorialist :- Rohit Pratap Singh
-
Editorial :-
i/p string :- DD/MM/YYYY o/p string :- MM/DD/YYYY Consider the string as s[0]s[1]s[2]s[3]s[4]s[5]s[6]s[7]s[8]s[9] The required answer is s[3]s[4]s[2]s[0]s[1]s[5]s[6]s[7]s[8]s[9] Overall time complexitity :- O(1*testcases) -
Solution :-
A cpp
//#Rohitpratap311
//#Keep Calm And Stay Happy
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
string s;
cin>>s;
cout<<s[3]<<s[4]<<s[2]<<s[0]<<s[1]<<s[5]<<s[6]<<s[7]<<s[8]<<s[9]<<endl;
//OR
//swap(s[0],s[3]);
//swap(s[1],s[4]);
//cout<<s;
}
return 0;
}
Problem B
-
Code :- HBTU001B
-
Problem Link :- The Jumping Boy
-
Setter :- Rohit Pratap Singh
-
Tester :- Shivangi Dubey
-
Editorialist :- Avantika Singh Parihar
-
Editorial :-
Initially , the boy is on curr=0 and jumping limit = X and p= We have the array track points a[] Now iterate over a[] from 0 t (n-1) if(a[i]-x>L ) then its a invalid jump else its a valid jump update curr=a[i] if(invalid jumps <= P ) { Print YES } else { Print NO } -
Solution :-
B cpp
//#Rohitpratap311
//#Keep Calm And Stay Happy
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int t;
cin>>t;
while(t--)
{
ll N,P,X;
cin>>N>>P>>X;
ll arr[N];
for(ll i=0;i<N;i++)
{
cin>>arr[i];
}
ll curr=0;
string ans="YES";
for(ll i=0;i<N;i++)
{
if(arr[i]-curr>X)
{
if(P>0)
{
P=P--;
}
else
{
ans="NO";
}
}
curr=arr[i];
}
cout<<ans<<endl;
}
return 0;
}
Problem C
-
Code :- HBTU001C
-
Problem Link :- The Lottery
-
Setter :- Rohit Pratap Singh
-
Tester :- Avantika Singh Parihar
-
Editorialist :- Rohit Pratap Singh
-
Editorial :-
We have N,p,q,a,b,c,d First check N is a gap numbers or not . if N is gap number :- X = |a-d|+|b-c|-q else X = |a-d|+|b-c|+p Now if X is even ticket is LUCKY otherwise UNLUCKY . -
Solution :-
C cpp
//#Rohitpratap311
//#Keep Calm And Stay Happy
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll N,p,q,a,b,c,d,X;
cin>>N>>p>>q>>a>>b>>c>>d;
ll temp=N;
ll digits=0;
while(temp>0)
{
digits++;
temp=temp/10;
}
ll x=N/pow(10,digits-1);
ll y=N%10;
ll num=(x*10)+y;
if(N%num==0)
{
X=abs(a-d)+abs(b-c)-p;
}
else
{
X=abs(a-d)+abs(b-c)+q;
}
if(X%2==0)
{
cout<<"LUCKY";
}
else
{
cout<<"UNLUCKY";
}
return 0;
}
Problem D
-
Code :- HBTU001D
-
Problem Link :- The Path to HBTU
-
Setter :- Rohit Pratap Singh
-
Tester :- Avantika Singh Parihar
-
Editorialist :- Rohit Pratap Singh
-
Editorial :-
Consider any path string e.g. NWESSWWWN and staring point = (x,y) Now , the distance = length of path It means distance = size of string Now we can get the end point by traversing the string from :- If path[i] = N y1=y+1 If path[i] = S y1=y-1 If path[i] = E x1=x+1 If path[i] = W x1=x-1 And displacement = [ (x1-x)^2 + (y1-y)^2 ]½ Print (distance - displacement) And take care of the output format. Overall Time Complexity :- O(n) (n=string size)W -
Solution :-
D cpp
#include<bits/stdc++.h>
using namespace std;
//#Rohitpratap311
//#Keep Calm And Stay Happy
int main()
{
int t;
cin>>t;
while(t--)
{
int x,y;
cin>>x>>y;
string s;
cin>>s;
int a=0,b=0;
for(auto i:s)
{
if(i=='N') a++;
if(i=='S') a--;
if(i=='E') b++;
if(i=='W') b--;
}
double displacement=sqrt(pow(a,2)+pow(b,2));
int distance=s.size();
double ans=(double)distance-displacement;
cout<<fixed<<setprecision(6)<<ans<<endl;
}
return 0;
}
Problem E
-
Code :- HBTU001E
-
Problem Link :- The Children and Candies
-
Setter :- Naitik Varshney
-
Tester :- Rohit Pratap Singh
-
Editorialist :- Ishank Katiyar
-
Editorial :-
For Subtask 1 (15 points) : For each Bi, loop through A and find the j such that, A[1] + ... A[j] > B[i], so the answe for this Bi is j - 1. But the time complexity of this code will be O (N * M) . For original constraints: First, calculate the prefix-sum of the array A, let's call it preA. Now for each Bi you can Binary search for the index in preA whose number is just less than and equal to Bi. lets say that index (0-based indexing) if X, answer for that Bi = X + 1. Overall Time Complexity :- O(M*log(N)+N) -
Solution :-
E cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> vec(n);
int i;
for(i=0;i<n;i++)
cin >> vec[i];
sort(vec.begin(), vec.end());
int mark[1000001] = {0};
int j;
vector<int> ans;
for(i=0;i<n;i++)
{
j = i;
while(j < n && vec[j] == vec[i])
j++;
if(j == i + 1)
{
if(!mark[vec[i]])
{
ans.push_back(vec[i]);
int s = vec[i];
while(s < 1000001)
mark[s] = 1, s+=vec[i];
}
}
else
{
if(!mark[vec[i]])
{
int s = vec[i];
while(s < 1000001)
mark[s] = 1, s+=vec[i];
}
}
i = j - 1;
}
if(ans.size() == 0)
cout << -1 << '\n';
else
{
cout << ans.size() << '\n';
for(auto j : ans)
cout << j << " ";
}
}
Problem F
-
Code :- HBTU001F
-
Problem Link :- The War with Primes
-
Setter :- Ekansh Verma
-
Tester :- Ishank Katiyar
-
Editorialist :- Rohit Pratap Singh
-
Editorial :-
Create an array arr For each integer X appearing in the sequence a, set arr[X]=1(i mod X=0,i>x) Specially , if X appears twice or more in the sequence A ,arr[X]=1 The answer is the number of i such that arr[X]=0 store all such X in a vector . If (answer >0) print answer followed by the answe vector in next line . else Print -1 Overall Time Complextity :- O(n*log(max(a[i])) -
Solution :-
F cpp
//#Rohitpratap311
#include<bits/stdc++.h>
using namespace std;
int ans[1000000+20],n,a[200000+20];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
if(a[i]==a[i-1])
{
ans[a[i]]=1;
}
}
int res=0;
vector<int> vec;
for(int i=1;i<=n;i++)
{
if(!ans[a[i]])
{
res++;
vec.push_back(a[i]);
}
if(a[i]!=a[i-1])
{
for(int j=2*a[i];j<=1000000;j+=a[i])
{
ans[j]=1;
}
}
}
if(res==0)
{
cout<<-1;
}
else
{
sort(vec.begin(),vec.end());
cout<<res<<endl;
for(auto i:vec)
{
cout<<i<<" ";
}
}
return 0;
}//There are many variation of the problem.
Problem G
-
Code :- HBTU001G
-
Problem Link :- The Sum
-
Setter :- Ishank Katiyar
-
Tester :- Rohit Pratap Singh
-
Editorialist :- Rohit Pratap Singh
-
Editorial :-
Let's count for each digit how many times it will be included in the final sum and in what place. Let's denote m as the length of the number n. Consider the digit ai at the position ii in the number n (1≤i≤m). If some part of the number to the left of the digit is removed, then the current digit will remain in its place — and we add the number of ways to remove the sub segment to the left to the answer multiplied by the current digit ( i∗(i−1)/2)×10^(m−i)×ai . If the segment to the right is deleted, then the place of the digit will change – (j+1)×10^j×ai for all 0≤j<m−i . The j sum can be pre-calculated for all values.
G cpp
#include<stdio.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string s;
cin >> s;
int n = s.size();
vector<ll> a(n);
for (int i = 0; i < n; ++i)
{
a[i] = s[i] - '0';
}
const int MOD = (int)1e+9 + 7;
ll ans = 0;
ll sum = 0;
ll p = 1;
for (ll i = n - 1; i >= 0; --i)
{
ll k = (i * (i + 1) / 2 % MOD * p % MOD + sum) % MOD;
sum = (sum + p * (n - i) % MOD) % MOD;
p = p * 10 % MOD;
ans = (ans + a[i] * k % MOD) % MOD;
}
cout << ans << endl;
return 0;
} //There are many variation of the problem.
Special thanks to the Executive Team for Smooth conduction of the Contest .
Thank you Again !!!