### kingofnumbers's blog

By kingofnumbers, 20 months ago, ,

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.

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!!

• +39

 » 20 months ago, # |   +8 30 minutes to start!
 » 20 months ago, # |   0 How to solve the 3rd problem?
•  » » 20 months ago, # ^ | ← Rev. 3 →   0 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.
•  » » » 20 months ago, # ^ |   +8 One can use prefix function dependency tree + binary lifting.
•  » » » » 20 months ago, # ^ |   0 What is a prefix function dependency tree? Can you elaborate a bit more or give any link?
•  » » » » » 20 months ago, # ^ |   0 Umm, I think he just meant kmp failure function
•  » » » » » » 20 months ago, # ^ |   0 Yes, just add directed edges p[i] -> i.
 » 20 months ago, # |   0 Any idea about how to solve the main or the subtask of the 4th problem?
•  » » 20 months ago, # ^ |   0 Let A[i] and B[i] are indices of i-th couple and A[i]