INLO32 - Editorial

complexity
editorial
inlo1601
inlo32
medium
number-theory

#1

PROBLEM LINK:

Practice
Contest

Author: RAVIT SINGH MALIK
Editorialist: RAVIT SINGH MALIK

DIFFICULTY:

MEDIUM

PREREQUISITES:

COMPLEXITY , NUMBER THEORY

PROBLEM:

You have choose correct option for the given questions.

EXPLANATION:

For question 1.
n^2 √n = n^{2.5}= O(n^{3})
A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) = O(g(n)) means it is less than some constant multiple of g(n). The notation is read, “f of n is big oh of g of n”.

for more information click here

For question 2.
Among the four Bellman-Ford is Dynamic alogorithm,while Prim's , Kruskal's , Dijkstra's algorithm all
are Greedy alogorithm.
Dijksra’s algorithm is a Greedy algorithm and time complexity is O(VLogV) (with the use of Fibonacci heap). Dijkstra doesn’t work for Graphs with negative weight edges, Bellman-Ford works for such graphs. Bellman-Ford is also simpler than Dijkstra and suites well for distributed systems. But time complexity of Bellman-Ford is O(VE), which is more than Dijkstra.

For question 3.
Then the number is 3^3 imes 2^6 = 1728, and the 28 divisors of 1728 are:
so,(3+1) imes (6+1)=28.

1 2 4 8 16 32 64 3 6 12 24 48 96 192 9 18 36 72 144 288 576 27 54 108 216 432 864 1728

For question 4.
last two digits of 11 imes 22 imes 33 imes 44 imes 55 can be find by (11 imes 22 imes 33 imes 44 imes 55)%100=20.

for last digit you can use %10 so,for last 3 digit use %1000.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

RELATED PROBLEMS: