We invite you to participate in CodeChef’s Starters 208, this Wednesday, 15th October, rated for 6 star (i.e. for users with rating < 2500).
Time: 8:00 PM — 10:00 PM IST
Joining us on the problem setting panel are:
Contest Admin, Statement Verifier and Text Editorialist: Nishank IceKnight1093 Suresh.
Tester: Shreyan Dominater069 Ray.
Setter: Nishank IceKnight1093 Suresh.
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 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!
Contest starts in 30 minutes.
what was the idea for div2 5th question, i thought of finding pairs such that i^j=k, now i need to find partition of values i+1,i+2...j-2,j-1 such that say partiton was i+1,i+2,,,m and m+1,m+2,..j-1 and xor of i with the first half of partiton values is <=k and xor of j with second half of partiton values is <=k. i couldn't find an efficient way to do this though:(
finding a single i^j=k pair is enough, and all other elements either go before this pair or after this pair.
why does it work for every i,j with i^j=k?
what do you mean every? we have to sort the array and if we take a pair such that i^j==k
let x = v[i] and y = [j] w.l.g, let x>y
then put [....x, y, ....], now no matter what we would have to calc x^y
we can put elements before and after smartly. should i tell you how?
i was going for similar construction, couldn't find the proper arrangement of values though. Can you tell how you constructed?
when k==1 just do 1 3 2 4 5... when k==0 its just 1,2,3,4,5...
for k>=2 msb(x) = most significant bit of x
choose x and y such that msb(x)!=msb(y) and x>y now we can put all values v which have msb(v) < msb(x) before x and values w which have msb(w) >=msb(x) after x both in sorted order.
there are some conditions which are impossible: 1. when k is a power of 2 and n==k 2. when msb(k) > msb(n)
try to find for each $$$i$$$ nearest $$$j$$$ $$$(j \gt i)$$$
and for each $$$j$$$ nearst $$$i$$$ $$$(i \lt j)$$$
such that $$$i \oplus j \gt k$$$ and
was there a particular reason in Div1 4 problem to make it either 1 or -1? because any values could have worked.