We invite you to participate in CodeChef’s Starters 91, this Wednesday, 24th May, rated till 6-stars Coders (ie. for users with rating < 2500).
Time: 8:00 PM — 10:00 PM IST
Note that the duration is 2 hours. Read about the recent CodeChef changes here.
Joining us on the problem setting panel are:
Setters: M.Sohel Traverser_25, Souradeep souradeep.99 Paul, Jatin rivalq Garg, emptypromises empty-promises, Danny dannyboy20031204 Boy, Ani Chimpanzee, Yash yash_daga Daga
Testers: Nishank IceKnight1093 Suresh
Video Editorialists: Madhav jhamadhav Jha, Suraj jhasuraj01 Jha, Jwala jwalapc , Adhish ak2006 Kancharla, Pravin pravin_as Shankhapal
Text Editorialists: Nishank IceKnight1093 Suresh
Note: Some problems have subtasks.
Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest.
The video editorials of the problems will be available for all users for 1 day as soon as the contest ends, after which they will be available only to Pro users.
Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.
Hope to see you participating. Good Luck!
Hoping this time, correct input test cases are there :)
All the best, everyone!
Note: Some problems have subtasks.
The idea to put 3 problems with 11 subtasks was pathetic.
agreed didnt get benefit of solving 4 q in 20min
+1
+1
Why the answer for 2nd problem (Odd GCD Permutation) for n = 1 is No. Isn't it should be yes coz for odd indices, gcd is 1 and for even indices, it will be 0. Hence gcd for odd indices is greater than the even one. Then why no?
Why is the gcd of empty array 0?
Vacuous_truth
Pick any positive integer (say g), for empty array (say A). this statement holds true -
g divides all the elements present in A.
Thanks for the info
Just now, I checked the announcement, they changed the constraints to N >= 2. I wasted too much time thinking about the edge case in it. It shouldn't be done ;/
In Limited Shopping, why is this submission fast enough?
I coded $$$O(n*n*k)$$$ brute force at the last minute to fetch 30 points and was surprised to see 100 points on it.
I did O(n*k*k*k) to get 11 points but got 30 points.
It seems like just low constant factor.
I did a quick operation count, your code does about $$$6\cdot 10^8$$$ operations in the worst case, but they're all pretty simple ones so it happens to run fast.
Loved the question -XOR & sum
How did you solve it?
Start with the simple observation that $$$a + b = a \oplus b \iff a \& b = 0$$$, ie $$$a$$$ and $$$b$$$ share no 'on' bits.
The observations from each subtask:
If $$$l = 0$$$ and $$$r = 2^k - 1$$$, the answer is simply $$$2^k$$$ or $$$r+1$$$. Why? Because for all $$$a$$$ such that $$$1\leq a\leq r$$$ we can generate $$$x = a$$$ by taking $$$x = 0 \oplus a = 0 + a$$$.
We also have a special case, $$$0\oplus 0 = 0 + 0 = 0$$$, so we can generate $$$x = 0$$$ as well. (This is only possible if $$$l = 0$$$, and is a corner case we'll use later)
In generating $$$2^k$$$ distinct $$$x$$$, we've covered all integers from $$$0$$$ to $$$2^k-1$$$. We can't get $$$x > 2^k-1$$$ because the most significant bit in $$$a \oplus b$$$ can't exceed the most significant bit of $$$\max(a, b)$$$. Hence we've generated all possible $$$x$$$.
If $$$l = 0$$$ and $$$r$$$ is essentially any number, then the answer is the $$$2^{k+1}$$$ where $$$2^k$$$ is the highest power of 2 contained in interval $$$[l, r]$$$. For example, if $$$r = 5$$$, the highest contained power of $$$2$$$ is $$$4$$$ and so the answer is $$$2\times 4 = 8$$$. The set of possible $$$x$$$ is $$$\{0, 1, 2, 3, 4, 5, 6, 7\}$$$
Since $$$l=0$$$, we have all numbers less than $$$2^k$$$. We can now generate $$$2^k$$$ values of $$$x$$$ from interval $$$[0, 2^k - 1]$$$ (by subtask 2). We can also generate all values of $$$x$$$ from $$$2^k$$$ to $$$2^{k+1} - 1$$$ by taking $$$x = 2^k \oplus a$$$ where $$$a < 2^k$$$. which adds in another $$$2^k$$$ values for a total of $$$2^{k+1}$$$.
This is the maximum number of possible $$$x$$$ since we've generated all $$$x$$$ from $$$0$$$ to $$$2^{k+1} - 1$$$ and any further values of $$$x$$$ would be $$$\geq 2^{k+1}$$$ and thus require the $$$(k+1)^{th}$$$ bit to be on, but the largest 'on' bit in the input range is the $$$k^{th}$$$ one.
Putting these together, we arrive at:
Initialize $$$ans = 0$$$
Iterate over all $$$2^k$$$ for $$$1 \leq 2^k \leq 10^{18}$$$
If $$$l \leq 2^k \leq r$$$, then add $$$2^k - l$$$ to $$$ans$$$.
Finally, if $$$l = 0$$$, increase $$$ans$$$ by $$$1$$$. (Corner case we noticed in subtask 2)
Similar to what we did in subtask 3, when we have some $$$2^k$$$ within our interval, we can say that $$$\forall a \leq 2^k, 2^k \oplus a = 2^k + a$$$. Further, for different powers of $$$2$$$ the values we get are guaranteed to be different since the most significant bit varies. So for each $$$2^k$$$, we can generate $$$2^k - l$$$ new values of $$$x$$$.
Now we need to prove that the set of $$$x$$$ we get is indeed exhaustive. Suppose $$$\exists a, b $$$ such that $$$0\leq a, b\leq r$$$ and $$$a + b = a \oplus b = x'$$$ such that $$$x' \neq 2^k \oplus c$$$ for some $$$k$$$ and $$$l \leq c < 2^k \leq r$$$.
The most significant bit of $$$a$$$ must not be equal to the most significant bit of $$$b$$$ (observation we started out with). Let the larger of the MSBs (for simplicity, say $$$a > b$$$ so this is the MSB of $$$a$$$) correspond to $$$2^k$$$. This implies $$$2^k$$$ lies within our interval. Since neither of $$$a$$$ and $$$b$$$ are powers of $$$2$$$, they have some 'on' bits apart from their MSB. Now consider $$$2^k\oplus x'$$$ (this is $$$x'$$$ without its most significant bit). At least one of its bits must come from $$$a$$$, so to retrieve $$$b$$$, I simply turn that bit off. This implies $$$b < 2^k\oplus x'$$$. Note that also $$$2^k\oplus x' < 2^k$$$ and hence $$$2^k\oplus x'$$$ must lie within $$$[l, r]$$$ given that $$$a$$$ and $$$b$$$ were within $$$[l, r]$$$. Now I can generate $$$x' = 2^k \oplus (2^k \oplus x')$$$ which is a contradiction and so no such $$$x'$$$ exists.
Therefore every possible value of $$$x$$$ can be generated with a power of $$$2$$$.
Here's my AC submission. Sadly couldn't come up with this during contest :P