# CQM 8.2 - Editorial

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

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())


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)

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


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())

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

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


1 Like

ll n;
cin >> n;
if(n < 10){
cout << n;
return 0;
}
ll ans = n/2;
ans = ans + 5;
if(n%2==0) ans–;
cout << ans << endl;

Can D be solved like , I missed the contest due to its clash with leetcode biweekly.

NO

Input

84


Output

46


47

1 Like

I don’t think so, your solution will fail the testcase

IP : 4586234
OP : 2293122

void test_case(){
ll n,c=0,i;
cin>>n;
if(n<10){
cout<<n<<nl;
return;
}
string s=to_string(n);
if(n%2==0 && (s.back()-‘0’)%2==0 && (s[0]-‘0’)%2==0)
cout<<n/2+5<<nl;
else if(n%2==0 && (s.back()-‘0’)%2==0 && (s[0]-‘0’)%2==1)
cout<<n/2+4<<nl;
else
cout<<n/2+5<<nl;
return;
}
I got this logic By Observation.It got AC.

Due to busy shedule at contest i was not able to submit solution to 1-2 problems I have solved how can I submit and check now if my code is working correctly ?

They should be available for practice now i think, if not i’ll ask the CC team

I don’t know but i am not able to find them if you have a link please share it here .I am a newbie here.
plus one more question probably I didn’t understood the question correctly but can you tell me which case would my code fail in one swap

T=int(input())
for _ in range(T):
A=input()
for i in range(len(A)):
if (i == (len(A) - 1) or (i== (len(A)-2))):
print(A)
break
elif((int(A[i])<int(A[i+2]))):
A = list(A)
A[i], A[i+2] = A[i+2], A[i]
print(''.join(A))
break

Oh I Did 99% same just due to one condition
i got WA

Here is my solution :
https://www.codechef.com/viewsolution/46489754