TIMPLEM - EDITORIAL

PROBLEM LINK:

Practice
Contest

Setter: Abhishek Pandey
Tester: Taranpreet Singh
Editorialist: This person

DIFFICULTY:

Simple (if you can understand the evil function of Setter :D)

PREREQUISITES:

Precomputation, Sieve of Eratosthenes and Prefix Sums would be enough.

PROBLEM:

Given T ranges L_i and R_i, compute the evil function for each range. Evil function can be referred from problem statement.

SUPER QUICK EXPLANATION

  •   For $x$, The flag given in problem is 0, if and only if $x$ is prime.
    
  •   Suppose we have an array $A$, $A[x] = x^x$, if $x$ is prime, else 0.
    
  • We just need Sum of A[x] for x \in [L_i, R_i], This can be easily done with Prefix Sum or Segment tree, as you wish to.

EXPLANATION

Let us discuss the evil function of Setter first.

  • Notice the innermost loop on variable j. It is just checking whether j is prime, by common prime testing in O(sqrt(N)). cantCheckJ is 0 if and only if j is prime.
  • If j is prime, it checks whether i is divisible by j, setting flag = 1 if i%j == 0.
  • So, Indirectly this function is checking for every i if i is divisible by any prime number from 2 to i-1, that is, checking if i is prime or not.
  • If i is prime, it adds i^i to answer.

So, we can simply write above function as

For x \in [L_i, R_i], if(isPrime(x))Sum+=x^x

Sub-task one can be solved by this much, but Don’t you expect 100 points, just by translating Vijju’s evil function, since Taran was devil enough to ask so many queries. (To time out their solutions in I/O itself)

For subtask two, we need to do something more.

Let us denote ans(L, R) as the answer for query(L,R).

We can notice that ans(L,R) can be represented as ans(1, R)- ans(1, L-1). You can verify that by observation as well as Mathematical Induction.

So, it suffices just to find ans(1, x) for all x \in [1, 10^5]. Also, ans(1, P) can also be written as ans(1, P-1) + A[P].

So, what are you waiting for?? Just compute prefix sum of array A and print ans[R]-ans[L-1] as answer.

Getting WA??, That’s probably because of modulo. It is possible that ans[L-1] is greater than ans[R] since we are working in modulo. So,we get the answer in negative. IN order to overcome this, I am giving you all a lifetime modulo hack. :stuck_out_tongue:

Answer if (ans[R]-ans[L]+mod)%mod. The proof is left as an exercise.

Complexity:
Precomputation take O(MAX) time and per query time is O(1). MAX = 10^5 for this problem.
So, overall complexity is O(MAX+T).

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution

Click to view
/*
 *
 ********************************************************************************************
 * AUTHOR : Vijju123                                                                        *
 * Language: C++14                                                                          *
 * Purpose: -                                                                               *
 * IDE used: Codechef IDE.                                                                  *
 ********************************************************************************************
 *
 Comments will be included in practice problems if it helps ^^
 */
 
 
 
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
vector<int> primes;
bool isComposite[100001]={1,1};
long long ans[100001]={0};
void sieve()
{
    int i,j;
    for(i=2;i<=100000;i++)
    {
        if(!isComposite[i])
            primes.push_back(i);
        //cout<<"i="<<i<<" Marked composite: ";
        for(j=0;j<primes.size() and i*primes[j]<=100000;j++)
        {
            isComposite[i*primes[j]]=1;
            //cout<<i*primes[j]<<" ";
            if(i%primes[j]==0)break;
        }
        //cout<<endl;
    }
}
int mod=pow(10,9)+7;
 
int fastExpo(int a,int n)
{
    if(n==1)return a;
    else if(n==2)return 1LL*a*a%mod;
    else if(n&1)return 1LL*a*fastExpo(fastExpo(a,n>>1),2)%mod;
    else return fastExpo(fastExpo(a,n>>1),2);
}
 
int main() {
	// your code goes here
	//#ifdef JUDGE
    //freopen("Large10.txt", "rt", stdin);
    //freopen("O-Large10.txt", "wt", stdout);
    //#endif
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
 
	int t,i;
	sieve();
	for(i=2;i<=100000;i++)
	{
	    if(!isComposite[i])
	    {
	        ans[i]+=fastExpo(i,i);
	        ans[i]%=mod;
	    }
	    ans[i]+=ans[i-1];
	    ans[i]%=mod;
	}
	//for(i=1;i<=10;i++)cout<<ans[i]<<" ";cout<<endl;
	//for(int i=1;i<=10;i++)cout<<primes[i]<<" ";cout<<endl;
 
	cin>>t;
	//assert(t==100000);
 
	int l,r,a,b;
	while(t--)
	{
	    cin>>a>>b;
		assert(a<=b and a>0 and b>0);
	    l=lower_bound(primes.begin(),primes.end(),a)-primes.begin();
	    r=upper_bound(primes.begin(),primes.end(),b)-primes.begin()-1;
	    if(r<0)
        {
           assert((mod+ans[b]-ans[a-1])%mod==0);
           cout<<0<<'\n';
           continue;
        }
	    //cout<<l<<" "<<r<<endl;
	    l=primes[l];
	    r=primes[r];
	    //cout<<a<<" "<<b<<" "<<l<<" "<<r<<endl;
	    assert((mod+ans[b]-ans[a-1])%mod==(mod+ans[r]-ans[l-1])%mod);
	    cout<<(mod+ans[r]-ans[l-1])%mod<<"\n";
 
	}
	return 0;
}

Tester’s solution

Click to view
import java.util.*;
import java.io.*; 
import java.text.*;
//Solution Credits: Taranpreet Singh
public class Main{
    //SOLUTION BEGIN
    void solve(int TC) throws Exception{
        long[] sum = new long[MAX];
        boolean[] comp = new boolean[MAX];
        for(int i = 2; i< MAX; i++)if(!comp[i]){
            sum[i] = pow(i,i);
            for(int j = i+i; j< MAX; j+=i)comp[j] = true;
        }
        for(int i = 1; i< MAX; i++)sum[i] = (sum[i]+sum[i-1])%mod;
        for(int qq = ni(); qq>0;qq--)pn((mod-sum[ni()-1]+sum[ni()])%mod);
    }
    int time = 0;
    long pow(long a, long p){
        long o = 1;
        while(p>0){
            if(p%2==1)o = (o*a)%mod;
            p/=2;
            a = (a*a)%mod;
        }
        return o;
    }
    //SOLUTION ENDS
    long mod = (int)1e9+7, IINF = (long)1e12;
    final int MAX = (int)1e5+1, INF = (int)1e9, root = 3;
    DecimalFormat df = new DecimalFormat("0.00000000");
    double PI = 3.141592653589793238462643383279502884197169399375105820974944, eps = 1e-8;
    static boolean multipleTC = false, memory = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        for(int i = 1, T= (multipleTC)?ni():1; i<= T; i++)solve(i);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
        else new Main().run();
    }
    long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
    int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n(){return in.next();}
    String nln(){return in.nextLine();}
    int ni(){return Integer.parseInt(in.next());}
    long nl(){return Long.parseLong(in.next());}
    double nd(){return Double.parseDouble(in.next());}
 
    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }
 
        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }
 
        String next(){
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        String nextLine(){
            String str = "";
            try{    
                str = br.readLine();
            }catch (IOException e){
                e.printStackTrace();
            }   
            return str;
        }
    }
}    
1 Like

AUTHOR’S AND TESTER’S SOLUTIONS Links Access Denied.

Analysis of Contestants Solutions

I had a great time overseeing the solutions of contestants for this problem. When we made the set, this was supposed to be the easiest problem of the set. Initially, it was #2 on set, because some coders found Partitioning Vijju intuitive dp which they knew.

All the solutions submitted in first few minutes had two things in common-

  • They were all in Python.

  • They all literally copy pasted the
    Evil function and submitted for
    partial.

Lmao, I kind of anticipated that, and made sure that it gets TLE for all test cases. Evil enough :D. Doesnt stop here, this was followed by many C++ solutions trying to get the evil function pass by applying heuristics, using break statements etc.

Now that I mentioned it, let me discuss the sub-task logic. This was supposed to be the easiest problem, this set we kind of got rid of “cakewalk” difficulty. Its just experimental, we wanted new users to feel that they know things, but need a little more for that AC. Getting into the scoring, first notice the evil function. What does it do? For all integers in range [L,R], it first checks if its prime by seeing if its divisible by any number smaller than it, and further, it has a redundant check that “For every number in [L,R] say K, first take a number smaller than it, check if its prime, then see if the K is divisible by it. If yes, then K isnt prime and we cannot add it.” Obviously, the last part of checking if divisor is prime or not is very, very redundant. I was happy giving 30 points to anyone who eliminated this part-

for(k=2;k<=FindSquareRootOf(j);k++)
                if(j%k==0)
                    cantCheckJ++;

Merely eliminating this part and submitting fetched people 30 points, which was the perhaps only cakewalk aspect of this contest XD. But still, not many users did that :/. I saw lot of people using break, heuristics etc. but they failed to observe the redundancy. Better luck next time!

That being said, python proved to be a favourite language for many guys this time. For top coders due to its in-built fast exponentiation and handling large numbers, and for new coders cause they can directly copy paste the EvilFunction and submit lol (only to get a TLE :stuck_out_tongue: ).

Lets move on to the full solution. Obviously, its summation of {i}^{i} in range [L,R] with condition that i must be prime. Sounds easy, right? I still saw a couple of surprising WA even from div1 guys, especially some 6 stars :p. Python guys loved its handling of large numbers so much that they forgot to print ans \%MOD. Then, some had implementation bugs where it didnt count L if L was a prime. Seeing those, I joked and wondered what if we had a penalty of 30 minutes per WA? :stuck_out_tongue:

But all in all, it was fun seeing you guys at it! Hopefully there werent any weak cases, I tried my best to set a lenient time limit so that all 3 major languages( JAVA, Python, C++) have no issues. Among the limited solutions I saw, I didnt saw any brute force passing - the majority of the pool was just evil function copy pasted trying to get it work XD. But seeing that, I’d emphasize to contestants that solving a problem without thinking is walking without direction- you’ll be back to square 1! Think, what are you going to do, how will you approach it, and try to implement it carefully with least bugs. This approach is going to make things easier and problem solving even more fun for you :slight_smile:

Regards
@vijju123

(PS: Looks like the implementation wasnt terrible enough :(. Lets see if we can make the problem nastier :wink: )

2 Likes

If its not fixed by tomorrow we will upload code on editorial for you guys to copy and see.

plz upload code in the ediorials, as done in previous #1 Editorials. Its not yet fixed.

Done for this problem. We will talk to @admin on why solutions are moved yet.

1 Like

Here’s a python implementation (if someone can let me know how to do the hidden content thing I’ll modify):

# https://www.codechef.com/problems/TIMPLEM

mdl = 1000000007
lim = 100001

# sieve for primes
prm = [False,True]*((lim+1)//2)
prm[1] = False
prm[2] = True
for k in range(3,317,2):
    if prm[k]:
        for m in range(k*k, lim, 2*k):
            prm[m] = False
        
# accumulate evil
evilcum = [0]*lim
ev = 0
for k in range(2,lim):
    if prm[k]:
        ev += pow(k,k,mdl)
    evilcum[k] = ev

# respond to input
for _ in range(int(input())):
    l,r = map(int, input().split())
    print( (evilcum[r] - evilcum[l-1])%mdl )