№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3773
3	Radewoosh	3646
4	ecnerwala	3624
5	jqdai0815	3620
5	Benq	3620
7	orzdevinwang	3612
8	Geothermal	3569
8	cnnfls_csy	3569
10	Um_nik	3396

№	Пользователь	Вклад
1	Um_nik	164
2	cry	160
2	maomao90	160
4	-is-this-fft-	159
5	atcoder_official	158
5	awoo	158
7	adamant	155
8	nor	154
9	maroonrk	152
10	Dominater069	149

Why isn't there TLE?

I was solving the D problem of the previous contest Div2.907
I used binary search, but it needed ridiculous optimizations before it got accepted, and even then, it was a close call.
I played around for a while trying to make it even closer.
After all a while, I noticed....

That, codeforces forgot what TLE is.

As far as I can make out, this is a supreme example of machine learning that in the future, should be of great service to all competitive programmers worldwide.

I made a last attempt at manufacturing a TLE, unfortunately, I failed to get it. It was very disappointing for me. As a competitive programmer, I thought that though I couldn't get AC all the time, at least I could get TLE, if I wanted. Apparently, even this is beyond my ability.

My Entire Program


#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_MACHINE
    template <class K, class V> ostream& operator<< (ostream& s, const pair <K, V> &p) {
        auto [x, y] = p; s << '(' << x << ", " << y << ")"; return s;
    }
    template <class T, class=typename T::value_type, class=typename enable_if<!is_same<T, string>::value && !is_same<T, complex <typename T::value_type>>::value>::type> ostream& operator<< (ostream &out, const T&v) {
        stringstream t; t << '{'; for(auto &x: v) {t << x << ", ";}  
        string s = t.str(); if(!v.empty()) {s.pop_back(); s.pop_back();} s += '}'; 
        out << s; return out;
    }
    template <class T> void __prnt(T x) {cerr << x << endl;}
    void __prnt() {cerr << endl;}
    template <class T, class...Ts> void __prnt (T&&a, Ts&&...etc) {cerr << a << ", ", __prnt(etc...);}
    #define print(...) if(#__VA_ARGS__ == "") __prnt(); else (cerr << #__VA_ARGS__ <<" = ", __prnt(__VA_ARGS__))
#else
    #define print(...) 4224224
#endif

#define int long long

const int MOD = 1000 * 1000 * 1000 + 7;
int mod(int n) {
    return ((n % MOD) + MOD) % MOD;
}

int epicmul(int a, int b) {
    a = mod(a);
    b = mod(b);

    if(b == 0)
        return 0;
    int x = epicmul(a, b / 2);
    if(b % 2 == 0)
        return mod(2ULL * x);
    else
        return mod(2ULL * x + a);
}

typedef vector <int> vi;
typedef pair <int, int> pii;

void solve();
void init();

void maxeq(int &a, int b) {a = max(a, b);}
void mineq(int &a, int b) {a = min(a, b);}

signed main() {
    int t = 1;
    cin >> t;

    while(t-- > 0) {
        solve();
    }
}


vector <vi> rngs = {{4, 7, 2}, {8, 8, 1}, {9, 15, 2}, {16, 31, 2}, {32, 63, 2}, {64, 127, 2}, {128, 255, 2}, {256, 511, 2}, {512, 728, 2}, {729, 1023, 3}, {1024, 2047, 3}, {2048, 4095, 3}, {4096, 8191, 3}, {8192, 16383, 3}, {16384, 32767, 3}, {32768, 50624, 3}, {50625, 65535, 4}, {65536, 131071, 4}, {131072, 262143, 4}, {262144, 524287, 4}, {524288, 1048575, 4}, {1048576, 2097151, 4}, {2097152, 4084100, 4}, {4084101, 4194303, 5}, {4194304, 5153631, 4}, {5153632, 8388607, 5}, {8388608, 16777215, 5}, {16777216, 33554431, 5}, {33554432, 67108863, 5}, {67108864, 134217727, 5}, {134217728, 268435455, 5}, {268435456, 481890303, 5}, {481890304, 536870911, 6}, {536870912, 594823320, 5}, {594823321, 1073741823, 6}, {1073741824, 2147483647, 6}, {2147483648, 4294967295, 6}, {4294967296, 8589934591, 6}, {8589934592, 17179869183, 6}, {17179869184, 34359738367, 6}, {34359738368, 64339296874, 6}, {64339296875, 68719476735, 7}, {68719476736, 78364164095, 6}, {78364164096, 137438953471, 7}, {137438953472, 274877906943, 7}, {274877906944, 549755813887, 7}, {549755813888, 1099511627775, 7}, {1099511627776, 2199023255551, 7}, {2199023255552, 4398046511103, 7}, {4398046511104, 8796093022207, 7}, {8796093022208, 11688200277600, 7}, {11688200277601, 17592186044415, 8}, {17592186044416, 35184372088831, 8}, {35184372088832, 70368744177663, 8}, {70368744177664, 140737488355327, 8}, {140737488355328, 281474976710655, 8}, {281474976710656, 562949953421311, 8}, {562949953421312, 1125899906842623, 8}, {1125899906842624, 1953124999999999, 8}, {1953125000000000, 2251799813685247, 9}, {2251799813685248, 2334165173090450, 8}, {2334165173090451, 4503599627370495, 9}, {4503599627370496, 9007199254740991, 9}, {9007199254740992, 18014398509481983, 9}, {18014398509481984, 36028797018963967, 9}, {36028797018963968, 72057594037927935, 9}, {72057594037927936, 144115188075855871, 9}, {144115188075855872, 288230376151711743, 9}, {288230376151711744, 430804206899405823, 9}, {430804206899405824, 576460752303423487, 10}, {576460752303423488, 1152921504606846975, 10}};

vector <int> prefix = {8, 9, 23, 55, 119, 247, 503, 1015, 1449, 2334, 5406, 11550, 23838, 48414, 97566, 151137, 210781, 472925, 997213, 2045789, 4142941, 8337245, 16285041, 16836056, 20673368, 36848248, 78791288, 162677368, 330449528, 665993848, 337082481, 404356714, 734240362, 24002400, 897513404, 339964299, 224866096, 994669697, 534276885, 613491268, 490841050, 152099860, 20223614, 543746355, 616413925, 761749065, 52419338, 633759898, 796441011, 121803230, 872449273, 758253169, 245623331, 220363662, 169844324, 68805648, 866728303, 462573599, 161508000, 465858721, 336487884, 288333919, 650941611, 376156988, 826587749, 727449264, 529172294, 132618354, 879713805, 723932337, 405914836};


int find_range(int x) {
    int l = -1;
    int r = rngs.size();

    while(r - l > 1) {
        int m = (l + r) / 2;
        vi rng = rngs[m];

        if(rng[0] <= x)
            l = m;
        else
            r = m;
    }
    return l;
}

int get(int l, int r, int v) {
    int size = mod(mod(r) - mod(l) + 1);
    return epicmul(size, v);
}

void solve() {
    int l, r;
    cin >> l >> r;

    int a = find_range(l);
    int b = find_range(r);

    int ans = 0;

    int res = 0;
    int lim = 10000000LL;
    //1
    for(int i = 0; i < lim;  i++) {
        for(int j = 0; j < lim; j++) {
            for(int k = 0; k < lim; k++) {
                for(int l = 0; l < lim; l++) {
                    ans++;
                    res++; 
                }
                ans -= lim;
                ans++;
            }
            ans -= lim;
            ans++;
        }
        ans -= lim;
        ans++;
    }
    ans -= lim;

    if(a + 1 <= b - 1) {
        ans = mod(ans + prefix[b - 1] - prefix[a]);
    }

    if(a != b) {
        ans = mod(ans + get(l, rngs[a][1], rngs[a][2]));
        ans = mod(ans + get(rngs[b][0], r, rngs[b][2]));
   } else 
        ans = mod(ans + get(l, r, rngs[a][2]));

    //cout << ans << "\n";
    cout << ans << "\n";
}

The solve() function that should create TLE

void solve() {
    int l, r;
    cin >> l >> r;

    int a = find_range(l);
    int b = find_range(r);

    int ans = 0;

    int res = 0;
    int lim = 10000000LL;
    //1
    for(int i = 0; i < lim;  i++) {
        for(int j = 0; j < lim; j++) {
            for(int k = 0; k < lim; k++) {
                for(int l = 0; l < lim; l++) {
                    ans++;
                    res++; 
                }
                ans -= lim;
                ans++;
            }
            ans -= lim;
            ans++;
        }
        ans -= lim;
        ans++;
    }
    ans -= lim;

    if(a + 1 <= b - 1) {
        ans = mod(ans + prefix[b - 1] - prefix[a]);
    }

    if(a != b) {
        ans = mod(ans + get(l, rngs[a][1], rngs[a][2]));
        ans = mod(ans + get(rngs[b][0], r, rngs[b][2]));
   } else 
        ans = mod(ans + get(l, r, rngs[a][2]));

    //cout << ans << "\n";
    cout << ans << "\n";
}

These are the links to my last attempts
- 230780232 This submission ran till test 17 before TLE occurred, some kind of self-realisation, maybe?!
- 230780567 My next attempt was totally unsuccessful, it got AC, what a pity.

On my local system, things work as normal. I'm currently expecting to see some output after a few decades.

As these violations of the universe are beyond my sphere of comprehension, could any wise sage possibly enlighten me?

Комментарии (6)

Написать комментарий?

jmichael

11 месяцев назад, # |

Auto comment: topic has been updated by jmichael (previous revision, new revision, compare).

→ Ответить

yash_1132

daulatojha17

Gassa

+29

You may appreciate a read about constant folding in compilers, or a link to try various optimization levels.

11 месяцев назад, # ^ |

I see, it converted the iterated increment into a single addition, and then applied other optimizations. Interesting, wasn't aware that compilers did this too.

benzabyte

well that's an interesting problem there

Блог пользователя jmichael

Why isn't there TLE?