We want to count how many times we can choose $$$i$$$ and $$$j$$$ such that $$$a_i = a_j$$$. Suppose $$$f_x$$$ stores the frequency of $$$x$$$ in $$$a$$$. Once we choose $$$a_i = a_j = x$$$, $$$f_x$$$ is subtracted by $$$2$$$. Thus, the answer is the sum of $$$\lfloor \frac{f_x}{2} \rfloor$$$ over all $$$x$$$.

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    print(sum([a.count(x) // 2 for x in range(n + 1)]))

It is worth noting that test $$$4$$$ is especially made to blow up python dictionaries, sets, and Collections.counter. If you are time limit exceeding, consider using a frequency array of length $$$n$$$.

You must check if you can find two integers $$$n$$$ and $$$m$$$, such that $$$n \cdot m+2=k$$$. You can either use a counter, or use two pointers. Do note that $$$n^2+2=k$$$ is an edge case that must be separated if you use a counter to implement it. This edge case does not appear in the two pointers approach. Time complexity is $$$O(n \log n)$$$ (assuming you are wise enough to not use a hash table).

testcases = int(input())
for _ in range(testcases):
    k = int(input())
    list = input().split()
    freq = []
    for i in range(k+1):
        freq.append(0)
    for x in list:
        freq[int(x)] = freq[int(x)]+1
    solution = (-1,-1)
    for i in range(1,k+1):
        if i*i==k-2:
            if freq[i]>1:
                solution = (i,i)
        elif (k-2)%i==0:
            if freq[i]>0 and freq[(k-2)//i]>0:
                solution = (i, (k-2)//i)
    print(solution[0], solution[1])

Remember that all even numbers greater than $$$2$$$ are composite. As $$$1+3 \gt 2$$$, any two numbers with same parity sum up to a composite number. Now you only have to find one odd number and one even number that sum up to a composite number. One can manually verify that there is no such pair in $$$n \leq 4$$$, but in $$$n=5$$$ there exists $$$(4,5)$$$ which sums up to $$$9$$$, a composite number.

for _ in range(int(input())):
    n = int(input())
    if n < 5:
        print(-1)
        continue
    for i in range(2,n+1,2):
        if i != 4:
            print(i,end=" ")
    print("4 5",end=" ")
    for i in range(1,n+1,2):
        if i != 5:
            print(i, end = " ")
    print()

Process from earliest to latest. Maintain a priority queue of power-ups left so far. If Mualani meets a power-up, add it to the priority queue. Otherwise (Mualani meets a hurdle), take power-ups in the priority queue from strongest to weakest until you can jump over the hurdle. This guarantees that each time Mualani jumps over a hurdle, she takes the minimum number of power-ups necessary. Time complexity is $$$O((n+m)\log m)$$$, where $$$O(\log m)$$$ is from the priority queue.

Note that the hurdle intervals are inclusive. If there is a hurdle at $$$[l, r]$$$, she must jump from position $$$l-1$$$ to $$$r+1$$$.

import sys
import heapq
input = sys.stdin.readline
for _ in range(int(input())):
    n,m,L = map(int,input().split())
    EV = []
    for _ in range(n):
        EV.append((*list(map(int,input().split())),1))
    for _ in range(m):
        EV.append((*list(map(int,input().split())),0))
    EV.sort()
    k = 1
    pwr = []
    for a,b,t in EV:
        if t == 0:
            heapq.heappush(pwr,-b)
        else:
            while pwr and k < b-a + 2:
                k -= heapq.heappop(pwr)
            if k < b-a + 2:
                print(-1)
                break
    else:
        print(m-len(pwr))

Notice that for if for some $$$r$$$ we have $$$f(1, r) \lt f(1, r + 1)$$$ then we can conclude that $$$s_{r + 1} = 1$$$ (if it is $$$0$$$ then $$$f(1, r) = f(1, r + 1)$$$ will be true) and if $$$f(1, r)$$$ is non-zero and $$$f(1, r) = f(1, r + 1)$$$ then $$$s_{r + 1}$$$ is $$$0$$$.

Unfortunately this is only useful if there is a $$$0$$$ in $$$s_1,s_2,...,s_r$$$, so the next thing can try is to find is the value of the longest prefix such that $$$f(1, r)$$$ is $$$0$$$ (after this point there will be a zero in all prefixes).

See that if $$$f(1, r) = 0$$$ and $$$f(1, r + 1) = k$$$ then $$$s_{r + 1} = 1$$$, the last $$$k$$$ characters of $$$s_1,s_2,...,s_r$$$ must be $$$0$$$ and the first $$$r - k$$$ characters must be $$$1$$$. To prove this we can argue by contradiction, suppose it is not true and then it will become apparent that some shorter prefix will be non-zero when we query it.

The one case that this does not cover is when all prefixes are zero, from similar contradiction argument as above we can see that the string must look like $$$111...1100....000$$$ in this case, in this case it is not hard to see that all queries will give a value of zero, and thus we can report that it is impossible.

So we should query all prefixes, the first one which is non-zero (if this does not exist we can report impossible) we can deduce its value as discussed above, then there will be a $$$0$$$ in the prefix so we can deduce all subsequent characters as discussed at the start.

def qu(a,b):
    if (a,b) not in d:
        print("?", a+1,b+1)
        d[(a,b)] = int(input())
    return d[(a,b)]
for _ in range(int(input())):
    d = dict()
    n = int(input())
    SOL = ["0"] * n
    last = qu(0,n-1)
    if last:
        z = 1
        for i in range(n-2,0,-1):
            nw= qu(0,i)
            if nw != last:
                SOL[i+1] = "1"
            last = nw
            if last == 0:
                z = i+1;break
        if last:
            SOL[1] = "1"
            SOL[0] = "0"
        else:
            last = 1
            for j in range(z-2,-1,-1):
                nw = qu(j,z)
                if nw == last:
                    SOL[j] = "1"
                last = nw
        print("!","".join(SOL))
    else:
        print("! IMPOSSIBLE")

Let's perform binary search on the minimum number of hits to kill at least $$$k$$$ enemies. How do we check if a specific answer is possible?

Let's consider a single enemy for now. If its health is $$$h_i$$$ and we need to kill it in at most $$$q$$$ attacks, then we need to be doing at least $$$\lceil\frac{h_i}{q}\rceil$$$ damage per attack to this enemy. If this number is greater than $$$m$$$, then obviously we cannot kill this enemy in at most $$$q$$$ attacks as the maximum damage Xilonen can do is $$$m$$$ damage per hit. Otherwise, we can model the enemy as a valid interval where we can place Xilonen. Specifically, the inequality $$$m-|p-x|\geq\lceil\frac{h_i}{q}\rceil$$$ must be satisfied.

Now that we have modeled each enemy as an interval, the problem is reduced to finding whether or not there exists a point on at least $$$k$$$ intervals. This is a classic problem that can be approached by a sweep-line algorithm, sorting the events of intervals starting and ending by time and adding $$$1$$$ to your counter when an interval starts and subtracting $$$1$$$ to your counter when an interval ends.

Note that the maximum possible answer to any setup with a solution is $$$\max( h_i)=10^9$$$, so if we cannot kill at least $$$k$$$ enemies in $$$10^9$$$ attacks then we can just output $$$-1$$$ as our answer.

The total time complexity is $$$O(n\log({n})\log({\max(h_i)})$$$.

import sys
input = sys.stdin.readline
from collections import defaultdict
for _ in range(1):
    n,m,k = map(int,input().split())
    h = list(map(int,input().split()))
    x = list(map(int,input().split()))
    lo = 0
    hi = int(1e10)
    while hi - lo > 1:
        mid = (lo + hi) // 2
        ev = defaultdict(int)
        for i in range(n):
            ma = (h[i] + mid - 1) // mid
            if ma > m: continue
            ev[x[i]-m+ma] += 1
            ev[x[i]+m-ma+1] -= 1
        sc = 0
        for y in sorted(ev.keys()):
            sc += ev[y]
            if sc >= k:
                hi = mid
                break
        else:
            lo = mid
    if hi == int(1e10):
        print(-1)
    else:
        print(hi)

Denote $$$dp[i]=$$$ the number of ways to get to city $$$i$$$. Brute-forcing all possible previous cities is out of the question, as this solution will take $$$O(n^2\cdot\log({\max{a_i}}))$$$ time complexity. What else can we do?

Instead, consider caseworking on what the greatest common factor can be. Let's keep track of an array $$$count$$$ which for index $$$i$$$ keeps track of the sum of $$$dp$$$ values of all previous cities who has a factor of $$$i$$$. Say the current city has attractiveness $$$a_i$$$. We can almost recover $$$dp[i]$$$ by adding up the $$$count$$$ values of all factors of $$$a_i$$$. Unfortunately, this fails as it overcounts many instances. For example, if $$$\gcd(a_i, a_j)=12$$$ the $$$dp$$$ state from $$$i$$$ will be counted five times: $$$2, 3, 4, 6, 12$$$.

Note that we don't actually care what the greatest common factor is, since the only requirement is that the greatest common factor is not $$$1$$$. This also means that repeat appearances of the same prime number in the factorization of $$$a_i$$$ doesn't matter at all — we can assume each prime factor occurs exactly once. Now, if $$$\gcd(a_i, a_j)=12$$$, it is only counted three times: $$$2,3,6$$$. Now, instead of blindly adding the $$$count$$$ values from all previous states, let's instead apply the Principle of Inclusion-Exclusion on the prime factors. Let's first add the $$$count$$$ values from all prime factors, then subtract the $$$count$$$ values from all factors with two prime factors, then add the $$$count$$$ values from all factors with three prime factors, and so on. It can be seen that actually, the value is only counted one time now.

So what's the time complexity of this solution? Precomputing the set of all prime number takes $$$O(\max(a_i)\log(\max(a_i)))$$$ time (by the harmonic series $$$\frac{n}{1}+\frac{n}{2}+\ldots+\frac{n}{n}\approx n\log(n)$$$). For each number $$$a_i$$$, we have to consider all $$$2^{f(a_i)}$$$ subsets of prime factors, where $$$f(a_i)$$$ is the number of prime factors of $$$a_i$$$. The number with the most distinct prime factors is $$$510510=2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17$$$, so worst case $$$2^7=128$$$ operations are needed per number. This goes to a total operation count of approximately $$$128\cdot n$$$ which will pass in the time limit.

Note that we may also use the Mobius function to compute the answer. The Mobius function's properties makes it utilize the Principle of Inclusion-Exclusion efficiently. The time complexity of this solution is $$$O(\max(a_i)\log(\max(a_i))+n\max(d(a_i)))$$$ where $$$d(a_i)$$$ is the maximum number of factors of $$$a_i$$$. This time complexity can be shown to be the same as the above time complexity.

import sys

def input():
    return sys.stdin.buffer.readline().strip()

MOD = 998244353
ma = int(1e6 + 5)
P = [1] * ma
D = [[] for _ in range(ma)]
for i in range(2, ma):
    if P[i] == 1:
        for j in range(i, ma, i):
            P[j] = i
F = [0] * ma
LU = [0] * ma
BMS = [[] for _ in range(ma)]
RES = []
from itertools import combinations
def getBMS(x):
    if not BMS[x]:
        y = help(x)
        for i in range(len(y)):
            p = combinations(y, i + 1)
            for a in p:
                xx = 1
                for j in a:
                    xx *= j
                BMS[x].append((xx,i))
    return BMS[x]
def helps(x):
    y = x
    while x != 1:
        s = P[x]
        D[y].append(s)
        while x % s == 0:
            x //= s


def help(x):
    if not D[x]: helps(x)
    return D[x]




for yy in range(int(input())):
    n = int(input())
    A = list(map(int, input().split()))
    for xx,i in getBMS(A[0]):
        F[xx] = 1
        LU[xx] = yy
    for i in range(1, n - 1):
        tot = 0
        for xx, j in getBMS(A[i]):
            if LU[xx] != - 1 and LU[xx] != yy:
                F[xx] = 0
            LU[xx] = yy
            if F[xx]:
                if j % 2:
                    tot -= F[xx]
                    tot %= MOD
                else:
                    tot += F[xx]
                    tot %= MOD
        for xx, j in getBMS(A[i]):
            F[xx] += tot
            F[xx] %= MOD
    S = 0
    for xx,i in getBMS(A[-1]):
        if LU[xx] != - 1 and LU[xx] != yy:
            LU[xx] = yy
            F[xx] = 0
        if F[xx]:
            if i % 2:
                S -= F[xx]
                S %= MOD
            else:
                S += F[xx]
                S %= MOD

    RES.append(str(S))
print("\n".join(RES))