JAN lunch Time Div2 4th problem Logic verification please :

help
21

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

1 Like
22

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.

23

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.

24

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
25

True

26

I fully agree to you.

27

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
28

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

29

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.

30

owwwwwwwwwwww thanks man

31

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
32

it sounds complex but anyway let me try today

33

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

34

you better explain a bit about your approach or thinking

35

i read the above posts …and i found that i am doing some unnecessary stuff!
i removed them and got AC … thnx

1 Like
36

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.