Блог пользователя kingofnumbers

Автор kingofnumbers, 7 лет назад, По-английски

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 [email protected])

Good Luck!
Hope to see you participating!!
Happy Programming!!

  • Проголосовать: нравится
  • +39
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

30 minutes to start!

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve the 3rd problem?

  • »
    »
    7 лет назад, # ^ |
    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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any idea about how to solve the main or the subtask of the 4th problem?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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)