Contest - 5 Hints to the Problems [OFFICIAL]

CodeChef-DSA-learners
,
22

Hey
Using Matrix exponentiation gives me TLE in FIBEASY.
Solution:- CodeChef: Practical coding for everyone

23

Hey
Using Matrix exponentiation gives me TLE in FIBEASY.
Solution:- CodeChef: Practical coding for everyone

24

can someone point out mistake in my code of CHMODā€¦followed as per the hints aboveā€¦precalculated the frequencies of each prime in dummy arrayā€¦but getting WA when submitted.
here is my code

25

Hey @rishup_nitdgp
In kth prime problem if k==1 how can answer be number of primes in range (a,b).
e.g. INPUT : 2 5 1
then according to you answer should be 3 (as 2 3 5 are prime) but answer is 4(as 2 ,3,4,5 have only 1 prime divisor)

27

Can anyone explain me the ā€œhint 2ā€ mentioned for problem Chef and Squares?

I understood that it would be factor of such two numbers which can be expressed as sum of two numbers X and M and other can be expressed as difference of X and Mā€¦ But at this point what will be the efficient way to check if we have such the divisors which can be expressed as sum of X and M and difference of X and M?

28

can anyone tell why my output Is wrong ??
problem (Yet Another Problem About Sequences)
code https://www.codechef.com/viewsolution/37186669
I think it should pass partial test case.
For full test case values becomes more than 1e9.
Help would be much appreciated.

29

why will prefix sum in CHMOD fail ??

32

As value of Mi is changing at every test case. If we form a prefix multiplication array before test cases then values in the array will overflow and we have to use modulo which we canā€™t because Mi is changing as I mentioned earlier.

33

CHMOD

Can anyone explain the idea for this problem?

34

In CHEFPRMS, could anyone guide why Iā€™m getting a segmentation fault?
#include <bits/stdc++.h>
using namespace std;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(tā€“){
int n;
cin>>n;
bool flag=false;
int prime[202];
for(int i=0;i<=n;i++){
prime[i]=1;
}
prime[0]=prime[1]=0;
for(int i=2;ii<n;i++){
if(prime[i])
for(int j=ii;j<=n;j+=i){
prime[j]=0;
}
}

    vector<int> semi;
    for(int i=2;i<=n;i++){
        for(int j=2;i<=n;j++){
            if(prime[i]!=prime[j] && prime[i]*prime[j]<=200){
                semi.push_back(prime[i]*prime[j]);
            }
        }
    }
    
    unordered_set<int> sum;
    
    for(auto i=semi.begin();i!=semi.end();i++){
        for(auto j=semi.begin();j!=semi.end();j++){
            sum.insert(*i+*j);
        }
    }
    semi.clear();
    unordered_set<int>::iterator itr;
    for(itr=sum.begin();itr!=sum.end();itr++){
        if(n==*itr)
            flag=true;
    }
    
    if(flag)
        cout<<"YES\n";
      else
        cout<<"NO\n";
}
return 0;

}

35

What does false Hint mean for the problem EARTSEO?

36

in question it is mention that factor must be different

37

Can anyone explain question 1 I am not understanding the question itself.

38

Can anyone explain question no. 1. I am not understanding the question itself.

39

Question: CHEFPRMS

I have solved this problem with the given constraints.
But as given in the hints section. What to do for higher constraints??

40

is CHEFPRMS solvable with python3 or pypy3 ? cause iā€™m pretty sure i wrote code as per editorial still showing me TLE. now i think its because iā€™m not using a fast language ? Can anyone plz ans.

prime = [True for _ in range(201)]
prime[0] = prime[1] = False

def seive_of_eratosthenes(n):
    for i in range(2, 201):
        if prime[i] is True:
            for j in range(i*i, n+1, i):
                prime[j] = False


def is_semi_prime(n):
    for i in range(1, n+1):
        if n%i == 0:
            if i==n//i:
                continue
            if prime[i] and prime[n//i]:
                return True
    return False

def is_ans(n):
    for i in range(1 , n+1):
        if is_semi_prime(i) and is_semi_prime(n-i):
            return True
    return False

seive_of_eratosthenes(200)
T = int(input())
for _ in range(T):
    n = int(input())
    if is_ans(n):
        print("YES")
    else:
        print("NO")
41

Iā€™ve just solved the issue. Issue was while taking inputs. I used sys.stdin.readline then the test cases passed

42

Can someone please tell where im going wrong in subtask 2 of Chef and Squares
https://www.codechef.com/viewsolution/46637612

43

Can someone please explain to me why my code does not work for FIBEASY I have brute tested it with literally all the test cases for n < 10 ** 10 and it gives all the correct answers. Also it passes subtask one but gives wrong answer on subtask two.

from math import log2
T = int(input())
for _ in range(T):
power = int(log2(int(input())))%4
print(9 if power== 1 and N!= 2 else power)

44

Can anyone please tell me my where am I going wrong in FIBEASY
https://www.codechef.com/viewsolution/47894277