Educational 106 problem D time limit and hacks

Правка en5, от thematdev, 2021-03-19 19:43:25

Hi, Codeforces! I have 13 successful hacks of problem D on last round, and also my solution are TLed(probably on one of my tests :)), and i am going to show you, how does it work.

So we have two part of solution.

Solution and complexity

Now we will try to adjust numbers $$$c, d, x$$$ to hack $$$O(t\sqrt{x} \log x + N \log \log N)$$$ solution. Because we are counting distinct prime factors of numbers like $$$\frac{\frac{x}{d_x} + d}{c}$$$, we will use $$$c = 1$$$. And we are factorizing $$$x$$$. So the first idea is to find $$$x$$$ with biggest divisors number, and that $$$x$$$ is $$$8648640$$$. And then we will try to maximize

$$$\sum\limits_{d_x \mid x} s(x/d_x + d)$$$

where $$$s(n)$$$ -- sum of powers of primes in factorization of $$$n$$$(exactly that much operations we do).

And we have first powerful hack. 10000 tests with $$$c=1, d=x=8648640$$$. List of successful hacks using this method below

But some solutions hadn't hacked by this test. And there are more reasons of it. Sometimes people precalculate lowest divisors powered to its power, and by Second Merten's Theorem it is $$$O(\log \log x)$$$ average, and also our $$$d$$$ doesn't work. But the main reason is memory and cache, so we can use randomized generator with more numbers with huge amount of divisors. But how can we use randomized generator on codeforces? It is simple, we just need to set seed in mt19937 and try to adjust it.

Some examples

#include <iostream>
#include <vector>
#include <random>

//const int bigDivNumbersSize = 46;
const int bigDivNumbersSize = 7;

//const std::vector<int> bigDivNumbers = {4324320, 5405400, 5654880, 5765760, 6126120, 6320160, 6486480, 6652800, 6683040, 6846840, 7068600, 7207200, 7469280, 7539840, 7567560, 7650720, 7761600, 7862400, 7900200, 8168160, 8288280, 8316000, 8353800, 8426880, 8482320, 8648640, 8910720, 8953560, 9009000, 9041760, 9129120, 9172800, 9189180, 9313920, 9336600, 9424800, 9480240, 9563400, 9609600, 9646560, 9729720, 9767520, 9828000, 9896040, 9959040, 9979200};

const std::vector<int> bigDivNumbers = {6486480, 7207200, 8482320, 8648640, 9424800, 9480240, 9979200};

const unsigned int seed = 1488;
const int MAXC = 3;
const int MAXT = 1e4;
std::mt19937 mersenneTwister(seed);
std::uniform_int_distribution<int> idxDistr(0, bigDivNumbersSize - 1);
std::uniform_int_distribution<int> numbersDistr(0, MAXC - 1);



void generateOneCase() {
    int c, d, x;
    //int idx = idxDistr(mersenneTwister);
    x = bigDivNumbers[idxDistr(mersenneTwister)];
    d = x;
    c = 1;
    std::cout << c << ' ' << d << ' ' << x << std::endl;
}

int main() {
    int t = MAXT;
    std::cout << t << std::endl;
    for (int i = 0; i < MAXT; i++) {
        generateOneCase();
    }
}
Теги educational round, #number theory, hacks

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru2 Русский thematdev 2021-03-19 20:42:03 47 (опубликовано)
ru1 Русский thematdev 2021-03-19 20:40:52 3063 Первая редакция перевода на Русский (сохранено в черновиках)
en9 Английский thematdev 2021-03-19 20:11:43 0 (published)
en8 Английский thematdev 2021-03-19 20:08:17 203
en7 Английский thematdev 2021-03-19 20:02:34 10
en6 Английский thematdev 2021-03-19 19:57:46 1566
en5 Английский thematdev 2021-03-19 19:43:25 52 Reverted to en3
en4 Английский thematdev 2021-03-19 19:40:39 52
en3 Английский thematdev 2021-03-19 19:36:55 2072
en2 Английский thematdev 2021-03-19 19:29:02 664 Tiny change: '} + d}{c}$\n\n\n\n\n' -> '} + d}{c}$, we will use $c = 1$.\n\n\n\n\n'
en1 Английский thematdev 2021-03-19 19:18:15 1065 Initial revision (saved to drafts)