The general form of the sequence

Note that we're considering the operations when $$$m_1 \le m_2 \le m_3$$$.

Consider the case where $$$n$$$ is even:

The number of operations is the length of the sequence $$${2,4,6,\ldots, 2(\frac{n}{2}-1)}$$$ which is $$$\frac{n}{2}-1$$$.

Consider the case where $$$n$$$ is odd:

The number of operations is the length of the sequence $$${1,3,5,7,\ldots, 2(\lfloor \frac{n}{2} \rfloor-1)+1}$$$

By the representation of odd numbers we've $$${2(0)+1,2(1)1+,\ldots, 2(\lfloor \frac{n}{2} \rfloor-1)+1}$$$ , which is equivalent to the length of $$${0,1,2,\ldots, \frac{n-1}{2}-1}$$$ which gives the length of $$$\frac{n-1}{2}$$$.

Both cases are equivalent to the close form

Complexity $$$\mathcal{O}(1)$$$.

from math import *

def solve():
    n=int(input())
    print((n-1)//2)

for _ in range(int(input())):
    solve()

It's possible to use fair split that's we use $$$\lfloor \frac{n}{3} \rfloor , \lfloor \frac{n}{3} \rfloor , \lfloor \frac{n}{3} \rfloor + n \bmod 3$$$ and keep simulating with $$$n=m_3$$$ on steps except the first step until you reach $$$m_2 \le 2$$$.

Complexity $$$\mathcal{O}(\log_3(n))$$$

from math import *

def solve():
    n=int(input())
    a,b,c=n//3,n//3,n//3+(n%3)
    ans=0
    while(n>2):
        ans+=n//3
        n=n//3+(n%3)
    print(ans)

for _ in range(int(input())):
    solve()

Great

Good

Neutral

Bad

Didn't Solve

If you've one $$$\color{blue}{\mathtt{B}}$$$ in string $$$s$$$ , then you'll have to do operations in $$$\mathcal{O}(n\log_2(A))$$$ which is $$$\sim \mathcal{O}(20 \cdot 30)$$$ which is fine for $$$n \le 20$$$ and $$$\sum q \le 10^4$$$ , at worst case this is roughly $$$\mathcal{O}(6 \cdot 10^5)$$$ which is safe.

If we've a string $$$s$$$ that's all $$$\color{red}{\mathtt{A}}$$$ i.e. :

then answer is simply for each $$$a_i$$$ is $$$a_i$$$ itself because we cannot do anything except just subtracting by $$$1$$$ many times ; otherwise the complexity becomes $$$\mathcal{O}(10^9q)$$$ for such cases which is slow.

Complexity $$$\mathcal{O}(nq \log_2(10^9))$$$.

def solve():
    n,q=map(int,input().split())
    s=input().strip()
    a=list(map(int,input().split()))
    A,B=s.count('A'),s.count('B')
    for i in range(q):
        if(B==0):
            print(a[i])
        else:
            ans=0
            while(a[i]):
                for j in s:
                    if(a[i]==0):break
                    ans+=1
                    if(j=='A'):a[i]-=1
                    else: a[i]//=2
            print(ans)

for _ in range(int(input())):
    solve()

Observation : The consuming part of processing the operations where a segment of $$$\underbrace{\color{red}{\mathtt{AAAAA\ldots AAA}}}_{}$$$ because we're processing one by one which is inefficient and answering query will take $$$\mathcal{O}(nq \log_2(10^9))$$$ , why ? , because processing $$$\underbrace{\color{red}{\mathtt{AAAAA\ldots AAA}}}_{}$$$ operation-by-operation is slow , for example consider the sequence $$$\underbrace{\color{red}{\mathtt{AAAAA\ldots AAA}} \color{blue}{\mathtt{B}}}_{}$$$

This case will take $$$\mathcal{O}(nq \log_2(10^9))$$$ at worst case , which is inefficient.

A good way to optimize is by compress the blocks of same type of operations as $$$(\mathrm{type},\mathrm{count})$$$ that way all long blocks of $$$\color{red}{\mathtt{A}}$$$ will be performed much faster , For blocks of $$$\color{blue}{\mathtt{B}}$$$ it's already fast to process them in order because of $$$\mathcal{O}(\log_2(a))$$$ and it reduces $$$a$$$ to $$$0$$$ in $$$\mathcal{O}(\log_2(10^9)) \sim 30$$$ at most , However compressing the operations is still better to compose the operations.

That's we're going to process at most $$$\sim 60$$$ blocks , because if we started with $$$\color{red}{\mathtt{A}}\color{blue}{\mathtt{B}}\color{red}{\mathtt{A}}\color{blue}{\mathtt{B}}\color{red}{\mathtt{A}}\color{blue}{\mathtt{B}}\ldots $$$ assuming $$$a=10^9$$$ , which is the worst case of the algorithm.

Now after composing the blocks as $$$(\mathrm{type},\mathrm{count})$$$ , you should iterate through them :

• If $$$s_i=\color{red}{\mathtt{A}}$$$ then we perform $$$a_i=a_i-\min(\mathrm{count},a_i)$$$
• If $$$s_i=\color{blue}{\mathtt{B}}$$$ then we perform $$$\displaystyle a_i=\left \lfloor \frac{a_i}{\displaystyle 2^{\min(\text{count},\lceil \log_2(n) \rceil)}} \right \rfloor$$$

make sure to update number of operations accordingly.

Complexity $$$\sim \mathcal{O}(n+q \log^2(10^9))$$$.

def solve():
    n,q=map(int,input().split())
    s=input()
    a=list(map(int,input().split()))
    A=s.count('A')
    B=s.count('B')
    last=s[0]
    seq=[] 
    cur=1
    for i in range(1,n):
        if(s[i]==last): cur+=1
        else:
            seq.append([last,cur])
            cur=1
            last=s[i]
    if(cur!=0): seq.append([last,cur])
    if(B==0):
        for i in a: print(i)
    else:
        for i in range(q):
            ans=0
            while(a[i]>0):
                for j in seq:
                    if(a[i]==0): break
                    if(j[0]=='A'):
                        mn=min(j[1],a[i])
                        ans+=mn
                        a[i]-=mn
                    else:
                        if a[i]==0: break
                        x=a[i]
                        p=0
                        while(x):
                            x//=2
                            p+=1
                        mn=min(p,j[1])
                        ans+=mn
                        a[i]//=(2**mn)
            print(ans)

for _ in range(int(input())):
    solve()

Great

Good

Neutral

Bad

Didn't Solve

We want the maximum gcd $$$g$$$ achievable after $$$\le k$$$ erases and any splits.

For a fixed $$$g$$$, the elements that won’t consume an erase are:

• all multiples of $$$g$$$ (already good), and
• any $$$x\ge 4g$$$ (can be made good via one split using the construction in hint 3).

Thus, the only "bad" numbers (that would have to be erased) are those with $$$x\lt 4g$$$ that are not multiples of $$$g$$$. Therefore $$$g$$$ is good if

Since $$$1\le a_i\le n$$$, precompute a frequency array and prefix sums $$$p[v]=\sum_{u\le v}f[u]$$$. Then

Iterate through $$$g=1,2,3,\ldots ,n$$$ and keep the largest good $$$g$$$.

Complexity : $$$\mathcal{O}(n)$$$.

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve(){
  int n,k;cin>>n>>k;
  vector<int>a(n),mp(n+1),p(n+1);
  for(auto &i:a){
     cin>>i;
     mp[i]++;
  }
  for(int i=1;i<=n;i++){
      p[i]=p[i-1]+mp[i];
  }
  int ans=1;
  for(int g=1;g<=n;g++){
    int t=min(n,4*g-1);
    int good=n-p[t];
    if(g<=n)good+=mp[g];
    if(2*g<=n)good+=mp[2*g];
    if(3*g<=n)good+=mp[3*g];
    if(good>=n-k)ans=g;
  }
  cout<<ans<<"\n";
}

signed main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;cin>>t;
  while(t--)solve();
}

Great

Good

Neutral

Bad

Didn't Solve

Recall from Hint 2 that $$$\text{bit}_k(i)$$$ is defined as $$$k$$$-th bit of the integer $$$i$$$. A naive solution using $$$n\log_2 n$$$ queries is as follows:

• Compute $$$\text{bit}_k(p_1) + \text{bit}_k(p_2) + \ldots + \text{bit}_k(p_{n - 1})$$$ for all $$$k=0,1,\ldots,\lfloor\log_2 n\rfloor$$$.

  • $$$\text{bit}_k(p_i)$$$ can be computed with a single query $$$p_i \ \mathtt{AND} \ 2^k$$$ ($$$1\le i\le n - 1$$$).

• If $$$\text{bit}_k(1) + \text{bit}_k(2) + \ldots + \text{bit}_k(n) = \text{bit}_k(p_1) + \text{bit}_k(p_2) + \ldots + \text{bit}_k(p_{n - 1})$$$, it means that the $$$k$$$-th bit of $$$p_n$$$ is zero. Otherwise, it is one.

  • This works due to the fact that $$$\text{bit}_k(p_1) + \text{bit}_k(p_2) + \ldots + \text{bit}_k(p_{n - 1}) = \text{bit}_k(1) + \text{bit}_k(2) + \ldots + \text{bit}_k(n) - \text{bit}_k(p_n)$$$.

To optimise this, we will half the search space after each step. Starting from $$$k = 0$$$, we still use $$$n - 1$$$ queries to calculate $$$\text{bit}_k(p_1) + \text{bit}_k(p_2) + \ldots + \text{bit}_k(p_{n - 1})$$$. After using this to determine the value of the $$$0$$$-th bit of $$$p_n$$$, we can discard all $$$p_i$$$ that has a different $$$0$$$-th bit from $$$p_n$$$.

More formally, let $$$S_0$$$ denote the set of elements $$$i$$$ such that $$$i$$$ has the same $$$0$$$-th bit as $$$p_n$$$, and $$$P_0$$$ denote the set of elements $$$i$$$ ($$$1\le i\le n - 1$$$) such that $$$p_i$$$ has the same $$$0$$$-th bit as $$$p_n$$$. $$$\sum_{i\in P_0} \text{bit}_1(p_i) = \left(\sum_{i\in S_0} \text{bit}_1(i)\right) - \text{bit}_1(p_n)$$$, so the $$$1$$$-st bit of $$$p_n$$$ is zero if $$$\sum_{i\in P_0} \text{bit}_1(p_i) = \sum_{i\in S_0} \text{bit}_1(i)$$$.

In general, we can let $$$S_k$$$ denote the set of elements $$$i$$$ such that $$$i$$$ has the same $$$0$$$-th, $$$1$$$-st, $$$\ldots$$$ , $$$k$$$-th bit as $$$p_n$$$, and $$$P_k$$$ denote the set of elements $$$i$$$ ($$$1\le i\le n - 1$$$) such that $$$p_i$$$ has the same $$$0$$$-th, $$$1$$$-st, $$$\ldots$$$ , $$$k$$$-th bit as $$$p_n$$$. Then, the $$$k$$$-th bit of $$$p_n$$$ is zero if $$$\sum_{i\in P_{k-1}} \text{bit}_k(p_i) = \sum_{i\in S_{k-1}} \text{bit}_k(i)$$$.

Observe that $$$|P_k| \le \left\lceil \frac{|P_{k - 1}|}{2} \right\rceil$$$ for all $$$k\ge 1$$$. Hence, the total number of queries used is

def query(index,num):
    print("?",index,num)
    return int(input())

def main():
    n = int(input())
    rest = set()
    likely = set()
    for i in range(1,n):
        rest.add(i)
    for i in range(1,n+1):
        likely.add(i)
    D = len(bin(n)[2:])
    ans = 0
    for d in range(D):
        index_0 = set()
        index_1 = set() 
        likely_0 = set()
        likely_1 = set()
        for index in rest:
            res = query(index, 1<<d)   
            if res == 0:
                index_0.add(index)
            else:
                index_1.add(index)  
        zeros = 0
        ones = 0  
        for num in likely:
            if num & (1<<d):
                ones += 1
                likely_1.add(num)
            else:
                zeros += 1
                likely_0.add(num)
        if zeros == len(index_0):
            ans += 1 << d
            rest = index_1
            likely = likely_1
        elif ones == len(index_1):
            rest = index_0
            likely = likely_0
        else:
            print("Error")
            return 
    print("!",ans)

T = int(input())
t = 1
while t <= T:
    main()
    t += 1

Great

Good

Neutral

Bad

Didn't Solve

Read the above hints before continuing.

As noted in Hint 1.2, we can binary search on the target beauty $$$g$$$.

For each index $$$1 \le i \le n$$$, recall that $$$f_g(a, i)$$$ is the number of indices $$$j\neq i$$$ satisfying $$$a_{\max(i, j)} - a_{\min(i, j)} \ge g$$$.

As mentioned in Hint 3, we only care whether $$$f_g(a, i)$$$ is $$$0$$$, $$$1$$$, $$$2$$$, or greater than $$$2$$$. We iterate through $$$i = 1, \ldots, n$$$, and maintain the three smallest previous values $$$a_j$$$ (for $$$j \lt i$$$). For each of these, we check whether the condition holds and increment both $$$f_g(a, i)$$$ and $$$f_g(a, j)$$$ if it does. This leads to an $$$\mathcal{O}(3n) = \mathcal{O}(n)$$$ computation per $$$g$$$.

We simulate each possible first move $$$p$$$ by Hao. Let array $$$b$$$ be array $$$a$$$ after removing index $$$p$$$. When Hao removes index $$$p$$$, only the $$$f_g(a, p)$$$ indices $$$q$$$ satisfying $$$|a_p - a_q| \ge g$$$ will have their $$$f_g(b, q) = f_g(a, q) - 1$$$, while all others remain unchanged.

Hao succeeds in keeping the beauty below $$$g$$$ if and only if removing index $$$p$$$ results in all $$$f_g(b, i) \le 1$$$. Equivalently, the indices $$$q$$$ paired with $$$p$$$ must include all indices that initially had $$$f_g(a, i) = 2$$$.

If no such removal $$$p$$$ works, Alex can achieve his goal of keeping the beauty at least $$$g$$$.

Checking each first move $$$p$$$ requires $$$\mathcal{O}(f_g(a, p))$$$ time, and summing up over $$$\sum_{1\le p\le n} f_g(a, p) \le 2(3n) = \mathcal{O}(n)$$$ since we only maintain at most three previous values of $$$a_j$$$ (for $$$j \lt i$$$) during the calculation of $$$f_g(a, i)$$$.

The total time complexity is $$$\mathcal{O}(n \log_2 10^9)$$$ since we perform a binary search over $$$g$$$ and compute $$$f_g(a, i)$$$ in linear time per iteration.

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

    # calculate the number of j for each i that satisfy arr[max(i,j)] - arr[min(i,j)] >= target
    def measurecount(arr,target):
        m = len(arr)
        count = [0]*m
        minimum = []
        for i in range(m):
            for j in range(len(minimum)):
                if minimum[j] + target <= arr[i]:
                    count[i] += 1
            minimum.append(arr[i])
            minimum.sort()
            if len(minimum) > 3:
                minimum.pop()
        maximum = []
        for i in range(m-1,-1,-1):
            for j in range(len(maximum)):
                if maximum[j] - target >= arr[i]:
                    count[i] += 1
            maximum.append(arr[i])
            maximum.sort(reverse=True)
            if len(maximum) > 3:
                maximum.pop()
        return count

    # binary search to judge if we can find such pair
    def judge(target):
        count = measurecount(arr,target)
        if max(count) <= 1:
            return False
        pick = []
        if max(count) > 2:
            for i in range(n):
                if count[i] > 2:
                    pick = [i]
                    break
        else:
            for i in range(n):
                if count[i] != 2: 
                    continue 
                for j in range(n):
                    if j==i: 
                        pick.append(j)
                    elif j < i and arr[j] + target <= arr[i]: 
                        pick.append(j)
                    elif j > i and arr[i] + target <= arr[j]:
                        pick.append(j)
                break

        for p in pick:
            count2 = measurecount(arr[:p]+arr[p+1:], target)
            if max(count2) <= 1:
                return False
        return True       

    front = -10**9 - 10
    rear = 10**9 + 10
    while front < rear:
        mid = front + (rear-front)//2
        res = judge(mid)
        if res:
            front = mid + 1
        else:
            rear = mid 
    ans = front - 1
    print(ans)
                       
T = int(input())
t = 1
while t <= T:
    main()
    t += 1
    

#include "bits/stdc++.h"
using namespace std;
 
const int MAXN = 200005;
const int INF = 1000000005;
 
inline int fdiv(int num, int denom) {
  return num / denom - ((num ^ denom) < 0 && num % denom);
}
inline int cdiv(int num, int denom) { return fdiv(num + denom - 1, denom); }
 
int t;
int n;
int a[MAXN];
 
vector<int> adj[MAXN];
void add_edge(int u, int v) {
  adj[u].push_back(v);
  adj[v].push_back(u);
}
bool check(int x) {
  for (int i = 1; i <= n; i++) {
    adj[i].clear();
  }
  set<pair<int, int>> st;
  for (int i = 1; i <= n; i++) {
    int cnt = 0;
    for (auto [prv, prv_id] : st) {
      if (a[i] - prv >= x) {
        add_edge(prv_id, i);
      }
    }
    st.insert({a[i], i});
    if ((int) st.size() > 3) {
        st.erase(prev(st.end()));
    }
  }
 
  int bad_cnt = 0;
  for (int i = 1; i <= n; i++) {
    if ((int)adj[i].size() >= 2) {
      bad_cnt++;
    }
  }
  for (int i = 1; i <= n; i++) {
    int delta = (int)adj[i].size() >= 2;
    for (int v : adj[i]) {
      if (adj[v].size() == 2) {
        delta++;
      }
    }
    if (delta == bad_cnt) {
      return false;
    }
  }
  return true;
}
 
int main() {
  cin >> t;
  while (t--) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
    }
    int lo = -INF, hi = INF;
    while (lo < hi) {
      int mid = cdiv(lo + hi, 2);
      if (check(mid)) {
        lo = mid;
      } else {
        hi = mid - 1;
      }
    }
    cout << lo << '\n';
  }
  return 0;
}

Great

Good

Neutral

Bad

Didn't Solve

Great

Good

Neutral

Bad

Didn't Solve

You should Read Editorial of F1 First

Let the initial permutation be $$$p=(p_1,p_2,\dots,p_n)$$$, and let the final array be $$$q=(q_1,q_2,\dots,q_n)$$$. Initialize $$$q_i=0$$$ for all $$$i$$$, meaning every position in the output is still undetermined. During the $$$t$$$-th iteration, find the smallest index $$$i$$$ whose value can be decreased to $$$t$$$. Repeatedly choose this $$$i$$$, locate indices $$$j,k$$$ such that $$$p_i=\max(p_j,p_k)+1$$$ and $$$p_i=\min(p_j,p_k)+2$$$, and perform the updates $$$p_i\leftarrow p_i-2$$$, $$$p_j\leftarrow p_j+1$$$, $$$p_k\leftarrow p_k+1$$$. This is equivalent to removing $$$p_i$$$ and setting $$$q_i\gets t$$$. After removing $$$p_i$$$, the remaining elements $$$p_1,\dots,p_{i-1},p_{i+1},\dots,p_n$$$ close the gap (preserving relative order), forming a permutation of length $$$n-1$$$.

This remove-and-assign simulation can be supported by a Fenwick tree or a segment tree so that each update and query runs in $$$\mathcal{O}(\log n)$$$ time; however, naively finding the correct index $$$i$$$ could still cost $$$\mathcal{O}(n)$$$ per step. Define the rank of $$$p_i$$$ as the number of alive (not yet removed) elements that are not greater than $$$p_i$$$, including $$$p_i$$$ itself.

To speed up the process, keep a pointer at the smallest alive index $$$i$$$ and check its rank. If the rank is odd, remove this element immediately. If the rank is even, move the pointer to the next smaller element to its right, that is, to the smallest $$$ j \gt i$$$ with $$$p_j \lt p_i$$$. Continue until you reach an element with odd rank.

Although a single "move to the next smaller on the right" step may look linear, the total number of such moves over the whole algorithm is at most $$$2n$$$. If an element is first visited when its rank is even, after some element to its right is removed, its rank becomes odd the next time it is visited; if an element’s rank is already odd, it is removed immediately upon visit. Therefore each index is visited at most twice.

To implement this, we maintain two data structures:

1. A Fenwick tree over values, where a $$$1$$$ at position $$$p_i$$$ indicates that the value $$$p_i$$$ is still alive (and $$$0$$$ otherwise). This lets you query the current rank of $$$p_i$$$ in $$$\mathcal{O}(\log n)$$$ time.

2. Let $$$ip$$$ denote the array that is the inverse of $$$p$$$, i.e., $$$ip_{p_i} = i$$$. Store a range-min segment tree over the array $$$ip$$$ . When the value $$$p_i$$$ is removed, set $$$ip_{p_i}=\infty$$$. If the current visited index is $$$i$$$, then a range-min query on $$$[1,p_i-1]$$$ returns the minimum position $$$j$$$ such that $$$j \gt i$$$ and $$$p_j \lt p_i$$$ (the next smaller element on the right by value). Each query and update costs $$$\mathcal{O}(\log n)$$$, and each index is examined at most twice, so the overall complexity is $$$\mathcal{O}(n\log n)$$$, which is sufficient for the F2 constraints.

inf = 10**9

class fenwick(object):
    def __init__(self, n):
        self.n = n
        self.cul = [0]*n
        self.maxd = len(bin(n))-3
    def update(self,index,diff):
        i = index
        while i<self.n:
            self.cul[i] += diff
            i += (i+1)&(-i-1)
    def getaccu(self,index):
        output = 0
        i = index
        while i>=0:
            output += self.cul[i]
            i -= (i+1)&(-i-1)
        return output

class segment_tree(object):
    def merge(self,num,accu):
        return min(accu,num)
    def __init__(self,n,initial):
        self.n = n
        self.inf = inf
        self.arr = [self.inf]*(2*n)
        for i in range(2*n-1,0,-1):
            if i>=n:  self.arr[i] = initial[i-n]
            else:     self.arr[i] = self.merge(self.arr[2*i],self.arr[2*i+1])

    def update(self,index,target):
        index += self.n
        self.arr[index] = target
        while index > 0:
            if index & 1:
                nexttarget = self.merge( self.arr[index], self.arr[index-1])
            else:
                nexttarget = self.merge( self.arr[index], self.arr[index+1])
            self.arr[index>>1] = nexttarget
            index = index >> 1

    def addnum(self,index,diff):
        self.update(index, self.arr[index+self.n] + diff)

    def query(self,left,right):
        i,j = self.n+left,  self.n+right+1
        output = self.inf  # initial output should be changed if you want to change the merge function
        while i<j:
            if i&1:
                output = self.merge(self.arr[i],output)
                i += 1
            if j&1:
                j -= 1
                output = self.merge(self.arr[j],output)
            i = i >> 1
            j = j >> 1
        return output

def main(t):
    n = int(input())
    p = list(map(int,input().split()))
    location = [0]*n
    for i in range(n):
        p[i] -= 1
        location[p[i]] = i 
    seg = segment_tree(n, location)
    fen = fenwick(n)
    for i in range(n):
        fen.update(i,1)
    ans = [-1]*n
    curr = 1
    for i in range(n):
        if ans[i] >= 0:  
            continue 
        index = fen.getaccu(p[i]) - 1
        if index % 2 == 0:
            fen.update(p[i],-1)
            seg.update(p[i],inf)
            ans[i] = curr 
            curr += 1
            continue
        j = i 
        while True:
            j = seg.query(0,p[j]-1) 
            nextindex = fen.getaccu(p[j]) - 1
            if nextindex % 2 > 0:
                continue 
            break
        ans[j] = curr 
        ans[i] = curr + 1
        curr += 2
        seg.update(p[i],inf)
        seg.update(p[j],inf)
        fen.update(p[i],-1)
        fen.update(p[j],-1)
    print(*ans)

T = int(input())
for t in range(T):
    main(t)

Great

Good

Neutral

Bad

Didn't Solve