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:
- Problem Setter: chemthan (Trung Nguyen)
- Tester: kingofnumbers (Hasan Jaddouh)
- Editorialist: likecs (Bhuvnesh Jain)
- Admin: kingofnumbers (Hasan Jaddouh)
- Statement Verifier: Xellos (Jakub Safin)
- Russian Translator: CherryTree (Sergey Kulik)
- Mandarin Translator: huzecong (Hu Zecong)
- Vietnamese Translator: VNOI Team
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 [email protected])
Good Luck! Hope to see you participating!!
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.
Update : Contest has started. Best of luck :)
Was third question about binary search + merge sort tree ?
I used treap with (keys, values) as (prefix sum, minimal position).
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.
Looks like Codechef is down.
Was anyone getting runtime error on 1st question, on using c++ map?
n=0 case
oh okay. -_-
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 :)
How to solve MINSUBAR anf ROTPTS ?
I used merge sort tree + binary search in MINSUBAR. I got WA.
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.
Editorial links are broken?
Below are the editorial links:
P1
P2
P3
P4
P5
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