A - Maximum Subset
Author : @ritul_14
Tutorial
Observation 1
It is obvious that in order to obtain maximum sum we should include only non negative integers in the subset. But it has been given that the size of the subset should be at-least 1, so if all the numbers are less than 0 ,then we have to choose the greatest negative number.
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
int n;
cin >> n;
int a[n];
for(int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n, greater<int>());
int cnt = 0;
int res = 0;
for(int i = 0; i < n; i++) {
cnt++;
res += a[i];
if(a[i] <= 0){
if(cnt==1){
break;
}else{
res-=a[i];
}
}
}
cout<<res<<endl;
}
int32_t main(){
solve();
return 0;
}
B - One Swap
Author : @ritul_14
Tutorial
Observation 1
It is always optimal to have the greatest digit to the left most index. Also, It is given that we can swap the digits at either even indexed positions or odd indexed positions. So, we can simply use a greedy strategy to solve this problem.
Solution
We will create a suffix array that will store the greatest digit encountered to the right of it and on same parity index.
formally suffix[i] = max(a[i],suff[i+2]).
Now traverse the string s and check if there is a greater digit to the right, formally at i’th position check if suffix[i+2] > a[i] ,
If there exist a greater digit to the right and on same parity index, start traversal from the end of the string and find the position of the same parity and greater digit and swap them.
Time Complexity : O(N)
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
string solve(){
string s;
cin >> s;
int n = s.length();
if(n==2)return s;
bool swapped = false;
int suffix[n];
suffix[n-1] = s[n-1] - '0';
suffix[n-2] = s[n-2] - '0';
for(int i = (n-3); i >=0 ;i--){
int temp = s[i] - '0';
suffix[i] = max(temp,suffix[i+2]);
}
for(int i = 0; i<(n-2) ;i++){
int temp = s[i] - '0';
if(temp<suffix[i+2]){
for(int j = (n-1);j >= 0 ;j--){
if((j%2)==(i%2)){
int temp2 = s[j] - '0';
if(temp2 == suffix[i+2]){
swap(s[i],s[j]);
swapped = true;
break;
}
}
}
}
if(swapped)break;
}
return s;
}
int32_t main(){
int t;
cin >> t;
while(t--){
cout<<solve()<<endl;
}
return 0;
}
C - Is It String Matching
Author : @s59_60r
Tutorial
Observation 1
The first observation in this problem is that for two strings to be anagram of each other
they need to have exactly same frequency of characters and same length.
Observation 2
Let’s say we consider the substring a[l:r], and we form the frequency array of characters between them.
Now, if we need to find the frequency array for the substring a[l+1:r+1], we can do that in O(1), by removing a[l] from the frequency array and adding a[r+1] into it, since it’s an array, both the operation will take constant time. This technique is also known as Sliding Window Technique.
Solution
So, we can compare and check if two strings are anagram by simply comparing their frequency array of characters, and since there are only 26 characters the comparison should take O(26)
We first create a frequency array for string B, as we need to compare B with all other substrings of A.
Since we have to compare substrings of size m we can start from a frequency array for substring a[0:m-1], and then we keep sliding it towards right, using Observation 2 . As a result, we manage to compare all substrings ( a[0:m-1], a[1:m], a[2:m+1] .... a[n-m+1:n] ), and we count the substrings that that are anagram of B.
Time Complexity : O(N \times 26 )
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll tt;
cin >> tt;
while(tt--) {
ll n; cin >> n;
ll m; cin >> m;
string a; cin >> a;
string b; cin >> b;
// Frequency Array for String b
int freq[26]={0};
// Frequency Array for String a
int cur_freq[26]={0};
for(ll i = 0 ; i < b.length() ; i++) {
// Create the Frequency Array for b
freq[b[i]-'a']++;
// Create the Frequency Array for a[0:m-1]
cur_freq[a[i]-'a']++;
}
bool isEqual;
// Check if the frequency array for a[0:m-1] is equal
isEqual=1;
for(int j=0;j<26;j++){
if(cur_freq[j]!=freq[j]){
isEqual=0;
}
}
ll res=isEqual;
for(ll i=m; i<n; i++) {
// Perform sliding of frequency array to move from a[l:r] to a[l+1:r+1]
cur_freq[a[i-m]-'a']--;
cur_freq[a[i]-'a']++;
// Check if the new frequency array is equal
isEqual=1;
for(int j=0;j<26;j++){
if(cur_freq[j]!=freq[j]){
isEqual=0;
}
}
// If Yes, add it to the result
res+=isEqual;
}
// Output the result
cout << res << '\n';
}
return 0;
}
D - Lucky Toys
Author : @s59_60r
Tutorial
There are a couple of ways to solve this particular problem, but here i will go through a solution based on Digit DP.
Let’s try to break the problem into two parts, as you will notice it makes it easier to solve that way.
Observation 1
Let’s try to find all the lucky numbers with at most K digits. We can solve this by trying out all valid combinations of first and last digits.
Now, for each valid pair of the first and last digit the no of lucky numbers would be \sum_{i=0}^{K-2} 10^i
So, we try this for all valid pair of first and last digit and find the lucky numbers with at most K digits.
Code Snippet For Observation 1
int lucky_numbers_with_atmost_k_digit(k){
int res=9;
for(int i=1;i<=9;i++)
for(int j=0;j<=9;j++)
for(int k=0;k<=(k-2);k++)
if((i+j)%2==0)
res += (powl(10,k));
return res;
}
Observation 2
Now, comes the Dynamic Programming part. I will be explaining a Top-down Approach.
Let’s define a function int solve(int idx,int first,int last_added,bool isLess,string &a);. It returns the number of lucky numbers of length M where M is the length of string A starting with digit first.
last_added denotes the last digit which was cosidered in the number.
isLess denotes if the prefix of number created till now is already less than N.
our base case would be
if(idx>=a.length())
return (first+last_added)%2==0;
so now we can preform transitions like this
iterate over all digits from 0....9
if your prefix is already smaller than the number, you can add all numbers in range 0...9 on the idx postion
for(int i=0;i<=9;i++)
if(isLess)
res += solve(idx+1,first,i,isLess,a);
if your prefix is not smaller and is equal to N, there will be two cases
if the digit you are adding is less than the digit at idx position, then it means that your prefix will become smaller.
for(int i=0;i<=9;i++)
int cur=a[idx]-'0';
if(i<cur)
res += solve(idx+1,first,i,1,a);
else your prefix will again remain equal
for(int i=0;i<=9;i++)
int cur=a[idx]-'0';
if(i==cur)
res += solve(idx+1,first,i,0,a);
Note that we don’t consider the case when the digit you are adding is greater than the digit at idx position, because if the prefix is equal and the current digit is greater, it will make the number greater than N.
Combining all the code snippets and adding memoizatoin, we get the
Code for observation 2
int dp[20][10][10][2];
int solve(int idx,int first,int last_added,bool isLess,string &a){
if(idx>=a.ln)
return (first+last_added)%2==0;
if(dp[idx][first][last_added][isLess]!=-1)
return dp[idx][first][last_added][isLess];
int res=0;
for(int i=0;i<=9;i++){
int cur=a[idx]-'0';
if(isLess){
res += solve(idx+1,first,i,isLess,a);
}else{
if(i<cur)
res += solve(idx+1,first,i,1,a);
else if(i==cur)
res += solve(idx+1,first,i,0,a);
}
}
return dp[idx][first][last_added][isLess]=res;
}
Now, for the full solution, we have a number N with M digits,so we can first find all lucky numbers of length at most M-1 using Observation 1
and then find the lucky numbers less than N with length M and brute force all the 9 starting digits using Observation 2
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll lucky_numbers_with_atmost_k_digit(ll k) {
ll res=9;
for(ll i=1; i<=9; i++)
for(ll j=0; j<=9; j++)
for(ll l=0; l<=(k-2); l++)
if((i+j)%2==0)
res += (powl(10,l));
return res;
}
ll dp[20][10][10][2];
ll solve(ll idx,ll first,ll last_added,bool isLess,string &a) {
if(idx>=a.length())
return (first+last_added)%2==0;
if(dp[idx][first][last_added][isLess]!=-1)
return dp[idx][first][last_added][isLess];
ll res=0;
for(ll i=0; i<=9; i++) {
ll cur=a[idx]-'0';
if(isLess) {
res += solve(idx+1,first,i,isLess,a);
} else {
if(i<cur)
res += solve(idx+1,first,i,1,a);
else if(i==cur)
res += solve(idx+1,first,i,0,a);
}
}
return dp[idx][first][last_added][isLess]=res;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n;
cin >> n;
if(n<=9) {
cout << n << '\n';
return 0;
}
string a=to_string(n);
ll len=(ll)a.length()-1;
ll res=lucky_numbers_with_atmost_k_digit(len);
memset(dp,-1,sizeof dp);
for(ll i=1; i<=9; i++) {
if(i<(a[0]-'0'))
res += solve(1,i,i,1,a);
else if(i==(a[0]-'0')) {
res += solve(1,i,i,0,a);
}
}
cout << res << '\n';
return 0;
}