FOCUS-ASTU-TECH-COMMUNITY-CONTEST-1

The Goal

We have two bears:

• Limak weighs a
• Bob weighs b

We know:

Every year:

• Limak's weight triples: (a \times 3)
• Bob's weight doubles: (b \times 2)

We need to find the number of years it takes for Limak to become strictly heavier than Bob:

Input Constraints

• Think about the constraints: The starting weights are at most 10. Since Limak's weight triples every year, it grows very fast.

• Do you really need a complex formula, or can you just calculate the weight year by year?

• Condition Check: Be careful with the stopping condition. Limak needs to be strictly larger (>), not equal (=).

Since the constraints are very small, we don't need to worry about the program running too slowly. We can use a Brute Force Simulation approach. This means we will simply simulate the process exactly as described in the problem statement.

Step-by-Step Logic

1. Initialize: We start with year = 0.
2. Check Condition: Keep going as long as Limak is not larger than Bob.
   c++ while (a <= b)
3. Update Weights: Inside the loop (representing one passing year):

• Limak's new weight = a * 3
• Bob's new weight = b * 2
• Increment year by 1

1. Stop: Once a becomes greater than b, the loop stops.
2. Result: The value of year is our answer.

Why this works

Even if a = 1 and b = 10, Limak triples every year.
The sequence grows like 1, 3, 9, 27... while Bob grows 10, 20, 40....
They will cross paths very quickly (within less than 10 years). This makes the simulation extremely fast.

Common Mistake

Using while (a < b) instead of while (a <= b).
If a becomes equal to b, Limak is not larger yet. He needs to be strictly greater, so the loop must continue if they are equal.

# Read input
a, b = map(int, input().split())

# Initialize years counter
years = 0

# Simulate year by year
while a <= b:
    a *= 3
    b *= 2
    years += 1

# Print the result
print(years)

Complexity:

• Time: O(1) effectively. Although it is a loop, the maximum number of iterations is very small (less than 10) due to exponential growth.
• Space: O(1). We only store a, b, and years.

The Story

Tanya climbs several stairways. For each stairway, she counts the steps aloud starting from 1 up to the total number of steps in that stairway.

For example:
- If a stairway has 3 steps, she says: 1, 2, 3
- If the next stairway has 4 steps, she resets and says: 1, 2, 3, 4

The Input

You are given the entire sequence of numbers she spoke:

1. First line: n — total numbers spoken
2. Second line: the sequence of numbers (e.g., 1 2 3 1 2 3 4)

The Goal

• Find how many stairways she climbed
• Find the number of steps in each stairway

Key Observation

• Every time Tanya starts a new stairway, she says the number 1
• The number just before a new 1 is the height of the previous stairway
• The last number in the sequence is always the height of the final stairway

• Look for Resets: What specific number indicates the start of a new stairway?
• The Previous Number: If you see a 1 at index i (and i > 0), what does the number at index i-1 represent?
• The End: Don't forget the last stairway! There won't be a 1 after the last stairway to signal its end, so you must handle the last element of the array separately.

Approach: Linear Scan (Array Traversal)

We can solve this by iterating through the list of numbers exactly once.
This is an O(N) approach, which is perfect for the constraint n ≤ 1000.

Logic Steps

1. Store Results: Create an empty list called stairs to store the height of each stairway.
2. Iterate: Loop through the sequence of numbers from beginning to end.
3. Detect Reset: Check if the current number is 1.

• If the current number is 1 and it is not the very first number of the sequence, it means a new stairway has started.
• Therefore, the previous number in the sequence was the top step of the previous stairway. Add that number to stairs.

1. Handle Last Stairway: After the loop finishes, the last number in the sequence is always the top step of the final stairway. Add it to stairs.

Output

• Print the length of the stairs list (this is the number of stairways).
• Print the elements of the stairs list separated by spaces.

Example Walkthrough

Input: 1 2 3 1 2 3 4

• Index 0: 1 (First element, ignore)
• Index 1: 2
• Index 2: 3
• Index 3: 1 → Reset detected! Previous number was 3 → Save 3
• Index 4: 2
• Index 5: 3
• Index 6: 4 → End of loop → Save last number 4

Result: [3, 4]

Common Pitfalls

• Forgetting the last stairway: If you only save a number when you see a 1, you will miss the last stairway because there is no 1 after it.
• Index Out of Bounds: When checking the "previous number" (i-1), ensure you don't do this for the very first element (index 0).

def solve():
    # Read n (total numbers)
    n = int(input())
    
    # Read the sequence of numbers as a list of integers
    a = list(map(int, input().split()))
    
    stairs = []
    
    # Iterate through the array using index
    for i in range(n):
        # If we see a 1 and it's NOT the first element (i > 0)
        # It means the previous element was the top of a stairway
        if a[i] == 1 and i > 0:
            stairs.append(a[i-1])
            
    # The last element of the array is always the top of the last stairway
    stairs.append(a[-1])
    
    # Output the number of stairways
    print(len(stairs))
    
    # Output the heights of each stairway separated by space
    # The * operator unpacks the list for printing
    print(*stairs)

if __name__ == "__main__":
    solve()

Complexity Analysis

• Time Complexity: O(N)
  We loop through the input array exactly once. With N ≤ 1000, this is effectively instant.

• Space Complexity: O(N)
  We store the result in a list stairs. In the worst case (every step is a stairway like 1 1 1 ...), the list size is N.

Approach: Lookahead (Checking the Next Element)

Topic: Arrays

Instead of checking if the current element is 1 (and looking backward), you can check if the next element is 1 (and look forward).

Logic

1. Loop through the array from index 0 to n-2 (stop before the last element).
2. If a[i+1] == 1, it means the current number a[i] is the top of the current stairway. Save a[i].
3. After the loop, save the last element a[n-1], because it's always the top of the last stairway.

Why use this?

Some beginners find looking forward (i+1) more intuitive than looking backward (i-1).
The complexity remains the same as the main solution.

Code Snippet

stairs = []
for i in range(len(sequence)-1):
    if sequence[i+1] == 1:
        stairs.append(sequence[i])
stairs.append(sequence[-1])

Both the Lookback (main solution) and Lookahead (alternative) methods are equally efficient and valid for this problem.

The Story

You have two joysticks with initial charges a1 and a2. You have only one charger.

Every minute:
- The joystick connected to the charger gains +1% charge.
- The joystick not connected loses -2% charge.

The Rules

• The game stops if any joystick reaches 0% or less.
• You want to maximize the number of minutes the game lasts.
• Constraints:

The Goal

Calculate the maximum number of minutes before one joystick dies.

Example

Input: 3 5

• Minute 1: Charge 3 → 4, 5 discharges → 3 → State: 4, 3
• Minute 2: Charge 3 → 4, 4 discharges → 2 → State: 2, 4
• And so on.

• Greedy Strategy: To keep the game alive longer, which joystick should you charge? The one with more charge or less charge?
• Small Constraints: Since the maximum charge is only 100, the game cannot last more than a few hundred minutes. You can simulate minute-by-minute.
• Edge Case: What happens if both joysticks start at 1%? Can you save both?

Approach: Simulation (Brute Force)

Since the constraints are very small ($$$a_1, a_2 \le 100$$$), we can simulate the game minute by minute until one joystick dies.

Greedy Logic

To maximize time, always charge the joystick with the lower charge:
- Why? The joystick with lower charge is closer to 0%. If we let it discharge by 2%, it might die immediately. By charging it (+1%), we keep it alive longer.
- The one with higher charge can afford to lose 2%.

Step-by-Step Logic

1. Initialize: minutes = 0.
2. Loop: Continue while both a1 > 0 and a2 > 0.
3. Check Death Trap: If a1 == 1 and a2 == 1, one will die anyway. Stop the loop.
4. Charge Strategy:

• If a1 < a2: charge a1 (+1), discharge a2 (-2)
• Else: charge a2 (+1), discharge a1 (-2)

1. Count: Increment minutes by 1.
2. Output: Print minutes.

Complexity

Since the total charge decreases net -1 per minute, the loop runs at most $$$a_1 + a_2$$$ times. Maximum input 100 → roughly 200 iterations → instant for Python.

def solve():
    # Read initial charges
    a1, a2 = map(int, input().split())
    minutes = 0
    
    # Simulate minute by minute
    while a1 > 0 and a2 > 0:
        # Edge Case: both 1%
        if a1 == 1 and a2 == 1:
            break
        
        # Greedy: charge the lower
        if a1 < a2:
            a1 += 1
            a2 -= 2
        else:
            a2 += 1
            a1 -= 2
        
        minutes += 1
        
    print(minutes)

if __name__ == "__main__":
    solve()

Complexity Analysis

• Time Complexity: O(A + B) → max 200 iterations → effectively O(1)
• Space Complexity: O(1) → only a few integers stored

Approach: Simulation with Sorting

Topic: Sorting & Brute Force

Instead of if-else, you can sort the two charges each minute to find the smaller one to charge.

Logic

1. Inside the loop, put a1 and a2 into a list.
2. Sort the list so the smaller charge is first.
3. Charge the first element (+1), discharge the second (-2).
4. Update a1 and a2.

Code Snippet

def solve_alternative():
    a1, a2 = map(int, input().split())
    minutes = 0
    
    while a1 > 0 and a2 > 0:
        if a1 == 1 and a2 == 1:
            break
        
        charges = [a1, a2]
        charges.sort()  # smaller first
        
        charges[0] += 1
        charges[1] -= 2
        
        a1, a2 = charges[0], charges[1]
        minutes += 1
    
    print(minutes)

Why use this?
- Useful for more than 2 joysticks (always charge the weakest).
- For 2 joysticks, if-else is faster; sort is more readable for beginners.

Common Mistakes

• Forgetting the (1,1) case: Without checking a1 == 1 and a2 == 1, you might count one extra minute where a joystick goes negative.
• Order of Operations: Ensure the stopping condition (>0) is checked before incrementing the minute counter.

The Story

Polycarp has n problems with different difficulties. He must solve all of them in exactly k days.

• Order: Solve in the given order (no skipping, no reordering).
• Split: Split the list of n problems into k contiguous parts (days).
• Profit: Profit of a day = maximum difficulty of problems solved that day.
• Total Profit: Sum of profits of all k days.

The Goal

1. Maximize the Total Profit.
2. Output the number of problems solved on each of the k days.

Input

• n, k — number of problems, number of days
• List a — difficulties

Example

n=8, k=3, a = [5, 4, 2, 6, 5, 1, 9, 2]

Optimal split: [5, 4, 2], [6, 5], [1, 9, 2]

• Day 1 Max: 5
• Day 2 Max: 6
• Day 3 Max: 9
• Total Profit: 5 + 6 + 9 = 20

• Think about the Maximums: Total profit = sum of daily maximums. Which numbers should be the maximums?
• Greedy Idea: Pick the k largest numbers to be the daily maximums.
• Construction: Once the top k values are chosen, split the array so each maximum is in a different day.

Approach: Greedy + Sorting

1. Maximizing Profit: The total sum is maximized if each day has one of the k largest values.

• Sort a, take the largest k values, sum them → maximum profit.

1. Constructing the Days:

• Find the indices of these top k values in the original array.
• Sort indices in ascending order.
• Make k-1 cuts after each of the first k-1 indices.
• The last day takes the remaining problems.

Common Pitfalls

• Duplicate Values: Treat top k values at distinct positions separately.
• Last Day: Ensure the last day includes all remaining problems.

def solve():
    # Read n and k
    n, k = map(int, input().split())
    
    # Read the difficulties
    a = list(map(int, input().split()))
    
    # --- Step 1: Calculate Maximum Profit ---
    # We create a sorted copy of 'a' to find the largest k values
    sorted_a = sorted(a)
    
    # The maximum profit is the sum of the last k elements in the sorted list
    max_profit = sum(sorted_a[-k:])
    print(max_profit)
    
    # --- Step 2: Construct the Days ---
    # We need to find the original indices of the top k values.
    # We store pairs of (value, original_index)
    pairs = []
    for i in range(n):
        pairs.append((a[i], i))
    
    # Sort pairs by value in descending order to get the top k
    # If values are equal, the order doesn't strictly matter for profit, 
    # but we need distinct indices.
    pairs.sort(key=lambda x: x[0], reverse=True)
    
    # Take the first k pairs (the top k values)
    top_k_pairs = pairs[:k]
    
    # Extract the original indices from these pairs
    indices = [p[1] for p in top_k_pairs]
    
    # Sort the indices in ascending order because we must split the array in order
    indices.sort()
    
    # Calculate the sizes of each day
    sizes = []
    prev_index = -1
    
    # We make k-1 cuts. The last day takes the rest.
    for i in range(k - 1):
        current_index = indices[i]
        # Size is the distance from the previous cut to this index
        # Example: prev=-1, current=0 -> size = 0 - (-1) = 1
        size = current_index - prev_index
        sizes.append(size)
        prev_index = current_index
    
    # The last day takes everything from the last cut to the end of the array
    # Total elements n. Last used index is prev_index.
    # Remaining elements = n - (prev_index + 1)
    last_size = n - (prev_index + 1)
    sizes.append(last_size)
    
    # Print the sizes separated by space
    print(*sizes)

if __name__ == "__main__":
    solve()

Complexity Analysis

• Time: O(N log N) → sorting dominates.
• Space: O(N) → store pairs and indices.

Approach: Threshold Value Counting

• Idea: Find the smallest value among the top k largest (threshold).
• Count numbers greater than threshold → they must end a day.
• Count threshold numbers needed → end days accordingly.

Why Main Solution is Better:
- Index sorting handles duplicates automatically.
- Simpler and less error-prone for beginners.

Common Mistakes

• Incorrect Splitting: Two top values in the same day → profit decreases.
• Output Format: First line = total profit, second line = sizes of k days.

The Story

Arkady creates problems one by one. Each problem has a difficulty level from 1 to n.

• To hold a contest, he needs exactly one problem of each difficulty from 1 to n.
• When a problem is created, it goes into a pool.
• If the pool contains at least one problem of every difficulty (1..n), a contest is held immediately.
• Holding a contest removes one problem of each difficulty from the pool.

Input

• n — number of difficulty levels
• m — total problems created
• Sequence of m integers — difficulties of created problems

The Goal

For each problem created (1st to m-th), output:
- '1' if a contest was held immediately after creating it
- '0' otherwise

Output as a single string.

Example

n = 3, Problems: 2, 3, 1, 2, 2, 2, 3, 2, 2, 3, 1

• After 2: Pool {2} → No contest (0)
• After 3: Pool {2,3} → No contest (0)
• After 1: Pool {1,2,3} → Contest! Remove {1,2,3} → Pool empty (1)
• ...and so on

• Use a frequency array or map to track how many problems of each difficulty are in the pool.
• Keep a distinct counter to know how many difficulties currently exist.
• When a contest occurs, remove one problem of each difficulty.
• With small n and m ≤ 10^5, simulation is fast if handled carefully.

Approach: Frequency Array + Simulation

1. Data Structures:

• count array of size n+1 — count[i] = number of problems of difficulty i
• distinct_count — how many difficulties currently have count[i] > 0

1. Initialize: count filled with 0, distinct_count = 0, empty output list
2. Process Problems: Loop over each created problem x

• Increment count[x]
• If count[x] was 0 → increment distinct_count

1. Check Contest:

• If distinct_count == n:
  • Append '1' to output
  • Remove one problem of each difficulty (1..n), decrement distinct_count if any drops to 0
• Else, append '0'

1. Output: Join the list of '0'/'1' into a string

def solve():
    # Read n and m
    # n = difficulty levels, m = total problems created
    n, m = map(int, input().split())
    
    # Read the sequence of problem difficulties
    problems = list(map(int, input().split()))
    
    # Frequency array to store count of each difficulty in the pool
    # Size is n + 1 because difficulties are 1-indexed (1 to n)
    count = [0] * (n + 1)
    
    # Tracks how many unique difficulties currently have count > 0
    distinct_count = 0
    
    # List to store the output characters ('0' or '1')
    result = []
    
    for x in problems:
        # Add the new problem to the pool
        if count[x] == 0:
            distinct_count += 1
        count[x] += 1
        
        # Check if we have a complete set (1 to n)
        if distinct_count == n:
            result.append('1')
            
            # Remove one set of problems (1 to n) from the pool
            # Note: Even though this is a loop, it runs at most m/n times total.
            # So the overall complexity remains O(m).
            for i in range(1, n + 1):
                count[i] -= 1
                if count[i] == 0:
                    distinct_count -= 1
        else:
            result.append('0')
            
    # Print the result as a single string
    print("".join(result))

if __name__ == "__main__":
    solve()

Complexity Analysis

• Time: O(M) — each problem is added and removed at most once
• Space: O(N + M) — count array and result list

• Instead of a fixed-size array, use a Python dictionary for count.
• Useful if difficulties are sparse or non-consecutive.
• Logic remains identical: increment, check distinct count, remove when contest happens.

def solve_alternative():
    # Read n and m
    n, m = map(int, input().split())
    problems = list(map(int, input().split()))
    
    # Dictionary to store frequency of each difficulty
    count = {} 
    distinct_count = 0
    result = []
    
    for x in problems:
        # Update count for difficulty x
        # get(x, 0) returns 0 if x is not in the dictionary yet
        count[x] = count.get(x, 0) + 1
        
        # If this was the first time we saw this difficulty, increment distinct_count
        if count[x] == 1:
            distinct_count += 1
        
        # Check if we have all n difficulties
        if distinct_count == n:
            result.append('1')
            
            # Remove one set of problems (1 to n)
            for i in range(1, n + 1):
                if i in count:
                    count[i] -= 1
                    # If count drops to 0, we no longer have this difficulty
                    if count[i] == 0:
                        distinct_count -= 1
                        # Optional: Remove key to keep dictionary clean
                        del count[i] 
        else:
            result.append('0')
            
    print("".join(result))

if __name__ == "__main__":
    solve_alternative()

Why prefer array?
- With consecutive difficulties 1..n, array is faster and memory-efficient.

Common Mistakes:
- Printing inside loop instead of storing → slow for large m
- Forgetting to decrement distinct_count when removing problems