×

# CHEFHACK - TLE

 0 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 15●12●21●24 accept rate: 0% 6.7k●62●119●138

 0 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; }  answered 15 Jan '13, 16:01 6.7k●62●119●138 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)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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