Where is The mistake plz !! i beg for help!!

general
#1

Problem :-
link text

My solution:- link text

Input cases for which my solution is wrong:- link text

Algorithm used same as others still i dont understand:-

  1. Generate prime numbers upto max query number or max number.
  2. Generate multiples of two primes (including prime squares) upto the limit.
  3. For each query we have to tell whether we can reach to any number generated in Step 2. For this
    we can generate all possible numbers, by multiplying Step 2 numbers with the given array numbers,
    repeatedly. Again we will check upto the max query number only. Using ordered (sorted) numbers
    with max number condition, we can reduce the time complexity significantly.

I have followed same logic if im not wrong . Plz help me. Whats mistake i cannot identify i tried very hard.

#2

while((a[i]*temp)<=LMT)

{

final[a[i]*temp]=1;

temp=(long)(temp*a[i]);

}

it results in an infinite loop if a[i]==0 or a[i]==1.

why did you write this?

if((temp*gen[j])>LMT)

break;

#3

@code_man

here is my accepted solution

https://www.hackerearth.com/submission/9269611/

please comment if you have any doubt.

#4

Okay, i see the error.

The reason you got WA is here-

if((temp*gen[j])>LMT)        // now mark product of given array(a[i]) and generated array(gen[i])=3*4=12)
            break;                       // bcoz 12 can be decompose to 4 (dividing by 3 ) which is product of two primes

This is wrong in principle. Your gen[j] array IS NOT SORTED. It follows this up-down fashion-

4,6,8.....highest multiple of 2... 9,12,15.....highest multiple of 3 possible...16,20...highest multiple of 4 possible...and so on

So essentially, you cannot break out due to that condition, because a possible product of temp x gen[j] can lie forward. Anywhere in your code, if you have not sorted the array and used this condition of breaking, you will get a WA on stronger test cases. Your code works fine for some cases related to multiple of 2, but fails elsewhere.

You are prematurely breaking out of the loop, without checking other fit/possible paths to decrypt.

And i think you know why your solution gets TLE. there can be around 78498 primes in your initial array prime[length]. Then, there are atleast 10x more numbers in the next array, gen[genlen]. Then, if i give an array of size 10^5 in input, it will easily cross the allowed threshold of 10^8 to 10^9 operations and get TLE. Generating all possible pairs will be too slow.

I hope this satisfies your curiosity on where your code was wrong ^^

#5

I corrected for a[i]==1 and a[i]==0. (using continue)

Inside inner for loop i wrote:-

      if((temp*a[i])>LMT)      //bcoz if product is greater no need to go              
         continue                        ahead.

Now im getting TLE for some cases and others got accepted.
I think everything is fine except inner for loop that causes TLE. Can u plz help me to identify my bug.

link:-link text

#6

why did u write this?

if((temp*gen[j])>LMT)
break;

If i remove this condition i get TLE.So what should i write to prevent TLE.

#7

anyone plz help me i already made around 15 submissions for these problem. plzz

#8

Your problem link is faulty. It leads to ideone.com . Without problem statement, you cant expect many people to turn up for help :confused:

#9

I edited @vijju123. Now can u help me

#10

Dont you think that there should be a cleverer way than checking for every combination?? Did you not get TLE in any case??

#11

I dont way know other method,i got tle in some case?can u explain me editorail

link:-https://www.hackerearth.com/practice/math/number-theory/basic-number-theory-2/practice-problems/algorithm/hacker-with-prime-bebe28ac/editorial/

#12

I will be satisfied if someone tells me whats wrong in code,although algorithm is right.im waiting almost 3 days.

#13

why don’t you write efficient code?Even you know that your’s is naive solution and waiting for others to tell mistake in your code.

#14

I need comments in your code. Your algorithm seems fine, but i need details like which part of your code does what or what was your intention in that part of code. Else, guessing someone else’s code is time consuming.

#15

@vijju123 entire solution documented and made simple.now U can debug it easily,which i fail to do so

link:- https://ideone.com/foMTE3

#16

Thanks but i dont know c++,have u used same algorithm.I just wanted to know why my code doesnot produces right answer.is it unsolvable in c?

#17

Thanks, i am giving it a look atm.

#18

ur most welcome i cannot express my feeling now ill sleep peacefully !! thanks bro:)

#19

your are getting tle or wa?

#20

i got it bro , thanks a lot lotttt, I just wanted to know how can i overcome TLE , Bcoz in c only 10^7 size array is allowed at max.In c++ this much size allowed for array ? If not ?Then which is alternative datastructure for storing numbers upto 10^9.