Invitation to CodeChef Starters 215 (Rated till 6-Stars)

#	User	Rating
1	jiangly	3810
2	Benq	3676
3	Kevin114514	3655
4	maroonrk	3463
5	strapple	3390
6	Um_nik	3387
7	tourist	3384
8	heuristica	3322
9	turmax	3319
10	jiangbowen	3291

#	User	Contrib.
1	Qingyu	155
2	nik_exists	150
2	maspy	150
4	Um_nik	144
5	AmShZ	139
5	Errichto	139
7	adamant	137
8	maroonrk	134
9	BledDest	132
10	qwexd	129

We invite you to participate in CodeChef’s Starters 215 aka Shaastra Programming Contest conducted by Shaastra IIT Madras and sponsored by Arcesium, this Wednesday, 3rd December, rated for 6 stars (i.e. for users with rating < 2500).

Time: 8:00 PM — 10:00 PM IST

Joining us on the problem setting panel are:

Contest Admin and Statement Verifier: Shreyan Dominater069 Ray
Tester: Nishank IceKnight1093 Suresh
Setter: Matul fstlrnr, Aaryan AaryanSriram Sriram, Pranav prnv10, Asher BlazinFiree
Text Editorialist: Nishank IceKnight1093 Suresh

Register here and also please fill out this form to be eligible for the offline finals where prizes worth 200K INR await!

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here. Hope to see you participating.

Good Luck!

struct Info { ll Atot = -inf; // sum of A within the node ll Btot = -inf; // sum of B ll ans = -inf; // answer for the node. ll Apmax = -inf; // A array max prefix sum ll Asmax = -inf; // A array max suffix sum ll Bpmax = -inf; // B array max prefix sum ll Bsmax = -inf; // B array max suffix sum ll ansAR = -inf; // answer, such that A subarray touch Right end ll ansAL = -inf; // answer, such that A subarray touch Left end ll ansBR = -inf; // answer, such that B subarray touch Right end ll ansBL = -inf; // answer, such that B subarray touch Left end ll ansALBL = -inf; // answer such that A array touch Left, B touches Left ll ansALBR = -inf; // answer such that A array touch Left, B touches Right ll ansARBL = -inf; // answer such that A array touch Right, B touches Left ll ansARBR = -inf; // answer such that A array touch Right, B touches Right ll Asubmax = -inf; // maximal subarray sum of A array ll Bsubmax = -inf; // maximal subarray sum of B array };

Info merge(Info l , Info r) { Info newnode; newnode.Atot = l.Atot + r.Atot; newnode.Btot = l.Btot + r.Btot; newnode.Apmax = max(l.Apmax , l.Atot + r.Apmax); newnode.Bpmax = max(l.Bpmax , l.Btot + r.Bpmax); newnode.Asmax = max(r.Asmax , r.Atot + l.Asmax); newnode.Bsmax = max(r.Bsmax , r.Btot + l.Bsmax); newnode.Asubmax = max(newnode.Asubmax , l.Asubmax); newnode.Asubmax = max(newnode.Asubmax , r.Asubmax); newnode.Asubmax = max(newnode.Asubmax , l.Asmax + r.Apmax); newnode.Bsubmax = max(newnode.Bsubmax , l.Bsubmax); newnode.Bsubmax = max(newnode.Bsubmax , r.Bsubmax); newnode.Bsubmax = max(newnode.Bsubmax , l.Bsmax + r.Bpmax); newnode.ansAR = max(newnode.ansAR , r.ansAR); newnode.ansAR = max(newnode.ansAR , r.ansARBL + l.Bsmax); newnode.ansAR = max(newnode.ansAR , l.ansAR + r.Atot); newnode.ansAR = max(newnode.ansAR , r.Bsubmax + r.Atot + l.Asmax); newnode.ansAR = max(newnode.ansAR , l.ansARBR + r.Atot + r.Bpmax); newnode.ansAL = max(newnode.ansAL , l.ansAL); newnode.ansAL = max(newnode.ansAL , l.ansALBR + r.Bpmax); newnode.ansAL = max(newnode.ansAL , r.ansAL + l.Atot); newnode.ansAL = max(newnode.ansAL , l.Bsubmax + l.Atot + r.Apmax); newnode.ansAL = max(newnode.ansAL , r.ansALBL + l.Atot + l.Bsmax); newnode.ansBR = max(newnode.ansBR , r.ansBR); newnode.ansBR = max(newnode.ansBR , r.ansALBR + l.Asmax); newnode.ansBR = max(newnode.ansBR , l.ansBR + r.Btot); newnode.ansBR = max(newnode.ansBR , r.Asubmax + r.Btot + l.Bsmax); newnode.ansBR = max(newnode.ansBR , l.ansARBR + r.Btot + r.Apmax); newnode.ansBL = max(newnode.ansBL , l.ansBL); newnode.ansBL = max(newnode.ansBL , l.ansARBL + r.Apmax); newnode.ansBL = max(newnode.ansBL , r.ansBL + l.Btot); newnode.ansBL = max(newnode.ansBL , l.Asubmax + l.Btot + r.Bpmax); newnode.ansBL = max(newnode.ansBL , r.ansALBL + l.Btot + l.Asmax); newnode.ansALBL = max(newnode.ansALBL , l.ansALBL); newnode.ansALBL = max(newnode.ansALBL , l.Atot + r.Apmax + l.Bpmax); newnode.ansALBL = max(newnode.ansALBL , l.Btot + r.Bpmax + l.Apmax); newnode.ansALBL = max(newnode.ansALBL , l.Atot + l.Btot + r.ansALBL); newnode.ansARBR = max(newnode.ansARBR , r.ansARBR); newnode.ansARBR = max(newnode.ansARBR , r.Atot + l.Asmax + r.Bsmax); newnode.ansARBR = max(newnode.ansARBR , r.Btot + l.Bsmax + r.Asmax); newnode.ansARBR = max(newnode.ansARBR , r.Atot + r.Btot + l.ansARBR); newnode.ansALBR = max(newnode.ansALBR , l.Atot + r.Btot + l.Bsmax + r.Apmax); newnode.ansALBR = max(newnode.ansALBR , l.Atot + r.ansALBR); newnode.ansALBR = max(newnode.ansALBR , r.Btot + l.ansALBR); newnode.ansARBL = max(newnode.ansARBL , r.Atot + l.Btot + r.Bpmax + l.Asmax); newnode.ansARBL = max(newnode.ansARBL , r.Atot + l.ansARBL); newnode.ansARBL = max(newnode.ansARBL , l.Btot + r.ansARBL); newnode.ans = max(newnode.ans , l.ans); newnode.ans = max(newnode.ans , r.ans); newnode.ans = max(newnode.ans , l.ansAR + r.Apmax); newnode.ans = max(newnode.ans , r.ansAL + l.Asmax); newnode.ans = max(newnode.ans , l.ansARBR + r.ansALBL); newnode.ans = max(newnode.ans , l.ansBR + r.Bpmax); newnode.ans = max(newnode.ans , r.ansBL + l.Bsmax); newnode.ans = max(newnode.ans , l.ansARBR + r.ansALBL); return newnode; }

Comments (4)

Write comment?

prnv10

10 months ago, hide # |

Auto comment: topic has been updated by prnv10 (previous revision, new revision, compare).

→ Reply

infernal_blaze

Contest starts in 30 minutes.

SSenpai69

+20

Very beautiful leaderboard of div2 div3 div4

Ashwanth.K

← Rev. 4 →

Nice problems , I solved this Intersecting Intervals in a tedious way. :) should have spent more time to think of easier implementation.
I thought this as a harder version of standard maximal subarray sum + point updates.

I tried to maintain all these parameters and merged them correctly in segment tree, and it worked.

Merge function

Code Submission It passed in 0.5 sec :) Time complexity. (50*NlogN)

prnv10's blog