dcordb's blog

TLE on Timus 1989
By dcordb, 10 years ago, In English

I'm stuck in this problem:
http://acm.timus.ru/problem.aspx?space=1&num=1989

It gives me TLE on test 15, my code uses Hashing and Fenwick Tree, so it's O(mlogn). The time limit is only 0.5s. Is there a better solution? (an O(m) solution).
Thanks in advance.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I got accepted on this problem with almost the same approach as you suggested. The only difference is Segment Tree instead of Bit. You probably have a bug somewhere in your code.

→ Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

You should post your code...

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Here is my code, sorry that I put it here like this, right now I don't have access to ideone.

    #include <cstdio>
#include <cstring>
using namespace std;

typedef long long int64;
const int MAX = 1e5 + 5;
const int64
    B = 37,
    MOD = 1e9 + 7;
int n, m;
int P[MAX];
char A[MAX];

struct bit {
    int tree[MAX];

    void update(int x, int val) {
        for(int i = x; i <= n; i += (i & -i))
            tree[i] = (tree[i] + val) % MOD;
    }

    int query_at(int x) {
        int sum = 0;

        if(x < 1)
            return sum;

        for(int i = x; i > 0; i -= (i & -i))
            sum = (sum + tree[i]) % MOD;

        return sum;
    }

    int query(int a, int b) {
        return (query_at(b) - query_at(a - 1) + MOD) % MOD;
    }
} T1, T2;

int main() {
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);

    scanf("%s%d", A + 1, &m);
    n = strlen(A + 1);

    P[0] = 1;
    for(int i = 1; i <= n; i++) {
        int64 val = (A[i] - 'a') * 1LL * P[i - 1];
        val %= MOD;
        T1.update(i, val);

        val = (A[n - i + 1] - 'a') * 1LL * P[i - 1];
        val %= MOD;
        T2.update(i, val);

        int64 tmp = (P[i - 1] * 1LL * B) % MOD;
        P[i] = tmp;
    }

    while(m--) {
        char s[20]; scanf("%s", &s);

        if(s[0] == 'c') {
            int x; char c; scanf("%d %c", &x, &c);
            int64 val = (c - 'a') * 1LL * P[x - 1];
            val %= MOD;
            int q = T1.query(x, x);
            T1.update(x, (val + 0LL - q + MOD) % MOD);

            x = n - x + 1;
            val = (c - 'a') * 1LL * P[x - 1];
            val %= MOD;
            q = T2.query(x, x);
            T2.update(x, (val + 0LL - q + MOD) % MOD);

            continue;
        }

        int a, b; scanf("%d%d", &a, &b);
        int na = n - b + 1, nb = n - a + 1;
        int64 val1 = T1.query(a, b), val2 = T2.query(na, nb);

        if(na >= a)
            val1 = (val1 * 1LL * P[na - a]) % MOD;

        else val2 = (val2 * 1LL * P[a - na]) % MOD;

        printf(val1 == val2 ? "Yes\n" : "No\n");
    }

    return 0;
}

    PD: I've updated my code, I realize that I don't need modular inverses (to compare the hashings) at all. But it still gives me TLE on test 16. In my PC with a full test case it runs in ~0.25s.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any ideas why it gives me TLE? I found a solution on the internet which uses segment tree and it gives AC. I mean WTF?? (segment tree has a bigger constant that Fenwick Tree)

→ Reply
»
10 years ago, # |
  Vote: I like it -8 Vote: I do not like it

I think that you have TLE because use mod operation many times ( this operation is slow ). You can easily decrease search operation to O(1). Use array, at position i you store sum from 0 to i. Now sum in [L;R] is sum[R] — sum[L-1].

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    How can we handle the update operations?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's my mistake :) I forgot for update operations...

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any way to improve the complexity of the modulo operation??

→ Reply