ACM Amritapuri online contest Editorials

editorial
,
1

When will the editorials for ACM Amritapuri online contest will be posted ?
Its very eager to gain some knowledge :slight_smile:

1 Like
2

also please move the problems to practice.

1 Like
3

@a____ i think they stopped practice section for a while for acm contest. they are inaccessible to me too from listing page, however you can access them through a direct url still.

You could use google’s cache till the time they restore it back, eg: http://webcache.googleusercontent.com/search?q=cache:https://www.codechef.com/problems/school+&cd=2&hl=en&ct=clnk&gl=in :stuck_out_tongue:

or wayback https://web.archive.org/web/20150914180434/https://www.codechef.com/problems/school

4

Alright , Let me try to help , please upvote if you find useful

1)Mahasena - was a cakewalk and I think everyone who knows to code was able to do it .

  1. I solved next Devasena -

Pre - Requisite :

Fermat’s little theorem (there is a generalised theorem too) , simple maths , Modular exponentiation

Explanation :
Notations : A[] stands for our input array

Clearly the constraints 1<=N<=10^5 , tell me that either you need a O(N * LOG N ) solution , dont try to think DP as its complexity according to me will be N * max(A[i]) i.e. approx. 10^5 * 10 ^ 6 . Why? because you need the GCD of the subsets to make a transition.

Ok , moving on

We can think of clubbing the subsets with the same GCD so as to make the complexity.

So , lets decrement an iterator i from 10^6 to 1 trying to make the set with GCD i !

Now to make the subset with GCD(i) I can club it with any i*j where j is a non negative Integer.
Why ?

GCD(i , i*j ) = i

Now ,

We can build a frequency table for any element as the number is quite reachable!

Now , during the contest what I did was ,
keep the number of subsets with gcd(i) at f2[i]

hence what we do is sum frequency of all elements from j*i where j varies from 1 to floor(i/j)

now the subsets with a common divisor(and not GCD) as i is (2^sum - 1) .

Now we have to subtract from this sum the subsets with GCD greater than i and having i as a common divisor of gcd as i.

This can also be done within the same loop by taking summation of f2[i*j] where j varies from 1 to floor(i/j)

Now the subsets with GCD i equal to 2^sum -1 - summation of f2[i*j]
Just multiply i ( No . of subsets with GCD i times ) i.e. power ( i , 2^sum -1 - summation of f2[i*j] ) .
But now to calculate this the exponent part can overflow but you can take its % with given MOD-1 as MOD was prime! (Fermat little theorem) using modular exponentiation

Here is a snippet of my code as I am unsure that can we post the code now!

 for(i=max_ele; i >= 1;--i)
            {
                to_add=F[i];
                to_subtract = 0 ;
                for(j=2 ;j*i <= max_ele;++j)
                    {
                        to_add+=F[j*i];
                        to_subtract+=F2[j*i];
                        to_subtract>=(MOD-1)?(to_subtract%=(MOD-1)):0;
                    }
 
                subsets = (((power(2 , to_add , MOD-1) ) - 1) - to_subtract)%(MOD-1) ;
 
                if(subsets<0)
                    subsets = (subsets%(MOD-1) +MOD-1)%(MOD-1);
 
                ans  = ans * power(i , subsets , MOD);
                F2[i]= subsets;
                ans %=MOD;
            }

I feel like I had complicated the things by using F2, I feel like we can do it without F2 by not taking j = 1. but it’s okay I haven’t thought about it and this is how I managed to get AC .

In the problem Avantika , my thoughts were

  1. Compressing the numbers in 0-N
  2. Trying Mo’s Algorithm coupled with Fenwick tree and Frequency table over compressed Numbers.
    But I couldn’t debug my solution in time and hence unsolved. As the problems are not available in the PEER section , I cannot write the solution unless I know it runs within the time limit as the constant will be high!