Can anyone explain their solution to any of the last 4 problems.
- Question 3 Apples and Oranges (Contest:16th Feb) Tono is super fond of eating oranges and apples alone, but not so fond of eating them together. Today, she finds that all the 'n' apples and the 'm' oranges that she has are kept in a straight line. As she does not like apples and oranges together, find the expected number of unwanted pairs (adjacent) of apples and oranges if all the arrangements of apples and oranges have equal probability.For example:"O A O A" have 3 unwanted pairs while "O O A A" has 1 unwanted pair.
- Question 4 Min query (contest 16th feb) You are given a rooted tree with N nodes and node 1 as root. Node i initially has a value A[i]. You have to process Q queries on it. Query can be of two type Type 1: Find the minimum element in the subtree of Node X. Type 2: Change all the elements in the subtree of Node X to thier value xor K.
- Question 5 Game of bits (contest 16th feb) F(1,x) = number of set bits in the binary representation of the number x F(k,x) = F(k-1, F(1, x)) ; k > 1 You have to find the number of x for 1 <= x <= N such that the smallest k for which F(k, x) = 1 is C. For example smallest k for x = 1 is 1 x = 2 is 1 x = 3 is 2 x = 4 is 1 x = 5 is 2
Question 6 Tricky Chapo! (Contest: 16th Feb) As always, Sid has come up with a new problem on Number Theory. Since it is too tricky to solve, can you help him. A bonus, you'll get a chapo for solving it right. Given an integer n, let F(n) be the product of all positive integers i less or equal than n such that n and i are co-prime. Now you're given an integer X, you need to find the sum of (F(i) modulo i) for all positive integers i less than or equal to X. If the answer is A, report the value of (A % 1000000007).
The contest has ended
What are the constraints on 6th problem?
https://paste.pics/833VI https://paste.pics/833WH
3th.
This is a direct problem of linearity of expectation. Consider each adjacent pair as independent and you will get (n+m-1) places * (2*n*m/((n+m)*(n+m-1)) probability for each pair.
How to find probability for each pair?
4th.
You can do euler tour on the tree which transforms the problem into array problem.
l r x do xor from l to r.
l r print min value from l to r.
You can now do sqrt deco on the array and keep a trie for each block. Now those blocks which lie partially van be rebuilt and completely can be lazily updated. Similarly, queries on complete blocks are like xor minimization.
For updation, are you XOR'ing all the numbers in the trie with k? If so, how do to that efficiently?
No, I am storing a lazy variable. And while querying I would try to minimize the lazy value of that block with the trie just as we normally minimize a value xor some value with binary trie.
For lazy value = K, you found the min value of K ^ A[i] for all the A[i] in block okay. But how does the lazy value make A[i] := A[i] ^ K in the trie so that next time the updated values are to be used?
5th.
This is a straightforward digit dp problem. Don't know why the problemsetter gave constraint 10^423 to force big integer usage. Any number upto 10^423 has about 1500 bits in binary. So you can do digit dp[i][j][2] that how many numbers will become which number from 0 to 1500 after doing the operation and remaining is straightforward.
6th.
I solved it using oeis. I don't know the intended solution. But you can search the sequence on oeis to get phitorial mod(n). Now you need to calculate it sum and then you would realize that only numbers whose primitive root exist's phitorial(n) mod n equals n-1 and all others are equal to 1. These numbers are 1,2,4 and p^i and 2*p^i where p is an odd prime and i>=1. Now p^j, 2*p^j where j>=2 is easy to calculate. Only problem is to calculate summation of primes. Now for this, you can precompute summation of primes on 1e6 sized blocks and hardcode these values and run segmented sieve to compute the value on the rest.