### kingofnumbers's blog

By kingofnumbers, history, 4 years ago,

Hello CodeForces Community! I would like to take this opportunity to extend this invitation for CodeChef May Cook-Off. As usual it is scheduled for the second last Sunday of the month.

Joining me on the problem setting panel, we have:

You will be provided by 5 problems of various difficulties to solve during 2 hours and 30 minutes, I have found the problemset very interesting and I recommend coders of various skills to participate especially GrandMasters, please feel free to provide your feedback in the comments section after the contest, I hope you will enjoy solving the problem set.

You can find the rest of the details about the contest below.

Time: Sunday, 21st May, 2017 at 21:30 HRS (IST) (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: https://www.codechef.com/COOK82

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Prizes: Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://www.codechef.com/laddu. (For those who have not yet got their previous winning, please send an email to winners@codechef.com)

Good Luck! Hope to see you participating!!

• +58

 » 4 years ago, # |   +3 25 minutes left to start!
 » 4 years ago, # |   +13 Did someone manage to solve "Nasty Queries" using a Segment Tree?
•  » » 4 years ago, # ^ |   0 No and I didn't even try. Hashing is the way to go — check if the xor of all edge endpoints in the given range is 0 and if some other prefix hashes (for example polynomial hash of vertex degrees) are equal. Fast, simple, fairly reliable.
•  » » » 4 years ago, # ^ |   +5 I had an approach like give each vertex a prime and its inverse for the sake of hashing.for l to r. ans[l] *inv(ans[r-1]) . if it is 1 yes else noIs it hackable??
•  » » 4 years ago, # ^ |   +13 They intend to kill an easy solotion with MO. :(
•  » » » 4 years ago, # ^ |   +5 Well I got Mo's solution through, so I guess killing Mo's is not so easy :)
•  » » » » 4 years ago, # ^ |   0 Here is my solution 13704547.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   +3 Isn't the comlexity of your code O(M * SQRT(Q)) ?
•  » » » » » » 4 years ago, # ^ |   0 Yes I think so. But it is not absurd to jam through 10^9 I believe :)
•  » » » » » 4 years ago, # ^ |   0 I was also trying to fit MO in TL. Even after using the same block size as yours, I still cannot get AC. https://www.codechef.com/viewsolution/13706799
•  » » » » » » 4 years ago, # ^ |   0 I also got TL doing MO. https://www.codechef.com/viewsolution/13703479 Later on solved with hashing.
•  » » » » 4 years ago, # ^ |   +5 MO was intended to be killed. I think all people except you got TLE :D I think we should have set the TL to 1second :P
•  » » » » » 4 years ago, # ^ |   +5 Nope :) My MO is got AC Too: 13702714
•  » » » » » » 4 years ago, # ^ |   +8 Even before seeing comments here I checked the submissions page and I saw a lot of TLE based on sqrt and MO and these stuff.Anyway this problem turned to be the 3rd easiest , so I don't really mind :P
•  » » » » » 4 years ago, # ^ |   0 Question for you, in these short contests on Codechef is the Java time limit indeed 2x? I am certain that in the long contests it is because I can see runtimes on cases, but here I am not sure.
•  » » » » 4 years ago, # ^ |   0 Can anyone point out the bug in my code problem:Nasty Queries , I used MOS,code
 » 4 years ago, # |   0 How to approach Nasty Queries?
•  » » 4 years ago, # ^ |   0 The degree of any vertex must be even.
•  » » » 4 years ago, # ^ |   +8 Yes but why does the solution use hashes? Sorry if this is a stupid question.
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   +7 The degrees are even means all the endpoints in the given query range appear even number of times. So your query basically is to check if there's any element with odd frequency in given range.You can do that by checking if the xor of elements in that range is zero (if each number appears even number of times, they cancel out in pairs). This solution might give wrong decisions for some set of values like: 1, 2, 3. Even though their xor is zero, all of them have odd frequency. The idea is to hash each number from 1 to n to distinct and very large numbers chosen randomly so that the probability of such sets occurring becomes very small. Then you can simply check for zero xor.
•  » » » » » 4 years ago, # ^ |   0 Thanks! :)
•  » » » » » 4 years ago, # ^ |   +3 I got it, but what if you are submitting such a solution on codeforces where you will not be able to know whether your randomization failed or not till the end of the contest ?
•  » » » » » » 4 years ago, # ^ | ← Rev. 4 →   +18 Yes you can't know but you can take safety measures to reduce the failure probability to almost zero. On CF I'd probably use 4 - 5 different hashes (in fact, you can take around 50 hashes in this constraint). I'd answer "Yes" only if all of them gave zero. It's close to impossible for such solution to fail.
•  » » » » » » » 4 years ago, # ^ |   0 Nice one !!
•  » » » » » 4 years ago, # ^ |   +3 Could you tell how to design such hash function.Any resources would be useful.
•  » » » » » » 4 years ago, # ^ |   +10 Just assigning a large random number to each value from 1 to n suffices. I did the following. const long long MOD = 1e14 + 7; for (int i = 1; i <= n; ++i) { hashValue[i] = (rand() * 1LL * rand()) % MOD; } There's no need to "design" any hash function here. You just need the numbers to be scattered enough so that there's no range with xor zero. For the xor to be zero you need even number of ones in every bit position, the probability of which gets smaller as the number of bits increase. Here's my code if you need reference.
 » 4 years ago, # |   +5 That deceiving scoreboard submissions got me again. For 2 hours i was trying to squeeze C with either bitset+sqrt -_-. And then read D in last 30 mins. Solution to D appeared so easy to me with just Deque use (Submission)Btw did anyone do C without hashing? I really hope there exists some solution without hashing.
•  » » 4 years ago, # ^ |   0 here. Can this idea be hacked with some clever test case??
•  » » » 4 years ago, # ^ |   +5 Yes, it is very much like hashing only so hackable. Infact it is very easy to generate hack cases if prime numbers aren't random.Your solution fails on this case: 1986 4 1 3 1 6 1 276 1 1986 1 1 4 
 » 4 years ago, # |   0 can anybody tell bug in my code of nasty query simple approach through xor code
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Try this case: 10 3 1 2 1 4 3 5 1 1 3 Your code would give "Yes", but answer is "No".
•  » » 4 years ago, # ^ |   0 Fails if the numbers in range are 2, 3, 4, 5.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 thank you both of you i got my bug. can you suggest one method two overcome it?
 » 4 years ago, # |   0 For Hussain set, some solutions with 10*N*log(10*N) also passed. Mine not among them :(
 » 4 years ago, # |   0 Solution for Hussain Set?
•  » » 4 years ago, # ^ |   +13 First of all sort numbers in asc order , then group them by the most significant bit. Iterate on the buckets from the most significant to the least. After you finish a bucket divide all its elements by 2 then merge it with the previous one in O(n) (merging 2 sorted sequences).complexity N log N + 64 * N
•  » » » 4 years ago, # ^ |   0 Great, thanks!
•  » » » 4 years ago, # ^ |   0 This is exactly what I thought but was unsure if this would work. Can you please share your implementation for this? Thanks!
•  » » » » 4 years ago, # ^ |   +10 My AC implementation is the same I believe : Code
•  » » » » » 4 years ago, # ^ |   0 Thank you! :)
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I solved it after contest using this idea.Code
 » 4 years ago, # |   +3 How to solve E ?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 An editorial will be posted soon I think. The idea mainly was to keep data about only some potential nodes, in this problem It's necessary only to keep data about ancestors of deleted nodes. And when deleting a node you just need to go and update its ancestors, and update their data based on the time shift occurred since the last update. Afterwards just iterate through them and make changes due the deletion of the node.
•  » » » 4 years ago, # ^ |   0 "Soon"...It is really annoying when the editorials for a contest are not posted. This is also the case for CodeChef's recent long challenge. Only the editorials to easier problems were posted, I am still waiting for an editorial to the KILLER problem. Similar thing has happened before too. I wonder when CodeChef will fix this problem of incomplete or no editorials.
•  » » » » 4 years ago, # ^ |   0 I am also waiting for the editorial of E. T1duS, How many days more?
•  » » » » » 4 years ago, # ^ |   0 I am not writing for E. I wrote the other 4. The problem required tries which I do not know yet so I asked Praveen Dhinwa. He said he'll write it for that problem.
•  » » » 4 years ago, # ^ |   0 Any updates on the editorial? Or can anyone share their approaches?
 » 4 years ago, # |   0 How can I submit after the contest?
•  » » 4 years ago, # ^ |   +5 Try the PRACTICE tab.
•  » » » 4 years ago, # ^ |   0 Found it. Thanks.
 » 4 years ago, # |   +24 Is there any deterministic solution for problem D?