Codenation Republic Hiring challenge

21

can anyone provide the link for the questions of codenation republic contest for practice??

22

Represent the whole scenario as permutation of numbers from 1 to N(Bag has balls numbered from 1 to N and permutation represents which ball is picked in which move).Now if a permutation has answer K, then there are K winning positions in that permutation and each position contributes 1 to the answer for that permutation. So I translated the same to contribution of each position in all permutations. For position i, contribution is number of ways that position is ‘a’ winning position.So number of ways are :
nCi*(i-1)!*(n-i)! = (n! / i)

So for each i, we add the respective term to the answer ,and at the end divide whole sum by n! to get the expectation (total permutations possible are n!).

2 Likes
23

bro can you explain more clearly??

24

Follow their facebook page

25

Why is nCi being multiplied??

26

Or simply, it’s sigma(1*i^-1) right?

27

Because for every (i) you just have only i position to place that particular number .So to choose i places total of n places you multiply with nci.Lets understand with an example suppose you have n=10 and at currently you need to find for the 4 th position so at right you have( n-i) numbers so you need to take their all positions .Now on the left you have (i-1) position so you take their factorial now you need to put 4 in such a way so that it will always be in winning position so you have only 4 places in which your 4 will be at winning position so you just multiply with (nci) also…

1 Like
29

HI can you please explain me how to do the first i was getting WA in that thanks :slight_smile:

30

i solved the second problem in like 25 mins completely coded the 3rd problem went to try test case. error . variable name was wrong. corrected the var name , went to see test case all correct :innocent: and then before i hit the submit button time was out. :face_with_thermometer::sneezing_face:

1 Like
31

easy one just make a function isprime which as name suggests returns true if a number is prime else false

like isprime(7) = true
isprime(10) false

now decompose a number in its canonical form
100 = 2^2 * 5^2

if the number of primes in canonical form is more than 1 print(NO)

solution
if n==1:
print(“No”)
if n==2:
print(“YES”)

else:
canonical_form = get_canonical(n)
if len(canonical_form) > 1:
print(NO)
else if isprime(canonical_form prime’s power + 1):
print(“YES”)
else:
print(“NO”)

32

Hey thanks but Can you explain me why “number of primes in canonical form is more than 1 print(NO)” i dont get that.

33

Given a number of the form P_{1}^{a}.P_{2}^{b}..., then what are the total factors? By using basic combinatorics it is (a+1).(b+1)... So, If the canonical form has more than 2 primes, then total number of factors is definately not a prime because it has atleast two factors which are not 1 or the number itself. However, if there is only one prime in the canonical form you have to put an additional prime check on a+1.

2 Likes
34

Oh okay wowww really great explanation man Thanks alot! Also did u do the 3 question?

1 Like
35

However, I think this question can be solved using a slightly simple approach. You can count the total number of factors of a number in sqrt(N). Then check if this number is a prime, build a Linear Sieve in the pre-processing step.

1 Like
36

Nah. I didn’t appear for the test besides I am a Noob in CP. :slight_smile:

1 Like
37

I did that thats why it was giving WA idk

1 Like
38

You need to find all the factors of N in sqrt(N) time… put it in an array… then find the length of the array and print if the length is prime or not

39

How did you find the P for it ?

40

I did that too but idk WA :(((

41

I guess it’s the flow error… send the code if you have. I got AC for what I said above :smiley: