Hello CodeForces Community!
I hope the month of February was one filled with programming escapades for you! To provide you with more coding action, here is the February Lunchtime 2018 featuring 4 interesting programming challenges!
I hope you will join your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:
- Problem Setter: kingofnumbers (Hasan Jaddouh)
- Problem Tester: mgch (Misha Chorniy)
- Problem Editorialist: .o. (Suchan Park)
- Statement verifier: Xellos ( Jakub Safin)
- Russian Translator: CherryTree (Sergey Kulik)
- Mandarin Translator: huzecong (Hu Zecong)
- Vietnamese Translator: VNOI Team
I hope you will enjoy solving them. Please give your feedback on the problem set in the comments below, after the contest.
Contest Details:
Time: 24th February 2018 (1930 hrs) to 24th February 2018 (2130 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.
Contest link: https://www.codechef.com/LTIME57
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://www.codechef.com/laddu.
(For those who have not yet got their previous winning, please send an email to winners@codechef.com)
Good Luck!
Hope to see you participating!!
Happy Programming!!
30 minutes to start!
How to solve the 3rd problem?
I did the following:
Run Z algorithm on the given input string.
Sort the queries in ascending order of p.
At the i'th query, for each index j between the p value of (i-1)th query and the ith query, check if (z[j] + j) >= p, then insert the index along with its corresponding (z[j]+j) value to a set. Also update the j'th index of the segment tree with +1. Then iterate over the set to find out the elements x whose (z[x]+x) value is less than p and erase them from the set. The set is kept sorted according to ascending value of (z[x]+x) and also update the x'th index of the segment tree with -1.
Finally to answer the query, you just need to find out the kth index from the indices with positive value of the segment tree from the right.
One can use prefix function dependency tree + binary lifting.
What is a prefix function dependency tree? Can you elaborate a bit more or give any link?
Umm, I think he just meant kmp failure function
Yes, just add directed edges p[i] -> i.
Any idea about how to solve the main or the subtask of the 4th problem?
Let A[i] and B[i] are indices of i-th couple and A[i] <B[i]
Let H = sum for all i ( min(B[i] — A[i] -1, 2*n -B[i] +A[i] — 1) )
note that min(B[i] — A[i] -1, 2*n -B[i] +A[i] — 1) means minimum number of swaps needed to make i-th couple adjacent (distance — 1)
let G be equal to number of pairs i,j such that A[i] < A[j] <B[i] <B[j]
the answer is simply H — G (try to think why)