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

$$$2$$$. 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"

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

Track by number, not position.

Let factors talk to each other.

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)
        

Group values, not positions.

Treat it like House Robber on numbers.

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

$$$2$$$. Initialize the DP array f:

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

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

• Use the recurrence relation to fill f[i]

$$$4$$$. 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()

    
    

Break big whites smartly.

Subtree sizes are gold.

Cut edges, track splits.

DFS from root, think gain.

You are given a tree with $$$n$$$ nodes.

A tree is an undirected graph that is: - Connected (there is a path between any two nodes) - Acyclic (no cycles)

Each node is initially white.

You play a game on this tree as follows:

• On your first move, you choose any node and paint it black.
• On subsequent moves, you can only paint a white node adjacent to any black node.
• Each time you paint a node, you earn points equal to the size of the white connected component it belonged to just before it was painted.

The game ends when all nodes are painted black.

Objective

Your goal is to choose:

1. The first node to paint.

2. The order in which you paint the rest of the nodes.

such that the total number of points is maximized.

Strategy Overview

Let’s denote: - The first black node as the root. - The tree rooted at this node allows us to define a parent-child relationship between nodes.

This problem becomes one of selecting the best root (i.e., first node) and modeling the painting process as a traversal through the tree.

The idea is to:

1. Fix a node (say, node $$$1$$$) as the root.
2. Use dynamic programming to compute the score for that root.
3. Use a technique called rerooting to efficiently compute the score for every other possible root.

Finally, select the root that gives the maximum score.

Step 1: Fix a Root and Compute Initial DP

Let’s fix node $$$1$$$ as the root of the tree.

We define two arrays:

• $$$\text{siz}_v$$$: the size of the subtree rooted at node $$$v$$$. This includes $$$v$$$ itself and all its descendants.
• $$$\text{dp}_v$$$: the total score of the tree if we start the painting process with $$$v$$$ as the root.

Let $$$\text{ch}(v)$$$ be the set of children of $$$v$$$ in the tree.

We compute:

Why this formula works:

Let’s break it down: - $$$\text{dp}_{\text{to}}$$$: total score from each child subtree. - $$$\text{siz}_v$$$: added because when we select $$$v$$$, we paint it and gain points equal to the number of white nodes connected to it — i.e., its entire subtree before it’s painted.

Using DFS (Depth-First Search), we traverse the tree and compute $$$\text{siz}_v$$$ and $$$\text{dp}_v$$$ for each node.

At this point, we know the score if the root is node $$$1$$$.

Step 2: Rerooting the Tree

Now we want to find the score $$$\text{dp}_v$$$ for every possible root $$$v$$$, not just node $$$1$$$.

A naive way would be to recompute everything from scratch for each root, costing $$$O(n^2)$$$ time.

Instead, we use rerooting to compute the new score in constant time per move, and thus $$$O(n)$$$ total time.

Rerooting Logic

Let’s say the current root is node $$$v$$$, and we want to move the root to its child $$$\text{to}$$$.

We do this in two main steps:

Step 1: Cut the edge $$$(v, \text{to})$$$

• We remove $$$\text{to}$$$ from $$$v$$$'s subtree.
• This means:
  • Subtract $$$\text{dp}_{\text{to}}$$$ from $$$\text{dp}_v$$$
  • Subtract $$$\text{siz}_{\text{to}}$$$ from $$$\text{siz}_v$$$

Step 2: Connect $$$v$$$ as a child of $$$\text{to}$$$

• Now $$$\text{to}$$$ becomes the root.
• We attach $$$v$$$ as a child of $$$\text{to}$$$.
• So we:
  • Add updated $$$\text{dp}_v$$$ to $$$\text{dp}_{\text{to}}$$$
  • Add updated $$$\text{siz}_v$$$ to $$$\text{siz}_{\text{to}}$$$

In math terms:

Now, $$$\text{dp}_{\text{to}}$$$ holds the score with $$$\text{to}$$$ as root.

We update our global answer.

Step 3: Backtrack (Rollback)

After processing $$$\text{to}$$$, we undo all changes and restore the original state. This allows the next sibling to be processed correctly.

Final Steps

$$$1$$$. Run a first DFS from any node (say, node $$$0$$$) to compute:

• $$$\text{siz}_v$$$ for all $$$v$$$
• $$$\text{dp}_v$$$ for all $$$v$$$

$$$2$$$. Run a second DFS that reroots the tree at every node:

• At each step, compute the new $$$\text{dp}_v$$$ in constant time
• Track the maximum score seen

Time Complexity

• First DFS (computing subtree sizes and initial DP): $$$O(n)$$$
• Second DFS (rerooting): $$$O(n)$$$

Total Time Complexity: $$$O(n)$$$

Why This Works for Tree Painting

The painting process and the scoring rules align perfectly with subtree structure:

• When a node is selected, its score equals the size of the connected white component — which is exactly the subtree size.
• By modeling the process as rooting the tree, we reduce the problem to a root-based score maximization.
• Using rerooting, we try all possible starting points efficiently and choose the best one.

This guarantees that we find the maximum possible score achievable in the Tree Painting game.

import sys
import threading

n = int(input())
graph = [[] for _ in range(n)]

for _ in range(n - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v)
    graph[v].append(u)

subtree_size = [0] * n
dp = [0] * n
max_score = 0

def dfs(v, parent):
    subtree_size[v] = 1
    for neighbor in graph[v]:
        if neighbor == parent:
            continue
        dfs(neighbor, v)
        subtree_size[v] += subtree_size[neighbor]
        dp[v] += dp[neighbor]
    dp[v] += subtree_size[v]

def solve(v, parent):
    global max_score
    max_score = max(max_score, dp[v])
    
    for neighbor in graph[v]:
        if neighbor == parent:
            continue

        dp[v] -= dp[neighbor] + subtree_size[neighbor]
        subtree_size[v] -= subtree_size[neighbor]
        
        dp[neighbor] += dp[v] + subtree_size[v]
        subtree_size[neighbor] += subtree_size[v]

        solve(neighbor, v)

        subtree_size[neighbor] -= subtree_size[v]
        dp[neighbor] -= dp[v] + subtree_size[v]

        subtree_size[v] += subtree_size[neighbor]
        dp[v] += dp[neighbor] + subtree_size[neighbor]

def main():
    dfs(0, -1)
    solve(0, -1)
    print(max_score)

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