Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### kingofnumbers's blog

By kingofnumbers, history, 19 months 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
•

 » 19 months ago, # |   +3 25 minutes left to start!
 » 19 months ago, # |   +13 Did someone manage to solve "Nasty Queries" using a Segment Tree?
•  » » 19 months 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.
•  » » » 19 months 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??
•  » » 19 months ago, # ^ |   +13 They intend to kill an easy solotion with MO. :(
•  » » » 19 months ago, # ^ |   +5 Well I got Mo's solution through, so I guess killing Mo's is not so easy :)
•  » » » » 19 months ago, # ^ |   0 Here is my solution 13704547.
•  » » » » » 19 months ago, # ^ | ← Rev. 2 →   +3 Isn't the comlexity of your code O(M * SQRT(Q)) ?
•  » » » » » » 19 months ago, # ^ |   0 Yes I think so. But it is not absurd to jam through 10^9 I believe :)
•  » » » » » 19 months 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
•  » » » » » » 19 months ago, # ^ |   0 I also got TL doing MO. https://www.codechef.com/viewsolution/13703479 Later on solved with hashing.
•  » » » » 19 months 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
•  » » » » » 19 months ago, # ^ |   +5 Nope :) My MO is got AC Too: 13702714
•  » » » » » » 19 months 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
•  » » » » » 19 months 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.
•  » » » » 19 months ago, # ^ |   0 Can anyone point out the bug in my code problem:Nasty Queries , I used MOS,code
 » 19 months ago, # |   0 How to approach Nasty Queries?
•  » » 19 months ago, # ^ |   0 The degree of any vertex must be even.
•  » » » 19 months ago, # ^ |   +8 Yes but why does the solution use hashes? Sorry if this is a stupid question.
•  » » » » 19 months 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.
•  » » » » » 19 months ago, # ^ |   0 Thanks! :)
•  » » » » » 19 months 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 ?
•  » » » » » » 19 months 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.
•  » » » » » » » 19 months ago, # ^ |   0 Nice one !!
•  » » » » » 19 months ago, # ^ |   +3 Could you tell how to design such hash function.Any resources would be useful.
•  » » » » » » 19 months 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.
 » 19 months 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.
•  » » 19 months ago, # ^ |   0 here. Can this idea be hacked with some clever test case??
•  » » » 19 months 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 
 » 19 months ago, # |   0 can anybody tell bug in my code of nasty query simple approach through xor code
•  » » 19 months 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".
•  » » 19 months ago, # ^ |   0 Fails if the numbers in range are 2, 3, 4, 5.
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 thank you both of you i got my bug. can you suggest one method two overcome it?
 » 19 months ago, # |   0 For Hussain set, some solutions with 10*N*log(10*N) also passed. Mine not among them :(
 » 19 months ago, # |   0 Solution for Hussain Set?
•  » » 19 months 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
•  » » » 19 months ago, # ^ |   0 Great, thanks!
•  » » » 19 months ago, # ^ |   0 This is exactly what I thought but was unsure if this would work. Can you please share your implementation for this? Thanks!
•  » » » » 19 months ago, # ^ |   +10 My AC implementation is the same I believe : Code
•  » » » » » 19 months ago, # ^ |   0 Thank you! :)
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   0 I solved it after contest using this idea.Code
 » 19 months ago, # |   +3 How to solve E ?
•  » » 19 months 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.
•  » » » 19 months 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.
•  » » » » 19 months ago, # ^ |   0 I am also waiting for the editorial of E. mathecodician, How many days more?
•  » » » » » 19 months 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.
•  » » » 19 months ago, # ^ |   0 Any updates on the editorial? Or can anyone share their approaches?
 » 19 months ago, # |   0 How can I submit after the contest?
•  » » 19 months ago, # ^ |   +5 Try the PRACTICE tab.
•  » » » 19 months ago, # ^ |   0 Found it. Thanks.
 » 19 months ago, # |   +24 Is there any deterministic solution for problem D?