Is this theory somehow related to coulomb's law???

The constraints in this question were so tight for no reason at all. We kept getting TLE while calculating a simple two line formula in Python3 and C++. The same code in Python 2 passed.

What is the final formula for this problem? We came up with a formula but unfortunately it had precision errors (might be incorrect).

This problem isn't even original lol

Press F to pay respect

What did you google search exactly?

This question and all its submissions must be removed

Because it is hosted on the best website (read worst) in the world algocodemarshal.

It is on codemarshall

This is really sad to hear :(

That is very sad to hear! Something similar happened to us. We submitted problem G and got TLE. Spent 45mins debugging what's wrong and couldn't figure out. Then we submitted the Physics question and still got TLE.

This TLE submission was $$$\mathcal{O}(T)$$$, so we were very surprised. Immediately, we converted both our problem G and problem C codes to C language (instead of C++), and submitted, and got both the probelms AC! :(

Yup, they were very similar problems.

For a fixed starting position, prefix gcd changes only log(A_max) times. So we can find n*log(A_max) tuples of type [g,L,R1,R2] , where subarrays [L,R1] to [L,R2] has gcd g.

Let's consider queries for single gcd g :

we maintain a segment tree where ith value stores maximum length of subarray ending at that index. For a single tuple [L,R1,R2] we add R1-L+1 at index R1, R1-L+2 at index R2 and so on. Process all the tuples and queries offline in reverse sorted order of L.

We have a solution which we believe is correct but we were getting WA.

Apply meet in the middle. Divide the people into two groups left_part and right_part, calculate dp[mask] for all subsets in left_part and right_part separately in $$$O(3^{10})$$$. Now consider a pair of subsets from left_part and right_part i.e {m1, m2}, Calculate dp[m1 | m2] by iterating over all subsets of m1 i.e. dp[m1 | m2] = min(dp[m1 | m2], dp[m1 ^ b]+dp[m2 | b], where b is the subset of m1.

Overall complexity: $$$(O(T*(3^{10} * 2^{10})) = O(T*(6^{10}))$$$

The total number of operations are roughly $$$6e8$$$ and 4 sec is a little strict but it should pass.

Ok so we had a solution using fwht which passed in around 2.8s. Lets enumerate all "good" masks as you stated above. Now consider a polynomial $$$P$$$(of degree $$$2^{n}$$$), where coeff of $$$i$$$ is $$$1$$$ if mask $$$i$$$ is good. Suppose mask $$$2^{n} - 1$$$ is good, then answer is 1 for sure. It can be seen that the optimal solution is bitwise xor of some good masks, so we need to figure out how many minimum good masks are required to get $$$2^{n}-1$$$. Now we add one by one taking xor convolution of current polynomial $$$Q$$$ with intial polynomial $$$P$$$. After $$$n$$$ iterations we will surely find our answer, and if our answer is $$$x$$$, then $$$P^{x}$$$ must be having coeff of $$$2^n-1 > 0$$$. So just take fwht $$$n$$$ times and print the very first moment where we can obtain mask $$$2^n-1$$$. This is a bit weird solution acc to me. But it was completely random hit and trial.

Find all bitmasks that represent valid house assignments. Then use fast subset transform to OR "polynomials" of these bitmasks till you get the polynomial which has all bits 1 mask present. Answer is number of times you had to use FST+1. Complexity n^2*2^n

Alice will always pick the root node first. After that, all the edges are split into k different/disjoint components and since K is even, Bob will take exactly half and Alice will take the other half of the remaining edges. Let the total number of edges be: N. Then the answer should be K + (N-K)/2.

The number of non leaf nodes in a k-ary tree would be : 1 + k^2 + k^3 + ....... k^(d-1). Since D<=1e9, a simple loop will give TLE so we use matrix exponentiation to calculate the abouve expression in log(d). After this, the answer is simple to calculate

Lmao, why even wait for rank list when no other team even solved 7 XD. Anyways, congrats!

Can you share the link for the same

Amritapuri RCD in the online round's problem discussion session said he would try to hold next season's regional in December this year. He won't wait for long in hope of an onsite regional.

where did you find the certificate? If you're talking about Kanpur regional