kingofnumbers's blog

Invitation to CodeChef February Lunchtime 2018!
By kingofnumbers, 7 years ago, In English

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

  • Vote: I like it
  • +39
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

30 minutes to start!

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve the 3rd problem?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      One can use prefix function dependency tree + binary lifting.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What is a prefix function dependency tree? Can you elaborate a bit more or give any link?

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Umm, I think he just meant kmp failure function

          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yes, just add directed edges p[i] -> i.

            → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply