Sort 15 Discussions, By:
Please Login in order to post a comment
Took me some time to realise the output of 5 1 2 is 10007 10009 instead of 10007 10037 (Python, it gave wrong answer for Test #3 and #10).
5 1 2
Was trying to save time by returning the first plausible result from digit replacement generated by looping through digits from 0 to 9, and it turns out that way it's not necessarily the minimum result.
Eventually I computed all plausible results from all digit replacement and its corresponding permutations. I would say it's too ugly to my taste.
EDIT: Made use of generator combining permutations with deque() to yield the next smallest replacement position, so it does not have to generate the whole thing in advance. Sounds simple, troublesome to implement. The slowest time for me is 4.74s for #18. Previous version took almost 8s...
test cases are weak.
for input 3 2 1 my solution is giving output 113, but it should be 101.
Hey, I seem to be getting WA for cases 7 and 8 only. Any boundary cases that I need to be careful about?
same here, still not getting the issue ...
Make sure the number you're currently considering is actually in the set that you print, otherwise you might output a non-minimal solution...
Thanks very much, this saved me.
7 4 6
2422027 3433037 5455057 6466067 8488087 9499097
Am I missing something, or for sample input #01 (2 1 3) there are many possible answers? ((11, 13, 17), (11, 13, 19), (11, 31, 41), (11, 31, 61) and so on)
If so, how should we decide which solution to choose?
The minimalistic set. Say 11 is smallest for 3 length family, then compare on second number and so on.
please fix the description to address this
You have to actually consider those numbers only which gives only 3 prime numbers if arranged as per the input conditions. Like if you are considering (11,13,17) by fixing 1 and replacing 2nd digit with some number will also give 19 as prime number. So it will be considered for L as 4 but the input is 3.
Then why does it say, "Print the first L numbers of the prime value family"?
That seems to suggest the family can be larger than L, but it only wants you to print the first L.
finally , i finish ;) ,, this problem is very good
8 4 7
.. i like this problem,
the first , i build prime <=100000000 ,, then
i use dfs to creat all permutation
,, then , use them to test all prime in condition n ,,
Can someone please tell what is Test Case 16.
I've all tests but Test Case 16. Can someone suggest any way to reduce number of primes we scan or choosing k from n digits.
Really liked the problem.
But for the one test case which is 7 1 ? I had to cheat a bit. I am using JAVA and in the test environment I got the test passing in 2.8 seconds although sometimes it also timedout but in grading it timedout every time.
I had rewritten a lot of logic just for the one test case yet it still was not enough. As I had no ideas on how to improve more. Based on the answer from test environment for 7 1 I just limited the prime count to be analysed. That enabled me to pass the case.
Did it with python3 and really had to squeeze everything out to get it under time. However, interesting to note that only about 25% of the time was spent in divisibility tests. A lot of little stuff was killing me, binary search and sorting, and both could probably be eliminated. I think you could get close to 1 second on 18 and 19 in C.
(a) Prime sieve up to 10^7
(b) Look for primes nearest to 10^(N - 1) and go up
(c) Assemble masks by recursion, ensuring along the way that all replaced digits are equal