Solution: Codeforces Round #827 (Div. 4) Editorial

By Md Shoriful Islam

 Solution: Codeforces Round #827 (Div. 4) Editorial

1742A - Sum

Idea: flamestorm

Tutorial

1742A - Sum

You only need to write an if statement and check if any of these are true: a+b=c, b+c=a, c+a=b.

Solution
#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
	int a, b, c;
	cin >> a >> b >> c;
	cout << ((a + b == c || c + a == b || b + c == a) ? "YES\n" : "NO\n");
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

1742B - Increasing

Idea: mesanu

Tutorial

1742B - Increasing

If there are two elements with the same value, then the answer is NO, because neither of these values is less than the other.

Otherwise, the answer is YES, since we can just sort the array.

The time complexity is O(nlog⁡n) or O(n) depending on the implementation.

Solution
#include <bits/stdc++.h>
using namespace std;

void solve()
{
    int n;
    cin >> n;
    int x[n];
    set<int> a;
    for(int i = 0; i < n; i++)
    {
        cin >> x[i];
    }
    for(int i = 0; i < n; i++)
    {
        if(a.find(x[i]) != a.end())
        {
            cout << "NO" << endl;
            return;
        }
        a.insert(x[i]);
    }
    cout << "YES" << endl;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        solve();
    }
}

1742C - Stripes

Idea: flamestorm

Tutorial

1742C - Stripes

Note that if a stripe is painted last, then the entire stripe appears in the final picture (because no other stripe is covering it).

Since rows are only painted red and columns are only painted blue, we can just check if any row contains 8 Rs. If there is such a row, then red was painted last; otherwise, blue was painted last.

Bonus

How do you write a validator for this problem? (Given a grid, check if it is a valid input.)

Solution
#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
	char g[8][8];
	vector<int> r;
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			cin >> g[i][j];
			if (g[i][j] == 'R') {r.push_back(i);}
		}
	}
	for (int i : r) {
	    bool ok = true;
	    for (int j = 0; j < 8; j++) {
	        if (g[i][j] != 'R') {ok = false; break;}
	    }
	    if (ok) {cout << "R\n"; return;}
	}
	cout << "B\n";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

1742D - Coprime

Idea: badlad, SlavicG

Tutorial

1742D - Coprime

Note that the array has at most 1000 distinct elements, since ai≤1000. For each value, store the largest index it is in. Then we can brute force all pairs of values, and find the coprime pair with largest sum of indices.

The time complexity is O(ai2log⁡ai+n) per testcase.

Solution
#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

vector<int> pairs[1001];
void solve() {
    int n; cin >> n;
    vector<int> id[1001];
    for(int i = 1; i <= n; ++i) {
        int x; cin >> x;
        id[x].push_back(i);
    }
    int ans = -1;
    for(int i = 1; i <= 1000; ++i) {
        for(int j: pairs[i]) {
            if(!id[i].empty() && !id[j].empty()) {
                ans = max(ans, id[i].back() + id[j].back());
            }
        }
    }
    cout << ans << "\n";
}   
 
int32_t main() {
    for(int i = 1; i <= 1000; ++i) {
        for(int j = 1; j <= 1000; ++j) {
            if(__gcd(i, j) == 1) {
                pairs[i].push_back(j);
            }
        }
    }
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

1742E - Scuza

Idea: mesanu

Tutorial

1742E - Scuza

Let's compute the prefix sums of the array a: let bi=a1+⋯+ai. Rephrasing the problem: for each question containing an integer k, we need to find the largest ai such that a1,…,ai are all at most k, and then output bi. In other words, max(a1,…,ai)≤k.

Let's make the prefix maximums of the array: let mi=max(a1,…,ai). Then we need to find the largest i such that mi≤k, which is doable using binary search, since the array m is non-decreasing. Once we find the index i, we simply need to output bi.

The time complexity is O(nlog⁡n) per testcase.

Solution
#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int n, q;
    cin >> n >> q;
    vector<long long> pref;
    pref.push_back(0);
    vector<int> prefmax;
    for(int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        pref.push_back(pref.back()+x);
        if(i == 0)
        {
            prefmax.push_back(x);
        }
        else
        {
            prefmax.push_back(max(prefmax.back(), x));
        }
    }
    for(int i = 0; i < q; i++)
    {
        int k;
        cin >> k;
        int ind = upper_bound(prefmax.begin(), prefmax.end(), k)-prefmax.begin();
        cout << pref[ind] << " ";
    }
    cout << endl;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        solve();
    }
}

1742F - Smaller

Idea: SlavicG

Tutorial

1742F - Smaller

First of all, let's think about how we should rearrange the two strings in such a way that a<b (if that is ever possible). It's always optimal to arrange a's characters increasingly in lexicographic order and b's characters decreasingly.

Since initially both a and b contain a character "a", the first time b receives any other letter than "a" the answer will always be "YES", because that character will always be lexicographically larger than a's first character which should be "a".

In the other case, we know that b doesn't have any other characters than "a", so we can compare the string a with multiple "a" characters and we know that a will be smaller if and only if it's only formed of "a"s and has a smaller size than b.

Solution
#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

void solve() {
    int q; cin >> q;
    bool otherA = false, otherB = false;
    ll cntA = 0, cntB = 0;
    while(q--) {
        ll d, k; string x; cin >> d >> k >> x;
        for(auto c: x) {
            if(d == 1) {
                if(c != 'a') otherA = 1;
                else cntA += k;
            } else {
                if(c != 'a') otherB = 1;
                else cntB += k;
            } 
        }
        if(otherB) {
            cout << "YES\n";
        } else if(!otherA && cntA < cntB) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

1742G - Orray

Idea: SlavicG

Tutorial

1742G - Orray

Note that in this context maxval denotes 109.

We can make the observation that only the first log2(maxval) elements matter, since after placing them optimally we can be sure all bits that could be set in the prefix OR would have already been set. So, we can brute force the optimal choice log2(maxval) times (we choose to add an element if it provides the largest new prefix OR value among all unused elements) and then just add the rest of the unused elements.

Solution
#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

void solve() {
    int n; cin >> n;
    vector<int> a(n);
    forn(i, n) cin >> a[i];
    //we care at most about first log2(a) values
    int cur_or = 0;
    vector<bool> vis(n, false);
    for(int i = 0; i < min(31, n); ++i) {
        int mx = 0, idx = -1;
        for(int j = 0; j < n; ++j) {
            if(vis[j]) continue;
            if((cur_or | a[j]) > mx) {
                mx = (cur_or | a[j]);
                idx = j;
            }
        }
        vis[idx] = true;
        cout << a[idx] << " ";
        cur_or |= a[idx];
    }
    forn(i, n) if(!vis[i]) cout << a[i] << " ";
    cout << '\n';
}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

Comments

Post a Comment

Popular posts from this blog

Whiteboarding Interviews

By Md Shoriful Islam
Image
 ⭕ Whiteboarding interviews are a common way of assessing the technical and non-technical skills of candidates for software development positions. They involve solving a coding problem or designing a system on a whiteboard, either in person or virtually, while explaining your approach and reasoning to the interviewer.  ⭕ Some of the benefits of whiteboarding interviews are that they can test your problem-solving ability, communication skills, and coding proficiency in a realistic scenario. They can also help you demonstrate your creativity, collaboration, and passion for the role. However, some of the drawbacks of whiteboarding interviews are that they can be stressful, artificial, and biased. They can also favor memorization over understanding and overlook other aspects of your skills and experience.  ⭕ If you want to ace a whiteboarding interview, you should practice beforehand, prepare for the interview setting, set objectives and expectations, create a good candidate ...
Read more

Version Control with Git: A Beginner’s Guide

By Md Shoriful Islam
Version Control with Git: A Beginner’s Guide If you are a developer, you probably know how important it is to keep track of your code changes and collaborate with other developers on a project. But how do you do that effectively and efficiently? The answer is version control. Version control is a system that records changes to a file or set of files over time so that you can recall specific versions later. It allows you to revert files back to a previous state, compare changes over time, see who last modified something, and more. Version control also enables you to work with other developers on the same code base without stepping on each other’s toes. One of the most popular version control systems in the world is Git. Git is a free and open source distributed version control system that is designed to handle everything from small to very large projects with speed and efficiency. Git has many features that make it superior to other version control systems, such as: Cheap local branchin...
Read more

Callback function in JavaScript

By Md Shoriful Islam
Image
Callback function in JavaScript What is a callback function in JavaScript? A callback function is a function that is passed as an argument to another function and is executed after the first function has completed its task. Callback functions are useful for handling asynchronous events, such as network requests, file operations, or timers. For example, you can use a callback function to display the result of a calculation after the calculation is done. Callback function in JavaScript Here is a simple example of a callback function in JavaScript: // Define a function that takes a callback as an argument function sayHello (callback) { // Do some task console .log ("Hello, world!"); // Invoke the callback function callback (); } // Define another function function sayGoodbye () { // Do some task console .log ("Goodbye, world!"); } // Call the first function and pass the second function as a callback sayHello (sayGoodbye); // The output will be: // Hello, wo...
Read more