Hello Codeforces community,
You are invited to CodeChef December Long Challenge 2018 sponsored by ShareChat. This is a 10-day competition with 8 problems and it’s open to programmers across the globe. The contest problems will be available in English, Hindi, Bengali, Russian, Mandarin and Vietnamese.
Participants will also be in the running for some exciting jobs at ShareChat — India’s fastest growing social network. To apply, all you need to do is fill the application form on the contest page and participate in the December Long Challenge.
I hope you will join your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:
- Admin: mgch (Misha Chorniy)
- Tester: Andrei1998 (Andrei Constantinescu)
- Statement Verifier: Xellos (Jakub Safin)
- Editorialist: adamant (Alexander Kulkov)
- Setters: Morokei (Vladislav Milshin), huzaifa242 (Huzaifa Yusufbhai Mankda), tmwilliamlin168 (William Lin), Barichek (Igor Barenblat), Fekete (Ivan Fekete), jtnydv25 (Jatin Yadav), TooNewbie (Abutalıb Namazov), DOlaBMOon (Max Hsia), whzzt (Zhenting Zhu)
- Mandarin Translator: huzecong (Hu Zecong)
- Vietnamese Translator: Team VNOI
- Russian Translator: Mediocrity (Fedor Korobeinikov)
- Bengali Translator: solaimanope (Mohammad Solaiman)
- Hindi Translator: Akash Shrivastava
Contest Details:
- Start Date & Time: 7th December 2018 (1500 hrs) to 17th December 2018 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone
- Contest link: https://www.codechef.com/DEC18
- 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. First to solve each problem except challenge — 100 laddus. 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!! Happy Programming!!
How to solve CBFEAST?
Let's try to solve an easier task first:
We start with an empty set and have three types of queries:
We can solve this by maintaining four integers for the given set:
Now when we insert a number in the front:
max(0, old maximal prefix + inserted value)
sum + inserted value
max(sum, old maximal suffix)
max(old maximal subarray sum, max(maximal prefix sum, maximal suffix sum))
When we insert a number in the back it is similar.
Ok so we solved that easier task. For the original task we just need to maintain a segment tree with such a structure in each node (the four numbers). We keep two lazies — one for queries which insert in the front and one for those queries which insert in the back.
When we have an update query we will do a range update in the interval
[c - K; c + K]
. And when we have query to print an answer we just do a index query on c.Can it be solved using square root decomposition?
No, You have to answer queries online.
https://www.codechef.com/viewsolution/21921638
hot to solve INT_XOR
First ask 1 2 3 and 1 2 4, which gives you 3^4. Then asking 3 4 5 and 3 4 6 would give you 5 and 6 Then you can ask 5 6 7, 6 7 8, 8 9 10, ...
You can ask these triples: 1 2 3, 2 3 4, …, N–2 N–1 N, N–1 N 1, N 1 2. Then, if you xor these triples you will have a1^a2^a3^a4^ …^aN. If N % 3 == 1 or N % 3 == 2 it’s easy to see that you can find any value of this sequence. But If N % 3 == 0 you can divide your sequence into two and find answer for each subsequence independently. My solution: https://www.codechef.com/viewsolution/21925944
thanks sir..it helped
How to solve EDGEDIR. I was thinking of greedy approach where I take edge count (in-degree and out-degree both) for each node, then start solving with the nodes having the smallest edge count till the nodes having the most edge count.
My solution is:
Take a random direction for each edge and after that mark all nodes which currently have odd in-degre with 1s and all the remaining nodes with 0s. It can be easily proven that if M is even there will be even number of 1s after this operation. If M is odd then the answer is -1.
Now we need to change the direction of some edges to make all the nodes marked with 0 (make those which are currently marked with 1 to 0). We can see that if we take a randon path of the form (1->0->0....->1 (starting and ending with ones and 0 or more zeroes in between)), and we change the direction of each edge in this path the only thing that will change will be that the two ending nodes (the two 1s will become 0s). So we only need to pair the nodes marked with 1 in pairs find a random path between each pair and change the direction of edges on this path.
One way to do thia is to take a random spanning tree and do a dfs to count subtree sizes(considering only nodes marked with 1) for each node in the spanning tree then for each node if the number of nodes marked with 1 in the subtree is even then we can match them in the subtree itself and we don't have to do anything. Else if the number is odd then we need to change the durection of the edge which leads to the parent of the current node.
https://codeforces.net/blog/entry/11186?#comment-162599
Can anyone point out in what test-cases mentioned greedy approach will fail?
When will official editorials be published ?
How do we solve BHD and BICONT?
+1 Specially for Bicont. I have tried going through the solutions but am unable to wrap my head around them. Any hints would be highly welcome. Thanks in advance.
Hint1: Can you compute dp[node][i][...other things...] = how many ways are there to split node's subtree into i node-disjoint biconnected components? (note: this dp may overcount!)
Hint2: To remove the overcounting, try looking up "Binomial Inversion".