You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFHACK - TLE

Hi, I have tried a lot during the contest to submit CHEFHACK problem:
http://www.codechef.com/JAN13/problems/CHEFHACK

but it always give me time limit exceeding ...kindly help me ??

this is my solution:
http://www.codechef.com/viewsolution/1715546

asked 15 Jan '13, 15:19

vivek07672's gravatar image

2★vivek07672
15122124
accept rate: 0%

edited 16 Jan '13, 13:13

anton_lunyov's gravatar image

6★anton_lunyov ♦
6.7k62119138


You should use usual array instead of map.
So that you can find the index of each prime in O(1) time instead of O(log P) time,
where P is the total number of primes less than 107.

Namely, just declare variable mymap as int mymap[MAX].

But wait. I've just noticed the following loop in your code

int ans=1;
for (int r = 2; r < a[i][j]; r++)
{
    if(a[i][j]%r==0)
    {
        ans=0;
        break;
    }
}

This slow down your program drastically.
You should use array data[] to check whether number is prime in O(1) time.
Note that after the Sieve loop data[i] = i only for prime numbers i.
Hence instead of this loop you could simply write

int ans = 1;
if(data[a[i][j]] == 0) {
    ans = 0;
}

link

answered 15 Jan '13, 16:01

anton_lunyov's gravatar image

6★anton_lunyov ♦
6.7k62119138
accept rate: 12%

but still i am getting wrong answer ?? please point out my mistake ....??
http://www.codechef.com/viewsolution/1724277

(15 Jan '13, 17:52) vivek076722★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×729
×22

question asked: 15 Jan '13, 15:19

question was seen: 975 times

last updated: 16 Jan '13, 13:13