LOTTERYTICK - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author:
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

There are N lottery tickets, all with distinct numbers A_1, A_2, \ldots, A_N.
Chef bought ticket A_1.

The lottery number is chosen to be an integer X in [1, 10^6], and anyone whose ticket is closest to X wins the lottery.
How many lottery numbers result in a win for Chef?

EXPLANATION:

Let’s look at only lottery numbers with values \leq A_1 first.
Note that for such a winning number, the only thing that really matters is the closest A_i to A_1 that’s smaller than it.

Let L \lt A_1 be the closest lottery ticket to A_1 that’s smaller than it.
That is, L is the maximum of all lottery tickets with numbers smaller than A_1.

For any X \leq A_1, if X is closer to A_1 than it is to L (or the distance is tied), Chef will win with this X.
This is because:

  • Since X \leq A_1, A_1 is certainly closer to X than any A_i \gt A_1 can be.
  • L is the closest value to A_1 that’s smaller than it. This means that for any other A_i \lt A_1, we also have A_i \lt L.
    But then X is closer to A_1 than L, so X is certainly closer to A_1 than anything smaller than L too.

So, once L is known, we only need to count the number of X \leq A_1 that are closer to A_1 than L.
This is quite simple: we want A_1 - X \leq X - L to hold, meaning X \geq \frac{A_1 + L}{2}.

Since X must be an integer, we take the ceiling to obtain X \geq \left\lceil \frac{A_1 + L}{2} \right\rceil.

The number of valid X is thus the length of the range [\left\lceil \frac{A_1 + L}{2} \right\rceil, A_1].

Note that there’s one edge case: it’s possible that A_1 is the smallest among all the A_i, i.e., no valid value of L exists.
In this case, every X from 1 to A_1 is valid instead.

The above discussion was for X \leq A_1.
X \gt A_1 is similar, just that we use the nearest value to the right of A_1 instead.
Again, if no other A_i is \gt A_1, every X till 10^6 is valid.

Add up the results of both sides to get the overall answer.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    left, right = 1, 10**6
    for y in a[1:]:
        if y < a[0]: left = max(left, a[0] - (a[0] - y)//2)
        else: right = min(right, a[0] + (y - a[0])//2)
    print(right - left + 1)
2 Likes
2

in case of a tie all of them are winners wasn’t not clear enough, as it could mean both all the players or the 2 players

1 Like
3 
#include <stdio.h>
#include <math.h>
void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    
    int L[n1], R[n2];

    
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
void mergeSort(int arr[], int l, int r)
{
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);
    }
}
int index_finder(int n,int A[],int m){
    for (int i=0;i<n;i++){
        if (A[i]==m){
            return i;
        }
    }
}
int mid_calculate(int i,int A[], char s){
    if (s == 'U'){
        return (A[i]+A[i+1])/2;
    }
    else if (s == 'D'){
        int k=(A[i]+A[i-1]);
        if (k%2==0){
            return k/2;
        }
        else{
            return k/2 +1;
        }
    }
}
int main() {
	// your code goes here
    int t;
    scanf("%d",&t);
    while(t--){
        int n,r=0;
        scanf("%d",&n);
        int A[n];
        for (int i=0;i<n;i++){
            scanf("%d",&A[i]);
        }
        int m=A[0];
        mergeSort(A,0,n);
        int index=index_finder(n,A,m);
        
        int mid1,mid2;
        
        if (index!=n-1){
            mid1= mid_calculate(index,A,'U');
            r+= mid1-A[index]+2;
            if (index>0){
                mid2= mid_calculate(index,A,'D');
                r+= A[index]-mid2;
            }
            
        }
        else  {
            r+= 1000001-A[index];
            if (index>0){
                mid2= mid_calculate(index,A,'D');
                r+= A[index]-mid2;
            }
        }

        printf("%d\n",r);
    }
}

what was the problem in my approach and code?

4

Problem is not clear at all , if its written all of them it should mean the entire array is the winner not the ones in between whom tie is being decided. Please mention clearly from next time. Thanks