mugurelionut's blog

By mugurelionut, history, 7 months ago, In English,

Hello CodeForces Community!

The calendar page has flipped to December. Take a break from your end planning and crack the codes by participating in December Long Challenge. Note down the details and be there. Joining me on the problem setting panel, we have:

I hope you will enjoy solving the problems. Please give your feedback on the problem set in the comments below after the contest.

Contest Details:

Time: 1st December 2017 (1500 hrs) to 11th December 2017 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: https://www.codechef.com/DEC17

Registration: You just need to have a CodeChef handle to participate. All those who are interested and do not have a CodeChef handle are requested to register in order to participate.

Prizes: Top 10 global and top 20 Indian winners get 300 Laddus each, 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!

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

»
6 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Nice problemset.

How to solve the last 2 problems : CHEFFIB and WESTAND.

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

    If O(nlog2n) can pass then I think centroid decomposition can be used.

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it -10 Vote: I do not like it

      Can you explain your approach please?

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

      doesn't work. Gets TLE.

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

        I am sorry, it does work. My code was not working since I had two update and query function. Once I merged both of them, my code ran. This is so dumb. My update function works in O(logn), while for a single query I have O(logn) updates. If I use two updates, it gets TLE. But if I use just one, it passes. Can't believe function overhead is so large. -_-

»
6 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Incase anyone needs a video tutorial for problem CHEFEXQ, here is the video https://goo.gl/Wi3C5Y.

Its always exciting to see how SquareRoot Decomposition can be used to solve such a variety of questions.

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

    Can you please tell me that why we have to update only bth bucket in every update query?

    I mean all buckets after bth bucket should also change because the index i which has been changed is also in the prefix of all those later indexes.

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

      A bucket is reponsible for only RTN elements. The complete array is divided into RTN sections or buckets, each of size RTN.

      So update only that section or bucket that contains the index that is modified.