Slowdown Sprint#12234

Slowdown Sprint (Editorial)

Problem Author:	Imran AKKI
Prepared by:	Imran AKKI
Edited by:	Hasan Saleh (MathModel)

Solution The problem is equivalent to get the total distance travelled by each contestant and compute how many contestants who travelled strictly more than Bob did.

Let's simulate the total travelled distance for some speed $s$ and decrement of speed $t$ , at each step you'll continue to decrease original $s$ by a multiple of $t$ as long as it's positive , Formally the total distance $d$ will be

d = s + (s - t) + (s - 2 t) + (s - 3 t) + .... + (s - k t)

\displaystyle d=s+(s-t)+(s-2t)+(s-3t)+....+(s-kt)

Here $k = ⌊ \frac{s - 1}{t} ⌋$ k=\lfloor \frac{s-1}{t} \rfloor , which is the maximum positive speed we can reach.

To calculate the distance , notice that $s$ appears $k + 1$ k+1 times and we've $(1 + 2 + 3 + ... + k) t$ (1+2+3+...+k)t as of in the negative part and we know $1 + 2 + 3 + ... + k = \frac{k ( k + 1 )}{2}$ 1+2+3+...+k=\frac{k(k+1)}{2} then the total distance is computed as

= s \times k - t \times \frac{k ( k + 1 )}{2}

\displaystyle = s \times k - t \times \frac{k(k+1)}{2}

Now according to this , compute distance for $i_{t h}$ i_{th} contestant as $d_{i}$ d_i sort values and count how many contestants ran more than Bob.

for _ in range(int(input())):
    n,b=map(int,input().split())
    s=list(map(int,input().split()))
    t=list(map(int,input().split()))
    a=[]
    want=-1
    for i in range(n):
        x=s[i]
        r=(s[i]-1)//t[i]
        x+=s[i]*r
        v=(r*(r+1))//2
        x-=v*t[i]
        a.append(x)
        if(i+1==b):
            want=x
    a.sort()
    ans=1
    for i in range(n-1):
        if(a[i]==want and a[i+1]>want):
            ans=n-i
            break
    print(ans)

Python

Complexity $O (n lo g n)$ \mathcal{O}(n \log n).