Apptica's blog

By Apptica, history, 8 years ago, In English

Programming Club of IIITDM Jabalpur is hosting a team programming contest as warmup for ICPC 2017. It contains 6 problems of varying difficulty. Contest is scheduled on 25-September-2016 at 9:30 PM (+5:30).

Link to Contest : https://www.hackerearth.com/codering/

Hope you enjoy Coding ! See you all at the arena !

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

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

Yo!! Ready to take challenge!!

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone explain how to solve this problem?

Only gchebanov and Vax were able to solve during the contest.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I solved it using bitmask dp. Let dp[mask][i] be the number of topological sorts in a graph created using vertexes from mask, which starts from vertex i. You can easily calculate all states in O(2^n*n^2). Now we can find the answer, assume that we are looking for the first vertex in the answer. Let's start with mask = 2^n-1, then our answer starts from minimal vertex i for which dp[mask][1]+dp[mask][2]+...+dp[mask][i] >= k (we want to have k'th lexicographically topological sort, so we can't start with lower vertex, because there ale less than k topol. sorts starting with vertex lower than i). Then it's easy to observe that next vertex we are searching for is first vertex in (k-dp[mask][1]-dp[mask][2]-...-dp[mask][i-1])'th topol. sort in graph: mask xor 2^i. So we push i to answer, subtract dp[mask][1]+...+dp[mask][i-1] from k, and do the same, until you get all n vertexes. Remember that you shouldn't consider vertexes which are already in our result.

  • »
    »
    8 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Let us have a function go(mask), that tells you all the number of valid topological sortings that can be made of the numbers(bits) that are not set in mask. This can be easily found by DP and some simple transitions(let me know in comments if you need help on this).

    Now that we have our function go, we can easily formulate the answer as follows:

    We start from the first index and start checking from number 1, if it can be put into this position or not. First let us do this only for the first index. How do we check which number comes into position at index 1? You can understand by this pseudocode(it is hard to explain, again let me know in comments if you don't understand :P).

    runningSum = 0
    mask = 0
    for i = 1 to N:
        temp = go(mask|(1<<(i-1)))
        runningSum += temp
        if runningSum >= K:
            index_at_this_position = i
            runningSum -= temp
            break
    

    Now after this step, we continue our search for the 2nd index and so on. Also remember that for the second index, we update our mask to mask|1<<(index_at_this_position-1) which is used in lines 2 and 4 in the above pseudo code.

    My Code for reference.

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

How to solve this problem ?

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

    Let us first limit this problem for a linear array in which you have to perform two such operations. So we can use segment tree for that. Rememeber that for each node of segment tree you should be able to predict what is the nature of the sequence in the range L to R. By nature i mean that whether the sequence from L to R in each node ends with an increasing slope or decreasing slope i.e 3 4 or 4 3 . Now think how this information can be used to combine the solution. After you solve this problem for a linear array you can simply think of HLD decomposition and then using the same concept there to. So query time becomes log(N)2 . Extra logN factor is due to the HLD concept.

    It will be very difficult to understand this unless you know the HLD concept. Comment for more help