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:
Problem setter: Pepe.Chess (Hussain Kara Fallah)
Testers: kingofnumbers (Hasan Jaddouh) and iscsi (Istvan Nagy)
Editorialist: T1duS (Udit Sanghi)
Language Verifier : arjunarul (Arjun Arul)
Russian Translator : CherryTree (Sergey Kulik)
Mandarin Translator: huzecong (Hu Zecong)
Vietnamese Translator: VNOI Team
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 [email protected])
Good Luck! Hope to see you participating!!
25 minutes left to start!
Did someone manage to solve "Nasty Queries" using a Segment Tree?
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.
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 no
Is it hackable??
They intend to kill an easy solotion with MO. :(
Well I got Mo's solution through, so I guess killing Mo's is not so easy :)
Here is my solution 13704547.
Isn't the comlexity of your code O(M * SQRT(Q)) ?
Yes I think so. But it is not absurd to jam through 10^9 I believe :)
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
I also got TL doing MO. https://www.codechef.com/viewsolution/13703479 Later on solved with hashing.
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
Nope :) My MO is got AC Too: 13702714
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
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.
Can anyone point out the bug in my code problem:Nasty Queries , I used MOS,
code
How to approach Nasty Queries?
The degree of any vertex must be even.
Yes but why does the solution use hashes? Sorry if this is a stupid question.
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.
Thanks! :)
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 ?
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.
Nice one !!
Could you tell how to design such hash function.Any resources would be useful.
Just assigning a large random number to each value from 1 to n suffices. I did the following.
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.
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.
here. Can this idea be hacked with some clever test case??
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:
can anybody tell bug in my code of nasty query
simple approach through xor code
Try this case:
Your code would give "Yes", but answer is "No".
Fails if the numbers in range are 2, 3, 4, 5.
thank you both of you i got my bug. can you suggest one method two overcome it?
For Hussain set, some solutions with 10*N*log(10*N) also passed. Mine not among them :(
Solution for Hussain Set?
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
Great, thanks!
This is exactly what I thought but was unsure if this would work. Can you please share your implementation for this? Thanks!
My AC implementation is the same I believe : Code
Thank you! :)
I solved it after contest using this idea.
Code
How to solve E ?
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.
"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.
I am also waiting for the editorial of E. T1duS, How many days more?
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.
Any updates on the editorial? Or can anyone share their approaches?
How can I submit after the contest?
Try the PRACTICE tab.
Found it. Thanks.
Is there any deterministic solution for problem D?