CARDSWIPE - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: notsoloud
Tester: satyam_343
Editorialist: iceknight1093

DIFFICULTY:

1172

PREREQUISITES:

None

PROBLEM:

You’re given a sequence of N swipe-ins and swipe-outs to a building.
Find the maximum number of people in it, at any point of time.

EXPLANATION:

Let \texttt{cur} denote the number of people currently in the building.
Initially, \texttt{cur} = 0.

Then, for each 1 \leq i \leq N:

  • If A_i is not inside the building, this is an in-swipe.
    So, \texttt{cur} will increase by 1.
  • Otherwise, A_i was already inside the building, and this is an out-swipe.
    \texttt{cur} will decrease by 1.

The final answer is the maximum value of \texttt{cur} across the entire process.

We only need to quickly check whether A_i is already inside the building or not.
This can be done, for example, with a mark array.

That is, keep an array mark of length N, where mark[x] = 1 means person x is inside the building, and mark[x] = 0 otherwise.
Then,

  • When person A_i enters, set mark[a[i]] = 1.
  • When person A_i exits, set mark[a[i]] = 0.

Each enter/exit is handled in \mathcal{O}(1) time, for a solution in \mathcal{O}(N) overall.

TIME COMPLEXITY

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    a = [0]*(n + 1)
    inside, ans = 0, 0
    for x in map(int, input().split()):
        if a[x] == 1: inside -= 1
        a[x] ^= 1
        if a[x] == 1: inside += 1
        ans = max(ans, inside)
    print(ans)
3 Likes
2 
for i in range(int(input())):
    length = int(input())
    entry_logs = list(map(int, input().split()))
    emps = [0 for i in range(2*(10**5))]
    max_people, people = 0, 0
    for i in range(length):
        if emps[entry_logs[i]]:
            people -= 1
            emps[entry_logs[i]] = 0
        else:
            people += 1
            emps[entry_logs[i]] = 1
        if people>max_people:
            max_people = people
    print(max_people)

Hi, My code is giving TLE, Please help.

3

Use Set instead of emp list.

4

Nice problem !!