Indian Institute of Technology, Indore is back with its online programming contest ‘Divide By Zero 2014’ on the Codechef platform.
Details : Date : 1st February 2014 Time : 2130 to 0000 IST Official Time Announcement Sponsored by : IBM Programming Partner : Codechef Prizes : Worth Rs 20,000.
This contest is open to all.
However all prizes are for Indian students only.
It will be an ACM-ICPC style contest with all problems visible from the start and no hacks.
In order to participate, first register at Fluxus website.
Then register on Codechef.
After this, login during the contest and view and submit problems on the following link.
(The page is not currently up, but will be up before the contest begins. In case there is any change in the link to the contest page, it will be announced here.)
Good Luck! Hope to see you participating!
Will you be publishing an editorial?
Doesn't seem that way. But, you can find my solution of Subtrees here; Inversions can be solved in O(N2) if you sort the queries by the right border, process them in that order, add elements up to the right border of the next query, for each element remember X[i] — the number of elements A[j > i] < A[i] among the elements added so far (when adding an element, iterate over all preceding elements and increment X[i] if those 2 elements form an inversion), and you can get the answer as the sum of X[L..R].
The first problem was easy, the second was just about several corner cases (N = 2, at least two zero elements etc.) and always applying an operation on the two largest numbers, because that makes them as large as possible.
I think Great Game can be solved using LCA-style sparse table (LCA preprocessing), possibly plus HLD. I'm not sure, though, since I didn't really try to solve it.
Can you please explain this — 'sort the queries by the right border...'?
A query is a pair [L, R], plus its number (you need to print queries in that order). You can sort pairs by one coordinate first, by the other in case of a tie. The coordinate you sort by in this case R, the right border of the interval it's asking about.
The editorial will be published in the next 2-3 days.
Extremely short descriptions (just ideas):
Ciphers — Trivial
Perfect Array — Ad Hoc, Careful Case Analysis
Subtrees — Tree DP
Inversions — Intended Solution: Chunk based sort of intervals (See footnote) + BIT
Great Game — Heavy Light Decomposition + Segment Trees.
Note 1: To understand the interval sorting trick, you can refer to http://discuss.codechef.com/questions/32696/gerald3-editorial or http://mirror.codeforces.com/problemset/problem/86/D
Note 2: Nice N^2 (as explained by Xellos) solution also exists. We did not anticipate this.
Note 3: Subtrees Tree DP: Root the tree at any vertex. DP[vt] = number of non-empty subtrees having their least depth node as vt which contain all selected vertices in subtree rooted at vt.