Mockvita 1 2020 Problem B - Prime Fibonacci

I was getting Wrong Answer in private test cases. Can anybody please help me?

import math

from itertools import permutations

primes = []

def getPrimes(limit):

    for i in range(2, limit+1):

        isPrime = True

        for j in range(2, i//2 + 1):

            if i%j == 0:

                isPrime = False

                break

        if isPrime:

            primes.append(i)

if __name__ == "__main__":

    getPrimes(10000)

    n1, n2 = [int(x) for x in input().split()]

    filtered_primes = [x for x in primes if x >= n1 and x <= n2]

    l = [int(str(x[0]) + str(x[1])) for x in list(set(permutations(filtered_primes, 2))) if int(str(x[0]) + str(x[1])) in primes]

    l = list(set(l))

    a = min(l)

    b = max(l)

    count = len(l)

    for c in range(3, count+1):

        s = a + b

        a = b

        b = s

    print(b, end="")

Thanks in advance…

I couldn’t do this too, I wrote this explicitly in python because for range 1 to 100, the 2nd list will have around 128 primes. As we know considering starting points (0,1), we can only store 94th fibonacci number in signed long long. so there is no way we can store 128th fibonacci number whose starting 2 number are greater than 2… However one of my friend got this accepted in Java using “Long” type.

There can be two things -

  1. My solution is wrong.
  2. The output generator didn’t take into account the overflow that might occur.So the test cases were faulty.

I would like to know if someone got it correct using Big-Integer or in python Only.

import java.util.*;
import java.io.*;
class compete {
static void generatePrime(TreeSet<Integer> primes){
    boolean[] sieve=new boolean[10000]; Arrays.fill(sieve,true);
    for(int i=2;i<sieve.length;i++){
        if(sieve[i]){
            primes.add(i);
            for(int j=2*i;j<sieve.length;j+=i) sieve[j]=false;
        }
    }
}
public static void main(String args[] )throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    int[] a = Arrays.stream(br.readLine().split("\\s+")).mapToInt(Integer::parseInt).toArray();
    TreeSet<Integer> primes=new TreeSet<Integer>();
    generatePrime(primes);
    Object[] firstList=primes.subSet(a[0],true,a[1],true).toArray();
    HashSet<Integer> combinations=new HashSet<Integer>();
    for(int i=0;i<firstList.length;i++){
        for(int j=i+1;j<firstList.length;j++){
            combinations.add(Integer.valueOf(Integer.toString((int)firstList[i])+(int)firstList[j]));
            combinations.add(Integer.valueOf(Integer.toString((int)firstList[j])+(int)firstList[i]));
        }
    }
    Iterator it=combinations.iterator();
    TreeSet<Integer> secondList=new TreeSet<Integer>();
    while(it.hasNext()){
        int n=(int)it.next();
        if(primes.contains(n)) secondList.add(n);
    }
    long f1=(long)secondList.first(),f2=(long)secondList.last(),f3=0;
    for(int i=3;i<=secondList.size();i++){
        f3=f1+f2; f1=f2; f2=f3;
    }
    pr.println(f3);
    pr.close();
}
}

I don’t know actually why but initially I wrote the code in python but it gave me runtime error + presentation error but when I wrote the same code in C++, it got accepted.
Approach was simple just followed the instructions of question and nothing else.

I am not able to understand why you are finding permutation because no where in question is mentioned about permutation, simple

a = min(primes)
b = max(primes)

now just find the kth fibonacci number using a and b where k is the size of prime list

2 100 will give you a very large answer

Step 2 says you need to find all unique combinations…

Same happened with me. I try much testcases and on large second number and very small first number, my python code gives a large output.

it does not mean in this sense…
see let’s take this example:

A = [1, 32, 41, 26]

all combinations = 1 + 32 = 132
                   1 + 41 = 141
                   1 + 26 = 126
                   32 + 1 = 321
                   32 + 41 = 3241
                   32 + 26 = 3226
                   41 + 1 = 411
                   41 + 32 = 4132
                   41 + 26 = 4126
                   ..............   

final_list = [132, 141, 126, 321, 3241, 3226......]
        

before combinations, you need to have a list of all primes from n1 to n2 (input)…so your list is wrong…

See, i made this list just to make you understand about the concept. when did I say that this is prime list??
I just thought it would help you in making sense of what the question is asking

because even you didn’t understand properly how to make combinations out of first prime list!!

I understand what you’re trying to say…but in the code I’m making combinations by converting them to strings, concatenating them and putting the result in a new list…that’s like a shortcut to combine integers.

And I’ve ran the code, and it’s giving me the output…what’s the point of arguing?

#include
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
// your code goes here
int i,j,n,sp=0;
ll n1,n2,tmp;
cin>>n1>>n2;
int arr[9999]={0};
vector primes;
vector combinations;
vector presence(9999,0);
for(i=2;i<=9999;i++)
{
if(arr[i])
continue;
else
{
if(i>=n1 && i<=n2)
primes.push_back(i);
for(j=i*2;j<=9999;j+=i)
{
arr[j]=1;
}
}
}
n=primes.size();
n1=9999;
n2=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i==j)
continue;
if(primes[j]<10)
{
tmp=primes[i]*10+primes[j];

      }
      else
      {
          tmp=primes[i]*100+primes[j];
      }
        combinations.push_back(tmp);
        if(arr[tmp]==0 && presence[tmp]==0)
        {
	        if(tmp>n2)
	        n2=tmp;
	        if(tmp<n1)
	        n1=tmp;
	        sp++;
	        presence[tmp]=1;
        }
      
  }

}
for(i=3;i<=sp;i++)
{
tmp=n1+n2;
n1=n2;
n2=tmp;
}
cout<<tmp;

return 0;
}
This solution cleared private test cases.See this you may get some idea.

I tried Python too, couldn’t get it to work.

1 Like

@chaudhary_19
@mohittkkumar
Please help me why I am wrong…

from itertools import permutations
a,b=map(int,input().split())
l=[]
for j in range(a,b+1):
p=0
for k in range(2,j):
if(j%k==0):
p=1
break
else:
pass
if(p==0):
l.append(str(j))

l=set(l)
lx=[]
lp=permutations(l, 2)
for e in lp:
z="".join(e)
lx.append(z)

l2=[]

lx=list(set(lx))

for e in lx:
e=int(e)
p=0
for k in range(2,e):
if(e%k==0):
p=1
break
else:
pass
if(p==0):
l2.append(e)

l1=sorted(l2)
a=l1[0]

b=l1[-1]

n=len(l1)
for i in range(3,n+1):
s=a+b
a=b
b=s
print(b)

A s i suspected, the integer overflow was not taken into account, using long long int was not sufficient, but still it got accepted because the test cases were made using that only. That’s why all python solutions kinda failed.

Don’t get mislead by his use of permutations function… His full sentence means finding the permutation of any two objects taking from that list. Meanwhile permutation of a and b, is “ab” and “ba” only, which you tried to explain. So there is nothing wrong in that part. It does something similar what you said in the example.


Here what do we mean by permutations. What you are taking about is the value of nPr. But here in the question we need to find all unique permutations.