Hello CodeForces Community,
I would like to invite you all to take part in the CodeChef July Lunchtime. It is an IOI Style contest where participants will be given 4 problems to solve in 3 hrs. With the IOI just two weeks away, LunchTime forms a great way to practice and test your preparation.
The problems were set by me animeshf (Animesh Fatehpuria) and PraveenDhinwa (Praveen Dhinwa) and were tested by me and pushkarmishra (Pushkar Mishra). I hope you will enjoy solving them. We have problems of various difficulty levels ensuring that everyone can find something interesting to solve! Please give me your feedback on the problem set in the comments below after the contest.
You can find the rest of the details about the contest below.
Time: 30th July 2016 (1930 hrs) to 30th July 2016 (2230 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.
Details: Contest Page
Registration: You just need to have a CodeChef handle to participate. For all those who are interested and do not have a CodeChef handle, please register here in order to participate.
- Problem Setter: PraveenDhinwa (Praveen Dhinwa), animeshf (Animesh Fatehpuria)
- Problem Tester: animeshf (Animesh Fatehpuria) pushkarmishra (Pushkar Mishra)
- Editorialist: animeshf (Animesh Fatehpuria) pushkarmishra (Pushkar Mishra)
- Russian Translator: Antoniuk (Vasya Antoniuk)
- Mandarin Translator: huzecong (Hu Zecong)
- Vietnamese Translator: VNOI Team
- Contest Admin: PraveenDhinwa (Praveen Dhinwa), pushkarmishra (Pushkar Mishra)
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
Reminder : Contest starts in 30 minutes.
Contest has started.
I like problemset! It is bad to change TL during contest. Now seems that task with number of combinations is the most interesting and I didn't spend on it more than 3 minutes :)
Can someone provide me needed solution for tree task? My code works in O(n2), with several breaks and optimizations to use small number of ifs. I see I can optimize it more, but still it is O(n2) in worst case.
I implemented naive solution, got AC; timelimit has been decreased, after rejudge I have TL. I optimized naive solution, got AC again. Timelimit has been decreased for second time, now it's another TL for me. I'm rewriting it for third time with yet more optimizations, finally AC in 2.9.
Intended solution is Mo's algorithm on a tree.
It's not your (our) fault, the front page says "contest ended".
Why I am not so pro for hacking test data :D I must ask you or Xellos for giving extra classes :)
Oops, I thought it ended
Great! For me better option was hacking testdata :D I didn't used idea of MO algorithm on tree, but I know it is very useful :)
Note about CLOSEFAR Time Limit:
The constraints were such that some brute force solutions passed during the contest, although our tester done some testing to ensure that it doesn't. We had no option but to make the TL very strict, at 3.5 seconds, in order to cut out the brute force O(N2) solutions. We realize that this was unfair to those who had correct solutions and were forced into making constant optimizations. We deeply regret any inconvenience caused.
The test data was certainly very weak as well, as some solutions involve precomputing K best pairs and answers queries in O(K) time if certain conditions are met :(
I think it was your first experience as a problem setter, you will learn slowly on how people can be evil in hacking test data :) Btw nice problemset, i enjoyed solving problems.
Thank you for your feedback. We are glad that you liked the problemset!
Yes, I now realize that the main mistake I made was that I focused on making the trees structurally strong and did not think about the values of the nodes — I just randomly generated node values for all test cases. Xellos and I_love_Tanya_Romanova both have hacky solutions which exploit this.
It was a learning experience and I will be more careful from next time while generating data.