Vasiljko's blog

By Vasiljko, history, 7 years ago, In English

I'm preparing for Team Selection Competition and these are some problems that I want to know how to solve. Problems are from previous competitions

Problem 1
Problem 2
Problem 3
Problem 4
  • Vote: I like it
  • +17
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  1. Assign a unique random number to each element. Then, "number of subarrays such that every element in subarray appears even times" = "number of subarrays with XOR 0".
  2. Compute the hash of each string, and the hash of its reverse.
  3. Does biggestDigit mean most significant digit or the one with the highest value?
  4. First of all, look up "Chebyshev distance". What does the set of all points at a distance  ≥ D look like? Once you've figured that out, try to answer queries of this type: "Is there an element smaller than Ax, y at a distance  ≥ D"?
  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    1. Maybe I misunderstood, but I don't think it's going to work. For example: 5 6 7 and randomized values are 2 3 1 , than xor is 0
    2. I'm stupid, wanted to do that way and thought that complexity is so big... Btw how to solve it with trie
    3. Updated the statement
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it -6 Vote: I do not like it
      1. But what if the randomized values are, well, random? There is a small chance for this approach to fail. You could however run the same algorithm 5 or 6 times, and it should work normally.
      2. The complexity is . I'm not sure.
      3. I have no idea.
      • »
        »
        »
        »
        7 years ago, # ^ |
        Rev. 2   Vote: I like it +8 Vote: I do not like it
        1. No matter how small, chances are there and I want the solution without randomization
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          1. If you use 64bit random integers for each value, twice, probability of collision on 105 numbers is so small that you can consider it deterministic for contest environment :)
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
            Rev. 4   Vote: I like it +5 Vote: I do not like it

            Actually no! You can't consider it deterministic even in contest (here). Because such solution can easily be hacked using Gaussian Elimination. If you get experienced codes in your room they will hack you in no time :)

            Probability of collision in Polynomial Hash is too low, something like , but this xor hash has very high probability of collision. Actually the more numbers are there, more probability of collision you get.

            To be precise, if n > 64 then then it is always possible to generate a test case that breaks that solution, let alone n ≤ 105 :)

            You can test yourself, run this code with the randomly generated array, it will find some cases where distinct numbers xor to 0 —

            Hack XOR Hash with Gaussian Elimination
            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              I think it's unfair to consider that the hacker has access to the randomly generated array — what if we generate the number with some high precision seed?

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

                In CF you can see others' code, thus see the seed right? Use generator script to hack. :\
                It is still hackable even if you seed with time. You can assume that CF will run your your hack between [T, T+10] seconds. You can just hack all of those seeds and create a test by concatenating them :)

                Anyway, the point here is this xor hash can't be called deterministic. It is almost always hackable.

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

                  You can seed with micro/nano seconds which will cause some troubles to hackers tho :)

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

        Even if you run it few times, what if you get different results? Which one are you going to take?

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

          If you get even a single different result, then you skip that value (you can do something like a map<pair<long long, long long>, int> and XOR every possible prefix)

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

    I have no idea why this is getting downvoted. The author asked for help, not a full solution. There is no point in spoiling the full solutions.

»
7 years ago, # |
  Vote: I like it +20 Vote: I do not like it

First task can be done with hashing.

First you need to make all numbers in range [1, N]. Than you can save binary string S with length N for each prefix of array : Si = 1 if we have odd amount of numbers i in current prefix, otherwise Si = 0. Now for current prefix and binary string S we add amount of same strings in smaller prefixes. This looks as O(n2) time complexity and memory (or even worse) — but we can use hashing. We can save hash values for all prefix strings instead of whole string and this will save our memory space. Also we should notice that string for prefix x and string for prefix x + 1 are different only at one position, so we do not need to hash whole string again, just need to change hash value for that position. Total complexity O(n).

»
7 years ago, # |
Rev. 3   Vote: I like it +11 Vote: I do not like it

1. It may be hard to solve if you've never seen the idea before.

First compress the array to [1, 5*10^5], after that imagine binary array of pairness of the compressed length for every prefix. For example if the array was [1 2 2 1], pairness array would be:

   - for prefix [1] : [1 0];
   - for prefix [2] : [1 1];
   - for prefix [3] : [1 0];
   - for prefix [4] : [0 0];

Now, string [si, si + 1, ...sj] is "good" for the task iff pariness arrays for prefix[i-1] and prefix[j] are equal. Now since those two arrays may be hard to compare for every [i, j], it would be good to hash them.

With generated hashes of those "binary strings" it should be easy to solve the task. Generating those hashes should take O(N(logN+F)), where F is for Hashing.

»
7 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

Problem 2: The order of concatenation matters (for example, b and bc).

  1. For each string, compute the suffixes that are palindrome (using hashing, manacher, etc).
  2. Add the strings in a trie. And for each node, store the number of strings where this position is followed by palindrome suffix (for example in the string, abdkkmkk the nodes for positions 3, 6, 7 and 8 (1-indexing) are followed by palindrome suffixes).
  3. For each string, match and find the node of its reverse and add the answer.
    Note: this solution will calculate strings abc, and cba twice but will count abdkkmkk and dba once because of the order of concatenation. We can, however, avoid double counting if necessary.

Problem 4:

  1. Transform every point (X, Y) to (X + Y, X - Y). This changes the distance metric from Manhattan to Chebyshev (i.e. D = maxX, Δ Y) instead of D = Δ X + Δ Y).
  2. Create a segment tree for the N rows and a segment tree for the N columns, where each node store the minimum value in the rows (or columns) between [L, R]. Also a segment tree for each row and for each column where each node contain the minimum value in the range [L, R] in the corresponding row (or column).
  3. For the second query, update the corresponding row and column segment tree. Then update the segment tree for the rows and the other for the columns.
  4. For the first query, binary search on the distance D. The candidate points are in a range of rows [0, X - D] and [X + D, N] or the range of columns [0, Y - D] and [Y + D, N]. Find the minimum and check that it's less than A[X][Y].
    Note: we can add constant C to X - Y to avoid negative array indices.
  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    For second problem, can we just compute hash value of string itself and its reverse and then check all N*N combinations (this must hold if new string is palindrome hsh1+hsh2*powerOfPrimeNeededHere = invhsh2+invhsh1*powerOfPrimeNeededHere)

    I know I have asked for trie solution but just curious if hashing is going to work. By the way thank you, it will take some time to solve 4th problem