Zlobober's blog

Topcoder SRM #613
By Zlobober, 11 years ago, translation, In English

Tomorrow at 11:00 UTC -4 there will be SRM #613. Don't miss!

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

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

I almost solved 500. I realized my silly mistake too late to change it. Wait and see as I reach red by always solving just the easiest problem :D

My idea was pretty much DP + inclusion-exclusion principle. It's clear that if we replace low by and high by , then we just need to find the number of sequences with elements in (low, high] whose GCD=1.

Let dp[d] be the number of sequences whose GCD equals d. We can transform low and high in a similar manner (except it's and ) and find out the total number of such sequences: (high - low)N by modular exponentiation. Then, we just need to try all GCDs that are multiples of d (kd, at least 2d) and subtract dp[kd] from dp[d]. We can even afford to use map<> to store the DP.

This is too slow, so let's just try divisors that aren't  > high - low. For any other divisors, all the elements of any array with a suitable GCD are equal (there can't be 2 distinct elements in the corresponding range), so we can modify the DP to store (in dp[d]) just the number of sequences with at least 2 distinct elements; the total number of sequences also decreases by high - low. The answer now is dp[1], plus 1 if 1 can be an element of the array (an array of 1s also has GCD=1).

My mistake was not checking the sequences with distinct elements separately. Shit happens...

UPD: The time complexity of this approach is , where L = high - low after the initial transformation (taking K to 1). That's because we access the DP states times in total, where each access costs per map<> access or insertion, plus run modular exponentiation once per each DP state.

Since the DP states (as used here) take 1 parameter d ≤ L, we can use a vector<> instead of a map<>, which gives a runtime of .

code

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

    I think we can pass the slow approach by using unordered_set in c++.

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

      The transition to vectors is a matter of less than a minute, and is faster and simpler than hash tables. But I used a map during the contest, because I wasn't sure about the form of the DP when I made that decision. I code first and see what I coded second.

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

    This is too slow, so let's just try divisors that aren't  > high - low. For any other divisors, all the elements of any array with a suitable GCD are equal (there can't be 2 distinct elements in the corresponding range), so we can modify the DP to store (in dp[d]) just the number of sequences with at least 2 distinct elements; the total number of sequences also decreases by high - low. The answer now is dp[1], plus 1 if 1 can be an element of the array (an array of 1s also has GCD=1).

    Could you give more details about this ? I don't really understand it :(

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

      Do you understand the part before this? If you do, then it's easy. Just think about the DP as computing "the number of sequences with at least 2 distinct elements and GCD equal to d" (when all elements that you can choose are multiples of d) and think how it has to work. You compute the total number of sequences (with GCD being any multiple of d), subtract the number of sequences with all elements identical, and then subtract the number of all sequences with at least 2 distinct elements but bad GCD. And those are counted in larger DP states.

      The answer you'd get by this DP can be off by 1 — if you can make a sequence consisting of all 1s, this would also have GCD=1, and contributes +1 to the correct answer. Add it if necessary.

      → Reply