Explanation of alternate solution in a very easy to understand language
Lets say that the element under consideration is
A[i]
Using factorization we will find all the distinct factors of all the elements before A[i] namely A[0], A[1], … ,A[i-1]
Lets keep an array named count[100005] that will keep count of number of times a factor has appeared.
Now we have all the factors of all the elements before A[i] and if A[i] would have been a factor of elements before A[i] then it would have been reflected in the count array that we are maintaining to count how many times a factor occurs.
Now we simply need to find the maximum value in the array count.
The array int dp[10^{6}+1] is used to store the count of divisors 1 \le d \le 10^{6} for all previous subsequene items A_{j}, 1 \le j <i, in the i-th iteration. Initially, dp[d] = 0 for all d. The maximum star value can be computed iteratively as \max \limits_{i=1}^{n} dp[A_{i}]
Brother…you get TLE hence your approach is OK…you just need to optimise it.
I review your code https://www.codechef.com/viewsolution/27403611
You are calling max function in loop 2 everytime even it is not needed…Max should be called after execution of loop 2.
I think for test cases in which loop 2 runs frequently it generates TLE…
you can re submit your code again …Of course it will not give you point…
But you can check.
If the condition remains same…Update me and then @admin will take care of it.
Try 2 loop inside if h[i]==0…
i knew it is a hit and trial.
Honestly, i couldn’t get the main reason …why your code isn’t running successfully.
Hope,expertise will look into this matter.
I think Codechef really needs to adopt a policy of always allowing tons of testcases in a testfile (at least 100 - possibly more like 1000) and always controlling the total size by having constraints of the form “blah less than or equal to bloo over all testcases” (in addition to per-testcase constraints) - you can’t think of every way a contestant can “game the system”, and randomised testcases often flush out these kind of things after ~100 or so testcases.
This would have been useful in ZOMCAV where a ton of people used an approach that was so obviously wrong that the Setter and Tester (understandably!) didn’t think of it, but which can be usually revealed as false only after ~150 random testcases. As far as I can tell, they still haven’t added testcases to guard against this wrong approach
Edit2:
Hehe - the same user also exploited this flaw in the testcases for ZOMCAV XD Edit3: Wait, no - I think he’s found an even deeper weakness in the testcase data - this one is exposed almost immediately by randomised tests. How is he doing this?? XD
Yes, we just found the test cases for this problem too weak after the contest started.
I also agree that codechef needs to allow problems to have many test cases. The reason that we minimize the number of tests is “to reduce server loads”…
But even if you can make a lot of tests, it’s still hard for some problems to make very perfect test data. MSV is an example IMO.
Assuming you meant CodeChef: Practical coding for everyone - there are two extra testcases that have been added in Practice mode that were not in the original OCT19B where adityas’s solution is taken from:
