meintoo's blog

Invitation to Insomnia 2016 Qualifier (Team programming contest)
By meintoo, 8 years ago, In English

Hello everyone,

Computer Club, MNNIT Allahabad invites you to the annual programming competition of MNNIT Allahabad, India, which is an ACM-ICPC style team programming contest of 3 hours duration held during its annual technical fest Avishkar.

Details:

Contest Date : 4th September 2016
Time : 2130 to 0030 IST
Programming Partner : Codechef
Contest Link

We have tried our best to make the problem set interesting for everyone.

Prizes:

For online round, top two teams will be getting Codechef goodies.

For onsite round, prizes worth Rs. 15000/- to be won.

Top 20 global teams will be called for the onsite round to be held at MNNIT Allahabad itself.

Problem Setters: meintoo, iamscrew, pakhandi, vippu95, vikky_codder, aaijmrt, Abhedyam and mmaks.

Please follow our facebook event page for further notifications.

Good luck to everyone, and I hope to see you at the contest :)

UPD:- Contest starts in 4:30 hours. We hope to see you all. All the best!

UPD2:- The contest has ended. Congratulations to the winners.

  1. Team beet_burger- Nerevar, Vercingetorix, pavel.savchenkov

  2. Team umnik_team- Um_nik, Merkurev

  3. Team matrixiitd- tapasjain, jtnydv25, yash_15

UPD3:- You can view the ranklist here

We hope everyone enjoyed the contest. Editorials will be published soon.

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

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

How to solve Joker and Batman, and also Raymond and Network? Also, Will you guys release editorial ? Problems were very nice. Thanks for them.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +21 Vote: I do not like it

    For Raymond and Network, build the block-cut tree of the graph and then each query (X,Y) is equivalent to finding the distance between the components of X and Y in the block-cut tree which can be found with LCA :)

    Edit: It is actually bridge tree, not block-cut tree, sorry for the misleading comment.

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

      I used Bridge tree for this problem.

      Make Bridge tree of the input graph. Now there are two cases. If both the vertices are in same bridge component , then answer is 0. else Problem reduces to finding distance between two nodes( here bridge component ) which can be solved in O(1) using LCA.

      My AC Code.

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

        It's the same thing...

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

          Yes! True.

          All the problems where Bridge Tree can be used can also be solved by Block-cut tree formed by "Biconnected Components" but many a times the bridge tree is far more intuitive than the block-cut tree.

          Cheers! :)

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

            I am sorry, I have always used block-cut tree to mean bridge tree thinking they are the same. Now I see... Thank you! :)

            → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +18 Vote: I do not like it

    For Joker and Batman, keep an array COLOR[X][P] which denotes the minimum level of color P in X's subtree. You can compute this using a DFS (note that a node X has children 2*X and 2*X+1).

    Then you need to sort the minimum levels for each color for all nodes. To answer a query for a node X and color K, find max of levels in first K entries of COLOR[X].

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

    For Joker and Batman:

    You can store log(N) "bitmasks" for each distance in each node, which tells you colors subtree in depth i (i<=log(N))

    For each query, you will just iterate the depths (log(N)) and find out in which you are "over"

    PS: This can be build by some recursion (or clever iteration) in Nlog(N)

    PS.S: Denote "bitmask" as integer(or short)

    Good Luck & Have nice day

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

      Could you provide a link to your solution? Thanks a ton.

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

        Hello,

        I guess it would be somewhat like this (anyway it was written by team mate — so no credits for me)

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

          Woah. Thanks a lot. Actually, this was the original thing I was trying to implement. But got stuck. Your code helped me a lot. Thanks again.

          → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 4   Vote: I like it +10 Vote: I do not like it

    PS: Sorry when I started writing there weren't other comments connected with this problem.

    For Joker and Batman the most important think to notice is that the number of the colors is up to 10 so you can store for every node on what level from it is located a node of each of the 10th colors. You can precompute that with a simple iteration over the tree from the leaves to the root. After that for each query you need just to sort all distances to the colors and find the k-th smallest.

    → Reply
»
8 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Can you move the problems to practice please?

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

Please, can someone explain how to solve JARVIS and LCP? I tried to use SQRT decomposition but I didn't succeed :(

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

    Build the suffix automata for all strings from input (s1 + '#' + s2 + '@' + s3 + ... + sn). Than, by iterating through all prefixes of every string and walking in automata, you can calculate number of occurences of every prefix(you should calculate number of occurences for every state in automata, it can be easily done with some dp). To find the answer for queries, just find a LCP position by binary search and hashes, than print number of occurences of founded prefix, which you have already calculated.

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

      Thank you, that is another reason to learn suffix automata but I understood the idea (I know what suffix automata is supposed to look like although I can't code it) :)

      → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +17 Vote: I do not like it

    Good day to you!

    Mine solution has big part similar to Alladin, anyway:

    Step 1) Concatenate all strings (knowing position and length of each string) (I used '!' between each string)

    Step 2) Make Suffix Array

    Step 3) From SA, make LCP Array

    Step 4) Find out, where (in SA) each of the strings begin [simple iteration, using SA[i] as index]

    Step 5) Build RMQ over LCP

    Til here, the cost is (Nlog(N))

    Now for each query:

    A) Find positions of both strings in SA {from step 4} — O(1)

    B) Find minimum LCP of those strings. This can be simply done, by finding minimum LCP on range <first_string,second_string> in LCP array. You can do this in O(1) with RMQ {step 5} [first_string is lexicographically lower — if not, just swap]

    C) As you have the LCP of the two strings, find maximum range (which includes first_string) on LCP, such that the minimum element is equal to the LCP. This can be done by two Binary Searches, on both (left/right) borders — you will find the minimum from RMQ. The cost is log(N).

    So it is log(N) per query and Nlog(N) for build.

    Changing RMQ/ST, we can do O(N)/Nlog^2(N)

    Good luck!

    Ask if anything unclear! :)

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

      Good day to you too! That's a great idea, thank you very much :)

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it +5 Vote: I do not like it

      How do you do the point number C in your explanation? I do it as follows:

      We have to find the leftmost suffix in the sorted order of suffixes which has a prefix equal to the LCP of our 2 query strings(this is what we have to do in point C right?).

      So I binary search for it. To check if the LCP of our 2 query strings is a prefix of the current middle in binary search, I again binary search on the maximum length of these 2 strings that match(this is done in logN with hashes).

      And I do a similar thing for the rightmost suffix.

      But I am getting TLE with the above approach. I believe my approach is log2 N per query. Is there something that I am doing wrong?

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

        God day to you!

        You are right, that is what we are doing.

        Anyway the solution is "only" log N . I'm not sure, whether I understood you correctly, but you do binary search on left, and for EACH such search you search for right (this would lead to the complexity).

        If no -I prolly understand wrongly... anyway one can BS for them one-after another (they don't affect each other)!

        And I'm also not sure about "hashes"? :O How you involed them (etc.) <just wondering about whether than migh/might no be the problem>

        Good Luck!

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

          Good day to you sir!

          Thank you for the help, I realised that I need only 1 Binary Search.

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

        Let id_up = position of the suffix which has ith string as prefix.

        Let id_down = position of the suffix which has jth string as prefix.

        Now , Initially the range of suffixes which has prefix = LCP(i,j) is [ id_up ,id_down].

        Now in order to expand this interval both sides , we will do 2 binary searches .

        1st Binary search: Find a suffix k < i in the suffix array till which LCP(k,i) >= LCP(i,j).

        2nd Binary search: Find a suffix w > j in the suffix array till which LCP(w,j) >= LCP(i,j).

        You don't need to do another binary search to compute LCP , since we can find longest common prefix of two Suffixes in O(1) constructing RMQ sparse table on LCP array.

        See my Code for better understanding.

        If anything is not clear , feel free to ask.

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

          Shit, I'm so dumb. Don't know why I did another Binary Search. Thanks a lot!

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

Nice problem set. When do you plan in releasing the editorials?

→ Reply