architkarandikar's blog

IIT Indore invites you to "Divide By Zero 2014" on Codechef
By architkarandikar, 11 years ago, In English

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!

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

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

Will you be publishing an editorial?

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

    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.

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

      Can you please explain this — 'sort the queries by the right border...'?

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

        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.

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

    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://codeforces.me/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.

    → Reply