changyuheng's blog

By changyuheng, 11 years ago, In English

I wrote two solutions for this problem. Both them got AC in C++ while getting TLE in Python. Could somebody give some tips to me to let me pass the test with Python?

Solution 1 (C++/203 ms)

#include <cmath>
#include <iostream>

#define MAX 1000001

using namespace std;

int main(int argc, char ** argv) {
    int a, b, c, ans = 0;
    cin >> a >> b >> c;
    static int D[MAX] = {1, 1};
    for (int i = 1; i < a + 1; i++) {
        for (int j = 1; j < b + 1; j++) {
            for (int k = 1; k < c + 1; k++) {
                int l = i * j * k;
                if (!D[l]) {
                    long double sqi = sqrtl(l);
                    unsigned long long int sum = 0;
                    for (int m = 2; m < (int) sqi + 1; m++) {
                        if (!(l % m)) {
                            if (sqi == m) {
                                sum++;
                                continue;
                            }
                            sum += 2;
                        }
                    }
                    D[l] = sum + 2;
                }
                ans += D[l];
            }
        }
    }
    cout << ans % (1 << 31) << endl;
    return 0;
}

Solution 2 (C++/218 ms)

#include <iostream>

#define MAX 1000001

using namespace std;

int main(int argc, char ** argv) {
    int a, b, c, ans = 0;
    static int D[MAX];
    for (int i = 1; i < MAX; i++) {
        for (int j = i; j < MAX; j += i) {
            D[j]++;
        }
    }
    cin >> a >> b >> c;
    for (int i = 1; i < a + 1; i++) {
        for (int j = 1; j < b + 1; j++) {
            for (int k = 1; k < c + 1; k++) {
                ans += D[i*j*k];
            }
        }
    }
    cout << ans << endl;
    return 0;
}

--

Solution 1 (Python/TLE)

a, b, c = map(int, raw_input().split())
d = {}
ans = 0
d[1] = 1
for ai in xrange(1, a + 1):
    for bi in xrange(1, b + 1):
        for ci in xrange(1, c + 1):
            i = ai * bi * ci
            if i not in d:
                sqi = i ** 0.5
                d[i] = sum(2 if j != sqi else 1 for j in xrange(2, int(sqi) + 1) if i % j == 0) + 2
            ans += d[i]
print ans % 1073741824

Solution 2 (Python/TLE)

a, b, c = map(int, raw_input().split())
m = a * b * c + 1
d = [1] * m
ans = 0
for i in xrange(2, m):
    for j in xrange(i, m, i):
        d[j] += 1
for ai in xrange(1, a + 1):
    for bi in xrange(1, b + 1):
        for ci in xrange(1, c + 1):
            ans += d[ai*bi*ci]
print ans % 1073741824

Update

Finally pass it in 578 ms with Python.

http://www.codeforces.com/contest/236/submission/2419288

Full text and comments »

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

By changyuheng, 12 years ago, In English

Here is my code for 222 B


table = [] n, m, k = map(int, raw_input().split()) [table.append(raw_input().split()) for i in xrange(n)] rs, cs = [i for i in xrange(n)], [i for i in xrange(m)] for i in xrange(k): s, x, y = raw_input().split() x, y = int(x) - 1, int(y) - 1 if s == "c": buf = cs[x] cs[x] = cs[y] cs[y] = buf elif s == "r": buf = rs[x] rs[x] = rs[y] rs[y] = buf else: print table[rs[x]][cs[y]]

It exceeded the time limit. I do not see any solution written in Python so come here for help. Could somebody give me an advise?

UPDATE: Thanks everybody. I just upload another solution in which replace the swap by buffer with by xor swap algorithm. It passed with 80ms under the time bound.

And I just saw that dkirienko submitted another solution with the a, b = b, a swap mechanism of Python. It speeds up a bit more.

Full text and comments »

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