SUBSTADD-Editorial

editorial
, , ,
1

PROBLEM LINK:

Division 3
Practice

Author: Daanish Mahajan
Tester: Takuki Kurokawa
Editorialist: Srikkanth R.

DIFFICULTY:

Cakewalk

PREREQUISITES:

Loops, Arrays, Logical Operators

PROBLEM:

You are given two arrays A and B and two integers X and Y. Determine if there exists a subset of indices of A so that B can be obtained by

  • Increasing the values of chosen indices by X
  • Increasing the remaining values by Y

EXPLANATION:

Suppose the random subset chosen to convert A to B was S. Consider an index i.

  • If the index i was present in S then B[i] must be equal to A[i] + X.
  • If the index i was not present in S then B[i] must be equal to A[i] + Y.
    Therefore we can iterate through the indices and figure out the subset S by simply looking at the values of A[i], B[i]. If we encounter an index i such that B[i] is neither equivalent to A[i] + X nor A[i] + Y, then such an S clearly does not exist and the answer is No, otherwise the answer is Yes.

The pseudocode is shown below:

string answer = "Yes"; // Initialise the answer to "Yes"
for (i=0;i<n;++i) { // Iterate through elements of the array (0 based index)
    if (A[i] != B[i] + X && A[i] != B[i] + Y) {
        answer = "No"; // Set the answer to "No"
        break; // Once the answer is found to be "No", we can break out of the loop, this line is optional as it prevents unnecessary comparisons but does not reduce worst case complexity
    }
}
cout << answer << '\n' // Print the answer and move to next line

The time complexity of the solution is O(n) as we perform a single linear scan of the arrays A and B.