Блог пользователя TLE

Автор TLE, история, 6 лет назад, По-английски

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 [email protected])

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

  • Проголосовать: нравится
  • +121
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +27 Проголосовать: не нравится

    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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

        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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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)

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Can you explain your query part ?

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.

            • »
              »
              »
              »
              »
              »
              »
              6 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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

              • »
                »
                »
                »
                »
                »
                »
                »
                6 лет назад, # ^ |
                Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                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).

»
6 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

How to solve prime trees?

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

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)?

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

    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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +32 Проголосовать: не нравится

        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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      Ok thanks.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      @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?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Codechef's contest is too hard for me.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can somebody explain MAGICHF2 with a proper mathematical proof?