It's hard to propose some "never seen before" problems, especially because they can't check if the problem they proposed is somewhere on the internet.

NO wander antontrygubO_o rejected all the problems

Btw in D the constraints could have been increased so that only randomized solutions work.

For C, I don't see how this link helps. You don't use this idea to solve the given task; you use it to optimize the solution and solve the bonus task, for example. This link is supposed to be helpful after you get the idea of using the numbers relatively prime to $$$n$$$, but then the remaining part (removing $$$p$$$ if it's not $$$1$$$) is really easy and shouldn't need the link or anything.

For D, I tried my best to fail the solutions based on MO's algorithm or any idea that solves the most frequent element problem in general, without using the fact that it has to be super-frequent. It sucks that some still passed...

also

for me it was guessForces

it's really sad. now i realize how C got so many solve

++

what will be the max sum is this case I constructed the array such that the max sum is (n-1)(2^k-1) :n-1 elements are 2^k-1 and one element is 0 :n-2 elements are 2^k-1 and one element is 1 and other is 2^k-2 :n-2 elements re 2^k-1 and one element is 2 and 2^k-3 and so on maintning the sum (n-1)(2^k-1) is this approach wrong

You can use persistent segment trees and binary search to get O(n*log(n)), because there's at most one value to occer more than ⌈x/2⌉ times, and you just need to find it.

Probably floating point errors, see the if(sqrt(a[i])*sqrt(a[i])!=a[i]){ line, you're dealing with floating point numbers.

Lets say there are a 100 tests each with $$$3*10^5$$$ queries.

Therefore, expected number of failure: $$$\frac{3*10^7}{2^{20}}$$$

which is sadly large. Unless you are lucky enough.

35 is a good number, you should pick it so that (1 — 0.5^k)^(30000000) >= 0.999.

If $$$\{x_1,x_2,...\}$$$ is the set of all integers coprime with $$$n$$$ (and less than $$$n$$$), then the product $$$q=x_1\cdot x_2\cdot...$$$ is also coprime with $$$n$$$. Therefore $$$p = q \mod n$$$ is coprime with $$$n$$$. (These can be proved using the definition of coprimality.) This further means that $$$p=x_i$$$ for some $$$i$$$. So we can exclude $$$x_i$$$ so that the product $$$x_1\cdot...x_{i-1}\cdot x_{i+1}...$$$ now equals 1 modulo $$$n$$$. No need to exclude $$$x_i$$$ if $$$x_i=1$$$.

I figured it out. Let the product formed be p. If a non co-prime number is in p, since p has a common factor witn n, it is of the form k*n, which can never be m*n + 1.

So, all numbers must be co-prime with n

Because otherwise you would have $$$p = kn + 1$$$ for some $$$k$$$ so $$$GCD(p,n)=1$$$ by Bezout's theorem and $$$p$$$ is coprime with $$$n$$$.

$$$gcd(p \space mod \space n,n)=gcd(p,n)=1$$$ since every element in $$$p$$$ is coprime with $$$n$$$.

Ok lets say you took some no. which is not co-prime with n in p then they would have a common factor say m, now we can express p and n as

p = m*a

n = m*b

for arbitrary a,b (which are co-prime to each other)

and now for getting (p mod n) = 1 ,we should have p = k*n + 1 and if we substitute values of p and n from our equations we have.

m*a = k*m*b + 1 but clearly the rhs is not multiple of 'm' which is contradiction.hence p should have all no.'s which are co-prime with n.

hope it helps :)

Intuition 100

Since we have to make the sum as large as possible while keeping their bitwise AND to be 0, we observe that we can do this by setting each bit from 0 to k-1 in exactly (N-1) of the numbers. It's easy to see that the bitwise AND of this comes out to be exactly 0, while the sum remains as large as possible(can be proved by contradiction). Now, we have to assign these k bits to (N-1) of these numbers so, the total number of ways for each bit will be N choose N-1 which is N. Hence, for k bits, it would be N^k.

For the first bit in all the $$$n$$$ numbers (which all their bits are initially $$$1$$$) , you have to make exactly one bit to be equal to $$$0$$$ and you have $$$n$$$ choices for that , and the same for the second bit .. up to the $$$k-th$$$ bit , so it becomes $$$n * n * n ... * n $$$ k times, which is obviously $$$n ^ k$$$.

Fixed. Thanks!

{0,16,16} is invalid for k=4 because 2^k — 1 = 15.

max possible sum is (2^k — 1)*(n-1) and you can't take 16 if k=4
the max value of any element can be 15 (for k=4)

.

This is really cool! Another solution is: if an element is super-frequent, it has to be the median. So you can calculate the median and check if it's super-frequent.

Another deterministic $$$O(q \log n)$$$ algorithm without tree-based data structures.

Suppose that the binary representation of $$$a_i$$$ is $$$b_{i, m - 1} \dots b_{i, 0}$$$ where $$$m = O(\log n)$$$.

The central observation is that if $$$a_i$$$ is the majority among $$$a_1, \dots, a_n$$$, $$$b_{i, j}$$$ is the majority among $$$b_{1, j}, \dots, b_{n, j}$$$. Therefore, we can find $$$b'_j$$$ which is the majority of $$$b_{1, j}, \dots, b_{n, j}$$$, and check whether $$$a' = b'_{m - 1} \dots b'_0$$$ is indeed the majority among $$$a_1, \dots, a_n$$$.

It is not only that we can, it is that we must take same element more than one time.

This is because the rules say we need to maximize the sum of the elements while having the ANDsum==0.

This is only possible by setting each bit only once to zero, ie if n>k+1 there will by (by pigeon principle) the number with all bits set at least twice.

It is like choosing k elements from N*K elements , which can result in multiple no.s having the same bit off, which will give WA.

Someone pasted this above, and it contains exactly what you are asking for: Link

So the algorithm is as follows: you have $$$2$$$ paths, and you want to merge them into one. To do this, you'll ask about the direction of the edge between the first nodes in each of the paths, let's call them $$$u$$$ and $$$v$$$. If it's from $$$u$$$ to $$$v$$$, remove $$$u$$$ and append it to the merged path. Otherwise, do this to $$$v$$$. Why does this work? Suppose you append $$$u$$$. In the next step, either $$$v$$$ will be appended, which is great because there's an edge from $$$u$$$ to $$$v$$$, or the node after $$$u$$$ in the path will be appended, which is again great because then the edge clearly exists.

Yes, the sum for every array of size $$$n$$$ has to be the same and maximum which can be achieved by turning off exactly $$$k$$$ bits at distinct position as all the bits are initialized to $$$1$$$.

Since range of length l contains most frequent number more than l/2 times (if there is such element in range), probability of some element in range being equal to it is 1/2, and not being equal to it also about 1/2. So when we pick 40 numbers, probability that none of them is equal to super-frequent number is 1/2 * 1/2 * ... * 1/2 = (1/2)^40

link

1) To your first question:

I think the reason for this is that if you take two numbers (a, b) that are co-prime with the given number (n), then (a * b) % n will always be co-prime with n (and hence would be in our earlier list of all co-primes).

We can prove this by contradiction. Assume that weren't the case and you could have a remainder that's not co-prime with n (i.e. the remainder (r) has a factor that's greater than 1 common with n).

(a * b) % n = k * n + r
=> (a * b) % n = g * (k * n / g + r / g)     [here, g = gcd(n, r)]
=> (a * b) % n = g * (some_number)
Also, since (a * b) % n = (a % n) * (b % n)
 => (a % n) * (b % n) = g * (some_number)
Since both a and b are less than n here,
=> a * b = g * (some_number)

We know that both a and b are less than n, which means that g has to be a multiple of either a or b. In which case, one of a or b is not co-prime with n, contradicting our assumption that both a and b are co-prime with n.

2) To your second question, check out: https://math.stackexchange.com/questions/28913/consider-the-product-b-1-b-2-cdots-b-phim-when-is-this-congruent-to?noredirect=1&lq=1

Basically, the product of co-prime numbers (mod n) leading up to n is either 1 or -1. It's -1 in cases when there is a primitive root, otherwise its 1. Since, -1 is congruent to n — 1, in cases when you have a non-1 value remaining, (n — 1) needs to be divided as well.

I thought about solving the problems linked but returned after opening the links, reason being the problem tags showed 2500 and 3200.

I think most of the Div2 competitors might have never solved problems in that range.

Particularly I felt D was a nice problem although the idea may be old.

can you please explain the condition when "n is the power of an odd prime (pk,k≥1) or twice the power of an odd prime (2pk,p>2,k>=1), then the answer is ϕ(n)−1".Thanks!

Преврати все n чисел в бинарные строки длины k. Тогда если ты их выпишешь в отдельных строках, то получишь табличку n x k из ровно n строк. Вспоминаем как работает битовый AND, он возвращает 0 если хотя бы один 0. Значит в каждом столбце получившейся таблички должен быть хотя бы один нолик. Но мы хотим максимальную сумму! Каждое число, если у него изменить 0 на 1 в битовом представлении, очевидно увеличивается. Следовательно, если в столбце есть больше одного нуля, то можно изменить один из нулей на 1 и получить сумму больше чем с двумя нулями в столбце. Отсюда следует, что в табличке в каждом столбце должно быть ровно один ноль. Осталось доказать, что все такие таблички имеют одинаковую сумму. Почему? Потому, что от перестановки слагаемых сумма не меняется. Каждая единичка в i-м столбце даёт два в соответствующей степени. В каждом столбце ровно n-1 единиц. Поэтому сумма всегда одинаковая. Пример n=3, k=3 громоздкий. Это все таблички 3х3 где в каждом столбце ровно один ноль.

You don't want to find a subarray, all you need is an array consist of n elements and each of them should be in range 0 — 7. So now you need to choose some bits to be 0.

If an element is super-frequent on interval $$$[l,r]$$$, it has over $$$1/2$$$ chance to be chosen if we pick a random element. If we repeat this process $$$40$$$ times, the probability of hitting the super-frequent element at least once is $$$1-(1/2)^{40}$$$, so we're practically guaranteed to find the super-frequent element (if there is one) by just querying randomly enough times.

For the first bit in all the $$$n$$$ numbers (which all their bits are initially $$$1$$$) , you have to make exactly one bit to be equal to $$$0$$$ and you have $$$n$$$ choices for that , and the same for the second bit .. up to the $$$k−th$$$ bit , so it becomes $$$n∗n∗n...∗n$$$ k times, which is obviously $$$n ^ k$$$.

You want the values to have Bitwise AND 0, so for each bit you need at least one element that has it off. Since you want to maximize the sum of elements, you must have only one such element and the rest will have that bit on.

Thus, for each bit you can choose any of the $$$n$$$ elements to have it off and there are $$$k$$$ independent bits. Thus, you can distribute the $$$0$$$s in $$$n^{k}$$$ ways.

Good catch but I think it should be occurrence[lower_bound + floor(x/2)]. But this helps only to check if an element is present more than x/2 times. You still need the upper bound to compute f, right?

There's at most 1 super-frequent element in any interval, and your segment tree is guaranteed to find it if it exists. Otherwise, it doesn't really matter if your segment tree finds the wrong frequencies because the answer won't change (it's $$$1$$$).