900

Day 1

Array Reodering

Case 1: a[i] is EVEN

If a[i] is even:

• It contains at least one factor of 2.
• 2a[j] is always even (because of the extra 2).

So:

gcd(even, even) ≥ 2

ALWAYS greater than 1.

That means:

If the first element in the pair is EVEN, the pair is ALWAYS good.

Case 2: a[i] is ODD

Now suppose a[i] is odd.

gcd(odd, 2a[j])

Since a[i] has no factor 2, the extra 2 doesn’t help.

So this becomes:

gcd(a[i], a[j])

Now the pair is good only if they share some common factor > 1.

So:

Odd + Odd → sometimes works Odd + Even → might work But NOT guaranteed

Big Insight

Since:

• EVEN as first element → ALWAYS good pair
• ODD as first element → only SOMETIMES good

To maximize pairs:

Put ALL EVEN numbers FIRST Put ALL ODD numbers AFTER

This guarantees:

• Every even forms good pair with ALL elements after it.

Rorder all items and cout which fulfill the condition.

Bad Boy

To annoy Anton, Riley decided to throw exactly two yo-yos in cells of the room (they can be in the same cell).

Means:

• Both yo-yos at Anton’s cell
• One at Anton’s cell, one somewhere else
• Two different cells
• Two same cells somewhere else

Exciting Bets

Odd Divisor

Intitution was right, approach gone wrong

even * even = even
odd * even = even
odd * odd = add

• if n is odd, it definitly have odd divisor

• if n is even, we need to extract the odd part

  • by dividing we will get another even number

  odd * even = even
  odd * (even *2) = even

  • to get the exact odd value, we have to keep divide it by 2
  • actually the number will be in following format

  odd * 2^k = even

  • so n shouldn't contain 2^k

Mocha and Math

Important properties of bitwise AND (&):

• x & y ≤ x and x & y ≤ y
• AND operation can only turn bits off, never on.
• Repeating AND operations can only make numbers smaller or equal.

So the operation always reduces or keeps values the same.

What Is Our Goal?

We want to minimize the maximum element in the array after any number of operations.

So we’re trying to make every element as small as possible.

Suppose we select the entire array ([1, n]).

Then:

$$a_1 = a_1 \,\&\, a_n$$ $$a_2 = a_2 \,\&\, a_{n-1}$$

and so on.

If we repeat operations cleverly on different intervals, something important happens:

Every element can eventually become the AND of all elements.

Why?

Because:

• You can keep shrinking values using AND with other elements.
• AND is associative and commutative.
• Repeated mixing spreads bit removals across the array.

So eventually, every element can be reduced to:

$$a_1 \,\&\, a_2 \,\&\, a_3 \,\&\, \dots \,\&\, a_n$$

Let’s call this value:

$$X = a_1 \,\&\, a_2 \,\&\, \dots \,\&\, a_n$$

• AND only removes bits.
• So no element can ever go below this global AND.
• But we can make all elements equal to this value.

Therefore:

The minimum possible maximum value = Bitwise AND of all elements