Is this time normal or there is faster algorithm? I used trivial search for primes p and q, solved k1*p+k2*q=1 by analog of Euqlid algorithm and assume idemponets are 0, 1, k1*p (where k1*p is positive) and n+1-k1*p.

Since now Timus has some division of the problems on types (which is brought by tag field), why not to add on the author's page information about percent of the problems in every type, solved by the author?

A very nice thing happend to me! When I used long arithmetic with base 10^17 I got TL many times. Even after I made my program calculate an expression like (2^N * 3^M) only one time! (I didn't use fast power). Then I generally rewrote my class BigInteger, and now it can calculate the product of two big numbers :) So I used the "fast-power" algo, and after this I immediately got AC in 0.156s.

It should be noted that now I use base = 10^9 and store the numbers in vector (earlier they were stored in arrays). Of course, these "upgrades" make this class work slower and use more memory. But my program uses only ~700 KB of memory (it was another surprise for me). The only thing I did to make my program faster was use the algo written above. I didn't expect it would work much faster...

So, fast power RULEZZZ! :D

Edited by author 27.09.2010 01:39

What test is it?

I have WA 7, write answer for this test, please

A 01:00:01 100 12:12:02 20
E 10:10:01 12 01:02:02 2
F 00:00:00 110 23:00:02 100
W 00:10:01 56 00:00:02 12
AFWE
AAEE

Admins, maybe you deny users who has less than 10 (15, 20) accepted problems writing on forum?

My program does every test in this forum right, but it doesn't pass test #2.... Please send test to mail: paezand@gmail.com. Any help would be greatly appreciated!


Edited by author 26.09.2010 22:17

please smb send me the solution or the idea
my mail is vgvavlad@gmail.com

What does this test look like?

You calculate f2 by this formula: f2 = f1 + f0
f2 may be small enough to be stored by an integer, but f1 and f0 may be very large.
For example:
1 = (-2935892358923598) + (2935892358923599)

Hello
what's compiler is on the server? where is my typeof() ?

I use sqrt decomposition and some DP.
My DP idea is to keep for each robot the shortest path which we can find if we detour by left or right. And I use sqrt decomposition to find the next encountered robot on the current path.
Could someone give me a tricky example?

Edit: I wrote the update of the sqrt decomposition again(different) and now I get WA23.

Edited by author 22.09.2010 15:13

#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

int a[501][3], f[501], trace[501], n, ans, t;

void sort(int l, int r) {
    int x = a[(l + r) >> 1][0];
    int i, j, t[3];
    i = l;
    j = r;
    do {
        while (a[i][0] < x)
            i++;
        while (a[j][0] > x)
            j--;
        if (i <= j) {
            memcpy(t, a[i], sizeof(t));
            memcpy(a[i], a[j], sizeof(t));
            memcpy(a[j], t, sizeof(t));
        }
        i++;
        j--;
    } while (i <= j);
    if (i < r)
        sort(i, r);
    if (l < j)
        sort(l, j);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &a[i][0], &a[i][1]);
        a[i][2] = i;
    }
    for (int i = 1; i <= n; i++)
        f[i] = 1;
    sort(1, n);
    for (int i = 2; i <= n; i++)
        for (int j = 1; j < i; j++)
            if ((a[j][0] < a[i][0]) && (a[j][1] > a[i][1]) && (f[j] + 1 > f[i])) {
                f[i] = f[j] + 1;
                trace[i] = j;
            }
    ans = 0;
    t = 0;
    for (int i = 1; i <= n; i++)
        if (f[i] > ans) {
            ans = f[i];
            t = i;
        };
    printf("%d\n", ans);
    while (t != 0) {
        printf("%d ", a[t][2]);
        t = trace[t];
    }
    return 0;
}

Читаю который раз, а все понять не могу, что за бред...
I read which time, and all I can not understand that for delirium...

What it can be???i have TL 15 if i change code i have wa 15 it's terrible)

5+5+13+14=37
27+8=35
result=2

of course you need O(n) and I had it but
I was mad about this(TLE), but I thought a little and tried to use
char s[200010]
and now
AC 0.031))))))))))))))
don't use list or string in this problem
write your own implementation of std::list
good luck)

Edited by author 10.07.2009 23:29

Edited by author 10.07.2009 23:49

why my answer of the test#1 is incorrect?
codenames
grille
keywords
mnemonic
playgame
random
rectangle
rejudge
shaitan
size
twosides