All are prime numbers maybe. So, sieve thing isn’t beneficial
Weak testcases, I suppose: it fails on:
1
7
240 440 112 132 571 556 139
Edit:
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
It fails on anything above 100 value being as MSV for example
1
7
1000 1000 1000 1000 1000 1000 1000
he is simply reducing N(actual MSV number) to 100
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.
tl for python is very strict.I had to use sieve to get comlexity<nlog(n) then only it passed
I tried implementing similar solution like @aditya_kandi6 But getting 2 TLE don’t know why this is happening ,Someone please help .
my solution link : https://www.codechef.com/submit/complete/27537109
adityas solution link : CodeChef: Practical coding for everyone
I’m getting “Access Denied” for this link.
Edit:
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:
https://www.codechef.com/OCT19B/
Presumably, if adityas re-submitted his solution in Practice mode, it would also now TLE, like yours does.
“Sum of N over all test cases does not exceed 100,000”. What is the meaning and use of this line given in constraints ?
Can you help me with some suggestions to improve my code .
One optimisation that’s worth doing is to cache the value of sqrt(arr[i])
so that you’re not re-calculating it for every j
- not sure if it will be enough to make it AC though
Pretty much exactly what it says - add up the values of N across all T testcases, and the result is guaranteed to be \le 100000.
Without this line, the sum of N across all T test cases could be as high as T \times 100000 =1000000, and this would be too much computation to perform in 1 second. This line tells you that you never have to deal with this extreme case - the sum of N across all T testcases will be much lower than this extreme upper limit.
Thanks ,Got Accepted
Nice one - wasn’t sure if that would work, but am pleased to see it did
Was trying to implement the alternate solution but getting WA even on subtask 1.
Any ideas as to where I got wrong?
My solution
That’s a submission to SAKTAN, not MSV
Ah, sorry!
Solution worked ultimately!
Can you explain? I didn’t get the logic.
just awesome