Hello CodeForces Community!
We always look forward to offering you a fresh set of challenges to test your coding skills upon and we are back with the May Cook-Off 2018 sponsored by ShareChat. In addition, there are some exciting job/internship opportunities by ShareChat in the May Cook-Off 2018. For more details, you may visit the May Cook-Off contest page here: https://www.codechef.com/COOK94
Looking forward to seeing bright minds like yours come together to be the best! Joining me this time on the problem setting panel are:
- Problem Setter and Editorialist: hloya_ygrt (Yuri Shilyaev)
- Problem Tester: Pepe.Chess (Hussain Kara Fallah)
- Statement Verifier: Xellos (Jakub Safin)
- Russian Translator: hloya_ygrt (Yuri Shilyaev)
- Mandarin Translator: huzecong (Hu Zecong)
- Vietnamese Translator: (VNOI Team)
Contest Details:
Time: 20th May 2018 (2130 hrs) to 21st May 2018 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone
Contest link: https://www.codechef.com/COOK94
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://discuss.codechef.com/questions/51999/how-do-i-win-a-codechef-goodie
(For those who have not yet got their previous winning, please send an email to [email protected])
Good Luck!
Hope to see you participating!!
Happy Programming!!
Starts in 5 minutes.
Cam somebody find counter-test for my solution to SHEFPIC? For some reason it got AC. The idea is to find for each point 5 closest points and from this 5 closest points find 2 of them, that form the smallest square with given point. Now sort this triples of points in order of increasing size of square for each triplet. Go from the triple with smallest square to triple with the highest square and mark used[x1] = used[x2] = used[x3] = true if x1, x2 or x3 are not used or delete this triple otherwise. Now find maximum square from remaining triples. Complexity is O(5·T·N2)
How to solve Difficult Choice?
Do 1 dfs run on the tree, keeping track of number of vertices that satisfy the condition in a pair with the root vertex (class 1), and the ones that don't (class 2). It turns out, that all pairs of vertices belonging to the same class also don't satisfy the condition. And then it is just arithmetics.
Define a root and calculate distance from that root to all node with dfs. But Take dis mod 2
Then define g[i] = v[i]^dis[i] Answer will be #nodes which g[i] has odd 1's bits x #nodes which g[i] has even 1's bits.
Silence_for_Melody Can you please Explain more ?
I will give you the theory behind and you have to figure it out, sorry for my English since now.
You must know some properties about trees and XOR operation.
For one moment forget about ages in the problem and try to solve the following: How many pairs of cities are so their distance is even? How many there are so their distance is odd?
Now forget about the distance on work over ages. How many pairs of cities there are so the bits in their XOR are even? How many there are so the bits in their XOR are odd?
Last, and what makes this problem awesome, observation: When you want to evaluate parity of bits in the XOR of A and B, does the order of bit in A and B matter? Just think about it. Hope everything is clear
Got that. Thanks man. 18621772
Editorials are out on codechef!
Where are the editorials? Can you give me the link? I am not able to find it.
here
Atleast they should add a link below the problem for editorial.Anyway thanks.
For the problem Difficult Choice , in the editorial its mentioned that |au⊕av| % 2=(|au| % 2)⊕(|av| % 2). where |x| be the number of one-bits in binary representation of x
Can someone help me prove the statement ? Thank you :)