PRMDIV - Editorial

editorial
, , , , ,
6

Thanks @fr4nkesti3n ,

My AC approach here -
I was just trying luck along with double sieve. Hence I used a variable named lucky. xD. In case I get AC this is reason behind it.

Approach -

Sieve to find S[i]

Maintain Counter Array.

Used Map. Although Set is more appropriate then Map :wink:

Brute force for 1<=a[i]<=lucky. With lucky<=100 Atmost 100 iterations.

For a[i]>lucky. One loop for 1<=i<=lucky and rest sieve. Atmost 200 iterations.

But still in TL .

Unfortunately it failed on last test case. And I made 15 submissions with different values of lucky with hope of getting AC.

Finally I got AC after seeing @fr4nkesti3n soln.

And bingo it resulted in A.C. Soln.

Never use % until and unless it is absolutely necessary.

I repeat Never use % until and unless it is absolutely necessary.

It can take you from 100 pts to 20 pts And you will never realise reason behind it.

He added condition if(cnt[j]) then only compute s[j]\%s[i]

Editorials soln can be optimised further by using set/map for outer loop. By in that case insertion complexity will be O(logn) And overall complexity will be again O(NlogN) .

2 Likes
7

@likecs in the pseudocode to calculate the final answer

for i in [2, 1000000]:
        if freq[a[i]] > 0:
            # Element is present

Should’nt it be freq[i] instead of freq[a[i]] ?

8

@likecs could you please clear the linear sieve and an additional O(n) array approach?

9

Hello everyone,I m getting TLE in last test cases and i m not able to figure out the reason…please help me out.
Here is the link to my solution:- XUhDs1 - Online C++0x Compiler & Debugging Tool - Ideone.com

10

Can someone point out what was wrong with my code (I was targeting for subtask 1)
https://www.codechef.com/viewsolution/19376505

11

After trying to understand it for 10hrs and after doing nearly 15 submissions, I am still struggling to get AC.

please check my PA Solution here and tell me what I am missing.

12

I tried the way as mentioned in the editorial, but am getting TLE on the 1st, 2nd and last Test Cases. I find my and ediorialist’s codes almost similar but couldn’t figure out why I am getting TLE. Is the O(MAX^2) complexity in every precalculation is causing TLE.

Secondly, I tried to sieve only up to the maximum element in the input array. It decreased the time of execution but all tasks gave WA.(Some still gave TLE)

My code _ TLE One

My code _ WA One

13

Time Complexity:- O(XlogX+N) per test case, where X=1000000
On Computing time, it is similar to 2*10^7
and there can be 100 test cases at maximum, when i am assuming N=10^4
then total time will be over >10^9 still no TLE according to editorial… why? please SomeOne Explain where I am wrong

14

In the last section psuedo-code line no. 5 if freq[a[i]] > 0: should it not be changed to freq[i] > 0: here is the AC Code.

15

I have been trying to solve for subtask 1 but not getting an AC. Please someone help.

16

@likecs It will have 10^9 (approx) computations.How will it be completed in 1 sec?

17

Can someone please explain, why the author is

ensuring that “i” divides “j” ?

when he is calculating good[i] array,

does he mean if “i” doesn’t divide “j” => “s[i]” doesn’t divide “s[j]” ?

18

Need Help !!! Since I am a beginner I don’t understand How Counting is performed to clear subtask 2. I try to do the dry run in my rough copy but was not able to solve due to the huge size of the array. Can u plz tell me where I am lacking and which concept should I study to understand this. You can also share some link.

19

Can someone help me out ? I can’t find reason why it still TLE
Here is my code
CodeChef: Practical coding for everyone
Thank you!!

20

I tried implementing the solution in the editorial in Java. Its giving me TLE. Can someone please tell me why?
Solution Link: CodeChef: Practical coding for everyone

21

In java you can implement editorial’s method like this:
https://www.codechef.com/viewsolution/19737889

(I was getting TLE if I pre-processed using Lists of Java)

22

Author’s solution link is wrong. It should be for the tester. Correct one is : b1dJXm - Online C++0x Compiler & Debugging Tool - Ideone.com

23

I was so close to a full AC in this one. I didn’t realize we could precompute the good pairs and store them to speed up each test case. TLE on the absolute last test case :frowning:

24

Correct. Check again.

25

@aryanc403, think you. Hint: The answer is yes and instead of using only the linear sieve, we can use an additional O(N) loop again. Do you get some hint or more is required?