It's rated of course. And no, you don't have to register, we would contact the prize winners.

Thanks to the authors for this amazing div 3 round!

based on whether you will cheat or not

Ofc you'd have to keep your nationality as Indian for that. We will be asking you for details like mobile number and address.

All the Best

Because its kinda impossible for us to deliver them overseas keeping in mind the cost and tediousness of that.

Orz

Orz.

Orz Qg3

Le Indians:

not really*

hahaha lol :)

Also that shit games of 2^n rounds

Good luck!

Thank you Messi

I face a lot of difficulty in solving in c++ than I coded in python

Even though you have solved max of the problems!!!! Indian rounds are quite good but this one was little bad

Indeed

The same thing happened to me, but I solved it with modular inverse

i used int128 then took the mod

idk about E, but there is nothing interesting about D.

Did you create a new account just to hate this round? really? xd

No, it's not. You just don't know how to solve it.

Do binary search on $$$l$$$. Now you need to check if there is a square of size $$$l$$$ with all $$$a_{ij} \geq k$$$. To do so, we can find the maximal square and just compare its side to $$$l$$$. Finding maximal square is a well known DP problem and can be solved in $$$\mathcal{O}(nm)$$$. Total compexity $$$\mathcal{O}(nm*log(n))$$$

simple math formula. https://oeis.org/search?q=1%2C7%2C22%2C50%2C95%2C161%2C&language=english&go=Search

Binary search

histogram

Binary search for answer + 2D prefix-sum

No,just 2D sum.

binary search answer + O(n) check for fixed l

Binary search + histogram to find max square removing all numbers <= x (binary search for the answer)

Binary search with 2D prefix sums. I’m pretty sure that this exact problem appeared before multiple times.

I did binary search on the answer L. For a certain $$$l$$$, we can decompose the checker function into checking a grid of numbers $$$a_{i, j}$$$ — $$$l$$$ for the largest square of positive numbers, which can be done in O(NM) time using a stack.

Don't use unordered_map

D is a binary search problem

By using monotonous queue and binary search.

monotonous queue will help you to find the minimum value of all possible sub-matrices.

Binary search for l and dp for each l.

When doing dp, let dp[i][j]={r[i][j],c[i][j]}, where {r,c} is the max size of good rectangulars which rightbottom corner is {i,j}. if a[i][j]<l, r=c=0, or we can calculate r,c by value of dp[i-1][j], dp[i][j-1] and dp[i-1][j-1].

Divide by the gcd and see what happens

Think about Euler's totient function

Yes I have also considered greedy but I cannot prove or disprove it.

The greedy is true,but your code may is wrong.

I solve it in 186980785 by C++.

My code is strange.You only need the last line.

Not sure if you used a hash map, but that's what I did initially and I also got stuck with TLE with a O(N * sqrt(N)) runtime. In the end, I replaced hash map with a fixed size array and it passed.......

I did this using a fixed size array and my blind arss couldn't see that the constraint was till 2e5 not 1e5 so ended up doing wrong submission 5-6 times

Yes, it involves using euler totient function. Basically, try adding (k-1) edges of weight k , starting from the largest such possible k. It's a greedy solution.

As , k = gcd(u,v). So, obviously k <= n/2 .

Now, what can be the maximum number of edges (u,v) whose weight / gcd will be k ?

It will be nothing but the total number of coprime pairs upto n/k. Let's save it in a coprime[] array. This can be easily pre-computed using coprime[i]=coprime[i-1]+ euler_totient(i).

Find the number of subarrays whose XOR has an odd number of divisors and subtract that from the count of all subarrays ($$$\frac{1}{2} \cdot n \cdot (n+1)$$$).

In fact, the number of coprime pairs is asymptotically about (n/pi)^2 * 6, so it will likely always be greater than nsqrt(n) if it satisfies it for the first few elements

Why did you use map instead of array? The value of XOR is just $$$10^6$$$ at maximum.

You only need to search the perfect square numbers because only perfect square numbers have odd number of
divisors.

Let xor[i]=a[1]^a[2]^...^a[i],xor[0]=0

For each xor[i], There are at most 512 different values of xor[j] where xor[i]^xor[j] is square number. So we just need to store the count of each xor[i] (i = 0 to n) and check the count of (sq^xor[i]), where sq is square numbers from 0 to 511^2.

Think about when a number has an even number of divisors and which numbers are those. Could there be some reason for that?

Because the time limit exceeded. Your code must be able to solve the problem (within the specified constraints) within 2.5 seconds. Your submission was not able to do so.

If you want any useful feedback, I suggest that you briefly explain your approach and trim your code to remove all unnecessary components, so that anyone reading your code can more easily see what you're actually doing. For this problem in particular, you need a time complexity of $$$O(n^{1.5})$$$ or better. Notably, a $$$O(n^{1.5} \log n)$$$ solution (that utilizes a map/dictionary, which is quite a common attempt) generally should not pass.

Also, why are you tagging Mike for this? This is not an issue with Codeforces; it's an issue with your solution. Even if you genuinely believed there was an error in the system testing (which is quite absurd when over 2000 people have solved it during the contest), you should be notifying those who prepared the contest, not Mike.

anyway to do it w/o interpolation :(

search for division modulo a prime