How this solution works ? (Gold Mining , LTIME85 , Weak TC ? )

Do I know you??

No :slight_smile:

Lol me too, I was hoping to get 100 in maximum AND but I had to settle for 50. I had 5 minutes left and I thought “If so many people got it right, it must be simple”. I noticed that pattern in the sample test cases and coded it straight away. After I saw AC, I was shocked. How the heck is that optimal? And who’s idea was that n \leq 2 should be a subtask? But anyway, rank acchi h lol.

How many Id’s u have @therealnishuz @nishuz :roll_eyes:

Does the grader consider 10 & 10.000000 as same or different? As the the only difference that fixed introduce was setting trailing zeros up to 6 digits and nothing else.

fixed also disables scientific notation.

ok, Thank you, got my mistake

No bro, it’s not related to weak testcases , in this question you just have to check this only , that either they work in same mine with there own speeds or they work in different mine with there speeds …in both way optimization is done.:sweat_smile::sweat_smile:

Prove mathematically :slight_smile:

1 Like

Most people did gold mine problem by believing rather than proving

1 Like

Welp… totally defies my intuition, but it passes

Generator source

I thought just like aptitude and reasoning , I call my friend (after saw AC verdict ) , who is preparing for civil services hope he proves how this way is optimal … :rofl: untill wait for editorial :slight_smile:

Can please you share your approach for Squared SubMatrix

Actually wait, I guess there is some form of intuition for it.

At each moment in time, consider the mine that isn’t yet depleted but gives the optimal rate for both players. Let’s say A’s rate is better than B’s rate. Then, no matter what B does, they’ll be losing to A if they let A mine with the better rate. So their best move would be to switch to that mine and prevent A from getting that rate as much as possible.

If the two rates are the same, then ties will be broken by the opposite player’s rate, but the outcome will be the same - both players on the same mine, at all times.

I deleted @nishuz due to some reasons. Ye apna official h

Suppose there is a submatrix of size n (each side of square is n)
Let the submatrix be from (x1,y1) to (x2,y2)
n = x2 - x1 or y2 - y1
Now consider the element A[x1], all the elements of B from B[x1][y1] to B[x1][y2] will have A[x1] in them since B[x1][j] = A[x1] + A[j]. So in total sum of the submatrix A[x1] gets added n times. This can be proved for all elements [x1,x2] and [y1,y2] of A. So our equation becomes n * (Sum of [x1,x2] and [y1,y2] in A) = X. This means n should be a factor of X.

Find all factors of X. Now we will iterate over all of them. For a factor f, We want (Sum of [x1,x2] and [y1,y2] in A) = X / f.
Now iterate over all subarrays of length f of A and find its sum using sliding window technique and increase the frequency of it.
After that iterate over sums of all the subarrays of length f again and add to answer frequency[X / f - sum]. Here the subarray with sum is [x1,x2] and the subarray with X / f - sum is [y1,y2] stored in frequency[X /f -sum].

Repeat this for all factors of X.

4 Likes

Your explanation is awesome :smiley:

1 Like

Okay, now to do C from ABC.

The main idea is to fix the number of books you take from the first desk. Then for each possible number, take as many books as you can from the second stack. You can find out how many you can take from the second stack with binary search or two pointers. Of all ways to take from the first stack, output the one that gets you the most books in total.

Can you please help, I have done the same approach as yours, but getting a WA . The link to my submission-https://www.codechef.com/viewsolution/34826052