Overview

This is a problem where you select only the first flower found for each species from among the flowers you discovered, and calculate the count and sum of species numbers.

Analysis

The key point of this problem is “when the same species number appears multiple times, only adopt the first occurrence.”

For example, consider the case where flower species numbers are found in the order [3, 1, 2, 1, 3, 4]: - 1st: Species 3 → First time seeing it → Adopt - 2nd: Species 1 → First time seeing it → Adopt - 3rd: Species 2 → First time seeing it → Adopt - 4th: Species 1 → Already seen → Exclude - 5th: Species 3 → Already seen → Exclude - 6th: Species 4 → First time seeing it → Adopt

Result: The count is \(4\) flowers, and the sum of species numbers is \(3 + 1 + 2 + 4 = 10\).

Why use a set?

We need to efficiently determine “whether we’ve already seen it.”

• Naive approach (using a list): Scan through the entire list each time to check → Each check takes \(O(N)\), resulting in \(O(N^2)\) overall
• Using a set: Adding to and searching in a set is \(O(1)\) on average → \(O(N)\) overall

Since \(N\) can be up to \(2 \times 10^5\), \(O(N^2)\) might not be fast enough, but \(O(N)\) is sufficiently fast.

Algorithm

1. Prepare a set seen to manage “species numbers already seen”
2. Initialize a variable count for counting flowers and a variable total for holding the sum of species numbers to \(0\)
3. Process each flower one by one in the order they were found:
   • If that species number is not contained in seen:
     • Add that species number to seen
     • Increment count by \(1\)
     • Add that species number to total
   • If already contained in seen, do nothing (exclude as duplicate)
4. Output the final count and total

Complexity

• Time complexity: \(O(N)\)
  • For each flower, adding to and searching in the set can be done in \(O(1)\) on average
  • Processing \(N\) flowers sequentially results in \(O(N)\) overall
• Space complexity: \(O(\min(N, 100))\)
  • The set seen can contain at most 100 species (species numbers range from 1 to 100)
  • This can essentially be considered \(O(1)\) (constant)

Implementation Notes

• Python’s set can perform element addition (add) and existence checking (in) in \(O(1)\) on average, making it ideal for “removing duplicates” operations like this

• Use if s not in seen: to check “is this a species we haven’t seen yet,” and only update the count and sum when the condition is met

• Since the range of species numbers is small (1 to 100), it’s also possible to implement this using an array (a list of size 101) and manage it like seen[s] = True

  Source Code

N = int(input())
S = list(map(int, input().split()))

seen = set()
count = 0
total = 0

for s in S:
    if s not in seen:
        seen.add(s)
        count += 1
        total += s

print(count, total)

This editorial was generated by claude4.5opus.