PRMDIV - Editorial

editorial
, , , , ,
21

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

22

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.

23

ans += freq[i]*(freq[i] - 1) ;

ans += freq[i]*freq[good[i][j]] ;

Either use ans += 1LL*freq[i]*(freq[i] - 1) ; etc or use long long.

24

for(int i=2;i<=sqrt(MAX);i++) => Mistake is here, this is enough to compute if a number is prime is or not but not enough to calculate S[x]. Think about counter examples.

1 Like
25

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

26

https://www.codechef.com/submit/complete/19404615

Your AC code. A judicious and appropriate use of data structures is a must. Your map gave a heavy, extra logN factor. Also, use arrays wherever possible.

27

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

28

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.

29

Okay, got it, Thanks :slight_smile:

30

okay got itā€¦looks like someone already asked this question before
thanks :))

31

Its typo. Corrected it.

32

waiting for replyā€¦ plz someOne help

33

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

34

Because at any instance, only {10}^{4} of the {10}^{6} elements will be present in an array. This reduces time complexity. Further, if operations are basic,such as addition etc. then its easy to get {10}^{8}-{10}^{9} operations done in a second.

35

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

36

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]ā€ ?

37

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.

38

Can someone help me out ? I canā€™t find reason why it still TLE
Here is my code
https://www.codechef.com/viewsolution/19452525
Thank you!!

39

I tried implementing the solution in the editorial in Java. Its giving me TLE. Can someone please tell me why?
Solution Link: https://www.codechef.com/viewsolution/19435752

40

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)