Greetings Codeforces Community!
Brace yourself because Long Challenge contest of the month is HERE! Expect nothing short of a thoroughly thrilling 10-day code-cation; featuring exciting problems, amazing competition and lastly, a chance to level up your rating.
Moreover, the Long Challenge is particularly crafted to help you hone your coding skills, while competing amongst the best of the best. Top 20 participants from each college/university will win scholarships for CodeChef Certification exam. Visit the contest page to know more.
In addition, if you have some original and engaging problem ideas, and you’re interested in them being used in the CodeChef's contests, you can share them with our admins here: https://www.codechef.com/problemsetting/new-ideas
Do join your fellow programmers and actively participate in this exciting contest. Joining me on the problem setting panel are:
- Setters: Newaj_69 (Md. Shafiq Newaj Shovo), Soul_Full_Of_Thunder (Yulian Yarema), sayantan_das24 (Sayantan Das), YouG22 (Utkarsh Garg), kartik_24 (Kartik Singhal), mraron (Noszály Áron), babin (Claudiu Babin), VladProg (Vlad Zavodnik), Danylo99 (Danylo Mocherniuk), Lewin (Lewin Gan), Morphy (Alei Reyes)
- Admin: Alex_2oo8 (Alexey Zayakin)
- Editorialist: vijju123 (Abhishek Pandey)
- Statement Verifier: Xellos (Jakub Safin)
- Russian Translator: Mediocrity (Fedor Korobeinikov)
- Vietnamese Translator: Team VNOI
- Bengali Translator: solaimanope (Mohammad Solaiman)
- Hindi Translator: Akash Shrivastava
- Mandarin Translator: gediiiiiii (Gedi Zheng)
Contest Details:
- Start Date & Time: 2nd August 2019 (1500 hrs) to 12th August 2019 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.
- Contest link: https://bit.ly/2LFPyxM
- 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 20 performers in Indian category and top 10 performers in Global 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://goodies.codechef.com/
(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!
Rating prediction for div1 is here and for div2 is here.
How to solve CHGORAM ?
only 3 possible trends are possible Peak trend i.e. p1>max(p0,p2), Valley trend p1<min(p0,p2) or line trend(increasing/decreasing) where p0<p1<p2 or p0>p1>p2. All three of them can be solved separately with DP on trees.
Alright. I got this part, but how exactly we are calculating no. of possible p0, p1 candidates for a fixed p1 ? . I means if I had to count such triplets in an array, I'd have gone with segment tree/merge sort tree or similar data structures to count p0, p1 for each possible p1. But here it is tree.
You basically have to calculate contribution for each child(ci) of node vi the number of values less than vi and number of values greater than vi in subtree of ci. and then use combinatorial approach for calculation for each specific trend by iterating over all children of node vi.
for more detailed explanation you can have a look @ my implementation https://www.codechef.com/viewsolution/25912378
Thank you. Now, I got it.
How to solve CSTREE??
https://pdfs.semanticscholar.org/d032/1ff6d99626b488e7ef7d97af82df329d95ae.pdf
Use theorem given in part c in https://en.wikipedia.org/wiki/Determinant#Sylvester's_determinant_theorem along with kirchoff's theorem.
Is there is some better way to solve "Tree Sequence".
I try Heavy-Light Decomposition + maintaining four segment tree for each type of query + some combinatorics,
But it's implementation become too hard and error prone.