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'))