SEQSEARCH - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: harsh_h
Tester: mexomerf
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Binary search

PROBLEM:

A sequence X is defined as:

  • X_1 = 0, X_2 = A, X_3 = B
  • X_i = X_{i-1} + X_{i-2} - X_{i-3} for i \gt 3.

Find the K'th smallest element of this sequence.

EXPLANATION:

Let’s look at a few further terms of the sequence

\begin{aligned} X_3 &= A+B \\ X_4 &= A+B+B-A = 2B \\ X_5 &= 2B + A+B - B = A+2B \\ X_6 &= A+2B+2B-(A+B) = 3B \\ X_7 &= 3B + A+2B - 2B = A+3B \\ \vdots \end{aligned}

We see something of a pattern here: the odd terms are of the form A+x\cdot B, while the even terms are of the form x\cdot B.
This does indeed hold.

Proof

We use induction.

Our claim is that:

X_{2i} = A + B\cdot i \\ X_{2i+1} = B\cdot i

This is of course true for X_1, X_2, X_3, which will be our base cases.
Let’s look at further indices.

Suppose N = 2i where N\gt 3. Then,

\begin{aligned} X_{2i} &= X_{2i-1} + X_{2i-2} - X_{2i-3} \\ &= A + B\cdot (i-1) + B\cdot (i-1) - (A + B\cdot (i-2)) \\ &= B\cdot (i-1 + i-1 - (i-2)) \\ &= B\cdot i \end{aligned}

Similarly, if N = 2i+1 and N \gt 3, we have

\begin{aligned} X_{2i+1} &= X_{2i} + X_{2i-1} - X_{2i-2} \\ &= B\cdot i + (A + B\cdot (i-1)) - B\cdot (i-1) \\ &= B + (A + B\cdot (i-1)) \\ &= A + B\cdot i \end{aligned}

This proves our claims.

Let’s use this to find the K'th smallest element.
The even and odd terms are individually simple enough - they start at A or 0 respectively, and then keep increasing by B, forming an arithmetic progression.

This allows us to binary search for the answer.
That is, consider the function f(x) = number of elements in the sequence that are \leq x.
We’ll find the smallest x such that f(x) \geq K: that will be our answer.

To compute f(x), we look at the even and odd terms separately.

  • The odd terms are 0, B, 2B, 3B, \ldots
    n\cdot B \leq x if and only if n \leq \frac{x}{B}.
    So, we want to count the number of non-negative integers that are \leq \frac{x}{B}.
    This is exactly
1 + \left\lfloor \frac{x}{B} \right\rfloor
  • The even terms are A, A+B, A+2B, \ldots
    A+n\cdot B \leq x if and only if n \leq \frac{x-A}{B}
    Again, the count of such n is
1 + \left\lfloor \frac{x-A}{B} \right\rfloor

\left\lfloor \ \cdot\ \right\rfloor here is the floor function.

Note that in the second case, if x \lt A then the count of valid n is in fact 0 - make sure to take care of that correctly.

Now that a single f(x) can be computed in \mathcal{O}(1) time, we simply use binary search to find the answer.

The only remaining thing to think about is the initial bounds of the binary search.
The lower bound is clearly 0, since X_1 = 0.
As for the upper bound: a simple upper bound is K\cdot B, which for our constraints is \leq 10^{18}.
So, you can safely always choose 10^{18} as an upper bound.

A slightly more strict upper bound on the answer is A + \frac{K}{2}\cdot B.

It is also possible to further exploit the pattern and solve this problem in constant time with a bit of casework, which can be seen in the tester’s solution below.

TIME COMPLEXITY:

\mathcal{O}(\log (A+K\cdot B)) per testcase.

CODE:

Tester's code (C++) 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
    int t;
    cin>>t;
    while(t--){
        int a, b, k;
        cin>>a>>b>>k;
        int temp = (a / b);
        if(k <= temp + 1){
            cout<<(k - 1) * b<<"\n";
        }else{
            if(k % 2 == temp % 2){
                cout<<a + ((k - temp - 1) / 2) * b<<"\n";
            }else{
                cout<<(temp + ((k - temp) / 2)) * b<<"\n";
            }
        }
        
    }
}
Editorialist's code (Python) 
for _ in range(int(input())):
    a, b, k = map(int, input().split())
    
    lo, hi = 0, 10**18
    while lo < hi:
        mid = (lo + hi)//2

        # 0, a, b, a+b, 2b, a+2b, 3b, a+3b, ...
        # odd terms: x*b
        # even terms a + x*b

        # odd terms: x*b <= mid -> x <= floor(mid/b)
        ct = mid//b + 1

        # even terms: a + x*b <= mid -> x <= floor((mid-a)/b)
        if a <= mid: ct += (mid-a)//b + 1

        if ct >= k: hi = mid
        else: lo = mid+1
    print(lo)
1 Like
2

Can you explain the tester’s code.

3

can be solved without binary search too ,
the pattern is as follows
0 , B , 2*B , … x * B , A , (x+1)B , A + 1B , (x+2)B , A + 2B , (x+3)B , A + 3B.

1 Like
4

Can someone help me find a case for this problem? I even tried stress testing but all cases passed.
https://www.codechef.com/viewsolution/1088802682

void solve()
{
    int a, b, k;
    cin >> a >> b >> k;



    k--;

    int start = 0; // 0 se kam hi lunga elements
    int end = 1e18;
    pair < int, int > store;

    while (start <= end)
    {
        int mid = start + (end - start) / 2;

        int x = mid / b;
        int y;
        if (mid >= a)
            y = 1 + (max(0ll, mid - a)) / b;
        else
            y = 0;

        if (x + y <= k)
        {
            store = {
                x,
                y
            };
            start = mid + 1;
        }
        else
            end = mid - 1;
    }

    int left = k - (store.first + store.second);
    int x = b * store.first;
    int y;
    if (store.second == 0)
        y = 0;
    else
        y = a + b * (store.second - 1);

    while (left--)
    {
        if (x <= y)
            x += b;
        else
            y += b;
    }

    cout << max(x, y) << endl;
}
5

Found it easier to spam kth smallest of 2 sorted arrays Binary Search after realising its 2 linear sequences
https://www.codechef.com/viewsolution/1088620737

6

I tried developing a recurrence equation for the same and it did seem to work for the cases that I could think of, kindly let me know what case am I missing?

using System;
using System.Linq;
using System.Text;
using System.Numerics;
using System.Collections.Generic;

public class Test
{
	public static void Main()
	{
		// your code goes here
		int T = int.Parse(Console.ReadLine());
		StringBuilder v = new StringBuilder();
		for(; T > 0; T--)
		{
		    string[] ip = Console.ReadLine().Split(' ');
		    long A = long.Parse(ip[0]);
		    long B = long.Parse(ip[1]);
		    long K = long.Parse(ip[2]);
		    if(A > B)
		    {
		        if((K & 1) == 1)
		            K--;
		        else
		            K++;
		    }
	        long ans = 0;
	        if((K & 1) == 1)
	            ans = B * (K - 1) / 2;
	        else
	            ans = (2 * (A - B) + (B * K)) / 2;
            v.Append(ans);
		    v.Append("\n");
		}
		Console.Write(v);
	}
}
7

Try this:

1
4 1 5
1 Like
8

Recognised the pattern but missed the point that before starting with first A, there can be multiple elements with B possible ( B , 2*B , … x * B , A ).

1 Like
9

Thanks a lot!

10

Thanks

11

thanks a lot…you saved me a lot of time and debugging

12

Binary search correct solution:-

    int lo = 0;
    int hi = 1e18;
    int ans = 0;

    auto check = [&](int x){
        int p = x / b  + 1;
        int q = x < a ? 0 : (x - a) / b  + 1;
        return p + q >= k;
    };

    while(lo <= hi){
        int mid = (hi + lo)/2;
        if(check(mid)){
            ans = mid;
            hi = mid - 1;
        }else{
            lo = mid + 1;
        }
    }

    cout<<ans<<endl;

PS: int is long long in my template, so no worries.

1 Like
13

@iceknight1093 a question, when we find x with binary search, what guarantees that x is part of the sequence, in other words what guarantees that x can be written either x = n.B or x = A + n.B ?
whether x is even or odd we count the number of lower or EQUAL elements in both cases, while x cannot be both even and odd

14

In the middle of the binary search, nothing (and no such claim was made).
The only guarantee is that the final value of x will appear in the sequence.

We’re binary searching to find the smallest x such that f(x) \geq K, meaning that at least K terms of the sequence are \leq x.
This was the smallest x, meaning f(x-1) \lt K; in particular f(x) \neq f(x-1).
f(x-1) and f(x) differ only in the count of x appearing in the sequence; so them being unequal means x does appear in the sequence (and is hence the K-th smallest element of the sequence).