CS2023_STK - Editorial

PROBLEM LINK:

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

Author: himanshu154
Tester: jay_1048576
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given the solve counts of Om and Addy on each of N days, find which one among them had the longer streak.

EXPLANATION:

First, let’s try to find Om’s longest streak of solving problems.
That is, we want to find the longest subarray of A that contains only non-zero elements.

That can be done by iterating across the array and maintaining the current length of a non-zero subarray.
In particular,

  • Let \text{cur} be a variable denoting the current length of a non-zero subarray.
    Initially, \text{cur} = 0.
  • Then, for each i from 1 to N:
    • If A_i \gt 0, increase \text{cur} by 1.
    • Else, set \text{cur} to 0.

The maximum value of \text{cur} ever reached is the number we’re looking for.
Let this value be \text{mx}_A.

Similarly, Addy’s maximum streak can be found by applying this algorithm to array B, giving us the value \text{mx}_B.

Finally, compare \text{mx}_A and \text{mx}_B, and print Om, Addy, or Draw depending on which one is higher or if they’re equal.

TIME COMPLEXITY

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python)
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    
    amx, bmx = 0, 0
    cura, curb = 0, 0
    for i in range(n):
        if a[i] == 0: cura = 0
        else: cura += 1
        
        if b[i] == 0: curb = 0
        else: curb += 1
        
        amx = max(amx, cura)
        bmx = max(bmx, curb)
    print('Om' if amx > bmx else ('Addy' if amx < bmx else 'Draw'))