Hello,
First of all thanks for the initative, i am new on this website and enjoy the challenges so far.
I have some issues with these 2 beginner problems : FCTRL and FCTRL2. I have browsed the Forum already but I did not find anything relevant that might help me. I mainly code in Java and I am not an expert, the issues I am having are :
Wrong answer for FCTRL.
Too much time for FCTRL2.
In both case it takes at lest 2 minutes for the tests to compute and to send me a response.
I don’t really see what is wrong in my code as I get the good answers for the examples given in the problem wording and it is fast.
Here are my programs :
FCTRL :
import java.io.IOException;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
PrintWriter stdout = new PrintWriter(System.out);
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
BigDecimal value = new BigDecimal(sc.nextInt());
int trailingZeros = 0;
while (value.divide(new BigDecimal("5")).compareTo(new BigDecimal("1")) == 1) {
trailingZeros += value.divide(new BigDecimal("5")).intValue();
value = value.divide(new BigDecimal("5"));
}
stdout.println(trailingZeros);
}
sc.close();
stdout.flush();
stdout.close();
}
}
FCTRL2 :
import java.io.IOException;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class Main {
public static BigInteger[] compute(int max){
BigInteger[] nFact = new BigInteger[max];
nFact[0] = new BigInteger("1");
for (int i = 1; i < max; i++) {
nFact[i] = nFact[i-1].multiply(new BigInteger(i+1+""));
}
return nFact;
}
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
PrintWriter stdout = new PrintWriter(System.out);
int n = sc.nextInt();
List<Integer> values = new ArrayList<Integer>();
for (int i = 0; i < n; i++) values.add(sc.nextInt());
int max = Collections.max(values);
BigInteger[] nFact = compute(max);
for (int i = 0; i < n; i++) {
stdout.println(nFact[values.get(i)-1]);
}
sc.close();
stdout.flush();
stdout.close();
}
}
I really hope someone can help me ! Thanks !
EDIT :
For FCTRL to work I had to change the condition
If you can explain your algo in both codes, like what you did or what your thought process, i can help you further (not much acquainted with java).
As for FCTRL, big integer is supposed to give you TLE. The problems etter wanted you to do some clever implementation (Its actually a medium level problem).
Hi,
Thanks for the quick answer. I think i know where the issue was in FCTRL, I’ve modified my code and am currently running the verification. I am using BigDecimal though which might lead to TLE. I’ll try to switch back to double as it might be precise enough in the case BigDecimal does not work.
For FCTRL2, I find it weird that it gives me TLE as I ran it multiple time locally and it gave me an answer instantly. even it the worst case (100 inputs of the number 100) it was an instant answer.
I thought the complexity was not too bad as I only compute the largest number’s factorial and store all steps in an array. This way if I want to get any factorial of a number I just have to access its position in the array…
Anyway I’ll try to reproduce the code you’ve given and post an update here.
Your computer gave correct output, within stipulated time? Hmm, then i dont think TLE should had been there. Since you are using pre-computation, i too think that its the way to go (i mistook your algo to be computing every numbers factorial from scratch, sorry for that!)
Anyways, waiting for your update before beginning any further investigation :).
Alright, so FCTRL gave me AC after the tiny modification; so that’s done. I can maybe send my code for FCTRL2 again but with detailed comments on the way it works ?
I ran your code on worst case. It worked in 0.13 seconds. Moreever, i am seeing worse time algorithms pass too. I see people reporting that in contest also, some are getting unnecessary TLE, so i will suggest that you try aain submitting tomorrow MORNING (as load on server should be less at that time)
No, in the thread “Codechef submissions are very slow” (Its in front page only), people said that they tested it. They wrote program which only took input, and reported to get TLE, so i feel its server issue.
