Code To Decode-Editorial

PROBLEM LINK

(CodeChef: Practical coding for everyone)

Editorialist: bvpcsi_2020 (bvpcsi_2020 | CodeChef User Profile for BVP CSI | CodeChef)

DIFFICULTY:

SIMPLE

PREREQUISITES:

Basic maths

PROBLEM:

We have to find the maximum number of Tetris blocks, that can be placed while following the conditions.

QUICK EXPLANATION:

Answer is floor(A*B*0.5).

EXPLANATION:

Since there are A*B tiles on the board and each block covers exactly two of them we cannot place more for sure.

SOLUTIONS:

#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t–){
int a,b;
cin>>a>>b;

    cout<<(a*b)/2<<"\n";
}
return 0;

}

PROBLEM LINK:

(CodeChef: Practical coding for everyone)

DIFFICULTY:

EASY

PREREQUISITES:

Basic Programming

PROBLEM:

To find if “hello” word is present in the given string

QUICK EXPLANATION:

Find that the word “hello” can be formed from the given string by deleting the letters if needed, order of the letters matter.

EXPLANATION:

Firstly, we have to find in our string the first letter ‘h’ is present and then search for letter ‘e’ which should be to the right ‘h’. If we find the whole word ‘hello’ in such way, obliviously, answer is “YES”.
Otherwise check if the correct order of the letters in the word “hello” are present by removing the unwanted letters between them.
We have greedy algorithm with work time O(n), where n - length of the input.

SOLUTIONS:

#include<bits/stdc++.h>
#define ll long long int

using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);

int i,j;
string str;
string ans="hello";
cin>>str;
for(i=0,j=0;i<str.length()&& j<ans.length();i++)
{
    if(str[i]==ans[j])
    {
        j++;
    }
}
if(j==ans.length())
    cout<<"YES";
else
    cout<<"NO";

return 0;
}

PROBLEM LINK:

(CodeChef: Practical coding for everyone)

DIFFICULTY:

MEDIUM

PREREQUISITES:

Maths and basic programming

PROBLEM:

Find out the minimum number of thieves and the number of ornaments taken by them respectively.

QUICK EXPLANATION:

The answer cane be easily found out by 𝑔𝑐𝑑(𝑘1,𝑘2,…,𝑘𝑛)

EXPLANATION:

First observation is that for the fixed value of 𝑧 our problem is reduced to the following: we are given 𝑛 numbers 𝑎1,𝑎2,…,𝑎𝑛. We need to choose such values 𝑘1,𝑘2,…,𝑘𝑛 that 𝑎1+𝑘1⋅𝑧=𝑎2+𝑘2⋅𝑧=⋯=𝑎𝑛+𝑘𝑛⋅𝑧. And among all such values 𝑘1,𝑘2,…,𝑘𝑛 we need to choose values in a way to minimize ∑𝑘𝑖. And the sum of 𝑘𝑖 is 𝑦! Of course, for the fixed value 𝑧 the minimum sum of 𝑘𝑖 can be only one.

If 𝑧=1. It is obvious that if the maximum value in the array 𝑎 is 𝑚𝑥 the value 𝑘𝑖 equals 𝑚𝑥−𝑎𝑖 (for 𝑧=1). Assume that each 𝑘𝑖 from 1 to 𝑛 has some divisor 𝑑. Then if we multiply 𝑧 by 𝑑 and divide each 𝑘𝑖 by 𝑑 the answer will only become better. How to calculate this value of 𝑧 fast? We can see that this value equals to 𝑔𝑐𝑑(𝑘1,𝑘2,…,𝑘𝑛)! And it can be proven that this value of 𝑧 is always optimal and we can easily determine 𝑦 for such 𝑧.

SOLUTIONS:

#include<bits/stdc++.h>
#define MOD 1000000007
#define ll long long int
#define endl "\n"
using namespace std;
int main(int argc, char const *argv[])
{

int t;
cin>>t;
while(t--){
    int n;
    cin>>n;
    vector<int> a(n);
    for(auto &x: a){
        cin>>x;
    }

    int ma = *max_element(a.begin(), a.end());
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        sum += a[i];
    }
    int g = ma - a[0];
    for (int i = 1; i < n; i++) {
        g = __gcd(g, ma - a[i]);
    }    
    ll ans = (ma * 1ll * n - sum) / g;
    cout << ans << ' ' << g << endl;
}
return 0;

}

PROBLEM LINK:

(CodeChef: Practical coding for everyone)

DIFFICULTY:

MEDIUM

PREREQUISITES:

Basic programming

PROBLEM:

We have to find he minimum number of moves needed to make complete the level.

QUICK EXPLANATION:

Apply the given constraints. Think about different test cases.

SOLUTIONS:

#include<bits/stdc++.h>

using namespace std;

long long t, n, ans, x, y;

string s;

int main(){

cin>>t;

while(t–){

cin>>n>>s;

x=0;

y=0;

ans=0;
for(long long i=0; i<n; i++)

if(s[i]==‘@’) x++;

for(long long i=0; i<n; i++)

if(s[i]==‘@’) y++;
else ans+=min(y, x-y);

cout<<ans<<endl;

}

return 0;

}

PROBLEM LINK:

(CodeChef: Practical coding for everyone)

DIFFICULTY:

MEDIUM

PREREQUISITES:

Basic maths

PROBLEM:

Find the minimum number of game rounds the friends need to let the i - th person play at least ai rounds.

QUICK EXPLANATION:

Apply the given constraints. Think about different test cases.

EXPLANATION:

Let the answer be x games. Notice that max(a1, a2, …, an) ≤ x. Then i-th player can be game supervisor in x–ai games. If we sum up we get
( x-a1 ) + ( x- a2) + …… + (x - an) = nx - ∑ai — it’s the number of games in which players are ready to be supervisor. This number must be greater or equal to x — our answer.
=> x = ceiling ( ∑ai/ n )
There’s also the condition max(a1, a2, …, an) ≤ x.

SOLUTIONS:

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–){
long long n,a,s = 0,m = INT_MIN;
cin>>n;
for(int i=0;i<n;i++){
cin>>a;
m=max(a,m);
s+=a;
}

    cout<<max(m,(s-1)/(n-1)+1)<<"\n";
}

return 0;
}

PROBLEM LINK:

(CodeChef: Practical coding for everyone)

DIFFICULTY:

MEDIUM

PREREQUISITES:

greedy

PROBLEM:

Find the minimum number of moves (under the given constraints) required to obtain such a number that is divisible by 25.

QUICK EXPLANATION:

Iterate over all possible pair of digits that can be swapped to make the resulting number divisible by 25.

EXPLANATION:

Iterate over all pairs of digits in the given number. Take two pointers positioned at the opposite ends of the number say i and j. The first pointer greedily goes to the last position and then the second goes to the position next to that. Now the number can contain a leading zero. Find the leftmost non-zero digit of the number and move it to the first position. Then if the obtained number is divisible by 25, update your answer with the number of swaps. Notice that the order of swaps doesn’t matter and we can rearrange them in such a way that no leading zero appears on any step.

SOLUTIONS:

#include <bits/stdc++.h>

using namespace std;

int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin>>t;
while(t–)
{
string s;
cin >> s;
reverse(s.begin(), s.end());
int ans = 60;
for (int i = 0; i < s.size(); i ++){
for (int j = i + 1; j < s.size(); j ++){
string t;
t += s[i]; t += s[j];
int f = 0;
int k = j - 1;
while (i < k && s[k] == ‘0’)
f ++, k --;
if (j != s.size() - 1 || s.size() < 3)
f = 0;
if (t == “00” || t == “52” || t == “05” || t == “57”)
ans = min(ans, i + j - 1 + f);
if (t == “25” || t == “50” || t == “75”)
ans = min(ans, i + j + f);
}
}
cout << (ans == 60 ? -1 : ans)<<endl;
}
}

PROBLEM LINK:

(CodeChef: Practical coding for everyone)

DIFFICULTY:

HARD

PREREQUISITES:

Dynamic programming implementation

PROBLEM:

Find he minimum number of operations you have to perform to make the array increasing using the given operations,

QUICK EXPLANATION:

Apply largest increasing subsequence using dynamic programming solution.

EXPLANATION:

We see here that if array strictly increases, then b does not decrease, and vice versa. Here we have to find the maximum number of positions in the b array that can be left unchanged. This can be evaluated in O(nlog⁡n) by using the analogy of the largest increasing subsequence, but here we can take equal elements. But remember not to break the strict array increment rule.

SOLUTIONS:

#include <bits/stdc++.h>

using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); ++i)

const int N = 500 * 1000 + 13;

int n, k;

int a[N], b[N];

int main() {

int t;

cin>>t;

while(t–)

{ scanf(“%d%d”, &n, &k);
forn(i, n) scanf(“%d”, &a[i + 1]);

a[0] = -1e9;

a[n + 1] = 2e9;

forn(i, n + 2) a[i] -= i;
forn(i, k) scanf(“%d”, &b[i + 1]);
b[k + 1] = n + 1;

int flag=0;

int ans = 0;

forn(i, k + 1) {

int l = b[i], r = b[i + 1];
if (a[l] > a[r]) {

puts(“-1”);
flag=1;
break;
}
vector lis;
for (int j = l + 1; j < r; ++j) if (a[l] <= a[j] && a[j] <= a[r]) {
auto pos = upper_bound(lis.begin(), lis.end(), a[j]);
if (pos == lis.end()) lis.push_back(a[j]);
else *pos = a[j];
}
ans += (r - l - 1) - int(lis.size());
}
if(flag==0)
printf(“%d\n”, ans);

}
return 0;
}

PROBLEM LINK:

(CodeChef: Practical coding for everyone)

DIFFICULTY:

HARD

PREREQUISITES:

Dynamic programming implementation

PROBLEM:

Find he minimum number of operations you have to perform to make the array increasing using the given operations,

QUICK EXPLANATION:

We can solve this problem using dynamic programming and applying the given constraints.

EXPLANATION:

First, consider a sub-array from indices Left to Right(inclusive). We assume the part (Body part of majin but) at index Last to be the last part to be taken in this sub-array, we would say the strength gained to be-S[left-1]*S[last]*S[right+1]. Also, the total Strength Gained would be this value, plus dp[left][last – 1] + dp[last + 1][right], where dp[i][j] means maximum Strength gained for sub-array with indices i, j.
Therefore, for each value of Left and Right, we need find and choose a value of Last with maximum strength gained, and update the dp array. Our Answer is the value at dp[1][N].

SOLUTIONS:

#include<bits/stdc++.h>
#define ll long long int

using namespace std;

int main(){
int t;
cin>>t;
while (t–){
ll n;
cin>>n;
vectora(n,0);
for(ll i=0;i<n;i++){
cin>>a[i];
}

    ll dp[n][n] = {0}; 
    for(ll g=0;g<n;g++){
        for(ll i=0,j=g;j<n;i++,j++){

            ll maxval = INT_MIN;
            for(ll k=i;k<=j;k++){
                ll left = k==i?0:dp[i][k-1]; 
                ll right = k==j?0:dp[k+1][j]; 
                ll self =a[k];
                if(i>0){
                    self*=a[i-1];
                }
                if(j!=n-1){
                    self*=a[j+1];
                }
                ll total = left +right +self;
                maxval = max(total,maxval);
            }
            dp[i][j] = maxval;
        }
    }

    cout<<dp[0][n-1]<<"\n";
}

return 0;
}