NAMELESS's blog

By NAMELESS, history, 14 months ago, In English,

Hello everyone,

I am trying to solve this problem. If I can build the LCP array with O(n) complexity I can easily solve it. But building LCP array requires suffix array. I know the O(n*logn*longn) algorithm. But It will give me TLE in this problem. I need the O(n) algorithm to build suffix array. I searched for it and get a paper which is too complex to understand for me. Can anyone give me a simple and well explained tutorial to build suffix array with O(n) time? It will be great help for me.

Thank you.

Read more »

 
 
 
 
  • Vote: I like it
  • +9
  • Vote: I do not like it

By NAMELESS, history, 16 months ago, In English,

Hello Everyone,

It was known to me that lookup time in unordered_map is faster than map in C++. When I have to lookup frequent than insertion I should use unordered_map. In this problem I used unordered_map because in my implementation lookup is more frequent than insertion. But I got TLE. In my implementation with map I got accepted. what is wrong here? Any explanation will be helpful.

Thank you.

Read more »

 
 
 
 
  • Vote: I like it
  • +12
  • Vote: I do not like it

By NAMELESS, history, 18 months ago, In English,

I am trying to solve this problem. There is a tutorial but for me its not so clear. You can see that I am green. For me the state is [numberOfProgrammer][numberOfLine][maxBug] which is 500*500*500. The tutorial has a solution with state 2*500*500. It is very hard for me to understand the state elimination. Someone please explain the solution so that I(as a green) can understand.

Read more »

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

By NAMELESS, history, 18 months ago, In English,

Hello,

I am trying to solve this problem and getting TLE, and I think my code is the best thing I can do. Please help me solve the problem by any efficient idea or optimizing my code:

#include <bits/stdc++.h>

using namespace std;

#define MX 5000005
#define M 100000007
#define LL long long
#define dbg(x) cout<<#x<<" = "<<x<<"\n"

int n;
LL cnt[MX];
int b[MX];

int main(){
    while(cin>>n){
        if(n==0) break;
        memset(b,0,sizeof(b));
        for(int i=n,v=1;i>1;i--,v++){
            cnt[i]=v;
        }
        for(int i=2;i<=n;i++){
            if(b[i]==0){
                for(int j=i*2;j<=n;j+=i){
                    b[j]=1;
                    int t=j;
                    int div=0;
                    while(t%i==0){
                        div++;
                        t/=i;
                    }
                    cnt[i]+=cnt[j]*div;
                }
            }
        }
        LL ans=1;
        for(int i=2;i<=n;i++){
            if(b[i]==0){
                ans=(ans*(cnt[i]+1))%M;
            }
        }
        printf("%lld\n",ans);
    }
}

Read more »

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

By NAMELESS, history, 2 years ago, In English,

i don't know what is wrong with my idea. I tried many times but still wrong answer. can anyone tell me what is wrong?

source : http://www.spoj.com/problems/GSS2/

code: https://paste.ofcode.org/32Kc7W5baENjJqs2ckLYFwq

Read more »

 
 
 
 
  • Vote: I like it
  • -9
  • Vote: I do not like it

By NAMELESS, history, 3 years ago, In English,

KQUERY

How can i optimize my code?

#include <bits/stdc++.h>

using namespace std;

int n, m, a[30005];
int bs;
vector<int> block[300];

int sqrtDecomposition(int l, int r, int v){
        if(l / bs == r / bs){
                int cnt = 0;
                for(int i = l; i <= r; i++){
                        if(a[i] > v) cnt++;
                }
                return cnt;
        }

        int cnt = 0;
        for(int i = l; i / bs == l / bs; i++){
                if(a[i] > v) cnt++;
        }
        for(int i = r; r / bs == i / bs; i--){
                if(a[i] > v) cnt++;
        }
        for(int i = l / bs + 1; i < r / bs; i++){
                cnt += (block[i].end() - upper_bound(block[i].begin(), block[i].end(), v));
        }
        return cnt;
}

int main(){
        cin >> n;
        for(int i = 0; i < n; i++){
                scanf("%d", a + i);
        }
        bs = sqrt(n);
        for(int i = 0; i < n; i++){
                block[i/bs].push_back(a[i]);
        }
        for(int i = 0; i < 300; i++){
                sort(block[i].begin(), block[i].end());
        }
        cin >> m;
        for(int i = 0; i < m; i++){
                int l, r, v;
                scanf("%d %d %d", &l, &r, &v);
                l--; r--;
                int ans = sqrtDecomposition(l, r, v);
                printf("%d\n", ans);
        }
}

Read more »

 
 
 
 
  • Vote: I like it
  • -5
  • Vote: I do not like it