Hey guys,
Sadly the contest was unrated, but lets keep the discussion going! So, how did you all approached the problems? What are your views regarding the problems and topics? 
1 Like
how to solve FRCPRT? I thought of taking the last U/D and L/R and creating a solution from that but not only it was wrong/ it gave me TLE :|. The complexity was O(|S|)+O(m*n) to make the solution. Is there something better. I don’t need a solution, just a hint. I think I should have used FastIO
My approach for Prime Divisors-
Intense pre-processing. Use a sieve to determine S[i] values for all numbers. Then use sieve-like loop to find all numbers such that A_i\%A_j==0 and S[i]\%S[j]==0 as well.
This can be implemented as-
for(i=1;i<=1000000;i++)
{
for(j=2*i;j<=1000000;j+=i)
{
if(sumFactor[j]%sumFactor[i]==0)
{
nums[i].push_back(j);
}
}
}
Now, all thats left is making a frequency array of what elements are in the array and accounting for contribution of each element.
for(i=2;i<=1000000;++i)
{
if(!freq[i])continue;
for(int j:nums[i])
{
if(!freq[j])continue;
//cout<<i<<" "<<j<<" "<<freq[i]<<" "<<freq[j]<<endl;
ans+=1LL*freq[i]*freq[j];
}
ans+=1LL*(freq[i]-1)*freq[i];
}
Running outer loop for every element of array time outs because then O(NLogN) running time isnt guaranteed. Why? Recall that maximum elements in my nums[i] array will be for 2. If we run a loop for array elements, say every element is 2, then for each one nums[2] will be run from start to end. Hence, TLE. Above approach guarantees that nums[i] for each i runes only once giving O(NLogN) time.
4 Likes
Problem - PRMDIV.
I feel this problem is reason of all trouble.
Last test case was giving TLE. - Root cause of all trouble.
I myshelf made 15 submission with different optimizations.
Just to pass one test case instead of trying a new approach. But all failed against that test case.
And I was becoming greedy as time was passing. And contributed in increasing queue. xD
did same thing !!! getting TLE in last subtask
Did you also do the mistake I pointed out?
@beardaspirant Same here… exact same thing here, don’t understand how the solution can go wrong though. @vijju123 any idea? some problem in logic?
Check my post. Was it the same mistake you did?
can someone explain me the exact thing we have to calculate in the GCD SUM problem. what I understand from the sample case is that we have to calculate the sum of value of gcd of all the pairs (except two pairs in same row) and if so, can someone please point out my fault here
I fail on some test cases.
Test case
t = 1000
n = 1000
a[i]=i+2
Editorial for the first five problems is available:
Hope you all enjoyed the problemset.
1 Like
@hrishi1990 @beardaspirant. I was also doing the same thing. It works for a the given cases but is not correct.
000
010
101
ULD
Our approach won’t work for the above case. The editorial says to perform the first operation always and then do what we did. I haven’t completely understood the reason for doing so though
EDIT - On second though, I think I got it. You always have to perform the first operation because it would help in removing the 0’s between the 1’s column wise or row wise depending upon whether the operation is ‘L’/‘R’ or ‘U’/‘D’
Where Prmdiv editorial ??
I possible please share setter soln using ideone or other platform.
My solution used recursion and got TLE even at O(N*M) (I believe). Optimize it where ever possible.
Oops. t is atmax 100.
No, this is not my mistake.
What you thought of is partially correct because you need to consider one more movement which is first one. It can be any of L/R/U/D becuase that has impact on answer as if you perform LD or DL both will give you a different answer but in you case only considering last movement will of L/R and U/D will be the reason of wrong answer.
Talking about TLE it should not give TLE with this approach as i myself followed the same approach. TIP : If using endl avoid it.
Link is not working right now but i think soon it will resolve.
1 Like