TLE's blog

Invitation to CodeChef November Long Challenge 2018 sponsored by ShareChat!
By TLE, history, 6 years ago, In English

Hello CodeForces Community!

It’s time to gear up for CodeChef’s November Long Challenge sponsored by ShareChat! 10 days of coding fun plus opportunities to work at ShareChat! More details can be found on the contest page.

Joining me on the problem setting panel are:

  • Admin: mgch (Misha Chorniy)
  • Problem Tester: TLE (Zhong Ziqian)
  • Editorialist: taran_1407 (Taranpreet Singh)
  • Problem Setters: sunset (Xiuhan Wang), bciobanu (Bogdan Ciobanu), altruist (Denis Anishchenko), TLE (Zhong Ziqian), teja349 (Teja Vardhan Reddy), adamant (Alexander Kulkov), danya.smelskiy (Danya Smelskiy), Shivam Gupta, hm2 (Himanshu Mishra), sshhhh (Sumegh Roychowdhury)
  • Statement Verifier: Xellos (Jakub Safin)
  • Russian Translator: Mediocrity (Fedor Korobeinikov)
  • Mandarin Translator: huzecong (Hu Zecong)
  • Vietnamese Translator: VNOI Team
  • Hindi Translator: Akash Srivastava
  • Bengali Translator:solaimanope (Mohammad Solaiman)

I enjoy this set of problems personally and hope you will enjoy solving them too. You can give your feedback on the problem set in the comments below, after the contest.

Contest Details:

Time: 2nd November 2018 (1500 hrs) to 12th November (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Contest link: www.codechef.com/NOV18

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Prizes: Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. First to solve each problem except challenge — 100 laddus. Know more here.
(For those who have not yet got their previous winning, please send an email to winners@codechef.com)

Good Luck and Have Fun! Hope to see you participating!

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

Comments Comments (34)
| Write comment?
»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

How to solve Binary Strings ? I have some ideas with trie ,but it was difficult to implement .

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

    Basically, if max(|AL|, |AL + 1|..|AR|) > |X|, you will try to choose among ones with max lengths. Furthermore, you will choose from the ones that maximize the prefix before X. If you insert all strings of that same length into a trie, this is just the rightmost node of that depth in that trie. To deal with that range restriction, you can use divide and conquer / scanning line and segment tree etc. The rest is just walking on the trie. If max(|AL|, |AL + 1|..|AR|) ≤ |X|, just walk on several tries.

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

      i don't understand clearly ,how i can use segment tree TLE ?

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

        UPD: Sorry for misleading but my old solution might be way too complicated.

        For a query l, r, just consider the maximum of pair(length,string) (i.e. sort all same-lengthed strings and use sorted index). After finding that maximum, locate the correspondent trie node and you're done.

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

    I also implemented it with tries. Just insert all elements into the trie by making it of equal length(pad it with 0's) and compress it. Then for each query traverse the trie.

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

      What do you mean by compress it? My approach was to build multiple tries in each node, and it passed, but this sounds interesting as well. Do you mean like merging a node with its child if it have only 1 child?

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

        Yeah. Exactly just merge node and child if it is a single child. Initially add Max length amount of 0's and for each 0 store it's address in a map and access it for adding extra 0's(padding)

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

          Can you explain your query part ?

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

            Ok. For the query if the length of the string is greater than the length of strings on the trie (after padding all are of equal length) then take the substring of it and query it. Else if it is lesser then have a count of 0's that must be padded. Don't add the 0's to the query string as it may tle. Traverse the trie for the padding then for the string. Since the trie has been compressed it will be around 1000 ops in worst case. However it will be even smaller. For seeing which child lies between l and r at each node have a vector which stores all elements that pass through it. Since you will be adding it in order it will be sorted and you can binary search for it.

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

              Just wonderin', can you prove the 1000 part? I have recently faced a problem with the same thing, 1 million characters total in all strings with 1e5 of them. However, the O(N ^ 2) solution passed, with N being the number of nodes in the compressed trie. If you can prove it then that will solve my question for the other one: Is the test — case weak or is O(N ^ 2) supposed to pass

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

                Yeah ok. The worst case for the query will be having as much depth as possible. We do compression to reduce this. So the worst case will occur when the strings are 1,10,100,1000... . However since the total length of input is less than 1e6 the max such strings you will get is around 1000 (Len*(Len+1)/2<=1e6. So Len is around 1000).

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

How to solve prime trees?

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it

How to solve equations? I know the formulas, but it was difficult for me to use FFT to get better complexity that O(n^2). For example how to calculate those for j = 1, 2, ..., n? Those are the values of P' at a1, a2, ..., an where P(t) = (t - a1)(t - a2), , , (t - an). I can calculate P' in O(nlog2n) using FFT and divide and conquer, but how to evaluate at those points?

So a follow up general question: can we having a polynomial of degree n and n points a1, a2, ..., an. Evaluate all P(ai) in parallel faster than O(n2)?

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

    Yes, you can evaluate n points in using FFT. A simple Google search for "multi point evaluation" should give you descriptions. However my implementation was too slow for the time limit.

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

      For reference, my implementation (I can post it later after work) takes ~2 seconds to evaluate a polynomial of degree n = 60'000 at n points (using modular arithmatic). Does anybody have a faster one?

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

        I had the same problem. Precomputing all powers of root for ntt worked for me.

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

        That's a little out of my expectation. My solution takes about 1.2 seconds in total(using multi-point evaluation twice) so I set the time limit to 3 seconds. Maybe your template for multi-point evaluation is too slow.

        My code

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

How to solve Chef and Recipes. I tried Gaussian elimination which passed the small 2 but I could not eliminate excess equations properly leading to TLE or WA.

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

    In short: map 2n to 264 randomly.

    Assign a random value (say in [0, 264)) to each base soup and a composed soup's value is the bitwise-xor of the sub-soups' values. For each query use gauss elimination to find if those values are linear independent.

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

      Ok thanks.

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

      I tried doing 60 bits first, but that only passed a couple of files in total, after about half an hour of not finding any other solution, I did 500 bits and it passed

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

      @TLE — Can you explain why this works? When you assign random values to base soups, the xor could collide with an already assigned value right?

      The solution seems probabilistic. Since we need at most 30 linearly independent bit vectors per query, it seems the probability that values won't collide is 1 - (30 / 264), which means the overall probability of getting a collision across queries is quite low.

      Is there a deterministic solution for the problem under the given constraints?

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

    Gaussian elimination got accepted (0.2 seconds). However I had to write my own bitset class, since the size of the bitset has to be known at compile time (20'000) otherwise. By writing your own you only need the size to be as big as the number of different base soups. Also you can speed up searching for a pivot element (the first set bit in a bitset) by a factor of 64 pretty easily. My solution

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

is it bug or not ? other guys have rating that they haved ,but mine is changed .

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

    mgch please response on this.

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

    Probably not a bug. Mine has changed, and a lot of others' has changed too.

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

      i don't know,but only in mine page i see that codechef rating is not similar to codechef rating on graph rating.

      UPD:it is fixed now .

      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Codechef's contest is too hard for me.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can somebody explain MAGICHF2 with a proper mathematical proof?

→ Reply