DCP-513: Charming Numbers

Dev Skill archived problems can be discussed here.

DCP-513: Charming Numbers

by rayhan50001 » Mon Apr 02, 2018 1:25 am

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. :geek: :geek: :geek:

Update:

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

how should i improve my code :?: :?: :?: :?:
 
Posts: 11
Joined: Tue Oct 25, 2016 6:25 pm

Re: DCP-513: Charming Numbers

by feodorv » Tue Apr 03, 2018 5:01 pm

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.
 
Posts: 11
Joined: Thu Jun 15, 2017 3:37 pm

Re: DCP-513: Charming Numbers

by rayhan50001 » Tue Apr 03, 2018 6:38 pm

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

:?: :?: :?: :cry: :cry: :cry: :cry: :cry:
 
Posts: 11
Joined: Tue Oct 25, 2016 6:25 pm

Re: DCP-513: Charming Numbers

by rayhan50001 » Tue Apr 03, 2018 8:43 pm

update AC in C implementation.
:D :D :)

re implementation always works. :D

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. :?: :?: :?: :?:
 
Posts: 11
Joined: Tue Oct 25, 2016 6:25 pm

Re: DCP-513: Charming Numbers

by feodorv » Wed Apr 04, 2018 7:23 pm

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.
 
Posts: 11
Joined: Thu Jun 15, 2017 3:37 pm


Who is online
Users browsing this forum: Bing [Bot] and 1 guest
cron