Greetings Codeforces Community!
You are invited to participate in the CodeChef September Lunchtime — a 3-hour contest with 5 problems to be solved. This is a chance for you to participate and improve your programming skills along with your CodeChef rating.
The problem statements of the contest will be accessible in English, Hindi, Bengali, Russian, Mandarin, and Vietnamese. I hope you will connect with your fellow programmers and enjoy solving the contest problems. Joining me on the problem setting panel are:
Setters: kingofnumbers (Hasan Jaddouh), Odin- (Jafar Badour), Mhammad1 (Mohammad Shahhoud), Atreus (Abolfazl Soltani), Erfan.aa (Erfan Alimohammadi)
Tester and Editorialist: Pepe.Chess (Hussain Kara Fallah)
Statement Verifier: Xellos (Jakub Safin)
Mandarin Translator: gediiiiiii (Gedi Zheng)
Vietnamese Translator: Team VNOI
Russian Translator: Mediocrity (Fedor Korobeinikov)
Bengali Translator: solaimanope (Mohammad Solaiman)
Hindi Translator: Akash Shrivastava
Contest Details:
- Start Date & Time: 28th September 2019 (1930 hrs) to 28th September 2019 (2230 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone
- Contest link: https://www.codechef.com/LTIME76
- 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 Indian and top 10 Global school students from ranklist will receive certificates and CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://discuss.codechef.com/t/how-do-i-win-a-codechef-goodie/7344. (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!
problem TREEVERS is very similar to problem Minimum inversons from running contest in Hackerearth
You should have posted this after the contest.
Thanks for noticing it. it's really weird that these two problems appeared in two close (in time) contests. The problem TREEVERS was proposed to codechef two months ago, so I doubt that the author stole it from hacker-earth.
Also notice the problem in hacker earth has constraint "Arrays a,p are generated randomly". which doesn't exist in TREEVERS. I tried to check if it's possible to get AC in TREEVERS by copying a submission from hackerearth, but when checking some of the submissions there, it seems to me they are all wrong, take this as an example (https://www.hackerearth.com/submission/31738408/) a solution that sorts the children based on their own value, if two children has equal value then sort them based on the number of their own children! this solution seems to me wrong and it's not possible to get AC on TREEVERS by copying such solutions, it's not even possible to get a hint from them.
what do you think? did I miss anything?
How you solve ALLSUB ?
First of all, let Rr be the optimal reordered string of R. S must be a substring of it, so that it contains all the substrings of S.
The only thing left is to find optimal position of S. To make R lexicographically smallest , all the character other than that present in S should be lexicographically sorted.
But consider S = bbbaacc , R = aaaabbbbcccc. So the string would be aabbbbaacccc. But here optimal string would be aabbbaaccbcc.
So here the answer depends on the first different character in S from the previous ones. If it is greater than the previous character you should keep difference of frequency of R — S before the position of string S in Rr. If it is smaller than previous character , you should keep difference of frequency of R — S after the position of string S in Rr.
Backtracking solution passes in ICECREM.
How to solve TREEVERS and ICECREM ?
TREEVERS is dp on trees. Have a look at my solution. You will understand. https://www.codechef.com/viewsolution/26837251
How to solve APPLE42 ? https://www.codechef.com/LTIME76A/problems/APPLE42