# Different Ways

# Different Ways

punjabivirus + 0 comments I think, we can solve it using memoization for computing factorials. In scala, Streams can be used for memoization. Rest its a combinatorial problem. I solved it like this--

lazy val tempFact: Stream[BigInt] = BigInt(1) #:: BigInt(1) #:: (tempFact.zipWithIndex.tail).map{case (f, i) => (f * i)} val fact = tempFact drop 1 ................ println (fact(n)/(fact(k) * fact(n-k))%100000007)

ecastilla95 + 0 comments I am using Scala. This is the solution I found. It uses local mutation but it works. If you know how to make it more functional, please share:

`def getTable(n: Int = 1001, k: Int = 1001): Array[Array[Long]] = { val mutableTable: mutable.ArrayBuffer[Array[Long]] = collection.mutable.ArrayBuffer() mutableTable += 1L +: Array.fill(n-1)(0L) for (i <- 1 until k) { val a1 = mutableTable(i-1) :+ 0L val a2 = 0L +: mutableTable(i-1) mutableTable += (0 until n).map( e => (a1(e) + a2(e)) % modulo).toArray } mutableTable.toArray } [...] val table = getTable() [...] println(table(N)(K))`

lando_loeper + 1 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?

wizard2none + 1 comment [deleted]wizard2none + 0 comments 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.

**Alternatives:**Option 1)

Precompute the array once for n = 1000. Read the results for each test case out of the array.Option 2)

Use a recursive function with memoization (easy for this problem)

16wh1a0556 + 0 comments I am unable to inculde the clojure.math.combinatorics namespace could someone help me.. i am beginner in clojure.

(ns clojure.core (:require [clojure.string :as str]) (:require [clojure.math.combinatorics :as combo]) (:gen-class))

(def test_cases (Integer/parseInt(read-line)))

(dotimes[r test_cases] (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)))

bbyalcinkaya + 0 comments non-DP solution is accepted lol

Sort 6 Discussions, By:

Please Login in order to post a comment