CF 102697050 - The Array Checker-inator!

Rating: -
Tags: -
Solve time: 48s
Verified: yes

Solution

Problem Understanding

We are given two integer arrays. Their lengths and their order do not necessarily have to match. The checker should answer YES when both arrays contain exactly the same distinct values, regardless of how many times each value appears and regardless of the order in which the values occur. Otherwise it should answer NO.

For example, [1, 2, 3] and [3, 1, 1, 2, 3] are considered equal because removing repeated occurrences from the second array leaves {1, 2, 3}, which is also the set of values in the first array. In contrast, [1, 2, 3, 4] and [1, 2, 7] are different because their distinct value sets are different.

The input consists of n, followed by the n elements of the first array, then m, followed by the m elements of the second array. The original statement gives a one-second time limit and 256 MB of memory, but does not expose a useful numerical upper bound for n and m. That makes the asymptotic behavior especially relevant. A solution that performs only one pass over the input is preferable to repeatedly comparing elements or performing unnecessary work.

The first edge case is duplicate-heavy input. Consider:

The correct output is:

YES

A careless implementation that compares the arrays element by element would reject them because their lengths differ and because the second array contains repeated values. The actual condition ignores multiplicity, so this comparison is inappropriate.

The second edge case is different ordering. Consider:

The correct output is:

YES

Comparing positions directly would incorrectly produce NO, even though both arrays contain exactly the same distinct integers.

The third edge case is a value that appears only as a duplicate in one array. Consider:

The correct output is:

NO

After duplicates are removed, the first array becomes {1, 2} while the second becomes {1}. An implementation that merely checks whether every value of the smaller array appears in the larger one could accidentally accept this case unless it also checks the reverse direction.

Approaches

A straightforward approach is to sort both arrays and remove consecutive duplicates. Sorting puts equal values beside one another, so after deduplication the two resulting arrays can be compared directly. This is correct because sorting removes the relevance of the original order, while deduplication removes the relevance of multiplicity.

The problem with this approach is that sorting costs O(n log n + m log m). If both arrays contain around 10^5 elements, this means on the order of millions of comparisons. More precisely, the rough comparison count is n log2 n + m log2 m, which is about 3.4 million comparisons when both sizes are 10^5. That is feasible in many environments, but it is unnecessary for this problem.

The brute-force can also be made even worse by checking every element against every element in the other array. That requires O(nm) comparisons. With n = m = 10^5, this reaches 10^10 comparisons, which is far beyond what a one-second contest solution can afford.

The key observation is that the problem does not care about order or frequency. Those are exactly the two properties that a set discards. Converting each array to a set immediately removes duplicates, and set equality automatically ignores ordering. The brute-force works because sorting and deduplication explicitly construct the canonical representation of each array. The observation that only the distinct values matter lets us construct that representation directly with a hash set.

Thus the optimal solution is simply to read both arrays, construct their sets, and compare the two sets.

Approach	Time Complexity	Space Complexity	Verdict
Sort, deduplicate, compare	`O(n log n + m log m)`	`O(n + m)`	Accepted, but unnecessary work
Pairwise comparison	`O(nm)`	`O(1)` aside from input storage	Too slow for large arrays
Set equality	`O(n + m)` average	`O(n + m)`	Accepted

Algorithm Walkthrough

Read n and consume the next n integers as the first array. Insert every value into a set. The set is exactly the information that matters, because repeated occurrences have no effect on the required answer.
Read m and consume the next m integers as the second array. Insert every value into another set for the same reason.
Compare the two sets. If they contain exactly the same values, print YES; otherwise print NO. Python's set equality checks both directions implicitly, so a value missing from either array causes the comparison to fail.
Do not compare the original lengths. Different lengths are completely valid when one array contains duplicates. For example, the lengths 3 and 5 in the first sample still produce equal sets.

Why it works: after all elements have been processed, the first set contains precisely every distinct value occurring in the first array, and the second set contains precisely every distinct value occurring in the second array. Set equality holds exactly when every distinct value of one array occurs in the other array and vice versa. That is exactly the condition described by removing duplicates and ignoring order, so the algorithm cannot classify a valid pair as NO or an invalid pair as YES.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    pos = 0

    n = data[pos]
    pos += 1

    first = set(data[pos:pos + n])
    pos += n

    m = data[pos]
    pos += 1

    second = set(data[pos:pos + m])

    print("YES" if first == second else "NO")

if __name__ == "__main__":
    solve()

The solution reads the entire input as integers and advances an index through it. This is convenient here because the input format gives exact array lengths, while sys.stdin.buffer.read() avoids repeated line-reading overhead.

The first slice contains exactly n values, so the position is advanced by n before reading m. The same idea is used for the second array. Keeping these boundaries explicit prevents an off-by-one error where the length of the second array could accidentally be interpreted as one of its elements.

The conversion to set is the central operation. Python automatically discards repeated values, so no explicit sorting or duplicate-removal pass is needed. Python integers have arbitrary precision, so there is also no integer overflow issue for the array values.

Although the statement says that array elements are provided on separate lines, reading whitespace-separated integers is equivalent and makes the implementation robust to different whitespace layouts.

Worked Examples

For the first sample, the first array is [1, 2, 3], while the second array is [1, 1, 2, 2, 3]. The duplicate occurrences disappear when the second array is converted to a set.

Step	`first`	`second`	Result
Read first array	`{1, 2, 3}`	not read yet
Read second array	`{1, 2, 3}`	`{1, 2, 3}`
Compare	`{1, 2, 3}`	`{1, 2, 3}`	`YES`

The trace demonstrates why multiplicity must be ignored. The second array has five elements, but its set contains only three distinct values, exactly matching the first array. This is the official first sample.

For the second sample, the arrays are [1, 2, 3, 4] and [1, 2, 7].

Step	`first`	`second`	Result
Read first array	`{1, 2, 3, 4}`	not read yet
Read second array	`{1, 2, 3, 4}`	`{1, 2, 7}`
Compare	`{1, 2, 3, 4}`	`{1, 2, 7}`	`NO`

The value 3 is missing from the second set, while 7 is absent from the first. Set equality consequently fails. This is the official second sample.

Complexity Analysis

Measure	Complexity	Explanation
Time	`O(n + m)` average	Each array element is inserted into a hash set once, followed by an average linear-time set comparison
Space	`O(n + m)`	The two sets store at most one copy of every distinct value

The solution performs only linear expected work in the number of input elements. Even when the arrays contain many repeated values, every input element is processed once and duplicates occupy no additional set entries. With the one-second limit, this is the appropriate asymptotic approach for large inputs.

Test Cases

# helper: run solution on input string, return output string
import sys
import io

def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    pos = 0

    n = data[pos]
    pos += 1

    first = set(data[pos:pos + n])
    pos += n

    m = data[pos]
    pos += 1

    second = set(data[pos:pos + m])

    print("YES" if first == second else "NO")

def run(inp: str) -> str:
    old_stdin = sys.stdin
    old_stdout = sys.stdout

    sys.stdin = io.StringIO(inp)
    sys.stdout = io.StringIO()

    # The solution above uses sys.stdin.buffer, so use the same parsing
    # logic directly for the test harness.
    raw = sys.stdin.read()
    data = list(map(int, raw.split()))
    pos = 0

    n = data[pos]
    pos += 1
    first = set(data[pos:pos + n])
    pos += n

    m = data[pos]
    pos += 1
    second = set(data[pos:pos + m])

    print("YES" if first == second)

    result = sys.stdout.getvalue()

    sys.stdin = old_stdin
    sys.stdout = old_stdout
    return result

# provided sample 1
assert run("""\
3
1
2
3
5
1
1
2
2
3
""") == "YES\n", "sample 1"

# provided sample 2
assert run("""\
4
1
2
3
4
3
1
2
7
""") == "NO\n", "sample 2"

# minimum-size arrays with the same value
assert run("""\
1
42
1
42
""") == "YES\n", "minimum-size equal arrays"

# all values are equal, but the lengths differ
assert run("""\
5
9
9
9
9
9
1
9
""") == "YES\n", "duplicate handling"

# same distinct values in a different order
assert run("""\
4
10
20
30
40
6
40
30
30
20
10
40
""") == "YES\n", "order and duplicates"

# one distinct value differs
assert run("""\
4
1
2
3
3
4
1
2
4
4
""") == "NO\n", "different distinct sets"

# empty arrays, if zero-length arrays are accepted by the input format
assert run("""\
0
0
""") == "YES\n", "two empty arrays"

Test input	Expected output	What it validates
`1 / 42 / 1 / 42`	`YES`	Minimum-size arrays
Five copies of `9` versus one `9`	`YES`	Duplicate removal and different lengths
Same values in different orders	`YES`	Order independence and repeated values
`{1,2,3}` versus `{1,2,4}`	`NO`	A single distinct-value mismatch
`0 / 0`	`YES`	Empty-set boundary, if zero lengths are allowed

Edge Cases

The duplicate-heavy sample

produces YES. The first set becomes {1, 2, 3} and the second set also becomes {1, 2, 3}. The differing lengths never enter the decision, which is correct because repeated values do not matter.

The ordering case

also produces YES. The sets are {1, 2, 3} on both sides even though none of the positions needs to correspond. A position-by-position solution would fail here, while set equality directly captures the required behavior.

The missing-value case

produces NO. The first set is {1, 2} and the second is {1}. Checking only whether every value from the second array occurs in the first would incorrectly accept the input, but equality of the complete sets checks both directions.

Finally, consider

which produces YES. Both arrays reduce to the single-element set {5}. This is the smallest useful example showing that the number of occurrences has no significance at all, only the presence or absence of each distinct integer matters.