सुझाव Spoj

Question

मैं एक समस्या जो कुछ इस तरह है हल करने के लिए कोशिश कर रहा हूँ पर टीएलई पारित करने के लिए:

मैं दिया हूँ n संख्या (1 < = n < = 10^5) .मैं अपने बाईं ओर सभी संख्याओं का योग लिखना है जो वर्तमान संख्या से छोटे हैं और सभी एन संख्याओं के लिए प्रक्रिया दोहराएं। फिर मुझे पहले प्राप्त प्राप्त राशि का योग मिलना होगा। (प्रत्येक संख्या एन, 0 < = एन < = 10^6)।

उदाहरण के लिए,

1 5 3 6 4 
less1 less5 less3 less6 less4 
(0) + (1) + (1)+(1+5+3)+(1+3) 
    0 + 1 + 1 + 9 + 4 
= 15 

इस समस्या के लिए एक तुच्छ समाधान दो छोरों को चलाने के लिए किया जाएगा और दिए गए नंबर से प्रत्येक के लिए सभी नंबरों कि संख्या से कम की राशि मिल जाती है और अंत में उन की राशि देना योग आउटपुट के रूप में है। समय जटिलता ओ (एन^2) है।

मुझे लगता है कि बाइनरी इंडेक्सेड ट्री (फेनविक ट्री) का उपयोग करके इस समस्या के लिए एक बेहतर ओ (nlogn) समाधान है। प्रत्येक नंबर के लिए मैं प्रत्येक संख्या को वैश्विक सरणी में जोड़ दूंगा और बीआईटी के दो स्पष्ट संचालन करूँगा। मुझे लगता है कि इस एल्गोरिदम की समय जटिलता ओ (nlogn) है जो सत्य पिछले ओ (एन) से स्पष्ट रूप से बेहतर है^2)।

मैंने कोड को ++ में लागू किया है।

#include<iostream> 
#include<cstdio> 

using namespace std; 

#define max 1000001 

long int a[max]; 

void add(long int v,int idx){ 
while(idx<max){ 
    a[idx] += v; 
    idx += (idx & -idx); 
} 
} 

long int sum(int idx){ 
long int s=0; 
while(idx>0){ 
    s += a[idx]; 
    idx -= (idx & -idx); 
} 
return s; 
} 

int main() 
{ 
int t; 
scanf("%d",&t); 
for(int w=0;w<t;w++){ 
    int n; 
    scanf("%d",&n); 

    for(int i=0;i<max;i++) 
     a[i]=0; 

    int arr[n]; 
    for(int i=0;i<n;i++) 
     scanf("%d",&arr[i]); 

    long long res=0; 

    for(int i=0;i<n;i++){ 
     if(arr[i]!=0){ 
      add(arr[i],arr[i]); 
      res += (sum(arr[i]-1)); 
        } 
    } 

    printf("%lld\n",res); 
} 

return 0; 
} 

मैं दो प्रश्न हैं:

पहले, मैं यह सही कर रहा हूँ?/क्या मेरा तर्क सही है?

दूसरा, अगर मैं समय जटिलता के बारे में सही हूं तो ओ (nlogn) होने के बाद यह धीमा क्यों चलता है? क्या आप किसी और अनुकूलन के साथ मेरी मदद कर सकते हैं?

1.41 सेकंड के साथ स्वीकार्य हो गया। साथ ही मैंने अपना आखिरी स्वीकृत कोड अपडेट किया है। अनुकूलन के लिए कोई सुझाव?

टिप्पणियों के आधार पर मैं तेजी आई/ओ के लिए अपने खुद के समारोह की कोशिश की, लेकिन अभी भी यह मेरी है.यह नहीं हो रहा है तेजी से आई/ओ के लिए मेरे समारोह है:

inline int read(){ 
char c=getchar_unlocked(); 
int n=0; 
while(!(c>='0' && c<='9')) 
    c=getchar_unlocked(); 

while(c>='0' && c<='9'){ 
    n=n*10 + (c-'0'); 
    c=getchar_unlocked(); 
} 
return n; 
} 

यह समस्या के लिए लिंक है :

http://www.spoj.pl/problems/DCEPC206/

अगर ऐसा कोई है जो इसे हल करने विकलांगों है, तो कृपया मुझे बताएं। धन्यवाद।

Answer 1

मुझे लगता है कि अपने दृष्टिकोण एक अच्छा एक है। मैंने इस के साथ बहुत कम खेला है और आपके पास जो कुछ भी है उससे आम तौर पर कुछ भी नहीं आया है।

हालांकि आपके कोड में कुछ बग हैं। पूर्णांक अतिप्रवाह से पीड़ित कुछ जगहें हैं। आप बदलना चाहिए करने के लिए:

long long a[max]; 

और

long long sum(int idx){ 
long long s=0; 

अधिक स्पष्ट बग कि आप संख्याओं जो वर्तमान संख्या को कम से कम या बराबर हैं संक्षेप रहे हैं। इस समस्या को हल करने के लिए, आप प्रत्येक मूल्य की गिनती पर नज़र रखने के लिए एक दूसरे वैश्विक सरणी जोड़ सकते हैं:

int b[max]; 
... 
... 
    for(int i=0;i<max;i++) 
     a[i]=b[i]=0; 
    ... 
    ... 
     res += (sum(idx)-(++b[idx]*val)); 

कि बग को ठीक करने का सबसे प्रभावशाली तरीका हो सकता है, लेकिन कुल मिलाकर यह अभी भी एक तेजी से समाधान की तरह लगता है।

Answer 2

यहां एक और दृष्टिकोण है: समस्या उलटा गिनने के समान है, सिवाय इसके कि आपको इनवर्जन उत्पन्न करने के लिए जिम्मेदार तत्वों को जोड़ना होगा। हम मर्ज सॉर्ट का उपयोग करके इसे हल कर सकते हैं। इस तरह मर्ज समारोह संशोधित करें:

merge(left, middle, right, array) 
    temp = new array 
    k = 0, i = left, j = middle + 1 

    while i <= middle and j <= right 
    if array[i] < array[j] 
     temp[k++] = array[i] 
     // array[i] is also smaller than all array[j+1], ..., array[right] 
     globalSum += array[i] * (right - j + 1) 
    else 
     // same as the classical function 

Intuitively, मैं कहूंगा कि एक पुनरावर्ती mergesort थोड़ा समाधान की तुलना में धीमी है, लेकिन कौन जानता है? कोशिश करो।

संपादित करें: यह हो जाता है एसी:

#include<stdio.h> 
#include <iostream> 

using namespace std; 

#define max 100001 

int n; 
long long res = 0; 

int temp[max]; 
int arr[max]; 
void merge(int left, int m, int right) 
{ 
    int k = 0; 
    int i = left, j = m + 1; 
    while (i <= m && j <= right) 
     if (arr[i] < arr[j]) 
     { 
      temp[k++] = arr[i]; 
      res += (long long)(right - j + 1) * arr[i++]; 
     } 
     else 
      temp[k++] = arr[j++]; 

    while (j <= right) 
     temp[k++] = arr[j++]; 
    while (i <= m) 
     temp[k++] = arr[i++]; 

    for (int i = 0; i < k; ++i) 
     arr[left + i] = temp[i]; 
} 

void sort(int left, int right) 
{ 
    if (left < right) 
    { 
     int m = left + (right - left)/2; 
     sort(left, m); 
     sort(m + 1, right); 
     merge(left, m, right); 
    } 
} 

int main() 
{ 
    int t; 
    scanf("%d", &t); 
    for(int w=0;w<t;w++) 
    { 
     scanf("%d", &n); 
     for(int i=0;i<n;i++) 
      scanf("%d", &arr[i]); 

     res=0; 
     sort(0, n - 1); 

     printf("%lld\n",res); 
    } 

    return 0; 
}