DCP-513: Charming Numbers

[rayhan50001]

Why Time Limit is now 2s.
it was 2.5 / 4 s.

another thing is when i am trying to use bitset it takes much time.

Update:

my solution: https://pastebin.ubuntu.com/p/jzBSNQ8W5k/
verdict : TLE
memory: 184MB (according to CF)

how should i improve my code

[feodorv]

It's really pity you get constantly TLE. The time limit has been changed because during the contest there is a large load on judge host and the solutions run up to two times slower.

Let's try to improve your code.

Firstly let's start from the sieve of Eratosthene:

Code: Select all

void seive()
{
    for(int i=3; i<=13333292; i+=2)
    {
        if(mp[i]==0)
        {
            prime[len++]=i;
            for(int j=i*2; j<=13333292; j+=i)
            {
                mp[j]=1;
            }
        }
    }
}

It's not optimized:

• I do not know why you have commented //bitset<13333295>mp; Does it not work properly? In order to set one bit you are accessing four bytes in your code, increasing the execution time. At the last end you can define mp as char.
• You start internal cicle from 2*i. Why? So your sieve has O(N*log(N)) time complexity. You can easily start it from i*i (with overflow checking), reducing the complexity to O(N*log(log(N))). For large N it is significantly better. Moreover you can use more advanced algorithms like this, but it is not necessary to solve this problem.
• You can increase j on 2*i, not simply i.

Your code is full of constans, but you can derive some of them from other constants. For example:

Code: Select all

const int maxv = 200000000;
const int limit = maxv / 15;


Is the value 13333295 correct?

Here is my C-incarnation of the sieve:

Code: Select all

#define MAXV 200000000
#define LIMIT (MAXV / 15)

#define PHAS(_n) (pbits[(_n)>>5] & (1u << ((_n) & 0x1f)))
#define PSET(_n) (pbits[(_n)>>5] |= (1u << ((_n) & 0x1f)))
unsigned int pbits[LIMIT/32+1];

int pr[1000000];
int pc;

void gen( void )
{
  int i, j, mx = (int) sqrt( LIMIT );

  pc = 0;

  for( i = 3; i < LIMIT; i += 2)
    if( !PHAS(i) )
    {
      pr[pc++] = i;
      if( i <= mx )
        for( j = i*i; j <= LIMIT; j += 2*i) PSET(j);
    }
}


It uses the array pbits as a bitset.

[rayhan50001]

link: http://codeforces.com/group/HtnK54FR7R/ ... /problem/D

i submitted my all possible solution. when i am trying to use two bitset it takes more time on devskill, and also i used O(n) sieve.

above link i submitted my code upto 30/34 times to check my time limit and memory.

and yes highest prime upto 200000000/15 is 13333291.

see this: https://paste.ubuntu.com/p/jd9Ps3Jdq8/

it accepted on CF with time 1076ms and memory:190MB

[rayhan50001]

update AC in C implementation.


re implementation always works.

thank you for pointing out " full of constant " and "char declaration".

i still confuse C implementation takes 1336ms on CF and on devskill 1.60s.
and C++ lowest 940ms on CF and devskill TLE.

i just implement BITSET in C that's it.

[feodorv]

Congrats!

The limits on CF are more friendly, yes. Here we have more competitive air.
And it's a big question why a bitset class is so slow on DevSkill.