Sort 4 Discussions, By:
Please Login in order to post a comment
My approach was to bottom-up fill an array A[i][j]. Where each cell represents the total number of ways you can select i elements from j possibiliities. The answer to the problem would be represented by the cell A[k-1][n-1].
The solution seems right, nevertheless I get a "Timeout Error" for the testcases 3 & 5. Is there a much more efficient way to solve that problem?
If you're computing the array each time it seems this solution would be on the O(T*n*m) ~ 10^9 which would explain why you ran out of time.
Precompute the array once for n = 1000.
Read the results for each test case out of the array.
Use a recursive function with memoization (easy for this problem)
I am unable to inculde the clojure.math.combinatorics namespace
could someone help me.. i am beginner in clojure.
(:require [clojure.string :as str])
(:require [clojure.math.combinatorics :as combo])
(def test_cases (Integer/parseInt(read-line)))
(def l (str/split (read-line) #"\s+"))
(def n1 (Integer/parseInt(nth l 0)))
(def n2 (Integer/parseInt(nth l 1)))
(println(combo/count-combinations n1 n2)))
non-DP solution is accepted lol
simple problem of combination. kCn
No more comments