ma5termind's blog

CodeChef April LunchTime 2016
By ma5termind, 9 years ago, In English

Hello CodeForces Community,

I have set the problems for the April LunchTime and would like to invite you all for the same. The contest takes place at https://www.codechef.com/LTIME35. I am sure this will serve as a good practice for all those aiming for IOI 2016, we have adhered to the syllabus IOI and made the problems accordingly.

Time: 30th April 2016 (1930 hrs) to 30th April 2016 (2230 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone

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

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.

  • Problem Setter & Editorialist: ma5termind (Sunny Aggarwal)

  • Problem Tester & Russian Translator: CherryTree (Sergey Kulik)

  • Contest Admin: PraveenDhinwa (Praveen Dhinwa) and pushkarmishra (Pushkar Mishra)

  • Mandarin Translator: huzecong (Hu Zecong)

  • Vietnamese Translator: VNOI Team

Prizes for April LunchTime 2016:

  • Top 10 school students each from 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]).

Rest, it promises to deliver on an interesting set of algorithmic problems with something for all. Please feel free to give your feedback on the problem set.

Good Luck! Hope to see you participating!!

UPDATE 1 Contest will be started in less than 40 minutes.

UPDATE 2 Contest will be started in less than 10 minutes. Good luck and have fun.

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

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

Is it possible to it 30 mins earlier, cause it's last 30 min overlaps with GCJ R1B.

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

Problem is Not Available after 5 Minutes of Contest Started ..

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

What is problem?
**Please click here to reload. If problem persists, please report to [email protected]**

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

I cann't access to problems are everyone facing such problem ?

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

https://www.codechef.com/problems/KSUM from this problem i learnt something interesting.. if we need to find all subarrays then what we can do is initially take the range [1,n] which will be maximum range now the next ranges can be generated as follows.. if you are on [l,r] then you need to take [l+1,r] and [l,r-1] (assume these as two childs of evry node and try making a tree type structure.. ofcourse the ranges will repeat but you will observe tht all the possible subarrays ranges are generated.. now for this problem.. we can take a priority_queue and push initial sum[1..n] and range [1,n] as this will be the maximum of the list.. take a data structure which keeps track of all already visited ranges and push only those ranges in queue which are not visited yet.. for calcluating sum in the range [l,r] you need to store the prefix sum in an array.. as k<=100000 complexity is nlogn and this will pass... sample implemention:- https://ideone.com/tPfXgC

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

I didn't do tasks, but I read them. I would like to disscuss about the second problem KSums. I saw many solutions with multiset, but I invent something much easier, and I didn't see any such code.

My solution :

We can binary search sum of k-th subarray. After that we can calucalte by two pointers how many arrays satisfied current value in search and change borders. Interesting thing in this solution that we can find k-th sum for much bigger values for k.

Whether you see something wrong in my approache ?

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

    I used the same approach.

    This solution is also used in a CF solution where you need to find the sum of the kth largest subarray, only difference is that negative numbers are allowed in that problem

    Link: http://codeforces.me/problemset/problem/191/E

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

      Cool !

      New task is really harder. Obivious we can apply binary search, but checking amount of subarrays is really hard, cetainly we need to use some data structure, but for me as blue coder it looks as unsolvable :P

      → Reply