AllCatsAreBeautiful's blog

By AllCatsAreBeautiful, history, 7 weeks ago, translation, In English,

Hello CodeForces Community! We are thrilled to invite you to participate in the August Long Challenge 2018 sponsored by ShareChat. In addition, there are some exciting internship and full-time job opportunities by ShareChat for Indian programmers in the August Long Challenge 2018. For more details, you may visit the contest page.

I hope you will join your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:

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: 3rd August 2018 (1500 hrs) to 13th August 2018 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Contest link: https://www.codechef.com/AUG18

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 global and top 20 Indian winners get 300 Laddus each, 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). First to solve each problem individually: 100 laddus (For problems common to both Divisions, only one user will get laddus for that problem).

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

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

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

The contest has started. Hope to see you at the leaderboard. Good luck and enjoy the contest.

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

How to solve Safe Partition ?
Subtask 1 was a variation to classical DP. I couldn't think of further tasks!

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

What's the idea behind KCOMPRES?

»
6 weeks ago, # |
  Vote: I like it +76 Vote: I do not like it

I like how CodeChef calls it a "tie-breaker" problem when all but 10 people are tied at 0 points.

»
6 weeks ago, # |
  Vote: I like it -31 Vote: I do not like it

Initial set of editorials:

1.SPELLBOB

2.SHKNUM

3.PROBLEMS

4.GCDMOD

5.KCOMPRES

6.LONCYC

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    When will you upload rest of the editorials?

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      Nightshade, Really sorry for the delays. I had been busy shifting to a new city for my work for the last week. Just got free today. Rest of the editorials will be available within 2 days. All queries in the previous ones will also be answered.

      1. INMAT

      2. RIVER

      3. PRINDRAG

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        The problem pages for those three don't have links to the editorials. When you put so much effort to writing these editorials, it's a pity if people can't find them!

        I can't find an editorial for SAFPAR, is it still work in progress?

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          Rev. 2   Vote: I like it +19 Vote: I do not like it

          The extent to which editorials on CodeChef are delayed is ridiculous.

          1. dp[i] = number of safe partitions given the first i elements.

          2. Consider the restriction min(S)<=|S|. Let b1(l) = the minimum r such that the inequality holds. It's obvious that all r>=b1(l) also work. b1(l) is monotonic and can be computed with two pointers. b2(r) can be found in a similar way and all subarrays such that l<=b2(r) work. For the rest of the explanation, I will ignore this restriction, but it can be included easily.

          3. Precompute next > elements and previous >= elements to find each element's "dominating range". Let [a, b] be the "dominating range" of element i. All subarrays [l, r] such that a<=l<=i and i<=r<=b will have a maximum of element i.

          4. There are 2 ways to process the dp normally. You could iterate through a<=l<=i and add all of dp[l-1] to dp[i], dp[i+1], ..., dp[b]. Using prefix sums, this will take O(i-a) per element. You could also iterate through i<=r<=b and add dp[a-1]+dp[a]+...+dp[i] to dp[r]. Similarly, this will take O(b-i) per element. Choosing any of them seems to result in an O(n^2) algorithm.

          5. If you choose the one with O(min(i-a, b-i)) independently for each element, then the total time complexity will be O(nlogn). See http://codeforces.com/blog/entry/56345.

          https://www.codechef.com/viewsolution/19445478 (I know, the indexing is cancerous)

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thank you!

            Can you explain your RIVER code? Is it a top-tree?

            • »
              »
              »
              »
              »
              »
              »
              4 weeks ago, # ^ |
                Vote: I like it +16 Vote: I do not like it

              Yes, it is just a top-tree with a dp for finding the maximum matching.

              • »
                »
                »
                »
                »
                »
                »
                »
                4 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                "just a top-tree with a dp"

                I spent several hours trying to make this approach work and failed. After the contest ended I saw your code and thought it seems familiar but it's way too short!

                Kudos, and thanks for the answers.