Hello CodeForces Community!
We’re back with a new and exciting set of coding challenges with the July Cook-Off 2018 sponsored by ShareChat. Plus there are some exciting job/internship opportunities by ShareChat for participants. More details on the July Cook-Off contest page here:
Looking forward to seeing your participation in yet another exciting monthly contest! Joining me this time on the problem setting panel are:
- Problem Setters: kefaa (Kirill Gulin), kingofnumbers (Hasan Jaddouh)
- Problem Tester: isaf27 (Ivan Safonov)
- Editorialist: vijju123 (Abhishek Pandey)
- Statement verifier: Xellos (Jakub Šafin)
- Russian Translator: Mediocrity (Fedor Korobeinikov)
- Mandarin Translator: huzecong (Hu Zecong)
- Vietnamese Translator: (VNOI Team)
Contest Details:
Time: 22nd July 2018 (2130 hrs) to 23rd July 2018 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone
Contest link: codechef.com/COOK96
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!
STICKS2 was a horrible problem
For me only terrible thing is that I am so stupid and couldn't figure what is wrong in my submission for 1.5.hours and after it made again 3 stupid bugs.
The fourth problem looks easier to me, It is really pitty that I didn't have enough time to code it correctly.
yes, it's tricky problem (among all 32 people who solved it only 3 got it from first submission). but why is it horrible?
is Tree question, HLD + auxilary tree ??
not really, it can be solved using 1D persistent segment trees in O((sum of K) * log n)
How to solve F2NDMAX?
I think you should make DAG with current constraints. After it all elements with in-degree 0 should be merged like segment tree.On that way you can get maximum, after it second element is one over the path of maximum in that segment tree. You will have approximately x log(x) queries, where is x amount of elements with in-degree 0.
I didn't get AC, but I believe it is correct.
You should also consider elements which are part of contraints and lost only to those with zero degree to be candidates for second maximum.Now since each vertex has weight. it wont be a segment tree. we want to minimize wt to a leaf from root of the comparison tree constructed which can be done using priority queue,
Maybe I am wrong but I think only one such element should consider — second of the maximum.
EDIT: I see my mistake, thank you!
Can you please sketch your solution ?
?detaR tI sI