# JAN lunch Time Div2 4th problem Logic verification please :

https://www.codechef.com/viewsolution/42113551
Was tellling you to do this, just. I hope you get it now!!

1 Like

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.

2 Likes

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.

1 Like

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 :

1 Like

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;
}