WA - KSUM (LunchTime)

general
,
1

I have followed the editorial and I have done the problem in C,But I am getting wrong answer.
Here is the snippet of the code:

#include <stdio.h>
typedef struct node {
    long long  sum;
    int l_index;
    int r_index;
}node_t;

long long  A[100005];
node_t Q[100005];

/*The number of elements in Q-array*/
int N = 0;

void swap(node_t* Q ,int index,int  index2){
     
    node_t temp;
#if 0
    temp.sum = Q[index].sum;
    temp.l_index = Q[index].l_index;
    temp.r_index = Q[index].r_index;

    Q[index].sum = Q[index2].sum;
    Q[index].l_index = Q[index2].l_index;
    Q[index].r_index = Q[index2].r_index;
    
    Q[index2].sum = temp.sum;
    Q[index2].l_index = temp.l_index;
    Q[index2].r_index = temp.r_index;

#endif
    temp = Q[index];
    Q[index] = Q[index2];
    Q[index2] = temp;
}

void insert(node_t * Q,long long sum, int l_index, int r_index){
    
    int index;
    
    N=N+1;
    
    index = N;

    Q[N].sum = sum;
    Q[N].l_index = l_index;
    Q[N].r_index = r_index;
    
    /*This is the concept of heapify up*/
    while(index > 1 && Q[index/2].sum < Q[index].sum) {
        swap(Q,index/2,index);
        index/=2;
    }

}

/*This uses the concept of heapify down*/
void  max_heapify(node_t* Q, int index){
    
    int largest,left,right;
    
    left=2*index;
    right=2*index+1;

    if(right<=N && Q[index].sum < Q[right].sum)
        largest=right;
    else
        largest=index;

    if(left<=N && Q[largest].sum < Q.sum)
        largest=left;
    
   if(largest != index){
        swap(Q,index,largest);
        max_heapify(Q,largest);
    }
}

int main() {
    
    int  n, k, i, left, right;
    long long sum = 0;
    node_t temp;

    scanf("%d%d", &n, &k);

    for(i = 1; i <= n; i++) {
        scanf("%lld", A + i);
        sum += A[i];
    }
  
    /*We will insert the sum*/
    insert(Q, sum, 1, n);
    
    /*We will loop only through the min((n*(n+1)/2, 10^5)*/
    for(i = 0; i < k; i++) {
        
        temp = Q[1];
        left =  temp.l_index;
        right = temp.r_index;
        Q[1].sum = -1;
        
        max_heapify(Q, 1);

        N--;
        printf("%lld ", temp.sum);

        if(left != right) {
            
            insert(Q, temp.sum - A, left + 1, right);
            insert(Q, temp.sum - A[right], left, right - 1);
        }
        
    }
    
    printf("\n");

    return 0;
}
2

My guess: You’re counting intervals multiple times. For example [2.n-1] might get inserted twice, smaller intervals even more often. In the tutorial a set is used instead if a priority queue, thereby eliminating duplicates.

1 Like