https://www.codechef.com/viewsolution/42113551

Was tellling you to do this, just. I hope you get it now!!

Based on my understanding, GOODGRID and This question are simple enough. This ask you if all numbers divisible by largest odd factors of k and GOODGRID ask you whether X is the product of two integers no larger than N.

I found tough good grid comparatively because thinking of the solution takes time (in the process first I came to the solution that If X<=n or xis divisible to n then answer is yess , which was wrong ) , and SHSPOONS one easy because I am familiar with these kind of question as they keep on coming in CF . And about dreaming of divisibility , I was unable to even think of how it could be solved.

I also felt that one should be able to solve SHSPOONS. The advantage here was we should just come up with some greedy strategies and test them out. It would have been way more difficult if they simply asked a âYESâ or âNOâ question as they wouldnât have provided the information about a possible solution in 2n moves.

Proving the strategy is more hard I feel.

True

I fully agree to you.

For GOODGRID:

You need to observe that if two entries (t_1,s_1) and (t_2,s_2) are âgoodâ, then they force the vertices of rectangle generated by them, namely all (t_i,s_j) , to have exactly the same value.

Now let T be a collection of âgoodâ entries, T_1 its x-projection and T_2 its y-projection. Clearly T\subset T_1\times T_2 . By above observation, all (t_1,t_2)\in T_1\times T_2 must have the same value, hence all are âgoodâ entries. So we have T_1\times T_2 \subset T. So X must be a product of two integers.

Also it is easy to generate an example with block matrix \begin{bmatrix}a&a+1\\a-1&a\end{bmatrix} where a is of the constant matrix of size k\times l for any k,l.

For DREDIV:

Let l be the largest odd factor of k (k=2^t l), let x be a multiple of l, then by doubling itself, k\mid 2^t x. Now if you have some set of numbers, say Y, not dividing l. For any y\in Y, since 2,l coprime, multiplication by two is an automorphism(at least bijection if you are not familiar with the language) of \mathbb{Z}/l-\{0\}, so we never reach any number dividing l. And for distinct y,z\in Y, you can remove at most 1 per operation, hence there will always be some number y\in Y left, resulting the impossibility of divisible by k.

For good grid I observed that , but it took time and was difficult then SHSPOONS . Thanks for such nice explanations.

Thanks for the unofficial Editorial . I have a question why can sum of 1 or more element of S with an element in Sâ canât result in S. (You wrote about contradiction for one from both the set but how is it no if we take more than one element from Sâ ) . Can you please provide proof by contradiction as well.

owwwwwwwwwwww thanks man

i was able to think that it must be a multiple of k ,or k/2,k/4,so onâŚ

wasnt able to think about 3k/4,3k/8,5k/8,7k/8âŚanyways âŚnicely explained :

it sounds complex but anyway let me try today

can anyone help me here âŚ i am getting TLE!!

plz have a look at my code

https://www.codechef.com/viewsolution/42155864

#include<bits/stdc++.h>

using namespace std;

#define ll long long int

#define fl(i,strt,n) for(i=strt;i<n;i++)

ll easy( ll k)

{

return (k/(k&( ~(k-1) )));

}

int main()

{

ios_base::sync_with_stdio(false);

cin.tie(NULL);

ll satisfy,flag=1,i,t,n,k;

cin>>t;

while(tâ)

{

cin>>n>>k;

ll m=easy(k);

ll tool,need,arr[n];

ll arr1[k]={0};

ll out=0,temp2=1,count=0;

fl(i,0,n)

{

cin>>arr[i];

if(temp2==0)

{

continue;

}

if(arr[i]%m==0)

{

count++;

if(arr[i]<k)

{

satisfy=arr[i];

}

else

{

satisfy=arr[i]%k;

}

```
if(arr1[satisfy]==-1)
{
//done;
out=1;
temp2=0;
}
else
{
arr1[satisfy]=1;
}
}
else
{
if(arr[i]<k)
{
need=arr[i];
}
else
{
need=k-(arr[i]%k);
}
if(arr1[need]==1)
{
//done
out=1;
temp2=0;
}
else
{
arr1[need]=-1;
}
}
}
if((k&(k-1))==0 || count==n || out==1)
{
cout<<"YES\n";
continue;
}
if(out==0)
{
cout<<"NO\n";
}
```

}

return 0;

}

you better explain a bit about your approach or thinking

i read the above posts âŚand i found that i am doing some unnecessary stuff!

i removed them and got AC âŚ thnx

The idea for this one was just to divide k by 2 for as long as you could and then loop to check if all array elements are divisible by the updated value of k.