TLE in BINTOUR while submitting in Scala

Why I’m getting TLE in BINTOUR while submitting in scala?

(Link for scala submission-CodeChef: Practical coding for everyone)

object Main
{

var Fact=new Array[Int](1000005)

var InvFact=new Array[Int](1000005)

var MOD=1000000009

def modPow(P:Int,Q:Int):Int=
{
	var X=1
	var A=P
	var B=Q
	while(B>0)
	{
		if(B%2==1)
		{
			X=(X*A)%MOD
			A=(A*A)%MOD
			B=B/2
		}
	}
	X
}

def GenerateFactorial():Unit=
{
	Fact(0)=1
	Fact(1)=1
	Fact(2)=2
	for(i<-3 until 1000002)
	{
		Fact(i)=(Fact(i-1)*i)%MOD
	}
}

def InverseMod(A:Int):Int=
{
	modPow(A,MOD-2)
}

def GenerateInverse():Unit=
{
	InvFact(0)=1
	InvFact(1)=1
	for(i<-2 until 1000002)
	{
		InvFact(i)=InverseMod(Fact(i))
	}
}

def C(N:Int,R:Int):Int=
{
	var Comb=1
	Comb=Fact(N)*InvFact(R)
	Comb=Comb%MOD
	Comb=Comb*InvFact(N-R)
	Comb=Comb%MOD
	
	Comb
}

def main(args:Array[String])
{
	GenerateFactorial()
	GenerateInverse()
	
	var N=readInt()
	
	var P=1<<N
	P=P-1
	
	for(i<-0 until P)
	{
		if(i<((P/2)-1))
		{
			println("0")
		}
		else
		{
			var sol=1L
			sol=(sol*Fact(P/2)*2)%MOD
			sol=(sol*C(i,P/2-1))%MOD
			sol=(sol*Fact(P/2))%MOD
			println(sol)
		}
	}
}

}

The same solution when submitted in C++ got me AC
Link of submission in C++:-
http://www.codechef.com/viewsolution/3541422

Hi,

The time limits for non-imperative languages are not correctly set for most problems…

Most problem setters never change the specified time limits accordingly so most solutions will always give TLE…

This is true in ALL of functional programming languages such as Scala, Clojure, Haskell, etc…

From now on I will set the time limits for these languages with a 4 to 8x multiplier so that people can still submit problems in these languages.

(In fact, the limits in Hackerrank for Haskell and Scala are as high as a 16x multiplier…)

Best,

Bruno

1 Like