chemthan's blog

Invitation to CodeChef December Cook-Off 2017!
By chemthan, history, 7 years ago, In English

Hello CodeForces Community!

To keep the coding clock ticking, we have some interesting challenges in the upcoming December Cook-Off. Joining me on the problem setting panel are:

All statements are short and clear. 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: 24th December 2017 (2130 hrs) to 25th December 2017 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

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

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://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
  • +51
  • Vote: I do not like it

Comments Comments (15)
| Write comment?
»
7 years ago, # |
  Vote: I like it +23 Vote: I do not like it

One hour to start!

Announcement: The time limit multipliers for languages which are usually greater than 2, have been made equal to 2 for this contest. Note that this change is temporary and for this contest only. For example, Python which usually has a multiplier of 5, will have 2 for this contest.

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

Update : Contest has started. Best of luck :)

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

Was third question about binary search + merge sort tree ?

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

    I used treap with (keys, values) as (prefix sum, minimal position).

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

is the isomorphic one using persistent seg tree and hashing over it for counts using some special number for each increase in count of power of a number??.
Or does deterministic approach exist??
UPD: Editorials are up.

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

Was anyone getting runtime error on 1st question, on using c++ map?

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

Feedback:

FBMT. trivial.

BTAR. Nice one, but I didn't finish my proof and just coded the greedy (greed is good).

MINSUBAR. This one looks very standard, it was even probably asked in coding interviews.

ROTPTS. Is the first time that I notice that .

ISOARRAY. Cool :)

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

    How to solve MINSUBAR anf ROTPTS ?

    I used merge sort tree + binary search in MINSUBAR. I got WA.

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

      MINSUBAR: let f[i]=a[1]+...+a[i]. For each i, find the rightmost j such that f[i]-f[j]>=d, so f[j]<=f[i]-d. We can keep the indices of the cummulative sums in a map.

      ROTPTS: Rotating a point in a range [l,r] can be done first by rotating the point and then adding some vectors. The operations can be performed with a segment tree.

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

Editorial links are broken?

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

I did MINSUBAR using TreeSet, coordinate compression for prefixes and segment tree. As a token of appreciation for over complexifying the solution, I was rewarded with loads of TLEs. :D

→ Reply