isaf27's blog

Invitation to CodeChef June Lunchtime 2018!
By isaf27, history, 6 years ago, In English

Hello CodeForces Community! Once again we bring to you a fresh set of programming challenges with the June Lunchtime 2018, a three-hour contest of your coding abilities. Hope to see you all join us and challenge for the top spot!. Joining me this time on the problem setting panel are:

  • Problem Setter: isaf27 (Ivan Safonov)
  • Problem Tester: kingofnumbers (Hasan Jaddouh)
  • Editorialist: likecs (Bhuvnesh Jain)
  • Admin: kingofnumbers (Hasan Jaddouh)
  • Statement Verifier: Xellos (Jakub Safin)
  • Russian Translator: CherryTree (Sergey Kulik
  • Mandarin Translator: huzecong (Hu Zecong)
  • Vietnamese Translator: (VNOI Team)

Contest Details:

Time: 30th June 2018 (1930 hrs) to 30th June 2018 (2230 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone
Contest link: https://www.codechef.com/LTIME61 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://discuss.codechef.com/questions/51999/how-do-i-win-a-codechef-goodie
(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!!

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Collides with WC :(

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

    I doubt that there's any member of any WC team was willing to participate in lunchtime if there were no collision :)

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Why is there an ACM style ranklist? Shouldn't it be IOI-style?

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

How to solve XORSORT2?

I had which passed everything but one test (it got 50 points). Did you have the same complexity or you have something better?

In short my idea was the following:

We notice that all bits of X (the number we xor with) are independent for the answer. This way we can see for each bit the value it will add to the number of inversions if it is set and unset. We can do this in . Then we can do binary search on the answer with meet in the middle to compute the answer.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +13 Vote: I do not like it

    That's exactly what I did, passing in 0.79s https://www.codechef.com/viewsolution/19029579

    Edit: but the binary search part is O(2^(k/2)*(logn+k))?

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

      I just saw your solution and it actually is for the meet in the middle, while my solution was . This may explain the time difference.

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

    Same solution, got 100 points 30 second before contest ended.

    Squeezed into TL changing cin to scanf, and sort to stablesort...

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

    At first i've split into two halves by 15 and 15 and got TL :(, but then i set 18 + 12, and got AC :)

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

The editorials for all the problems are available now:

NUM239

SUMPOWER

TREESORT

DOCSDEL

XORSORT2

TBGRAPH

Do provide your feedback for them and sorry for the delays.

→ Reply