JAN lunch Time Div2 4th problem Logic verification please :

help
1

So we had to basically do the simple operation Ai = Ai + Aj where i and j can be any index ,

i will be having K , all elements should be divisible by K ,

so to be honest those which are already divisible are of no use simply ,

now if we talk about other which has 1<=remainder1 <=k-1 , they need a conjugate pair of remainder2 where (remainder2 + remainder1 = k)

now the next point i observed that for satisfying the condition we have to use map and here i checked for satisfying condition criteria , like

  1. if there is a remainder2 present , and either of the two remainder any1 of them is say R , then it should satisfy powerof2(k/r) condition ,
  2. or if i dont find any remainder two then simply check the last condition of the first step ,

This logic got 80% correct , still wrong , only awarded 30 marks , out of 20 like cases only 2 failed , its hurting

1 Like
2

if K is a power of 2 it is always possible

1 Like
3

Same here bro​:sob::sob:

1 Like
4

When you apply A[i]=A[i]+A[j] to the remainder-compatible pair, your A[i] changed already, hence there is no way to modify A[k].

1 Like
5

Ohh right bro …thx

6

Approach the problem from the last step.

If A[p]=A[p]+A[q], was the last step, what could be the relation between p&q as well as A[p]&A[q].

1 Like
7

if ( lcm(a[i], k) / k ) is power of 2 a[i] can also be made divisible

1 Like
8

instead of r , use gcd(k,r), and you will be fine. I guess, although you can still simplify the solution.

9

https://www.codechef.com/viewsolution/42110701
Check it if interested

1 Like
10

I did the most random thing that came to my mind- Keep applying a[i] += a[i] for some steps and check if it becomes divisible by k. If it does, then continue, else the answer is No. Not sure if it is correct or not, but it got accepted anyway.
Link: CodeChef: Practical coding for everyone

2 Likes
11

I found this problem much more hard then the whole problem set of Div 2 , I upsolved last one just now , and would have done it in contest if I wouldnt have wasted 1:30 hour in this question . Moreover I found GOOD GRID harder than SHSPOONS

12

I did the same thing. Had just written a few examples and seen that if a[i] \mod k is not reachable after some finite number of operations and started repeating itself, then we can’t have a valid answer.

After that, I defined two sets R and R'
R denotes the set of reachable numbers, and R' is its complement.

We precompute the number of reachable numbers. The recursive formula is very simple to understand. It is, suppose we have a number y, it can either come from y / 2 or it can come from (y + k) / 2. Note, if y is odd, then you can just stop the process, because it can’t come from y / 2, or (y + k) / 2. The latter is not applicable when k is odd, because the process will stop at k itself. There is no k / 2, and (k + k) / 2 = k, which we have already found.

So we precompute R, as it is finite, because of the y is odd, you stop the process factor.
Not sure how big the set can be, but shouldn’t be > 10^3
Now, a_i * 2 can be written as (a_i \mod k) * 2
Thus, for all i from 1 to n, we make a_i = a_i \mod k.
So the task reduces to simple checking whether all a[i], whether its in R or not. If all are, the answer is Yes, else its No.

1 Like
13

i thought of this process for a while but ultimately moved on to something else

14

thanks alot

1 Like
15

:frowning: i didn’t observed that ,
https://www.codechef.com/viewsolution/42093055

it was my solution

16

ya i see many people trying to solve the last one rather than trying this one or good grid , i didn’t even had the time to read the last question btw.

1 Like
17

I was able to prove that each number must be something that when repeatedly added to itself, gives 0 (in modulo K)

Also, i was able to enlist all such possible numbers for each K.

These numbers will be:

  1. K/2. (if K is divible by 2)
  2. K/4, 3K/4 (if K is divisible by 4)
  3. K/8, 3K/8 5K/8, 7K/8 (if K is divisble by 8)
  4. and so on.

Then I just matched every number in the given array with this set.
Let me know if anyone needs a proof.

3 Likes
18

yes please

19

I worked backwards and felt that this was the correct approach(Didn’t prove it properly). Ran the code and was correct. I will be grateful if you can provide a clear proof.

20

Claim
For the answer to be yes, each number must be either 0 or something that when repeatedly added to itself, gives 0 (in modulo K).
Proof

  1. For numbers that are already 0, the proof is trivial. So we only consider those that are non zero.
  2. Let us denote S as the set of all numbers modulo K where S satisfies the property (i.e. repeated addition of any element in S to itself gives 0 modulo K). Denote the rest of numbers as S'
  3. Now, no matter how many operations we do, at least one element will remain in S’. Why? Assume we add two numbers from S’, one of them remains. If we apply the operation from 1 number in S and one in S’, the result is in S’ (easy to prove by contradiction).
  4. Therefore, all elements must be in S, otherwise at least 1 element wont be reducible.

How to construct S?
The construction of S needs some observation.
When we add an element x of S to itself repeatedly, we get x, 2x, 4x, 8x… and so on.
If any of these 2^{n-1}x becomes 0, all numbers after it will be zero as well.

  1. x cannot be 0, as its between 1 and K-1
  2. 2x is between 0 and 2K, it can only be 0 at K/2 (if K divides 2)
  3. 4x is between 0 and 4K, it can be 0 at K/4, 2K/4, 3K/4 (if K divides 4).
  4. and so on.

Therefore, find the highest power of 2 that divides K, say the power is N.
Then S is the set of all multiples of \frac{K}{2^{N}}.
So can just check the divisibility of each element of A by \frac{K}{2^{N}}, which completes the answer

4 Likes