avi224's blog

By avi224, 9 days ago, In English,

Hi all,

Programming club, Indian Institute of Technology, Mandi is hosting Dementia '18 as part of our cultural-cum-technical fest Exodia. The contest will take place on 12th April,2018 at 20:00 IST(14:30 UTC). The contest features 6 delectable problems of varying difficulty and you'll get 2.5 hours for solving them. The problem setters and testers for the contest are me(avi224) and hitesh_r. The contest is rated for division II on codechef(below 1800 rating). However, division I can participate out of competition.

There are prizes worth Rs 5K for the top participants(from both divisions) from India.

Link to the contest

Combined ranklist

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

»
9 days ago, # |
  Vote: I like it +27 Vote: I do not like it

What if someone gets into division 1 after this contest? Will he participate in long as division 1? He might already have solved problems in division 2.

»
8 days ago, # |
  Vote: I like it +14 Vote: I do not like it

Fine problems :)

Can someone elaborate solution for the hardest task ? I tried binary search + several wrong greedy strategies for picking optimal plants. I believe I can solve it on a little harder way (always is optimal to water smallest plant — it can be simulated somehow). But I believe there is some easier solution.

P.S. Can you share standings for unofficial participants ?

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks :)

    So the greedy approach would be to choose the smallest ai plants on i'th day and water them. Then you can apply binary search over days and find the ans.

    There is one other approach using segment tree. The idea is to first sort the heights of tree and then keep it sorted after every day. For eg 1 1 1 2 3 3 3 3 3 5 5 5 5 are the heights on some day and you have to water 6 plants, then you go to 6th index and find value ‘h’ and find first and last occurrence of ‘h’. Then increment all the numbers before the first occurrence and some of the numbers with height same as ‘h’, as needed. So the heights will become 2 2 2 3 3 3 3 4 4 5 5 5 5. So the array is still sorted.

    Editorial will be out soon which would give more clear idea about the binary search solution.

    Combined ranklist will be out soon as well.

    • »
      »
      »
      6 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I tried to find the lower bound and upper bound of value of h using binary search and then tried to update their heights by increasing them by 1 so that I need not sort the array d times. The complexity will be O(max(nlogn,nd)).I am getting TLE. What is the intended complexity?

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

      Still waiting for combined ranklist

      • »
        »
        »
        »
        5 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This is the reply we got from CodeChef:

        "The combined ranklist cannot be shown publicly now. That will take some time.

        For you privately, yes, sorry for the delay. I'll remind the concerned person again to get the combined ranklist. It takes some work because this is the first time we're doing it and some DB scipt needs to be written."

      • »
        »
        »
        »
        3 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I've put the link to the combined ranklist in the blog. Congrats!

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

    This problem seems somewhat similar to the "Halum and Candies " link: (http://codeforces.com/gym/101353/attachments) the editorial page describes the solution http://codeforces.com/blog/entry/51642

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

when the problem is add in practice.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Problems are automatically sent to practice now after the contest. You can submit from the problem page itself :)

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the ratings be updated,before ending long or after it??

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the intended solution to the problem where each query is of the form [Left, Right, x]

And the answer to the query is sum( ceil(A[i]/x) ).

I'm seeing many solutions which solved the problem by just going from Left to Right and summing over ceil(A[i]/x). O(NQ)

Is this the intended solution ?

  • »
    »
    5 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No, it was using binary search and/or merge sort tree. O(NQ) passed as we didn't expect 5*10^8 operations to pass in 1 s. The observation is that we have to count the frequency of O(sqrt(x)) numbers only for each query. I'll put a detailed editorial soon.

  • »
    »
    5 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can also be done using MO's algorithm + Binary Indexed Tree