We are given an array of length $$$n$$$ that represents whether Petya watered his flower each day.
Each element $$$a_i$$$ is either:

• $$$1$$$ → the flower was watered
• $$$0$$$ → the flower was not watered

The flower begins at a height of $$$1$$$ cm on day 0 (before processing any input days).

Simulation Logic

We iterate through the array starting from index $$$1$$$ (the second day), and at each step, we examine the current element $$$a_i$$$ and the previous element $$$a_{i-1}$$$.
There are four possible scenarios:

• Case 1: $$$a_i = 1$$$ and $$$a_{i-1} = 1$$$
  → The flower was watered both yesterday and today
  → It grows by $$$5$$$ cm
  → height += 5

• Case 2: $$$a_i = 1$$$ and $$$a_{i-1} = 0$$$
  → The flower was watered today only
  → It grows by $$$1$$$ cm
  → height += 1

• Case 3: $$$a_i = 0$$$ and $$$a_{i-1} = 1$$$
  → The flower was not watered today, but was yesterday
  → It doesn't grow, but remains alive
  → height remains the same

• Case 4: $$$a_i = 0$$$ and $$$a_{i-1} = 0$$$
  → The flower was not watered for two consecutive days
  → The flower dies
  → return -1

Initialization

• The simulation starts with: height = 1

We loop through the array once and apply the above logic. If the flower survives all $$$n$$$ days, we return the final height⁣. If it dies due to two unwatered days in a row, we return -1.

Time Complexity

• This approach has a time complexity of $$$O(n)$$$, since we loop through the array once.

t = int(input())
for _ in range(t):
    n  = int(input())
    arr = list(map(int, input().split()))
    
    height = 1
    if arr[0] == 1:
        height += 1
    for i in range(1, n):
        if arr[i] == 1 and arr[i - 1] == 1:
            height += 5
        elif arr[i] == 1 and arr[i - 1] == 0:
            height += 1
        elif arr[i] == 0 and arr[i - 1] == 0:
            height =  -1  
            break
    print(height)

You're given an array of integers $$$a_1, a_2, \ldots, a_n$$$.
In one move (costing 1 coin), you can increment or decrement any element by 1.
Your goal is to make the product of the entire array equal to 1 using the minimum number of moves.

Key Insight

The product of several integers is 1 if and only if: - Each element is either $$$1$$$ or $$$-1$$$ - The number of $$$-1$$$ elements is even

Step-by-Step Strategy

1. Convert each number to 1, -1, or 0:

• If $$$a_i \gt 1$$$:
  Convert to 1, cost is $$$a_i - 1$$$

• If $$$a_i \lt -1$$$:
  Convert to -1, cost is $$$-1 - a_i = |a_i + 1|$$$

• If $$$a_i = 0$$$:
  Count it separately, will cost 1 later

• If $$$a_i = 1$$$ or $$$-1$$$:
  No cost

1. Track:

• cost: total number of coins used
• neg_count: number of -1s
• zero_count: number of 0s

Final Adjustment

Let $$$k$$$ be the number of zeros.

• If $$$k \gt 0$$$:
  Spend $$$k$$$ coins to convert all zeros
  Use one of the zeros to fix the parity of negative numbers, if needed
  → No extra cost

• If $$$k = 0$$$:
  If neg_count is odd, we must convert one $$$-1$$$ to $$$1$$$
  → Extra cost of 2 coins

Time Complexity

The entire algorithm runs in $$$\mathcal{O}(n)$$$ time.

n = int(input())
arr = list(map(int, input().split()))

cost = 0
neg_count = 0
zero_count = 0

for num in arr:
    if num > 1:
        cost += num - 1
    elif num < -1:
        cost += abs(num + 1)
        neg_count += 1
    elif num == 0:
        cost += 1
        zero_count += 1
    elif num == -1:
        neg_count += 1

if zero_count == 0 and neg_count % 2 == 1:
    cost += 2

print(cost)

You are given a grid of size $$$n \times m$$$. You start at cell $$$(1,1)$$$ and want to reach cell $$$(n,m)$$$.

Allowed moves:

• Move right from $$$(x, y)$$$ to $$$(x, y+1)$$$, costing $$$x$$$ burles.
• Move down from $$$(x, y)$$$ to $$$(x+1, y)$$$, costing $$$y$$$ burles.

The question: can you reach $$$(n,m)$$$ spending exactly $$$k$$$ burles?

Key Insight: The total cost is constant regardless of the path

No matter which path you take (only moving right or down), the total cost to reach $$$(n,m)$$$ is always the same.

This can be proven by induction on $$$n + m$$$:

• Base case: $$$n = m = 1$$$.
  You are already at the target; no moves are made, so cost is $$$1 \times 1 - 1 = 0$$$.

• Inductive step:
  For fixed $$$(n, m)$$$, the last step to reach $$$(n, m)$$$ must be either:

• From $$$(n, m-1)$$$, costing $$$n$$$ burles, or
• From $$$(n-1, m)$$$, costing $$$m$$$ burles.

If the total cost to reach $$$(n, m-1)$$$ is $$$n \times (m-1) - 1$$$, then the total cost reaching $$$(n,m)$$$ from there is: $$$n \times (m-1) - 1 + n = n \times m - 1$$$.

Similarly, if the cost to reach $$$(n-1,m)$$$ is $$$(n-1) \times m - 1$$$, then coming from there costs: $$$(n-1) \times m - 1 + m = n \times m - 1$$$.

Since both paths give the same total cost, by induction the cost to reach $$$(n,m)$$$ is always: $$$n \times m - 1$$$.

What this means

You do not need to consider any particular path. Simply compute: $$$\text{cost} = n \times m - 1$$$

and check if it equals $$$k$$$.

• If $$$k = n \times m - 1$$$, print "YES"
• Otherwise, print "NO"

Code Implementation

```python n, m, k = map(int, input().split()) cost = n * m — 1

if k == cost: print("YES") else: print("NO")

t = int(input())

for _ in range(t):
    n, m, k = map(int, input().split())
    cost = n * m - 1

    if k == cost:
        print("YES")
    else:
        print("NO")

You are given a list of integers $$$a_1, a_2, \dots, a_n$$$ called good integers.
Your goal is to find the maximum length of a good sequence using these integers, satisfying the following conditions:

1. The sequence is strictly increasing.
2. No two adjacent elements are coprime, i.e., for every adjacent pair $$$(x_i, x_{i+1})$$$, $$$\gcd(x_i, x_{i+1}) \gt 1$$$.
3. All elements of the sequence must come from the list of good integers.

Core Idea

The key idea is to use dynamic programming (DP) combined with divisor information to construct and extend valid sequences efficiently.

Since we require adjacent numbers to not be coprime, we want them to share at least one common divisor greater than 1.

A natural way to organize this is by thinking in terms of divisors:
If two numbers are divisible by the same number $$$d \gt 1$$$, then their GCD is at least $$$d$$$, satisfying the condition.

Definitions

We define two key DP structures:

• $$$dp[x]$$$: the maximum length of a valid sequence ending at value $$$x$$$
• $$$d[i]$$$: the maximum length of any sequence that ends with a number divisible by $$$i$$$

Here’s what they mean:

• $$$dp[x]$$$ stores the best (maximum length) sequence that ends at $$$x$$$.
• $$$d[i]$$$ is a helper that tracks the best dp value among all previous values that were divisible by $$$i$$$.

This allows us to efficiently build on previous values that share common divisors.

Step 1: Preprocessing Divisors

To use the divisors efficiently in our transitions, we precompute all the divisors of every number up to the maximum number in the array.

This is done in $$$\mathcal{O}(n \log n)$$$ time using a sieve-like approach:

• For every $$$i$$$ from $$$1$$$ to $$$\max(a)$$$,
• Add $$$i$$$ as a divisor to every multiple of $$$i$$$.

At the end of this step, for any number $$$x$$$, we can instantly access all its divisors via divisors[x].

Step 2: Dynamic Programming Transitions

Now that we have all divisors available, we sort the array $$$a$$$ and remove duplicates to ensure the sequence we build is strictly increasing.

Then for each number $$$x$$$ in the sorted array:

Step 2.1: Compute $$$dp[x]$$$

We want to extend the best sequence that ends with a number sharing a divisor with $$$x$$$.

So we iterate over all divisors $$$i$$$ of $$$x$$$ and do:

This means: “Let’s try to extend a sequence that ends in some previous number divisible by $$$i$$$, and add $$$x$$$ at the end.”

Step 2.2: Update $$$d[i]$$$

Once we compute $$$dp[x]$$$, we update all relevant $$$d[i]$$$ values for the next transitions.

For all $$$i \mid x$$$, we do:

This ensures that any future number $$$y$$$ divisible by $$$i$$$ can use this newly improved path.

Why This Works

Because we're enforcing the GCD condition through shared divisors, this approach naturally guarantees:

• GCD > 1 for all adjacent elements (since they share a common divisor).
• Strictly increasing order, as we process the sorted array from left to right.

Also, since we only process a number's divisors, and the number of divisors of a number is at most $$$\mathcal{O}(\sqrt{x})$$$, and the total over all numbers from $$$1$$$ to $$$n$$$ is bounded by $$$\mathcal{O}(n \log n)$$$, the algorithm remains efficient.

Special Case: Single Element [1]

If the input array is just $$$[1]$$$, there's no possible sequence of length >1, since 1 is coprime with every other number (including itself).
In this case, the only valid sequence is $$$[1]$$$ of length 1.

So we must handle this edge case explicitly.

Time Complexity

This is efficient and works well for $$$n$$$ up to $$$10^5$$$.

Summary Table

Conceptual Takeaway

This approach cleverly transforms a hard GCD-based subsequence constraint into a tractable divisor-based DP problem.
By precomputing and reusing divisor relationships, we efficiently manage transitions and enforce the $$$\gcd \gt 1$$$ rule without needing pairwise comparisons.

n = int(input())
 
arr = list(map(int, input().split()))
 
def get_divisors(x):
    divisors = [[] for _ in range(x + 1)]
    for i in range(2, x + 1):
        for j in range(i, x + 1, i):
            divisors[j].append(i)
    return divisors
div_memo = [0 for _ in range(max(arr) + 1)]
memo = [-1 for _ in range(max(arr) + 1)]
divisors = get_divisors(max(arr))
 
 
def dfs(value):
    if memo[value] != -1:
        return memo[value]
    longest_good_sequence = 0
    for div in divisors[value]:
        longest_good_sequence = max(longest_good_sequence, div_memo[div])
    memo[value] = longest_good_sequence + 1
    for div in divisors[value]:
        div_memo[div] = max(memo[value], div_memo[div])
    return memo[value]
ans  = 0
for a in arr:
    ans = max(dfs(a), ans)
print(ans)
        

We are given a list of integers a of size n. We are allowed to repeatedly choose a number x from the list and:

• Gain x points
• Delete all occurrences of x, x - 1, and x + 1 from the list

Our goal is to maximize the total number of points we can collect through such operations.

This constraint — where selecting a number x forces the removal of its adjacent values — means we cannot pick both x and x+1. So, we must make choices that avoid conflicting selections.

Key Insight

Rather than working directly with the input array, it's helpful to preprocess it to count how many times each value appears.

Let cnt[x] be the number of times value x appears in the array. We now reframe the problem as:

• For every integer value x, we can either
• Take it, earning cnt[x] * x points, but then we must skip x-1
• Skip it, and rely on the optimal value already computed for smaller numbers

This makes the problem well-suited for a Dynamic Programming solution.

Dynamic Programming Approach

We define a dynamic programming array f where:

• f(i) is the maximum score we can get considering values from 1 to i

Base Cases

• f(0) = 0: no values to consider, so the score is 0
• f(1) = cnt[1] * 1: only one value to consider; we can either take it or not

Recurrence Relation

For all values i ≥ 2:

Explanation:

• f(i - 1): if we skip value i, the score is the best score we could get using up to i-1
• f(i - 2) + cnt[i] * i: if we take value i, we must skip i-1, so we add cnt[i] * i to the score we got up to i-2

This transition ensures we never take two adjacent values, which would violate the rule of deleting x-1 and x+1.

Implementation Steps

1. Build the frequency array cnt:

• Iterate through the input array and count the occurrences of each integer
• This helps reduce the problem from position-based to value-based

1. Initialize the DP array f:

• f[0] = 0
• f[1] = cnt[1] * 1

1. Iterate from i = 2 to the maximum value present in the input:

• Use the recurrence relation to fill f[i]

1. Final answer is f[max_val]:

• max_val is the largest number in the array a
• This value represents the best result considering all possible values

Time and Space Complexity

• Time Complexity: O(n + m) where:
• n is the size of the input array
• m is the maximum value in the input
• Counting frequencies takes O(n)
• Filling the DP array takes O(m)

• Space Complexity: O(m) for storing the frequency and DP arrays

Summary

This approach efficiently solves the problem by reducing it to a non-adjacent selection problem over the frequency of values, rather than the positions in the original array. The dynamic programming recurrence ensures optimal choices at each step by balancing between picking or skipping each number based on its contribution and its adjacency constraints.

import sys
import threading
def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    max_value = max(arr)
    trr = [0 for i in range(max_value + 1)]
    memo = [-1 for i in range(max_value + 1)]

    for a in arr:
        trr[a] += 1
    def dfs(index):
        if memo[index] != -1:
            return memo[index]
        if index == 0:
            return 0
        if index < 0:
            return 0
        
        not_take = dfs(index - 1)
            
        take = trr[index] * index  + dfs(index - 2)
        memo[index] =  max(take, not_take)
        return memo[index]
    print(dfs(max_value))


def main():
    solve()


if __name__ == '__main__':
    sys.setrecursionlimit(2 * 10**5)
    threading.stack_size(1 << 27)  # ~32 MB stack
    t = threading.Thread(target=main)
    t.start()
    t.join()