It is not true that the dp values are monotonically increasing. An easy to see counter case is that dp[5]=6 and dp[6]=5.
1 Like
Can u pls look into my solution. Its giving right answer on test case provided by you but not an AC.
Thanks in advance.
https://www.codechef.com/viewsolution/39027026
Hey guys.
Can someone tell me why below logic won’t work?
If I was given a number n , and I fill the n numbers with pairs of the number that form the required XOR like if I am given 4 3 3 and I make [1,2,1,2] then maximum pairs possible according to given condition become 4(which are Max pair I guess) and is more than required , so it’s always possible to alter array to print YES like [1,2,2,2]. So I tried like this making pairs of no. to get Max XOR and if Max is greater than required , then it’s always a YES. it passed sample cases but failed in test cases. Can anyone correct me plz.
Link to my code CodeChef: Practical coding for everyone
I have used this to initialize my dp still working fine(AC), I have used the condition (i%j==0) to initialize my dp[i], i.e I’m storing the minimum sum of two values such that thier product is i
i=x*y => dp[i]=x+y (max(x,y) is minimum possible which leads to dp[i] minimum for product of two value)
I just want to know that what is difference if I don’t use that condition (i%j==0) to initialize as it is mentioned in Editorial.
rep(i,1,MAXN-1) {
irep(j,sqrt(i),1) {
if(i%j==0) {
dp[i]=j+(i/j);
break;
}
}
}
Looks like many people have tried this. I also tried exactly the same approach and got wrong answer.
https://www.codechef.com/viewsolution/39017397
For everyone who had just split n into two equal parts (n/2) and (n-n/2) and checked if their product is greater than equal to k for the answer to be YES, here’s a testcase -
1
6 7 1
The answer is NO because the minimum n required to get k=7 is n=7 for which the expression is 2×3+1×1. But your codes will give YES as (n/2)*(n-n/2) = 3×3 = 9 >= k.
2 Likes
yeah I figured it wasn’t, which is why I don’t understand the editorial when it claims that dp[k - \sqrt{k}\sqrt{k}] \leq dp[2\sqrt{k}] (where \sqrt{k} denotes \lfloor \sqrt{k} \rfloor )
I too feel there’s something wrong here. Consider k=14. Here, \sqrt{k}=3. So, k-\sqrt{k}\sqrt{k}=5 and 2\sqrt{k}=6. But dp[5]>dp[6] which violates the condition.
1 Like
ah, thanks for a specific counterexample! just curious, when you got an AC on this problem in the contest, did you have some other proof that only checking the first 2\sqrt{k} transitions was sufficient for computing dp[k]? if you used a different method than the editorial then I guess the question doesn’t apply lol
Although I don’t have any proof for my solution. But it seems logical to check transitions only upto a number i such that k-i is of the form a^2-1 (which is at max 2\sqrt{k}) because a^2 and a^2-1 will have the same value and it may be beneficial to switch to a^2-1. Any other number less than a^2-1 seems worse because we want the two divisors to be as close as possible. I arrived at this observation by brute-forcing the first 100 numbers and it showed that checking upto 2\sqrt{k} is sufficient. And then I submitted the solution which passed.
hmmm, not sure if I buy the intuition exactly since it doesn’t disprove that you could also pick some k - i = b^2 such that b^2 < a^2. anyways, I guess I should’ve tried brute forcing something to check like what you did 
hopefully the editorialist clarifies their proof tho
Thanks! Got it!
This would give you 20 pairs. You need to have exactly K pairs. So basically for a prime number, only thing you can come up according to our solution is, 1x19 with 1+19=20 elements. Whereas with decomposing into smaller groups, we can get better answer.
Can someone tell more formal/intuitive way to state that checking till 2√k is sufficient, I understood the lower and upper bound but how it tells that checking till stated is sufficient.
And, also @gennady.korotkevich could you please explain your solution, it seems that for a particular x you are pairing it with maximum possible value from i(variables from your solution), but how this is working.
Thanks
In this approach, you are assuming that x can be a xor of only two numbers. But there may be multiple possibilities such that a^b=x.
According to my logic if n^2 >= 4 * k then output will be yes and no otherwise but i am getting WA . Can anyone tell the mistake in this logic . I am getting correct answer on given test case.
Yes I tried the same! and it gave WA…
Hi. If i take 3 X and 3 Y where X and Y are 2 no.s st X^Y=1 , i still get 9 pairs bcoz repetition of numbers is allowed . Where am I wrong
You need exactly 7 pairs and not at least 7 pairs. You can get exactly 9 pairs using 6 numbers, even exactly 8 pairs but you cannot get exactly 7 pairs using 6 numbers. You need minimum 7 numbers to get exactly 7 pairs.
Here your logic is right but if you put 1 at last and then when X=1 then XOR of 0 and1 is also 1. So it will increase extra number of pairs. You can put X+1 at last .